A-Chess For Three
因为序列满足a<=b<=c的情况
显然通过得分可以观察出得分总和必定为偶数
否则不成立
求的是最大平局数
那么直接假设全部都是平局
这时候发现如果c过大会导致后面的局数不是平局
那么只用把c>a+b的情况取出
而此时平均数为a+b
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
const int N=2e5+10;
void solve(){
int a,b,c;
cin>>a>>b>>c;
if((a+b+c)%2){
cout<<-1<<'\n';
}else {
if(a+b>=c)
cout<<(a+b+c)/2<<'\n';
else {
cout<<a+b<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}
B-Cat, Fox and the Lonely Array
二进制之间求最大的距离
先从简单的情况想
如果只有1和0
那么这题的最大或和
为两个1之间最远的距离
1 0 1 0 1 此时为2
1 0 0 0 1 此时为4
1 0 1 0 0 1 此时为3
那么很容易就想到
如果把它从二进制进行拆分
那么只需要求每个位上面的1之间的最大距离
为什么是最大
因为只有最大才能满足所有的需求
有点小细节要抠一下
比如
1 0 0 0 0 是5
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
const int N=2e5+10;
void solve(){
int n;cin>>n;
vector<int>a(n);
for(auto &t:a)cin>>t;
int len=1;
for(int k=0;k<=20;k++){
int nl=0;
for(int i=0;i<n;i++){
if((a[i]>>k&1)==0){
nl++;
}
else len=max(len,nl+1),nl=0;
}
if(nl==n)continue;
len=max(nl+1,len);
}
cout<<len<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}
C-Cat, Fox and Double Maximum
一道非常简单的构造
个人认为难度小于B
首先考虑如何构造一个凸的点
通过观察发现
其中凸点的个数必定为n/2-1
那么我们可以把头删去或者把尾删去来构造凸点
那么必定存在一组成立
把删去的点设为n/2+1
对其中的凸点从小到大赋值为n-i
对凹点从小到大赋值为n/2-i
因为删去的点赋值为n/2+1
所以存在差值
所以两组构造中必有一组成立
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
const int N=2e5+10;
void solve(){
int n,evenans,oddans;cin>>n;
vector<int>a(n),b(n/2),c(n/2-1),vis(n+1);
for(int i=0;i<n;i++)cin>>a[i];
auto ck=[&](){
int cnt=0;
for(int i=1;i<n-1;i++){
if(vis[a[i]]+a[i]>a[i-1]+vis[a[i-1]]&&vis[a[i]]+a[i]>vis[a[i+1]]+a[i+1])cnt++;
}
return cnt==n/2-1;
};
auto print=[&](){
for(int i=0;i<n;i++)cout<<vis[a[i]]<<" \n"[i==n-1];
};
vis[a[0]]=n/2+1;
for(int i=1;i<n;i++){
if(i&1){
b[i/2]=a[i];
}
else c[i/2-1]=a[i];
}
sort(all(b));
sort(all(c));
for(int i=0;i<n/2-1;i++)vis[c[i]]=n-i;
for(int i=0;i<n/2;i++)vis[b[i]]=n/2-i;
if(ck()){
print();return;
}
vis[a[n-1]]=n/2+1;
for(int i=0;i<n-1;i++){
if(i&1){
c[i/2]=a[i];
}
else b[i/2]=a[i];
}
sort(all(b));
sort(all(c));
for(int i=0;i<n/2-1;i++)vis[c[i]]=n-i;
for(int i=0;i<n/2;i++)vis[b[i]]=n/2-i;
print();
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}