总评:感觉这前面四题不是很需要什么知识,更像思维题,但是细节比较多。
1.简单的博弈:https://codeforces.com/contest/1990/problem/A
直接说结论:如果每一个数的个数都是偶数,那么失败,否则胜利。
很好证明:假如全是偶数,那么先手拿一个,后手一定可以拿相同的一个,于是先手必败。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[10010];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int k=1;
int f=1;
for(int i=1;i<=n;i++){
if(a[i]==a[k]) continue;
int w=i-k;
if(w%2){
cout<<"YES"<<endl;
f=0;
break;
}
k=i;
}
if(f){
if((n-k+1)%2==0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
}
2.构造+贪心:https://codeforces.com/contest/1990/problem/B
一开始想我在[y,x]都填1,然后在两侧-1,1交错并保证和为0或者-1即可。然后WA了两发。
这里有个细节:对于[1,y-1]一开始是填1还是-1需要根据它的区间长度的奇偶讨论/
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int t,n,x,y;
int main(){
cin>>t;
while(t--){
cin>>n>>x>>y;
int xx;
if(y%2) xx=1;
else xx=-1;
for(int i=1;i<=y-1;i++){
cout<<xx<<" ";
xx=-xx;
}
for(int i=y;i<=x;i++){
cout<<1<<" ";
}
xx=-1;
for(int i=x+1;i<=n;i++){
cout<<xx<<" ";
xx=-xx;
}
cout<<endl;
}
}
3.枚举:https://codeforces.com/contest/1990/problem/C
首先我们先自己进行一遍操作,发现序列一定长成如00002222333444这种形式,再来一遍:
00000222233344,我们可以看到就是左边多了个0,使整个序列向右平移一个,然后最边上的被挤了出去,因此我们可以从我们考虑倒数第i个数字a的贡献,它距尾还有n-i+1个距离:它还可以坚持n-i+1轮,也就是贡献a*(n-i+1),于是我们遍历一遍即可。
但是对于11123333,操作一次:01111333,我们发现2并没有做出贡献,而他是被1吸收了。那么怎么处理呢?
我们计:A1为原数列,A2为操作一次得到的,其中A2可能夹杂这单个元素。我们不妨对A2再操作一次A3,那么A3单个元素只可能出现在最后(不理解的可以自己试一下),这样即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll a[200010];
ll yuan[200010];
ll yuan1[200010];
ll sum;
int cun[200010];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sum=0;
for(int i=1;i<=n;i++) sum+=a[i];
memset(cun,0,sizeof(cun));
ll maxx=0;
for(int i=1;i<=n;i++){
cun[a[i]]++;
if(cun[a[i]]<2) yuan[i]=maxx;
else{
if(a[i]>maxx){
yuan[i]=a[i];
maxx=a[i];
}
else yuan[i]=maxx;
}
}
for(int i=1;i<=n;i++) sum+=yuan[i];
memset(cun,0,sizeof(cun));
maxx=0;
for(int i=1;i<=n;i++){
cun[yuan[i]]++;
if(cun[yuan[i]]<2) yuan1[i]=maxx;
else{
if(yuan[i]>maxx){
yuan1[i]=yuan[i];
maxx=yuan[i];
}
else yuan1[i]=maxx;
}
}
//>2次
for(int i=n;i>=1;i--){
sum+=(n-i+1)*yuan1[i];
}
cout<<sum<<endl;
}
}
4.贪心:https://codeforces.com/contest/1990/problem/D
首先:从1枚举到n假如出现长度>4的直接用一次操作2消掉。因为用一的话至少3次,而我们3次操作2就可以把周围两行+本行删掉。
其次对于长度1的等价于长度2,长度为3的等价于长度4.
这样我们就把问题简化成了2和4的长度。
对于连续的4,我们可以用两次操作2,也可以用1次操作1把它凸出来的消掉,然后剩下的22可以左右分或者直接删。我们发现两次操作一一定可以删掉,同时执行1次可以为后来更少次数留下更多可能(2442),于是1次操作1更优。于是我们用1次操作1。
现在图上只有连续的2以及孤立的4.
我们从1枚举到n,发现有连续的2就删。这样图上就只有单个的2/4了。
此时,从1--n,对于4直接用操作2,对于2直接操作1即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int t;
int n,a[200010];
int main(){
cin>>t;
while(t--){
cin>>n;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]>4){
a[i]=0;
cnt++;
}
else if(a[i]==0) continue;
else if(a[i]==1) a[i]=2;
else if(a[i]==3) a[i]=4;
}
//对于连续的4消掉
for(int i=1;i<=n-1;i++){
if(a[i]==4&&a[i]==a[i+1]){
a[i]=2;
a[i+1]=2;
cnt++;
}
}
//对于连续的2消掉
for(int i=1;i<=n-1;i++){
if(a[i]==2&&a[i]==a[i+1]){
a[i]=0;
a[i+1]=0;
cnt++;
}
}
//cout<<cnt<<endl;
//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//cout<<endl;
for(int i=1;i<=n;i++){
if(a[i]==0) continue;
if(a[i]==4) cnt++;
else if(a[i]==2&&a[i+1]==0) cnt++;
else{
cnt+=2;
i++;
}
}
cout<<cnt<<endl;
}
}