社区讨论

0分求条

P2602[ZJOI2010] 数字计数参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mjxpysji
此快照首次捕获于
2026/01/03 11:04
2 个月前
此快照最后确认于
2026/01/06 16:55
上个月
查看原帖
CPP
//神人做法阳历过不了
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tiaoshi;
struct zyl{
	int ling,yi,er,san,si,wu,liu,qi,ba,jiu;
	void clear_() {
		ling=0,yi=0,er=0,san=0,si=0,wu=0,liu=0,qi=0,ba=0,jiu=0;
	}
	void add(int x,int ads) {
		if (tiaoshi) cout << "I know,add" << x << " " << ads << endl;
		switch(x) {
			case 0:ling+=ads;break;
			case 1:yi+=ads;break;
			case 2:er+=ads;break;
			case 3:san+=ads;break;
			case 4:si+=ads;break;
			case 5:wu+=ads;break;
			case 6:liu+=ads;break;
			case 7:qi+=ads;break;
			case 8:ba+=ads;break;
			case 9:jiu+=ads;break;
		}
	}
	void print() {
		cout << ling << " " << yi << " " << er << " " << san << " " << si << " " << wu << " " << liu << " " << qi << " " << ba << " " << jiu << endl;
	}
	zyl operator+(const zyl& other) const {
		zyl res;
		res.ling=ling+other.ling;
		res.yi=yi+other.yi;
		res.er=er+other.er;
		res.san=san+other.san;
		res.si=si+other.si;
		res.wu=wu+other.wu;
		res.liu=liu+other.liu;
		res.qi=qi+other.qi;
		res.ba=ba+other.ba;
		res.jiu=jiu+other.jiu;
		return res;
	}
	zyl operator-(const zyl& other) const {
		zyl res;
		res.ling=ling-other.ling;
		res.yi=yi-other.yi;
		res.er=er-other.er;
		res.san=san-other.san;
		res.si=si-other.si;
		res.wu=wu-other.wu;
		res.liu=liu-other.liu;
		res.qi=qi-other.qi;
		res.ba=ba-other.ba;
		res.jiu=jiu-other.jiu;
		return res;
	}
};
struct dpp{
	zyl a;
	int y;
	bool operator==(const dpp& other) const {
		return (y==other.y)&&(a.ling==other.a.ling)&&(a.yi==other.a.yi)&&(a.er==other.a.er)&&(a.san==other.a.san)&&(a.si==other.a.si)&&(a.wu==other.a.wu)&&(a.liu==other.a.liu)&&(a.qi==other.a.qi)&&(a.ba==other.a.ba)&&(a.jiu==other.a.jiu);
	}
};
namespace std {
	template<> struct hash<dpp> {
		size_t operator()(const dpp& obj) const {
			size_t seed=0;
			hash_combine(seed,obj.y);
			hash_combine(seed,obj.a.ling);
			hash_combine(seed,obj.a.yi);
			hash_combine(seed,obj.a.er);
			hash_combine(seed,obj.a.san);
			hash_combine(seed,obj.a.si);
			hash_combine(seed,obj.a.wu);
			hash_combine(seed,obj.a.liu);
			hash_combine(seed,obj.a.qi);
			hash_combine(seed,obj.a.ba);
			hash_combine(seed,obj.a.jiu);
			return seed;
		}	
	private:
		template<typename T>
		void hash_combine(size_t& seed,const T& val) const {
			seed^=hash<T>()(val)+0x9e3779b9+(seed<<6)+(seed>>2);
		}
	};
}
int n,m,n_[25],size_;
unordered_map<dpp,zyl> mp;
zyl ans;
zyl dfs(int pos,int lead,int limit) {
	if(pos==0) {
		zyl res;
		res.clear_();
		return res;
	}
	dpp anss;
	anss.y=pos,anss.a={0};
	if(!limit&&!lead&&mp.find(anss)!=mp.end()) {
		return mp[anss];
	}
	int up=limit?n_[pos]:9;
	zyl res,tmp;
	res.clear_();
	for(int i=0;i<=up;i++) {
		tmp.clear_();
		if(!lead||(i!=0)) {
			tmp.add(i,1);
		}
		tmp=tmp+dfs(pos-1,lead&&(i==0),limit && (i == up));
		res=res+tmp;
	}
	if(!limit&&!lead) {
		mp[anss]=res;
	}
	return res;
}
zyl Seek(int x) {
	if(x<0) {
		zyl empty;
		empty.clear_();
		return empty;
	}
	ans.clear_();
	memset(n_,0,sizeof n_);
	size_=0;
	while (x) {
		n_[++size_]=x%10;
		x/=10;
	}
	mp.clear();
	return dfs(size_, 1, 1);
}
void solve() {
	tiaoshi=0;
	zyl popopo=Seek(m);
	zyl papapa=Seek(n-1);
	zyl res=popopo-papapa;
	res.print();
	return ;
}
signed main() {
  cin >> n >> m;
  if (n==0&&m==0) break;
  if (n>m) swap(n,m);
  solve();
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...