A.Remove Smallest
题目描述：
给出了你一个序列a,现在给定一种操作：任意选择序列a中的两个数ai和aj，如果满足：|ai - aj| <= 1那么就可以删除ai和aj中最小的那一个数，如果二者相等，那就可以任意删除一个。现在询问你对于一个序列a，经过有限次上述操作后，有没有可能使a中的元素只有一个。
题解：
分析可知，满足条件的a序列必须满足：当a从小到大排序后，对于每两个相邻的元素，其大小关系必须满足|ai - bi| <= 1。所以代码就出来了
AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100;
int a[maxn] = {};
bool cmd(int a,int b)
{return a < b;
}
int main()
{int t;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));int n,flag = 1;scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);sort(a + 1,a + 1 + n,cmd);for(int i = 2;i <= n;i++){if(a[i] - a[i - 1] > 1){flag = 0;printf("NO\n");break;}else continue;}if(flag) printf("YES\n");}return 0;
}
B.Gifts Fixing
题目描述：
现在你有n种糖果和n种橘子，你希望把他们都均分给n个孩子，也就是说，对于序列a和b，都要求满足：a1 = a2 = a3 = ...... = an和b1 = b2 = b3 = ....... = bn
现在给出你三种操作：
1.只对ai操作，使ai减一。
2.只对bi操作，使bi减一
3.同时对ai和bi操作，同时减一。
问你最少需要操作几次。
题解：
首先最后a的所有元素值和b的所有元素值一定是初始状态下对应的最小的元素值。那么我们就需要判断当前的ai和bi是不是比这个值大，如果同时大于那就取相差最小的那个作为执行操作3的数量，然后单独计算操作1和操作2的数量，相加即可。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 100;
const ll INF = 0x3f3f3f3f;
ll a[maxn] = {},b[maxn] = {};
int main()
{int t;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));int n;ll mina = INF,minb = INF;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%lld",&a[i]);mina = min(a[i],mina);}for(int i = 1;i <= n;i++) {scanf("%d",&b[i]);minb = min(minb,b[i]);}ll ans = 0;for(int i = 1;i <= n;i++) {if(a[i] > mina && b[i] > minb){if(a[i] - mina > b[i] - minb){ans += b[i] - minb;ans += a[i] - mina - (b[i] - minb);}else {ans += a[i] - mina;ans += b[i] - minb - (a[i] - mina);}}else if(b[i] == minb && a[i] == mina) continue;else if(b[i] == minb && a[i] > mina) ans += a[i] - mina;else if(b[i] > minb && a[i] == mina) ans += b[i] - minb;}printf("%lld\n",ans);}return 0;
}
C.Boats Competition
题目描述：
现在官方举办了一场龙舟比赛，现在要求两人一组，有n个人报名，这n个人的体重分别是w1,w2,wn.现在为了比赛公平，要求每艘船上的两个人的体重之和为一个定值s，现在要求你确定一个s，使得这n个人可以组成的队伍数最多，并输出这个队伍数目。
题解：
其实这个题目第一直觉是二分答案，但是后面发现数据不大可以直接暴搜TAT
这个题我写的s的取值是min * 2 - max * 2，min和max代表a中的最值，然后对于每一个s写出可以得到的组数，然后维护一个最大值即可。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int w[100],num[100],flag[100];
int main()
{int t;scanf("%d",&t);while(t--){memset(w,0,sizeof(w));memset(num,0,sizeof(num));int n,maxm = 0,minn = 0x3f3f3f3f,ans = 0;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&w[i]);num[w[i]]++;maxm = max(w[i],maxm);minn = min(minn,w[i]);}for(int s = minn + minn;s <= maxm + maxm;s++){//s取值int temp = 0;memset(flag,0,sizeof(flag));for(int j = 1;j <= n;j++){ //对每一种s进行搜索if(s <= w[j] || flag[w[j]] == 1) continue; //如果s无法凑出或者已经选过这个数，就跳过else if(w[j] != s - w[j]){temp += min(num[w[j]],num[s - w[j]]);flag[w[j]] = 1;flag[s - w[j]] = 1; //标记}else if(w[j] == s - w[j]){ //注意这里是两种算法temp += num[w[j]] / 2;flag[w[j]] = 1; //标记}}ans = max(temp,ans);}printf("%d\n",ans);}return 0;
}
D. Binary String To Subsequences
题目描述：
给了你一个01字符串，现在需要你找出里面的01子串都有多少个，并且输出每个字符的字串编号。
01子串：满足形如010101或者101010
题解：
其实这个题目就是找连续01子串，如果当前字符是0那就看上一个1有没有编号，如果是1同理。具体的看代码。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 2e5 + 11;
int a[maxn] = {};
int main()
{int t;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));int n,cnt = 0;string s;cin >> n >> s;vector<int> v[2]; //存子串的位置for(int i = 0;i < n;i++){int x = s[i] - '0';if(v[x ^ 1].empty()){ //如果对家没有被标记，那就证明需要再开一个子串v[x].push_back(++cnt);a[i] = cnt;}else{v[x].push_back(v[x ^ 1].back()); //对家已经有一个子串了，所以可以接着连起来a[i] = v[x ^ 1].back();v[x ^ 1].pop_back(); //这里注意，我们找到这个数的对家以后子串的编号就要转移到对家上了，所以需要把之前的编号pop出来}}cout << cnt << endl;for(int i = 0;i < n - 1;i++){cout << a[i] << ' ';}cout << a[n - 1] << endl;}
}