Codeforces Round 945 (Div. 2) A-C

本期封面 画师星屑ノユ

A. Chess For Three

题意

三人下棋，每次两个人下，赢了2分输了1分打平各1分，给你最后三人的总分，最大化平局场数

思路

首先不管什么结果每局总积分都是加2，所以最后积分是奇数的话那就是不满足题意
然后肯定是分少的优先跟分多的打平，最后剩下的再拿回来匹配，所以最优情况肯定是总积分除以2，但是如果比分差距过大也不行，所以取个min即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int a,b,c;scanf("%d%d%d",&a,&b,&c);int sum=a+b+c;if(sum%2!=0){puts("-1");return;}sum/=2;printf("%d\n",min(a+b,sum));
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

B. Cat, Fox and the Lonely Array

题意

给定一个数组，找到最小的k使得数组里任意连续k个数按位取或都相等

思路

注意到数据范围是$2^{20}$，考虑拆位，拆完之后我们可以看假如某一位依次是

0 1 0 0 0 0 1 1 1 0 0 1

我们一个一个试就可以发现规律，每一位的最小的k都得是最长的连续0的长度加1，最后整体取一个min就可以了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//0 1 0 0 0 0 1 1 1 0 0 10 1 0 0 0 0 1 1 1 0 0 1void solve()
{int n;scanf("%d",&n);vector<int> a(n+1);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}vector<vector<int>> b(n+1,vector<int>(20,0));//对每个a拆成二进制位for(int i=1;i<=n;i++){for(int j=0;j<20;j++){b[i][j]=a[i]%2;a[i]/=2;
//            printf("%d",b[i][j]);}
//        printf("\n");}int k=1;for(int i=0;i<20;i++){bool flag=true;//全是0int res=0;//最长连续0的长度int cnt=0;for(int j=1;j<=n;j++){if(b[j][i]==1 and flag){flag=false;}if(b[j][i]==0){cnt++;}else{res=max(res,cnt);cnt=0;}}res=max(res,cnt);if(!flag){k=max(k,res+1);}}printf("%d\n",k);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

C. Cat, Fox and Double Maximum

题意

给一个排列p，构造一个排列q，每一位对应相加得到a数组，最大化a数组里比左右两个数都大的数

思路

肯定要么是尽量放大所有奇数要么是尽量放大所有偶数，我们可以很简单的构造出使所有a相等的情况，然后我们考虑把奇数位或者偶数位全部加1，剩下的数再按顺序匹配给剩下的位置，但是有一个问题就是如果本来就是n了就没有办法加1了，所以我们就看n在奇数位还是偶数位，他在哪我就躲开他

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n;scanf("%d",&n);vector<int> p(n+1);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}vector<int> q(n+1);int flag;//0:even 1:oddfor(int i=1;i<=n;i++){q[i]=n-p[i]+1;if(q[i]==n){if(i%2==0)flag=1;elseflag=2;}}int mp[n+1];memset(mp,0,sizeof(mp));for(int i=flag;i<=n;i+=2){q[i]++;mp[q[i]]++;}vector<int> tmp;for(int i=1;i<=n;i++){if(mp[i]==0){tmp.push_back(i);}}sort(tmp.begin(),tmp.end());vector<pii> anothertmp;for(int i=flag==1?2:1;i<=n;i+=2){anothertmp.push_back({q[i],i});}sort(anothertmp.begin(),anothertmp.end());for(int i=0;i<tmp.size();i++){q[anothertmp[i].second]=tmp[i];}
//    printf("q:");for(int i=1;i<=n;i++){printf("%d ",q[i]);}printf("\n");
//    printf("a:");
//    for(int i=1;i<=n;i++)
//    {
//        printf("%d ",p[i]+q[i]);
//    }
//    printf("\n");
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}