专栏文章

题解：CF720E Cipher

MMeta_Morph
CF720E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0ums4
此快照首次捕获于
2025/12/02 11:31
3 个月前
此快照最后确认于
2025/12/02 11:31
3 个月前
查看原文

CF720E Cipher 题解

博客园链接：CF720E Cipher 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

进制，模拟，贪心。

分析

发现我们想要确定一位数时，只有两种方法：
  1. 该位数字自己加 11，从变化顺序可以看出它是哪一位。
  2. 该位数字加 11，导致高位数字出现变化，看出它现在变成了 00。这种情况包括整个数字达到了 n+1n+1 位的情况。
那么我们从高位开始遍历，记一个答案为 ansans，最小进位且变化的值为 lenlen，初始时设为 11。
每次想要确定这一位数是否可行，就要和别的数进行比较，直到能够把两个数区分开。假设此位为 cc，比较的为 jj，那么比较的方法有两种：
  1. 循环串最长公共前缀长度 +1+1。
  2. 如果 jj 能够引起高位进位，且进位能够看出来。
我们对于同一个 jj，在这两种中取 min⁡\min，得到这一位的答案 limlim，最后再整个答案 ansans 中取 max⁡\max。
当我们从高一位到低一位的时候，我们需要更新 ans,lenans,len，不过根据定义，也不难实现。
时间复杂度 O(nw2),w=10O(nw^2),w=10。

代码

CPP
constexpr int N(18+10);

char s[N],t[N];
int Cas,n;
ll ans,len;

int Cmain() {
	/*DE("Input");*/
	I(n),scanf("%s",s),ans=0,len=1;
	/*DE("Solve");*/
	FOR(i,0,n-1) {
		const int c(s[i]^48);
		scanf("%s",t),ans=ans*10-c;
		FOR(j,0,9)if(j!=c) {
			ll lim(len*10-max(j,c)); //上一位进位带来的影响
			FOR(k,0,min(lim-1,9ll))if(t[(c+k)%10]!=t[(j+k)%10]&&(lim=k,true))break;
			tomax(ans,lim);
		}
		len=len*10-c;
		FOR(j,1,9)if(t[c]!=t[(c+j)%10]&&(tomin(len,(ll)j),true))break;
	}
	/*DE("Output");*/
	O(ans,'\n');
	return 0;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	for(I(Cas); Cas; --Cas)Cmain();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...