Codeforces Round #661 (Div. 3)ABCD

前言

捋一下ABC的思路，补出D题

A. Remove Smallest

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int a[maxn],t;
int main(){scanf("%d",&t);while(t--){memset(a,0,sizeof(a));int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);bool flag=false;for(int i=1;i<n;i++){if(abs(a[i]-a[i+1])>1){flag=true;break;}}if(flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;}
}

B. Gifts Fixing

传送门

这道题还稍微有点意思，让a1=a2=…=an;b1=b2=…=bn;
我们要找的是a[]、b[]最小值，而不是次数最多的值，这走了点弯路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100;
int a[maxn],b[maxn];
ll sum;
int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int num1=0x3f3f3f3f,num2=0x3f3f3f3f;sum=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]),num1=min(num1,a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]),num2=min(num2,b[i]);for(int i=1;i<=n;i++){sum+=max(a[i]-num1,b[i]-num2);}printf("%lld\n",sum);}
}

C. Boats Competition

传送门

题意：给定一串数组，令两两一组，让所有组的值相等，问能凑出多少组
我们直接用map存一下，first我们存的是去重的数组值，second是first值在数组中出现的次数。我们假设有a、b、c、d三个数，a+b肯定不能等于a+c。也就是说a+b=num,c+d=num,a、b、c、d肯定是数组中不同的数。所以说我们用去重的first把所有的情况找出来，那个最大的就是结果，再除2即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2;
int t,n;
int p[maxn+100];
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);int sum=0;map<int,int> q;memset(p,0,sizeof(p));for(int i=1;i<=n;i++){int x;scanf("%d",&x);q[x]++;}map<int,int>::iterator it1,it2;for(it1=q.begin();it1!=q.end();it1++){for(it2=q.begin();it2!=q.end();it2++){int num1=it1->first;int num2=it2->first;p[num1+num2]+=min(it1->second,it2->second);sum=max(sum,p[num1+num2]);}}printf("%d\n",sum/2);}
}

我查了查网上是否有比我的还简单的，觉得这个双指针也很巧妙

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int a[maxn],t,n;
int main(){scanf("%d",&t);while(t--){memset(a,0,sizeof(a));scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);int sum=0;for(int i=1;i<=100;i++){int l=1,r=n;int num=0;while(l<r){if(a[l]+a[r]==i){l++;r--;num++;}else if(a[l]+a[r]>i){r--;}else l++;}sum=max(num,sum);}printf("%d\n",sum);}
}

D. Binary String To Subsequences

传送门

看了大佬的文章，思路非常的巧妙.
题意：给一段二进制序列，分成n个子序列，子序列为01010…或者1010…这种形式，问最少可以分几个。
vector相当于一个动态数组，queue相当于队列。
使用q0、q1分别存储0和1的下标。
当前值为0时，如果q1不为空的情况下，用vector存储q1最前面的子序列号，并移除q1最前面的值；如果q1为空，重新创建子序列号；
当前值为1时同理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int t;
char a[maxn];
int main()
{scanf("%d",&t);while(t--){int n;scanf("%d",&n);scanf("%s",a);queue<int> q0,q1;vector<int> temp;int num=0;for(int i=0;i<n;i++){if(a[i]=='0'){if(q1.empty())  temp.push_back(++num);else temp.push_back(temp[q1.front()]),q1.pop();q0.push(i);}else{if(q0.empty()) temp.push_back(++num);else temp.push_back(temp[q0.front()]),q0.pop();q1.push(i);}}printf("%d\n",num);vector<int>::iterator it;for(it=temp.begin();it!=temp.end();it++){printf("%d ",*it);}printf("\n");}
}