Codeforces Round #726 (Div. 2)
CF1537A Arithmetic Array
洛谷传送门
CF1537A
分析
用这 \(n\) 个数的总和 \(sum\) 判断:
如果 \(sum
如果 \(sum>n\) 意味着要用 \(sum-n\) 个 0 补上
代码
#include
#include
using namespace std;
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int main(){
for (int T=iut();T;--T){
int n=iut(),sum=0;
for (int i=1;i<=n;++i) sum+=iut();
print(sum>=n?(sum-n):1),putchar(10);
}
return 0;
}
CF1537B Bad Boy
洛谷传送门
CF1537B
分析
要想使三点曼哈顿距离最大，把另外两点放在对角即可
代码
#include
#include
using namespace std;
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int main(){
for (int T=iut();T;--T){
int n=iut(),m=iut(); iut(),iut();
printf("1 1 %d %d\n",n,m);
}
return 0;
}
CF1537C Challenging Cliffs
洛谷传送门
CF1537C
分析
首先第一个数和最后一个数可以先确定下来。
如果把剩下的数直接在中间升序排列，下界为 \(n-3\)
其浪费了第一个数和最后一个数所相邻的位置。
那么如果以 \((pos,n]\) 和 \([1,pos]\) 排列，就可以达到 \(n-2\) 的下界
代码
#include
#include
#include
using namespace std;
int n,a[200011];
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int main(){
for (int T=iut();T;--T){
n=iut();
for (int i=1;i<=n;++i) a[i]=iut();
sort(a+1,a+1+n);
if (n==2) printf("%d %d\n",a[1],a[2]);
else{
int pos=1;
for (int i=2;i CF1537D Deleting Divisors
洛谷传送门
CF1537D
分析
考虑一个奇数减去一个因子，会变成偶数，然后其又会变成奇数。
最后变为质数或 1 时终止，发现奇数时后手必胜。
同时含有奇质因子的偶数一定先手必胜。
剩下 2 的幂次方通过指数的奇偶性判断是否先手必胜。
代码
#include
#include
using namespace std;
int n,c;
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int main(){
for (int T=iut();T;--T){
n=iut(),c=0;
if (n&1) {puts("Bob"); continue;}
while (!(n&1)) n>>=1,++c;
if (n>1) puts("Alice");
else puts(c&1?"Bob":"Alice");
}
return 0;
}
CF1537E2 Erase and Extend (Hard Version)
洛谷传送门
CF1537E2
分析
答案肯定是一段前缀重复好多次的结果，设当前选中的前缀长度为 \(ans\)，
枚举新的前缀长度 \(i\)，判断末位大小，如果 \(s[i-1]
直接将 \(i\) 作为新的 \(ans\)，如果大于直接退出即可
代码
#include
#include
using namespace std;
int n,m,ans; char s[500011];
int main(){
scanf("%d%d%s",&n,&m,s),ans=1;
for (int i=1;is[i%ans]) break;
else if (s[i] CF1537F Figure Fixing
洛谷传送门
CF1537F
代码（分析在上篇题解中）
#include
#include
using namespace std;
const int N=200011; long long s[2];
struct node{int y,next;}e[N<<1];
int v[N],a[N],n,m,flag,et,as[N];
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
bool dfs(int x){
bool flag=1; s[v[x]]+=a[x];
for (int i=as[x];i;i=e[i].next)
if (v[e[i].y]==v[x]) flag=0;
else if (v[e[i].y]==-1) v[e[i].y]=v[x]^1,flag&=dfs(e[i].y);
return flag;
}
int main(){
for (int T=iut();T;--T){
n=iut(),m=iut(),flag=et=1;
for (int i=1;i<=n;++i) a[i]=iut(),v[i]=-1;
for (int i=1;i<=n;++i) a[i]=iut()-a[i];
for (int i=1;i<=m;++i){
int x=iut(),y=iut();
e[++et]=(node){y,as[x]},as[x]=et;
e[++et]=(node){x,as[y]},as[y]=et;
}
for (int i=1;i<=n;++i)
if (v[i]==-1){
v[i]=s[0]=s[1]=0;
bool now=dfs(i);
if (now&&(s[0]!=s[1])) {puts("NO"),flag=0; break;}
if (!now&&((s[0]^s[1])&1)) {puts("NO"),flag=0; break;}
}
for (int i=1;i<=n;++i) as[i]=0;
if (flag) puts("YES");
}
return 0;
}