Codeforces Round #846 (Div. 2) 解题报告
\(\text{By DaiRuiChen007}\)
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;
}