A. Plus One on the Subset
题意：简单题，每次可以选择数组里的任意多的数字进行加一，求要多少次可以使得整个数组里的所有元素相等
思路：直接遍历找到最大值和最小值的差值输出相同即可。
#include<bits/stdc++.h> using namespace std; int a[55]; int main() { int n,i,j,t; cin>>t; while(t--) { cin>>n; int min1=inf,max1=0; for(i=0;i<n;i++) { cin>>a[i]; max1=max(max1,a[i]); min1=min(min1,a[i]); } cout<<max1-min1<<endl; } return 0; }
B. Make AP
题意：给你三个数字x,y,z问选择任意一个数字乘以任意数之后，能否使得序列为一个等差数列。
思路：感觉写复杂了，枚举一下三种可能性就行，已知任意两个数，假设他们为等差，那么第三个数是固定的，判断是不是原数的因子即可。
#include<bits/stdc++.h> using namespace std; bool jg(int x,int y,int z) { if(x==y&&y==z) return true; if(x+z==2*y&&((z>y&&y>x&&z-y==y-x)||((x>y&&y>z&&x-y==y-z)))) return true; return false; } int main() { int n,i,j,t,x,y,z; cin>>t; while(t--) { cin>>x>>y>>z; if((x+z)%2==0&&(((x+z)/2)%y==0)&&jg(x,(x+z)/2,z)) { // cout<<x<<" "<<(x+z)/2<<" "<<z<<endl; scYES; } else if(2*y-z>0&&(2*y-z)%x==0&&jg(y-(z-y),y,z)) { // cout<<2*y-z<<" "<<y<<" "<<z<<endl; scYES; } else if(2*y-x>0&&(2*y-x)%z==0&&jg(x,y,y+(y-x))) { // cout<<x<<" "<<y<<" "<<2*y-x<<endl; scYES; } else { scNO; } } return 0; }
C. Division by Two and Permutation
题意：给出一个数组a，每次操作会使数组里的元素/2，求最后能否变成从1~n的全排列。
思路：直接暴力模拟，只要当前数字能变成1~n里的数就行，能变成就标机一下，然后继续，我之前卡住了，还以为是将当前数字能划分的所有数字当成一组，然后每组只能选一个，我就以为是个分组的背包，但是不懂怎么递归下去，然后发现不行，浪费了很多时间，看完这个思路也没懂，为什么这个打标机的操作没有先后呢? 猜过的ε=(´ο｀*)))唉
#include<bits/stdc++.h> using namespace std; const int maxn=55; int a[maxn]; vector<int >m1[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,i,j,t; map<int,int >mo; cin>>t; while(t--) { cin>>n; mo.clear(); bool ok=0; for(i=1;i<=n;i++) { cin>>a[i]; while(1) { if(mo[a[i]]==0&&a[i]>=1&&a[i]<=n) { mo[a[i]]++; break; } else if((mo[a[i]]!=0||(a[i]>n))&&a[i]!=0) { a[i]/=2; } else if(a[i]==0) { ok=1; break; } } } if(ok==1) scNO else scYES; } return 0; }
D. Palindromes Coloring
题意：其实可以把这题抽象一下，就是把一个字符串拆成k个子串，输出所有子串里回文子串的最大长度的最小值
思路：不难想到可以先把字母都以2为长度划分一下，这样可以一起划分到一个新的字符串都能构成回文串，但是如果有个字母长度为奇数，那么该字符串一定都作为k个答案的母串，但是还有一种情况容易漏，就是假设现在有5对a，我需要拆成3个串，那么我可能会拆成
aa aa
aa aa
aa
这样最短的长度是2，但其实并不是最优的，虽然5/3=1，意思是5对字母分成三个字符串，刚好可以每个字符串分一对aa，但是5%3=2
还多余了两对，再把这两对*2，就是还多了四个字母，很明显4个字母是大于k的
所以正确的划分应该是
aa aa
aa a
aa a
这样长度就是3了，所以只要为奇数的字符串的数量+能拆成的偶数对数*2%k之后的字符数量大于k，就可以多凑一排了
#include<bits/stdc++.h> using namespace std; int main() { map<char ,int >mo; string s1; int n,i,j,t,k; cin>>t; while(t--) { mo.clear(); cin>>n>>k>>s1; int cnt=0,sum=0; for(i=0;i<n;i++) { mo[s1[i]]++; } for(auto &[a,b]:mo) { if(b%2==1) { cnt++; } sum+=(b/2); } int ans=sum/k*2; if((sum%k)*2+cnt>=k) ans++; cout<<ans<<endl; } return 0; }
