(latex渲染问题,请展开查看)

通用题解
题目链接在标题上(别问我为什么超链接是黑的)
当时做题的时候,点开B题,想了十分钟,感觉我能想到的所有方法都会T掉,然后点开了C题,就有思路了......
这种要输出路径的一看就只有DFS了,可以用类似拓扑排序的方法,void dfs(下标,深度(输出用的));
相当于每个数字对 比他大数字的连边(当然不用真的连),dfs出来就是有序的了,但这是 的,而且还会有重复。重复好办,因为先枚举到的一定是最优的(后枚举到的不可能出现更多合法情况),就每个枚举到第一个在他之后的这个数字就
break
掉。
多说无益,核心代码:
int c[1000010],idx,cnt; int pt[17]; void Put(int len){ for(int i=1;i<=len;i++) if(pt[i]<10)putchar(pt[i]+'0');//输出转化 else putchar(pt[i]+'A'-10); puts(""); } void dfs(int st,int deep){ Put(deep);//搜索深度就是答案长度 for(int i=c[st]+1;i<=15;i++){ for(int j=st+1;j<idx;j++)//本人读入的字符串下标是1~idx-1 if(c[j]==i){pt[deep+1]=i,dfs(j,deep+1);break;} } }
但是复杂度还是的,咋办?我们刚刚用了什么操作?找到这个下标之后的最小的某个数字,这好办,因为下标是单调递增的,稍微存储一下就可以二分查找了,时间复杂度
。
int num[16][1000010],tot[16]; for(int i=1;i<idx;i++){ if(isdigit(c[i]))c[i]-='0'; else c[i]-='A'-10; num[c[i]][++tot[c[i]]]=i; }
于是,最终代码(32ms):
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } void print(int a){ if(a<0)putchar('-'),a=-a; if(a>=10)print(a/10); putchar(a%10+48); } /*前方为快读快出板子*/ int c[1000010],idx,cnt; int num[16][1000010],tot[16];//num数组按顺序存储对应值的下标,tot[a]为num[a]数组长度 int pt[17];//输出数组 void Put(int len){ for(int i=1;i<=len;i++) if(pt[i]<10)putchar(pt[i]+'0'); else putchar(pt[i]+'A'-10); puts(""); } void dfs(int st,int deep){ if(deep)Put(deep);//如果深度为0就不输出 for(int i=c[st]+1;i<=15;i++){ int*a=lower_bound(num[i]+1,num[i]+tot[i]+1,st);//二分,此时*a就是我们需要的下标 if(a!=num[i]+tot[i]+1)pt[deep+1]=i,dfs(*a,deep+1);//特判此下标不存在 } } signed main(){ while(!isspace(c[++idx]=getchar())&&c[idx]!=EOF);//手动读入 for(int i=1;i<idx;i++){ if(isdigit(c[i]))c[i]-='0';//读入转化 else c[i]-='A'-10; num[c[i]][++tot[c[i]]]=i;//把对应值的下标存起来 } c[0]=-1,dfs(0,0);//从深度为0开始枚举,值设为-1,让第一次dfs时i从0枚举 return~EOF; }
于是我们就有了第B题代码,然后我就在半分钟之内再A了一道题:
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } void print(int a){ if(a<0)putchar('-'),a=-a; if(a>=10)print(a/10); putchar(a%10+48); } int c[1000010],idx,cnt; int num[16][1000010],tot[16]; int pt[17]; void Put(int len){ /*for(int i=1;i<=len;i++) if(pt[i]<10)putchar(pt[i]+'0'); else putchar(pt[i]+'A'-10); puts("");*/ cnt++; } void dfs(int st,int deep){ if(deep)Put(deep); for(int i=c[st]+1;i<=15;i++){ int*a=lower_bound(num[i]+1,num[i]+tot[i]+1,st); if(a!=num[i]+tot[i]+1)pt[deep+1]=i,dfs(*a,deep+1); } } signed main(){ while(!isspace(c[++idx]=getchar())&&c[idx]!=EOF); for(int i=1;i<idx;i++){ if(isdigit(c[i]))c[i]-='0'; else c[i]-='A'-10; num[c[i]][++tot[c[i]]]=i; } c[0]=-1,dfs(0,0); print(cnt); return~EOF; }