CF1553部分题解及总结

前言

这一会 CF1553 的 vp 截取的是 DEFG 四道题目，因为 AC 两题我也做出来了，所以会放在一起。另外有一个 B 算法显然。因此本次题解包含 CF1553-ACDEFG 的解释加代码，以及 CF1553-B 的口胡。

总结

考试策略

CF 当天的考试写出了 AC，B 算法非常显然，也知道怎么做但是并没有写，因为看错数据范围了以为过不去。后面的时间一直在写 F 但是写不出来。vp 的时候第一个就去做 F，随后开始写 D，写完 D 后口胡出 G 的算法但是没来得及写了。E 是考后看题解知道的算法。

自我感觉整体策略还行，但是有一些瑕疵，比如看错数据范围之类，因为“个人恩怨”选择先写 F，放着别的题不管。

目前 vp 涉及的题目 DEFG 已经全部改对。

问题

看错数据范围错失良机。以及推演题目的过程较慢，严重拖慢了时间。实际上本来不需要这么慢。

打 vp 的时候尤其凸显。而且因为个人对一道题的兴趣和本来没做出来的怒气决定先做 F 这样一个恶心数论，而没有选择从最简单的 D 开始入手击破，是最大的问题所在。考场上不宜使用。

同时因为打 cf 的时候老师提出来了，特此注意：打 cf 的时候不要只拘泥于 ABC 这样的题目，否则能力无法得到训练，要多尝试往上走的难题，得到真正的训练，而不是划水试地做完一些是个人都会的签到题就不管了。

题解

CF1553A

定义 $\operatorname{S}(x)$ 为 $x$ 在十进制下各位数字之和。共 $T$ 次询问，每次询问给定一个数 $n$，求有多少不超过 $n$ 的正整数满足 $\operatorname{S}(x)>\operatorname{S}(x+1)$。$T\leqslant 10^3,n\leqslant 10^9$。

考虑到对于一个数，将这个数加 $1$ 后，要么进位要么不进位。不进位的情况，也就是个位比原来多 $1$，其他位不变，也就是 $\operatorname{S}(x)=\operatorname{S}(x+1)-1$。不符合题意。考虑进位的情况，此时个位本来是 $9$，现在变成 $0$，也就是减去 $9$。第二位要么和个位一样从 $9$ 变成 $0$，要么顶多也只会加一。所以总的 $\operatorname{S}$ 值一定是减少的。

因此题目转化为求 $[1,n]$ 内有几个数的个位数是 $9$。不难得出有 $\left\lfloor\dfrac{n+1}{10}\right\rfloor$ 个。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
 
int T,x;
 
signed main(){
	T=read();
	while(T--){
		int x=read();
		write((x+1)/10),putchar('\n');
	}
	return 0;
}

CF1553B

给定字符串 $s$，选定一个位置，放一个棋子，可以先将棋子向右移动若干次（可以不移动），再向左移动若干次（可以不移动），将棋子到过的字符（包括最开始选的位置）依次记录，求得到的字符串能否恰好为字符串 $t$。$1\leqslant \left| s \right|\leqslant 500,1\leqslant \left| t \right|\leqslant 2\times\left| s \right| -1$。

口胡一下做法。因为 $s$ 的长度极小，可以考虑枚举最开始放的位置，枚举向左移动到哪里。然后还需要移动多少次就向右移动多少次。每个枚举出的情况跑一遍验证。复杂度是 $\operatorname{O}(n^3)$ 的。

实际上可以进行进一步优化。我们不需要管开始和结束的位置，只枚举中间转折点的位置。不难得出 $t$ 串应该由两个可以为空的子串组成：起始点到转折点的部分，和终点到转折点的翻转串。对于前一部分，从起点到枚举出的转折点进行一次 kmp，对于后一部分，可以先提前预处理 $s$ 的翻转串方便操作，然后再跑一遍 kmp。两次都能匹配到说明可以。

CF1553C

$T$ 组询问，每次询问给定一个长为 $10$ 的字符串，下标为 $1\sim 10$，由 $0$ 或 $1$ 或 $?$ 组成。如果这个数是 $1$，则若其下标为奇数，A 队得一分，否则 B 队得一分。若即使将后面所有的结果都变成一方不得分另一方得分，得分方分数也小于不得分方，比赛结束，$10$ 轮结束时比赛也会结束。给每一个 $?$ 赋为 $0$ 或 $1$，使得比赛结束得尽量早，输出最早第几轮结束。$T\leqslant 10^3$。

因为字符串的长度最多为 $10$，枚举每一个 $?$ 赋哪个数，然后线性跑一遍判断第几轮结束，每次取一个最小值即可。总的复杂度是 $\operatorname{O}(T\times 2^{10}\times 10)$。可以通过。

不难发现不需要二进制枚举，直接贪心即可。贪心的做法十分显然，假设我们要让比赛尽早结束，无疑是让两队分差尽早拉开，所以我们可以先假设 A 队优势更大，对于每一个奇数位置的 $?$ 赋为 $1$，偶数位置为 $0$，让 A 更多地拿分，B 更少地拿分。得到一个结束时间。然后让 B 队优势更大，同理进行一遍，奇数位置的 $?$ 为 $0$，偶数位置为 $1$。得到结束时间。答案就是这两个结束时间之间的最小值。

因为对于每一个 $?$ 都是独立判断且是 $\operatorname{O}(1)$ 的，因此总的复杂度级别是 $\operatorname{O}(10T)$ 的，如果字符串长度不是 $10$ 而是 $n$，复杂度就是 $\operatorname{O}(Tn)$，达到理论上界。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline int readk(){ // 读入字符串内的信息
	char c=getchar();
	while(c!='0' && c!='1' && c!='?') c=getchar();
	if(c=='0') return 1;
	if(c=='1') return 2;
	return 3;
} // 1 表示 0，2 表示 1，3 表示 ?
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
 
int cnt[6],a[15],ans;
 
signed main(){
	int T=read();
	while(T--){
		cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
		ans=10; // 初始化为 10 避免不必要的麻烦
		memset(a,0,sizeof(a));
		for(register int i=1;i<=10;++i)
			a[i]=readk();
        // cnt0 A 队已经确定的得分
        // cnt1 A 队没有确定的得分，即 A 队 ? 数量
        // cnt2 B 队已经确定的得分
        // cnt3 B 队没有确定的得分，即 B 队 ? 数量
		for(register int i=1;i<=10;++i){
			if(i&1){
				if(a[i]==2) ++cnt[0];
				if(a[i]==3) ++cnt[1];
			}
			else{
				if(a[i]==2) ++cnt[2];
				if(a[i]==3) ++cnt[3];
			}
			if(cnt[0]+cnt[1]>cnt[2]+(11-i)/2){ // 达到条件，A 胜
				ans=i;
				break;
			}
			if(cnt[2]+cnt[3]>cnt[0]+(10-i)/2){ // 达到条件，B 胜
				ans=i;
				break;
			}
		}
		write(ans),putchar('\n');
	}
	return 0;
}

CF1553D

给定两个字符串 $s,t$，长度分别为 $n,m$，询问能否将 $s$ 的若干字符换位退格符（退格符表示删掉前一个输入的字符，没有字符则没有效果），得到字符串 $t$。（$1\leqslant m\leqslant n\leqslant 2\times 10^5$）

对于不是在第一个字符位置的退格符，显然将一个字符换位退格符的作用等价于连续删掉 $s$ 的两个字符。那么什么时候要删掉第一个字符呢，显然因为后面的一次只能删掉两个字符，长度的奇偶性不变。因此如果 $n,m$ 奇偶性不同，就要删掉第一个字符，否则不需要删掉第一个字符。

后面的话，可以将 $s$ 的每一位和 $t$ 匹配，如果和上一个匹配点之间是偶数个多余字符，那么这些字符可以删掉，当前点匹配成功，否则不能匹配。跑完后如果 $t$ 数组每一位在 $s$ 上都匹配到了，就可行，否则不可行。

代码：

#include<bits/stdc++.h>
using namespace std;
const int max_n=200005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,m;

string a,b;

inline bool check(int st){
	int j=0;
	for(register int i=st;i<n && j<m;++i){ // 匹配
		if(a[i]==b[j])
			++j;
		else
			++i;
	}
	return j>=m;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--){ // 多组数据
		cin>>a>>b;
		n=a.size(),m=b.size();
		if((n&1)!=(m&1)){ // 奇偶性不相同
			if(check(1)) // 从第二个数开始匹配，表示删掉第一个数
				puts("YES");
			else
				puts("NO");
		}
		else{
			if(check(0)) // 从开头开始匹配，表示不删
				puts("YES");
			else
				puts("NO");
		}
	}
	return 0;
}

CF1553E

给定一个大小为 $n$ 的排列，初始时是单调递增的。定义一次循环移动是将第 $i$ 个数移到第 $i+1$ 个数的位置上，第 $n$ 个数移到第一个数的位置上；一次交换为选择两个位置，交换这两个位置上的数。先对初始排列循环移动 $k$ 次，再交换 $m$ 次，得到排列 $a$。给出 $n,m,a$，求所有可能的 $k$ 值。$1\leqslant n\leqslant 3\times 10^5,0\leqslant m\leqslant \dfrac{n}{3}$。

假设我们现在已经循环移动完了，最多交换 $m$ 次能不能达到目标状态呢？因为一次交换是改变了两个位置，所以最多只能改变 $2\cdot m$ 次。如果现在没有匹配到（这里匹配指相同位置上数字相同）的数字超过 $2\cdot m$，那就不可能了。

因此如果有解，则有 匹配成功数大于等于 $n-2\times m$，因为 $m\leqslant \dfrac{n}{3}$，所以匹配数恒大于等于 $\dfrac{n}{3}$。进一步的值，答案不超过 $3$。

发现了这样一个问题就特别好办了。现在可以枚举 $k$ 值，每次将当前排列的 $a_i$ 向目标排列 $p_i$ 链接无向边，最后判联通块个数，$n$ 减去联通块个数就是最小交换数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int max_n=300005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}

struct graph{
	int ct,hd[max_n],nx[max_n*2],to[max_n*2];
	graph(){ct=1;}

	inline void clear(int n){
		ct=1;
		for(register int i=1;i<=n;++i)
			hd[i]=0;
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;

int n,m,a[max_n],t[max_n];

bool vis[max_n];

inline void dfs(int x){ // 找联通块的 dfs
	vis[x]=1;
	for(register int i=e.hd[x];i;i=e.nx[i]){
		int v=e.to[i];
		if(vis[v]) continue;
		dfs(v);
	}
}

signed main(){
	int T=read();
	while(T--){
		n=read(),m=read();
		for(register int i=1;i<=n;++i){
			int x=read();
			a[x]=i;
			++t[(i-x+n)%n];
		}
		int s=0,ans[5];// 答案数不超过 3
		for(register int i=0;i<n;++i){
			if(t[i]<n-2*m) continue;
			for(register int j=1;j<=n;++j)
				vis[j]=0;
			e.clear(n); // 重置
			for(register int j=1;j<=n;++j){
				int p=(i+j-1)%n+1;
				if(a[j]!=p)
					e.add(p,a[j]); // 连边
			}
			int cnt=0;
			for(register int j=1;j<=n;++j){
				int p=(i+j-1)%n+1;
				if(a[j]!=p && !vis[p]){
					++cnt;
					dfs(p); // 数联通块个数
				}
			}
			if(n-t[i]-cnt<=m) // 是答案
				ans[++s]=i;
		}
		write(s),putchar(' ');
		for(register int i=1;i<=s;++i)
			write(ans[i]),putchar(' ');
		putchar('\n');

		for(register int i=0;i<=n;++i) t[i]=0;
	}
	return 0;
}

CF1553F

对于一个长度为 $n$ 的，由互不相同的正整数组成的序列 $a$，构造一个数组 $p$，其中：

$p_k=\sum_{i=1}^{k}\sum_{j=1}^k a_i\bmod{a_j}$

求 $p$ 数组。（$n\leqslant 2\times 10^5,a_i\leqslant 3\times 10^5$）

考虑到 $p_i$ 不和 $i+1$ 及之后的位置有关系。所以不妨考虑差分 $p$ 数组。显然，有：

$p_k=p_{k-1}+\sum_{i=1}^{k-1}(a_i\bmod{a_k})+\sum_{i=1}^{k-1}(a_k\bmod{a_i})$

先来考虑前一个部分，我们知道，如果有一个倍数 $b$，使得 $a_i\in[ba_k,(b+1)a_k)$，那么有 $a_i\bmod{a_k}=a_i-ba_k$。不妨开一个树状数组，枚举一个倍数 $b$，查询 $[ba_k,(b+1)a_k)$ 中间有多少个数字，然后用 $\sum_{j=1}^{k-1}a_j$ 减去它即可。

第二个部分更加显得复杂。考虑到 $a_k\bmod{a_i}=a_k-a_i\left\lfloor\dfrac{a_k}{a_i}\right\rfloor$，结合手推，不妨再开一个树状数组 $b$，每次查询 $\sum_{j=1}^{a_i} b_j$，则这一部分就是 $k\times a_k$ 减去查询的结果。

枚举倍数看起来是非常耗时间的，但是考虑到所有的数字互不相同，假设值域范围是 $m$，对于每个数美爵倍数，而且不超过 $m$，总的复杂度是 $\ln m$，而每次树状数组的范围也是值域，总的复杂度就是 $\operatorname{O}(n\ln m\log m)$，完全可过。

代码如下：

#include<cstdio>
#define int long long

const int max_n=300005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int max(int a,int b){return a>b?a:b;}

int n,a[max_n],s[max_n],p[max_n],mx;

#define lb(x) (x&-x)
struct BIT{ // 封装后的树状数组
	int a[max_n];

	inline void add(int i,int x){
		for(;i<=mx;i+=lb(i))
			a[i]+=x;
	}
	inline int sum(int i){
		int res=0;
		for(;i;i-=lb(i))
			res+=a[i];
		return res;
	}
	inline int ask(int l,int r){
		if(r>mx) r=mx;
		return sum(r)-sum(l-1);
	}
}bit1,bit2;
#undef lb

signed main(){ // 都是公式，没什么好注释的
	n=read();
	for(register int i=1;i<=n;++i){
		a[i]=read();
		s[i]=s[i-1]+a[i],
		mx=max(mx,a[i]);
	}
	for(register int i=1;i<=n;++i){
		p[i]=p[i-1];

		p[i]+=a[i]*(i-1),
		p[i]-=bit2.ask(1,a[i]);
		for(register int k=1;a[i]*k<=mx;++k)
			bit2.add(a[i]*k,a[i]);

		p[i]+=s[i-1];
		
		for(register int k=1;a[i]*k<=mx;++k){
			int tmp=bit1.ask(a[i]*k,a[i]*(k+1)-1);
			p[i]-=tmp*a[i]*k;
		}
		bit1.add(a[i],1);
	}
	for(register int i=1;i<=n;++i)
		write(p[i]),putchar(' ');
	putchar('\n');
	return 0;
}

CF1553G

一个 $n$ 个节点的无向图，节点编号 $1\sim n$。每个点有一个权值 $a_i$，对于两点 $i,j$，若 $\gcd(i,j)>1$，则 $i,j$ 之间有一条边，否则没有边。你可以创建任意多个节点，创建方法为先选定正整数参数 $p(1\leqslant p\leqslant n)$，然后创建一个权值为 $a_p(a_p+1)$ 的节点，并按上述方法连边。求从 $s$ 号点到 $t$ 号点最少要创建几个节点。共 $q$ 次询问，询问之间独立。$n\leqslant 1.5\times 10^5,q\leqslant 3\times 10^5,a_i\leqslant 10^6$。

显然这不是一个标准的图论算法，因为连边的方式很显然偏数论。首先显然 $a_i(a_i+1)$ 一定是个偶数，因此所有的 $a_i(a_i+1)$ 都能被 $2$ 整除，所有的 $a_i(a_i+1)$ 都有一个公共的因子是 $2$。因此最多我只要 $s$ 创建一个，$t$ 创建一个就行。因此答案范围锁定为 $0,1,2$。

考虑什么情况下答案为 $0$，显然两个点一开始就在联通块里面，就可以直接走到。开一个并查集维护即可。

考虑什么时候答案为 $1$。注意到一个值域在 $10^6$ 内的数字，它最多有几个不同的质因数呢？$2\times 3\times 5\times 7\times 11\times 13\times 17\approx 5\times 10^5$，也就是最多 $7$ 个。显然含有相同质因子的数在相同联通块，对于每一个 $a_i$，找出其所在的联通块，以及 $a_i+1$ 的每个质因子对应的联通块，开一个 map 标记一下表示这两个联通块可以通过创建一个节点连通。查询的时候，如果他们的联通块被标记，答案为 $1$。

答案不是 $0$ 也不是 $1$ 那就是 $2$。代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=1000006;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,a[max_n],t[max_n],pr[max_n];

struct unionfind{
	int fa[max_n],sz[max_n];
	
	inline void clear(){
		for(register int i=0;i<=n;++i)
			fa[i]=i;
	}
	inline int find(int x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	inline void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y) return;
		fa[x]=y;
	}
}uf; // 并查集维护联通块

int c[max_n],d[max_n];

inline void getpr(){ // 筛质数的时候合并联通块
	for(register int i=2;i<max_n;++i)
		if(!pr[i])
			for(register int j=i,k=0;j<max_n;j+=i){
				if(t[j]){
					if(!k)
						c[i]=uf.find(t[j]);
					else
						uf.merge(k,t[j]);
					k=t[j];
				}
				pr[j]=i;	
			}
}

map<pair<int,int>,bool> mp; // 能用一个节点连起来的标记

signed main(){
	n=read();int T=read();
	uf.clear(); // 不要忘记初始化
	for(register int i=1;i<=n;++i){
		a[i]=read();
		t[a[i]]=i;
	}
	getpr();

	for(register int i=2;i<max_n;++i)
		if(pr[i]==i)
			c[i]=uf.find(c[i]); // 得到每个质数对应的联通块

	for(register int i=1;i<=n;++i){
		int j=a[i]+1,cnt=0;
		d[++cnt]=uf.find(i);
		while(j!=1){ // 分解质因数
			d[++cnt]=c[pr[j]];
			j/=pr[j];
		}
		sort(d+1,d+1+cnt),cnt=unique(d+1,d+1+cnt)-d-1; // 排序去重
		for(register int j=1;j<cnt;++j)
			for(register int k=j+1;k<=cnt;++k)
				mp[make_pair(d[j],d[k])]=1; // 打标记
	}

	while(T--){
		int x=read(),y=read();
		x=uf.find(x),y=uf.find(y);
		if(x==y){ // 在同一联通块
			puts("0");
			continue;
		}
		if(x>y) x^=y^=x^=y; // 不要忘记了
		if(mp[make_pair(x,y)]) puts("1"); // 这两个联通块有标记
		else puts("2");
	}
	return 0;
}