比赛地址&官方题解
题解
A
排序，输出两个数列的最大值即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i;
int a[500],b[500];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for (i=1;i<=m;i++) scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+m);
cout<<a[n]<<" "<<b[m]<<endl;
return 0;
}
B
首先把所有的正数全变成1，负数全变成-1,统计贡献，然后统计0的个数。每一个0的贡一定是1.然后，如果负数的数目是奇数，且0的数量不为0，则答案不变，否则答案加2,表示一个负数变为了1.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 100010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,c,d,e;
LL Ans=0;
int a[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
if (n==1){
cout<<Abs(1-a[1]);
return 0;
}
Ans=0;
sort(a+1,a+1+n);
for (i=1;i<=n;i++){
if (a[i]<0) c++;
else if (a[i]==0) d++;
}
if ((c%2)==0){
for (i=1;i<=c;i++)
Ans+=(LL)Abs(-1-a[i]);
for (i=c+1;i<=n;i++)
Ans+=(LL)Abs(a[i]-1);
} else
if ((c+d)%2==0){
for (i=1;i<=c+d;i++)
Ans+=(LL)Abs(-1-a[i]);
for (i=c+d+1;i<=n;i++)
Ans+=(LL)Abs(a[i]-1);
} else {
if (d) {
for (i=1;i<=c+1;i++)
Ans+=(LL)Abs(-1-a[i]);
for (i=c+2;i<=n;i++)
Ans+=(LL)Abs(a[i]-1);
} else {
for (i=1;i<c;i++)
Ans+=(LL)Abs(-1-a[i]);
for (i=c;i<=n;i++)
Ans+=(LL)Abs(a[i]-1);
}
}
cout<<Ans<<endl;
return 0;
}
C
推导之后不难发现，从1开始相邻的两个数一定分布在圆环的两边，因为要求n个数的和至多有两种取值，而且数字不能重复，所以，相邻的取值一定相差1，同时可以得出n为偶数时无解。然后把1和2按照找到的规律放置在圆环上，之后依次判断相邻两数的分布即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 400010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,w;
int a[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d",&n);
if ((n%2)==0){
cout<<"NO"<<endl;
return 0;
}
a[1]=1; a[n+1]=2;
w=3;
for (i=2;i<=n;i++){
if (i%2) x=1; else x=-1;
if (x==1) {
a[i]=w; a[i+n]=w+1;
} else {
a[i]=w+1; a[i+n]=w;
}
w+=2;
}
cout<<"YES"<<endl;
for (i=1;i<=2*n;i++)
printf("%d ",a[i]);
return 0;
}
D
最小环问题。
首先数据范围保证了一个数的二进制至多含有59个1，所以根据抽屉原理，当有效数字(指把0给剔除掉)的总数大于118时，答案为3。当二进制某一位为1的数字总数超过2时，答案也为3。对于一般情况，再拿Floyd计算最小环即可。此时点的数量规模在100左右，时间复杂度有保障。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 200010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,dp,d;
int z[N],dfn[N],f[N],low[N];
LL Ans;
LL dis[220][220],l[220][220];
LL a[N],b[N];
vector <int> son[N];
map <LL,LL> M,id,re;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
int i=0,j=0,k=0;
for (i=1;i<=n;i++){
for (j=0;j<=59;j++)
if (a[i]&((LL)1<<j)) son[j].push_back(i);
}
for (i=0;i<=59;i++)
if (son[i].size()>=3){
cout<<"3"<<endl;
exit(0);
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
l[i][j]=dis[i][j]=INF;
for (i=0;i<=59;i++)
for (j=0;j<son[i].size();j++)
for (k=j+1;k<son[i].size();k++)
l[son[i][j]][son[i][k]]=l[son[i][k]][son[i][j]]=1;
for (i=1;i<=n;i++) l[i][i]=1;
}
inline void Work(){
int i=0,j=0,k=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
dis[i][j]=l[i][j];
Ans=N;
for (k=1;k<=n;++k){
for (i=1;i<k;++i)
for (j=1;j<i;++j)
Ans=Min(Ans,dis[i][j]+l[i][k]+l[k][j]);
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
dis[i][j]=Min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
if (n<=2){
cout<<"-1"<<endl;
return 0;
}
sort(a+1,a+1+n);
for (i=1;i<=n;i++)
if (a[i]>0){
b[++b[0]]=a[i]; id[a[i]]=b[0]; re[b[0]]=a[i];
M[a[i]]++;
}
n=b[0];
for (i=1;i<=n;i++){
a[i]=b[i];
if (M[a[i]]>=3) Ans=3;
}
if (!n){
cout<<"-1"<<endl;
return 0;
}
if (Ans==3){
cout<<Ans<<endl;
return 0;
}
if (n>=121){
cout<<"3"<<endl;
return 0;
}
Ready(); Work();
if (Ans==N) cout<<"-1"<<endl;
else cout<<Ans<<endl;
return 0;
}
E
玄学构造交互题。
首先对于同一行的元素(x,y)，可以检查和（x,y-2）能否构成回文，对于每一行的前两个元素特殊处理即可。然后考虑类似棋盘的黑白染色，所有白色格子(左上角格子染成白色)的数已经确定，所有黑色格子的数的相等关系也已经确定。此时耗去询问数量
n^2-2
然后考虑(x,y)和(x+1,y+2)之间能否构成回文串。因为在当前情况下，答案只可能有两种情况，所以可以依次枚举。当枚举到某种情况，而且找到了(x,y)和(x+1,y+2)构成的回文串时，进行一次询问，如果结果为1，说明这种情况就是答案。因为假如不是答案，那么将黑色格子的数字翻转后，一定构不成回文串;如果结果为0，说明另一种情况才是答案。当枚举某种情况没有检测到这种格式的回文串时，再枚举另外一种情况，检查是否有回文串。如果有，处理方式同上。总的询问次数为
n^2-1
刚好符合要求。
这种方法的正确性基于以下原理：任意一个填数方案，一定存在上述格式的回文串(或者将黑色格子的数字翻转后的方案中一定存在)。但是这个原理目前并不会证明QAQ官方题解也给出了另外一种思路(带证明的)。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 55
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,x,flag=0;
int a[N][N],b[N][N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline bool Check(int p,int q){
int a=((b[p][q]==b[p+1][q+2])&&(b[p][q+1]==b[p][q+2]));
int c=((b[p][q]==b[p+1][q+2])&&(b[p+1][q]==b[p+1][q+1]));
return a|c;
}
inline bool Work(int p,int q){
printf("? %d %d %d %d\n",p,q,p+1,q+2);
fflush(stdout);
scanf("%d",&x);
return x;
}
int main(){
scanf("%d",&n);
a[1][1]=1; a[n][n]=0; a[1][2]=-2;
for (i=3;i<=n;i++){
printf("? %d %d %d %d\n",1,i-2,1,i);
fflush(stdout);
scanf("%d",&x);
if (x) a[1][i]=a[1][i-2];
else a[1][i]=(a[1][i-2]>=0)?1-a[1][i-2]:-5-a[1][i-2];
}
for (i=2;i<=n;i++){
for (j=2;j<=n;j++){
if (i+j==2*n) break;
printf("? %d %d %d %d\n",i-1,j-1,i,j);
fflush(stdout);
scanf("%d",&x);
if (x) a[i][j]=a[i-1][j-1];
else a[i][j]=(a[i-1][j-1]>=0)?1-a[i-1][j-1]:-5-a[i-1][j-1];
}
printf("? %d %d %d %d\n",i,1,i,3);
fflush(stdout);
scanf("%d",&x);
if (x) a[i][1]=a[i][3];
else a[i][1]=(a[i][3]>=0)?1-a[i][3]:-5-a[i][3];
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
b[i][j]=(a[i][j]>=0)?a[i][j]:a[i][j]+3;
for (i=1;i<=n-1;i++)
for (j=1;j<=n-2;j++)
if (Check(i,j)){
if (Work(i,j)){
cout<<"!"<<endl;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
printf("%d",b[i][j]);
cout<<endl;
}
} else {
flag=1; goto END;
}
return 0;
}
END:
if (flag){
cout<<"!"<<endl;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
printf("%d",(a[i][j]>=0)?a[i][j]:-2-a[i][j]);
cout<<endl;
}
return 0;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
b[i][j]=(a[i][j]>=0)?a[i][j]:-2-a[i][j];
for (i=1;i<=n-1;i++)
for (j=1;j<=n-2;j++)
if (Check(i,j)){
if (Work(i,j)){
cout<<"!"<<endl;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
printf("%d",b[i][j]);
cout<<endl;
}
} else goto END2;
return 0;
}
END2:
cout<<"!"<<endl;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
printf("%d",(a[i][j]>=0)?a[i][j]:3+a[i][j]);
cout<<endl;
}
return 0;
}
总结&吐槽
比赛前期状态良好,B题少打了一个等号导致吃了一次WA,但是切题速度还行.D题一开始读错了题目,理解成了求最大环,然后又突发奇想求强联通分量...就这都通过了9个测试点.反应过来后立刻换成Floyd求最小环,但是之前算强联通分量的缩点部分没有删除,导致了D题最后FST.同时因为浪费时间过多导致没有时间开E题.B题因为少考虑了一些情况也FST了...最后Rating迎来一波暴跌.
话说回来,这也是第一次在Codeforces上Hack别人,成功两次,失败一次.Hack用的正是会把我自己的B题代码卡掉的数据QAQ.看来很长时间不打cf导致稳定性出了些问题.下次做题的时候一定要认真读题,考虑各种边界情况,提升代码严谨程度.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: Codeforces Round #580 (Div. 2)
本文地址: Codeforces Round #580 (Div. 2)
