Educational Codeforces Round 70 部分题解

A. You Are Given Two Binary Strings...

题意：

给定两个二进制字符串 \(x\) 和 \(y\)，其对应的整数值分别为 \(a\) 和 \(b\)。对于任意非负整数 \(k\)，计算 \(v_k = a + b \cdot 2^k\)，并将 \(v_k\) 的二进制表示（无前导零）反转得到字符串 \(r_k\)。请选择一个 \(k\)，使得 \(r_k\) 的字典序最小。可以保证这样的 \(k\) 存在且有限。

思路：

要使 \(r_k\) 的字典序最小，我们需要让 \(r_k\) 的前导 \(0\) 尽可能多，即让 \(v_k\) 的二进制表示的低位连续 \(0\) 尽可能多。找到 \(y\) 中最低位的 \(1\) 的位置 \(i\)（从右往左，从 \(0\) 开始），然后在 \(x\) 中从第 \(i\) 位开始向右找到第一个 \(1\) 的位置 \(j\)，令 \(k = j - i\)，即为答案。

代码

点击查看代码 
string s1,s2;
void solve() {
	int n,p;
	cin>>s1>>s2;
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	int st=0;
	for(int i=0;i<s2.length();i++){
		if(s2[i]=='1'){
			st=i;
			break;
		}
	}
//	cout<<st<<' ';
	int ans=0;
	for(int i=st;i<s1.length();i++){
		if(s1[i]=='1'){
			ans=i-st;
			break;
		}
	}
	cout<<ans<<endl;
}

B. You Are Given a Decimal String...

题意：

给定一个十进制字符串 \(s\)（保证 \(s_0 = 0\)），它是由一个特殊的 \(x\)-\(y\) 计数器生成的序列的一部分（可能缺失了一些数字）。计数器的初始值为 \(0\)，每次操作先打印当前值的最低位，然后给当前值加上 \(x\) 或 \(y\)（可任意选择）。现在只允许在 \(s\) 中插入数字（不能删除或重排），问对于所有 \(0 \le x, y < 10\)，最少需要插入多少位数字，才能使 \(s\) 成为某个 \(x\)-\(y\) 计数器的可能输出。如果不可能，输出 \(-1\)。

思路：

设完整序列中相邻两个数字为 \(a\) 和 \(b\)，那么必须存在一次加法（加上 \(x\) 或 \(y\)）使得 \((a + c) \bmod 10 = b\)，即 \((b - a) \bmod 10 \in \{x, y\}\)。因此，对于给定的 \(x,y\)，我们可以建立一个有向图：节点为 \(0\) 到 \(9\)，每个节点 \(u\) 有两条边指向 \((u+x)\bmod 10\) 和 \((u+y)\bmod 10\)。那么从 \(a\) 到 \(b\) 所需的最少加法次数就是图中从 \(a\) 到 \(b\) 的最短路径长度（边数）。

法一：

记 \(f[d]\) 为从 \(0\) 出发到达数字 \(d\) 的最短路径长度（\(f[0]=0\)），并计算从 \(0\) 出发再回到 \(0\) 的最小正步数 \(cycle\)（即最短环的长度）。对于字符串 \(s\)，计算所有相邻数字的差值 \(d_i = (s_{i+1} - s_i + 10) \bmod 10\)，并统计每个差值出现的次数 \(cnt[d]\)。则对于差值 \(d\)：

  • 若 \(d = 0\)，需要的步数为 \(cycle\)（若不存在环则为无穷大）；
  • 若 \(d \neq 0\)，需要的步数为 \(f[d]\)（若不可达则为无穷大）。

若某个 \(cnt[d] > 0\) 且对应的步数为无穷大，则整体不可行，输出 \(-1\)。否则，总插入数字数为 \(\sum_{d=0}^{9} cnt[d] \cdot (step_d - 1)\)，其中 \(step_d\) 为上述步数。

对每个 \((x,y)\) 预处理 \(f\) 和 \(cycle\)，然后利用 \(cnt\) 数组快速计算答案即可。

法二：

由于计算的是 \(\bmod 10\) 意义下的长度，所以只要分别对 \(x\) 和 \(y\) 枚举 \(0\) 到 \(9\) 次即可，详细细节见代码。

代码

点击查看代码 
int p[15][15][15];
void solve() {
	cin>>s1;

	for(int x=0;x<=9;x++){
		for(int y=0;y<=9;y++){
			for(int i=0;i<=9;i++){
				p[x][y][i]=100;
			}
			for(int i=0;i<=9;i++){
				for(int j=0;j<=9;j++){
					if(i||j)p[x][y][(x*i+y*j)%10]=min(p[x][y][(x*i+y*j)%10],i+j);
//					cout<<i<<' '<<j<<' '<<(x*i+y*j)%10<<endl;
				}
			}
			int ans=0;
			
			for(int i=1;i<s1.length();i++){
				if(p[x][y][(s1[i]-s1[i-1]+10)%10]==100){
//					cout<<(s1[i]-s1[i-1]+10)%10<<endl;
					ans=-1;
					break;
				}
				ans+=p[x][y][(s1[i]-s1[i-1]+10)%10]-1;
			}
			cout<<ans<<' ';
		}cout<<endl;
	}
}

C. You Are Given a WASD-string...

题意：

给定一个由 \(W,A,S,D\) 组成的字符串 \(s\)，表示机器人上下左右移动。定义 \(Grid(s)\) 为能够容纳机器人执行完整命令序列的最小矩形网格面积（机器人可以放置在任意起始位置）。你可以在 \(s\) 的任意位置插入最多一个额外字符（从 \(W,A,S,D\) 中各有一个可用），使得 \(Grid(s)\) 的面积最小。求最小面积。

思路：

面积由水平和垂直方向的范围决定。插入一个字符只会影响一个方向的范围（\(W\)/\(S\)) 影响垂直，(\(A\)/\(D\)) 影响水平）。因此我们可以分别计算插入水平字符（\(A\)/\(D\)）和垂直字符（\(W\)/\(S\)）后所能达到的最小范围。预处理后缀和数组，然后计算在每个位置插入 \(+1\) 或 \(-1\) 后新的最大值和最小值，从而得到新的范围。取原始面积、插入字符后的面积的最小值。

代码

点击查看代码 
string s1,s2;

int u[N],d[N],l[N],r[N];
int px[N],py[N];
void solve() {
	cin>>s1;
	int x=0,y=0;
	int U=0,D=0,L=0,R=0;
	int n=s1.length();
	u[n]=d[n]=l[n]=r[n]=px[n]=py[n]=0;
	for(int i=s1.length()-1;i>=0;i--){
		if(s1[i]=='W'){
			x--;
		}
		if(s1[i]=='A'){
			y++;
		}
		if(s1[i]=='S'){
			x++;
		}
		if(s1[i]=='D'){
			y--;
		}
		U=max(U,x);
		D=min(D,x);
		L=min(L,y);
		R=max(R,y);
		u[i]=U;
		d[i]=D;
		l[i]=L;
		r[i]=R;
		px[i]=x;
		py[i]=y;
	}
	x=0,y=0;
	U=0,D=0,L=0,R=0;
	int mn=1e18;
	int X,Y;
	int nU=0,nD=0,nL=0,nR=0;
	X=x;
	Y=y;
	nU=max(U,u[0]+X-px[0]);
	nD=min(D,d[0]+X-px[0]);
	nR=max(R,r[0]+Y-py[0]);
	nL=min(L,l[0]+Y-py[0]);
	mn=min(mn,(nU-nD+1)*(nR-nL+1));
	X=x+1;
	Y=y;
	nU=max(U,u[0]+X-px[0]);
	nD=min(D,d[0]+X-px[0]);
	nR=max(R,r[0]+Y-py[0]);
	nL=min(L,l[0]+Y-py[0]);
	mn=min(mn,(nU-nD+1)*(nR-nL+1));
	X=x-1;
	Y=y;
	nU=max(U,u[0]+X-px[0]);
	nD=min(D,d[0]+X-px[0]);
	nR=max(R,r[0]+Y-py[0]);
	nL=min(L,l[0]+Y-py[0]);
	mn=min(mn,(nU-nD+1)*(nR-nL+1));
	X=x;
	Y=y+1;
	nU=max(U,u[0]+X-px[0]);
	nD=min(D,d[0]+X-px[0]);
	nR=max(R,r[0]+Y-py[0]);
	nL=min(L,l[0]+Y-py[0]);
	mn=min(mn,(nU-nD+1)*(nR-nL+1));
	X=x;
	Y=y-1;
	nU=max(U,u[0]+X-px[0]);
	nD=min(D,d[0]+X-px[0]);
	nR=max(R,r[0]+Y-py[0]);
	nL=min(L,l[0]+Y-py[0]);
	mn=min(mn,(nU-nD+1)*(nR-nL+1));
	for(int i=0;i<s1.length();i++){
		if(s1[i]=='W'){
			x++;
		}
		if(s1[i]=='A'){
			y--;
		}
		if(s1[i]=='S'){
			x--;
		}
		if(s1[i]=='D'){
			y++;
		}
		U=max(U,x);
		D=min(D,x);
		L=min(L,y);
		R=max(R,y);
		X=x;
		Y=y;
		nU=max(U,u[i+1]+X-px[i+1]);
		nD=min(D,d[i+1]+X-px[i+1]);
		nR=max(R,r[i+1]+Y-py[i+1]);
		nL=min(L,l[i+1]+Y-py[i+1]);
		mn=min(mn,(nU-nD+1)*(nR-nL+1));
		X=x+1;
		Y=y;
		nU=max(U,u[i+1]+X-px[i+1]);
		nD=min(D,d[i+1]+X-px[i+1]);
		nR=max(R,r[i+1]+Y-py[i+1]);
		nL=min(L,l[i+1]+Y-py[i+1]);
		mn=min(mn,(nU-nD+1)*(nR-nL+1));
		X=x-1;
		Y=y;
		nU=max(U,u[i+1]+X-px[i+1]);
		nD=min(D,d[i+1]+X-px[i+1]);
		nR=max(R,r[i+1]+Y-py[i+1]);
		nL=min(L,l[i+1]+Y-py[i+1]);
		mn=min(mn,(nU-nD+1)*(nR-nL+1));
		X=x;
		Y=y+1;
		nU=max(U,u[i+1]+X-px[i+1]);
		nD=min(D,d[i+1]+X-px[i+1]);
		nR=max(R,r[i+1]+Y-py[i+1]);
		nL=min(L,l[i+1]+Y-py[i+1]);
		mn=min(mn,(nU-nD+1)*(nR-nL+1));
		X=x;
		Y=y-1;
		nU=max(U,u[i+1]+X-px[i+1]);
		nD=min(D,d[i+1]+X-px[i+1]);
		nR=max(R,r[i+1]+Y-py[i+1]);
		nL=min(L,l[i+1]+Y-py[i+1]);
		mn=min(mn,(nU-nD+1)*(nR-nL+1));
	}
	cout<<mn<<endl;
}

D. Print a 1337-string...

题意：

给定整数 \(n\)，构造一个仅由字符 \(1\)、\(3\)、\(7\) 组成的字符串，使得其恰好包含 \(n\) 个不同的子序列为 \(1337\)。字符串长度不能超过 \(10^5\)。

思路：

构造题。
可以构造形如 \('1' + 2*'3' + r*'7' + (a-2)*'3' + '7'\) 的字符串，其中 \(a\) 是满足 \(\frac{a(a-1)}{2} \le n\) 的最大整数，\(r = n - \frac{a(a-1)}{2}\)。第一部分贡献 \(r\) 个子序列，第二部分贡献 \(\frac{a(a-1)}{2}\) 个子序列，总和为 \(n\)。

代码

点击查看代码 
void solve() {
	int n;
	cin >> n;
	s1.clear();
	int p = upper_bound(a + 1, a + 1 + 100000, n) - a - 1;
	int x = p;
	int y = n - x * (x - 1) / 2;
	string s = "133";
	for(int i=0;i<y;i++){
		s+='7';
	}
	for(int i=0;i<x-2;i++){
		s+='3';
	}
	s += '7';
	cout << s << endl;

}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	for (int i = 1; i <= 1e5; i++) {
		a[i] = (i - 1) * i / 2;
	}
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

E. You Are Given Some Strings...

题意：

给定一个字符串 \(t\) 和 \(n\) 个字符串 \(s_1, s_2, \dots, s_n\)。定义 \(f(t, s)\) 为字符串 \(s\) 在 \(t\) 中出现的次数（可重叠）。求所有拼接串 \(s_i + s_j\) 在 \(t\) 中出现次数的总和，即 \(\sum_{i=1}^n \sum_{j=1}^n f(t, s_i + s_j)\)。注意不同 \((i, j)\) 对即使拼接串相同也需要分别计数。

思路：

对于拼接串 \(s_i + s_j\) 在 \(t\) 中的一次出现，设起始位置为 \(p\)，则 \(s_i\) 恰好匹配 \(t[p \dots p+|s_i|-1]\)，\(s_j\) 恰好匹配 \(t[p+|s_i| \dots p+|s_i|+|s_j|-1]\)。因此，若固定 \(t\) 中的一个位置 \(k\)，令 \(s_i\) 结束于 \(k\)，\(s_j\) 开始于 \(k+1\)，则所有这样的 \((i,j)\) 对都对应一次拼接串的出现。
记 \(ced[k]\) 为以位置 \(k\) 结尾的 \(s_i\) 个数，\(cst[k]\) 为以位置 \(k\) 开头的 \(s_i\) 个数。则答案为 \(\sum_{k=1}^{|t|-1} ced[k] \cdot cst[k+1]\)。
然后使用 AC 自动机计算即可。
代码还没写，晚点补

代码

点击查看代码 
111
posted @ 2026-01-27 18:42  ptlks  阅读(22)  评论(0)    收藏  举报