题目链接:http://acm.csust.edu.cn/problem/4001
博客园食用链接:https://www.cnblogs.com/lonely-wind-/p/13412300.html
Description
众所周知,LJ精通 和 , 这天他遇到一个简单的加法题,但这个加法有一个特殊的性质,它是不进位加法,
比如当是10进制时 ,当一位大于 的时候我们我们对其模 ,取余数作为这位的值, 进制数同理。
现在给你 个数 ,并且每个数最多只有 位,然后给定一个 ,代表所有数都是 进制数,
接下来有 次询问 ,每次询问给你一个长度不超过 的 进制数,你需要在 个数中找到一个数和它进行
不进位加法时所得到的值最大,输出这个最大值。佳爷觉得这题太水了,就出给同学们做了。
Input
第一行两个正整数
,
。
第二行 个整数,每个整数最多只有 位。
第三行一个整数
,
接下来有
行,代表
次询问,每次给你一个位数不超过
的整数。
Output
输出有
行,每行对应一个询问的所求的最大值
Sample Input 2
4 10
998
997
886
885
4
991
998
119
190
Sample Output 2
889
886
995
976
emmm,比赛的时候似乎想到了字典树。。。不过好像就出现了一秒就被我抛了。。。然后我就一直用二分艹。。。。
QAQ要是我能坚定一下我的字典树的话这题也就过了。。。
如果能够看出是字典树的话,我们就知道,字典树的操作只有两种,一个是insert,一个是find,那么毫无疑问我们当然是直接将n个字符串全部插入到字典树里面的,不过为了后面的计算,我们要将每个数字补足10位,这样的话等会找的时候才能好找。
接下来找的话我们先预处理出每个数字在k进制下的需要匹配的最大数的排名,我们爬链找就是按照这个排名顺序来找的,如下所示:
ll find(char *s,int rt,int k) {ll ans=0;int ch[15];int nb=0;for(int i=0; s[i]; i++) {int x=s[i]-'0';for (int j=0; j<10; j++){//枚举排名if (trie[rt][ranks[x][j]]) {ch[nb++]=ranks[x][j]+x;rt=trie[rt][ranks[x][j]];break;}}}for (int i=0; i<10; i++){ans=ans*10+(ch[i]%k);}return ans;
}
********
scanf ("%d%d",&n,&k);
for (int i=0; i<k; i++) {for (int j=0; j<k; j++) {ranks[i][j]=(k-1-i-j+k)%k;}
}
于是,此题便结束了。。。。QAQ
以下是AC代码:
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int mac=2e6+10;int trie[mac][12],mark[mac];
int ranks[12][12],tot=0;void insert(char *s,int rt) {for(int i=0; s[i]; i++) {int x=s[i]-'0';if(trie[rt][x]==0) { //现在插入的字母在之前同一节点处未出现过trie[rt][x]=++tot; //字母插入一个新的位置}rt=trie[rt][x]; //为下个字母的插入做准备}mark[rt]=1; //对该节点标记为结束(代表再次链上以此字母为结尾的存在)
}ll find(char *s,int rt,int k) {ll ans=0;int ch[15];int nb=0;for(int i=0; s[i]; i++) {int x=s[i]-'0';for (int j=0; j<10; j++){if (trie[rt][ranks[x][j]]) {ch[nb++]=ranks[x][j]+x;rt=trie[rt][ranks[x][j]];break;}}}for (int i=0; i<10; i++){ans=ans*10+(ch[i]%k);}return ans;
}char s[15],s1[15];int main(int argc, char const *argv[])
{int n,k;scanf ("%d%d",&n,&k);for (int i=0; i<k; i++){for (int j=0; j<k; j++){ranks[i][j]=(k-1-i-j+k)%k;}}for (int i=1; i<=n; i++){scanf ("%s",s);int len=strlen(s);if (len<10) for (int j=0; j<10-len; j++)s1[j]='0';for (int j=10-len,cnt=0; j<10; j++,cnt++) s1[j]=s[cnt];insert(s1,0);}int q;scanf ("%d",&q);while (q--){scanf ("%s",s);int len=strlen(s);if (len<10) for (int j=0; j<10-len; j++)s1[j]='0';for (int j=10-len,cnt=0; j<10; j++,cnt++) s1[j]=s[cnt];ll ans=find(s1,0,k);printf("%lld\n",ans);}return 0;
}