Codeforces Round #846 (Div. 2) 解题报告

\(\text{By DaiRuiChen007}\)

Contest Link

A. Hayato and School

简单题，发现答案要么是一奇两偶、要么是三个奇数，分别考虑两种情况即可

时间复杂度 \(\Theta(n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=301;
int a[MAXN];
inline void solve() {
	int n;
	scanf("%d",&n);
	vector <int> cnt[2];
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),cnt[a[i]%2].push_back(i);
	if((int)cnt[0].size()>=2&&(int)cnt[1].size()>=1) {
		printf("YES\n%d %d %d\n",cnt[0][0],cnt[0][1],cnt[1][0]);
	} else if((int)cnt[1].size()>=3) {
		printf("YES\n%d %d %d\n",cnt[1][0],cnt[1][1],cnt[1][2]);
	} else puts("NO");
}
signed main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

B. GCD Partition

注意到如果分成的 \(k>2\)，那么把这些东西合成两段，其 \(\gcd\) 一定不会变小，因此只需要考虑 \(k=2\) 的情况，枚举断点暴力即可

时间复杂度 \(\Theta(n\log w)\)，\(w\) 为 \(\sum a_i\) 的值域，瓶颈在求 \(n\) 次 \(\gcd\) 上

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1;
int a[MAXN],sum[MAXN];
inline int gcd(int a,int b) {
	if(!b) return a;
	return gcd(b,a%b);
}
inline void solve() {
	int n,ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
	for(int i=1;i<n;++i) ans=max(ans,gcd(sum[i],sum[n]-sum[i]));
	printf("%lld\n",ans);
}
signed main() {
	int T;
	scanf("%lld",&T);
	while(T--) solve();
	return 0;
}

D. Bit Guessing Game

考虑这样的操作：

对于 \(n=2^k\) 的情况，操作 - 1 会使得 \(\operatorname{popcount}(n)\) 从 \(1\) 变成 \(k\)

同理，对于任意 \(n\)，操作 - 1 会使得 \(\operatorname{popcount}(n)\) 增加 \(\operatorname{lowbit}(n)-1\)

同理，我们用类似这样的方法，根据 \(\operatorname{popcount}(n)\) 的变化量每一次都能求出 \(n\) 的下一个 \(1\) 位在哪里

每次询问找到一个 \(1\)，总询问次数不超过 \(\log_2 n\) 次，满足要求

时间复杂度 \(\Theta(\log n)\)

#include<bits/stdc++.h>
using namespace std;
inline int read(int x) {
	cout<<"- "<<x<<endl;
	int ret; cin>>ret; return ret;
}
inline int bit(int x) { return 1<<x; }
inline void solve() {
	int tot;
	cin>>tot;
	int ans=0,lst=0,pre=tot;
	for(int i=1;i<=tot;++i) {
		int now=read(bit(lst));
		int nxt=lst+(now+1-pre);
		ans|=bit(nxt);
		lst=nxt+1,pre=now;
	}
	cout<<"! "<<ans<<endl;
}
signed main() {
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

E. Josuke and Complete Graph

把条件转化成统计所有 \(k\) 使得存在 \(l\le x,y\le r\) 且 \(\gcd(x,y)=k,x\ne y\) 的 \(k\) 的数量

注意到只要 \([l,r]\) 中有至少 \(2\) 个 \(k\) 的倍数，那么 \(k\) 就满足要求

因此等价于统计所有 \(\left\lfloor \dfrac rk\right\rfloor-\left\lceil \dfrac lk\right\rceil+1\ge 2\) 的 \(k\) 的数量即可，这又可以等价于 \(\left\lfloor\dfrac rk\right\rfloor -\left\lfloor\dfrac{l-1}k\right\rfloor \ge 2\) 的 \(k\) 的数量

显然对 \(l-1\) 整除分块：

  • 对于所有 \(k\le\sqrt{l-1}\) 的 \(k\)，暴力枚举并统计即可

  • 对于所有 \(k>\sqrt{l-1}\) 的 \(k\)，枚举 \(\left\lfloor\dfrac {l-1}k\right\rfloor=i\)，显然 \(i\) 的值域也是 \(\Theta(\sqrt l)\) 这一级别的

    那么我们要求：\(\left\lfloor\dfrac {l-1}k\right\rfloor=i,\left\lfloor\dfrac rk\right\rfloor\ge i+2\)，简单拆开变形一下即可得到 \(\left\lceil\dfrac l{i+1}\right\rceil\le k\le\min\left\{\left\lfloor\dfrac{l-1}i\right\rfloor,\left\lfloor\dfrac r{i+2}\right\rfloor\right\}\)，特判 \(i=0\) 的情况即可

注意特判 \(l=1\) 的情况，此时答案为 \(\left\lfloor\dfrac r2\right\rfloor\)

时间复杂度 \(\Theta(t\sqrt l)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
inline void solve() {
	int l,r;
	scanf("%lld%lld",&l,&r);
	--l;
	if(l==0) {
		printf("%lld\n",r/2);
		return ;
	}
	int ans=0,d=0;
	for(int k=1;k*k<=l;++k) {
		d=(l/k);
		if((r/k)-(l/k)>=2) ++ans;
	}
	for(int i=0;i<d;++i) {
		int L=(l+i+1)/(i+1);
		int R=r/(i+2);
		if(i>0) R=min(R,l/i);
		if(L<=R) ans+=R-L+1;
	}
	printf("%lld\n",ans);
}
signed main() {
	int T;
	scanf("%lld",&T);
	while(T--) solve();
	return 0;
}

F. Three Chairs

看到 \(\gcd(\max\{a_i,a_j,a_k\},\min\{a_i,a_j,a_k\})=1\) 第一时间想到反演

发现对形如 \(d\mid \gcd(\max\{a_i,a_j,a_k\},\min\{a_i,a_j,a_k\})\) 这样的 \((i,j,k)\) 进行计数很好做：

我们只需要先对 \(a_i\) 排序，再把所有 \(d\mid a_i\) 的 \(i\) 按顺序加入序列 \(\{k_i\}\)，然后在 \(\{k_i\}\) 中任选两个做 \(\min,\max\)，然后枚举中间数即可，即统计 \(\{k_i\}\)中所有 \(k_i>k_j\) 的 \(k_i-k_j-1\) 之和

那么我们记 \(f(d)\) 表示所有满足 \(\gcd(\max\{a_i,a_j,a_k\},\min\{a_i,a_j,a_k\})=d\) 的 \((i,j,k)\) 的数量，\(g(d)\) 表示所有满足 \(d\mid \gcd(\max\{a_i,a_j,a_k\},\min\{a_i,a_j,a_k\})\) 的 \((i,j,k)\) 的数量

进行对 \(f,g\) 莫比乌斯反演：\(g(n)=\sum_{n\mid d} f(d)\implies
f(n)=\sum_{n\mid d} g(d)\times \mu\left(\dfrac dn\right)\)

而我们要求的就是 \(f(1)\) 的值，按照上述过程计算即可，注意实现的常数

时间复杂度 \(\Theta(n\sqrt w)\)，其中 \(w\) 是 \(a_i\) 的值域

#include<bits/stdc++.h>
#define ll long long
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;
const int MAXN=3e5+1;
int a[MAXN],mu[MAXN],n;
ll ans,sum[MAXN];
int cnt[MAXN];
bool mark[MAXN];
vector <int> primes;
inline void solve(int p,int x) {
	if(mu[p]==0) return ;
	ans+=(ll)mu[p]*(ll)((ll)(x-1)*(ll)cnt[p]-sum[p]);
	sum[p]+=(ll)x,++cnt[p];
}
signed main() {
	for(int i=1;i<MAXN;++i) mu[i]=1;
	for(int i=2;i<MAXN;++i) {
		if(!mark[i]) mu[i]=-1,primes.push_back(i);
		for(int p:primes) {
			if(i*p>=MAXN) break;
			mark[i*p]=true,mu[i*p]=-mu[i];
			if(i%p==0) {
				mu[i*p]=0;
				break;
			}
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) {
		for(int j=1;j*j<=a[i];++j) {
			if(a[i]%j==0) {
				solve(j,i);
				if(j*j!=a[i]) solve(a[i]/j,i);
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}