社区讨论
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 条回复,欢迎继续交流。
正在加载回复...