打得比较漂亮的一场，光速过 ABCDE，但是 FGH 都太过神仙，EX 干脆赛时只有两人 AC/kk
A
Problem
link->https://atcoder.jp/contests/abc272/tasks/abc272_a。
Solution
按题意模拟即可。
Code
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
//#define int long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
signed main() {
int n;
scanf("%d",&n);
int sum=0;
rep(i,1,n) {
int x;
scanf("%d",&x);
sum+=x;
}
printf("%d\n",sum);
return 0;
}
B
Problem
link->https://atcoder.jp/contests/abc272/tasks/abc272_b。
Solution
拿一个二维 \(01\) 矩阵叫 \(a_{i,j}\) 记录 \((i,j)\) 两人是否在同一个聚会出现过，然后 \(m\) 次聚会，每次枚举每个参加聚会的人 \((x,y)\)，令 \(used_{x,y}=used_{y,x}=1\)；最终再枚举 \((i,j)\)，判断是否有 \(used_{i,j}=0\) 即可。复杂度 \(O(n^3)\)。
或者或许可以直接建图然后并查集，复杂度 \(O(n^2\log n)\)。
Code
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
//#define int long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e2+5;
bool used[N][N];
int a[N];
signed main() {
int n,m;
scanf("%d%d",&n,&m);
rep(i,1,m) {
int K;
scanf("%d",&K);
rep(j,1,K) {
scanf("%d",&a[j]);
rep(k,1,j-1)
used[a[j]][a[k]]=used[a[k]][a[j]]=true;
}
}
rep(i,1,n) {
rep(j,1,i-1) {
if(!used[i][j])
return 0&puts("No");
}
}
puts("Yes");
return 0;
}
C
Problem
link->https://atcoder.jp/contests/abc272/tasks/abc272_c。
Solution
考虑偶数一定是由两个偶数相加或两个奇数相加，所以直接记录奇数的最大值、次大值和偶数的最大值、次大值即可。
Code
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
//#define int long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
signed main() {
int max_odd=-1,max_even=-1,max_odd2=-1,max_even2=-1;
int n;
scanf("%d",&n);
rep(i,1,n) {
int x;
scanf("%d",&x);
if(x&1) {
if(x>max_odd) {
max_odd2=max_odd; max_odd=x;
} else if(x>max_odd2)
max_odd2=x;
} else {
if(x>max_even) {
max_even2=max_even; max_even=x;
} else if(x>max_even2)
max_even2=x;
}
}
if(max_odd2==-1&&max_even2==-1)
puts("-1");
else
printf("%d\n",max(max_odd+max_odd2,max_even+max_even2));
return 0;
}
D
Problem
link->https://atcoder.jp/contests/abc272/tasks/abc272_d。
Solution
考虑 bfs，对于每次拓展直接枚举对于 \(m=x^2+y^2\) 的 \(x\) 即可，数量级在 \(\sqrt{m}\)；然后解关于 \(y\) 的二次方程即可，可以考虑直接开根，也可以因为精度原因使用二分。复杂度 \(O(n^3)\)，因为在 \((n,m)\) 均为最大值是时，\(n<\sqrt{m}\)。
Code
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
//#define int long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int dx[]={-1,1};
const int dy[]={-1,1};
const int N=4e2+5;
int f[N][N],n,m;
bool inrange(int x,int y) {
return (x>=1&&x<=n&&y>=1&&y<=n&&f[x][y]==-1);
}
void bfs() {
queue<PII> Q;
cl(f,-1); f[1][1]=0;
Q.push(make_pair(1,1));
int k=sqrt(m)+0.5; k=min(k,n);
while(!Q.empty()) {
int x=Q.front().first,y=Q.front().second; Q.pop();
// printf("(%d,%d) = %d\n",x,y,f[x][y]);
rep(i,0,k) {
int l=0,r=k,ans=0;
while(l<=r) {
int mid=(l+r)>>1;
if(mid*mid+i*i<=m)
ans=mid,l=mid+1;
else
r=mid-1;
}
if(ans*ans+i*i!=m)
continue;
rep(_,0,1) {
rep(__,0,1) {
int tx=x+dx[_]*i;
int ty=y+dy[__]*ans;
if(inrange(tx,ty))
Q.push(make_pair(tx,ty)),f[tx][ty]=f[x][y]+1;
}
}
}
}
}
signed main() {
scanf("%d%d",&n,&m);
bfs();
rep(i,1,n) {
rep(j,1,n)
printf("%d ",f[i][j]);
puts("");
}
return 0;
}
E
Problem
link->https://atcoder.jp/contests/abc272/tasks/abc272_e。
Solution
容易发现，每次计算答案时，当时为负数的值是不会用到的，所以我们可以记录下每个元素第一次变成非负数的操作数哪次，记为 \(l_i\)，具体计算方法是解不等式 \(l_i\cdot i+a_i\ge 0\)，需要注意 \(a_i\) 本身就为非负数的情况。
然后给出一个引理：每一次操作中大于 \(n\) 的值是不用计算的。分两类讨论：第一种，那一轮没有数从负数变为非负数，而由于每个数都会变化，所以答案一定为 \(0\)，而 \(0<n\)；第二种，那一轮存在数从负数变为非负数，则考虑鸽巢原理，那次变换后，前几个小的数的值依次为 \(0,1,2,\dots\)。我们考虑构造出这样的情况，首先因为原来已经是非负数的每个数都已经发生变化，所以类似于 \(0\) 的值一定会空缺出来，而由新晋的非负数顶替，而新晋的非负数值最大为 \(-1+n=n-1\)，所以答案一定在 \([0,n]\) 之间，我们无需理会大于 \(n\) 的值。
所以我们可以记录下每个元素第一次变成大于 \(n\) 的操作数哪次，记为 \(r_i\)，具体计算方法是解不等式 \(r_i\cdot i+a_i>\le n\)，需要注意 \(a_i\) 本身就大于 \(n\) 的情况。
则我们把每个 \(a_i+ix,l_i\le x\le r_i\) 加入序列 \(\alpha_x\) 中。可以证明，\(\sum\limits_{i=1}^m |\alpha_i|\) 渐进于 \(O(n\log n)\)，因为调和数 \(\sum\limits_{i=1}^n r_i-l_i+1\) 最大为 \(\sum\limits_{i=1}^n \frac{n}{i}\)。
所以复杂度为 \(O(n\log n)\)。
Code
点击查看代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define int long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=2e5+5;
int n,m;
vector<int> vec[N];
signed main() {
scanf("%lld%lld",&n,&m);
rep(i,1,n) {
int x;
scanf("%lld",&x);
int l=min(m+1,(int)ceil(-1.0*x/i)),r=min(m,(int)floor(1.0*(n-x)/i)+2);
if(x>=0)
l=1;
if(x>n)
r=0;
// printf("(%lld,%lld) : [%lld,%lld]\n",i,x,l,r);
rep(j,l,r)
vec[j].push_back(x+j*i);
}
rep(i,1,m) {
sort(vec[i].begin(),vec[i].end());
int last=-1,len=vec[i].size();
rep(j,0,len-1) {
if(vec[i][j]==last+1)
++last;
else if(vec[i][j]!=last)
break;
}
printf("%lld\n",last+1);
}
return 0;
}