A. Div. 7
题意：
每次操作可以改变一个数中的一位，然后问最少的操作数使得当前的数经过操作变成能被7整除。
思路：
解法有挺多的吧，我的做法只能说又蠢又笨，还是推荐去看好一点的做法，不过留意一下范围非常小都数据量和数据范围都不超过1000，暴力即可
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t; cin>>t; while(t--) { cin>>n; if(n%7==0) { cout<<n<<endl; } else { int ans=inf; int ans1=7; if(n/100!=0) { int d1=n%10,d2=n/10%10,d3=n/100; for(i=105;i<=999;i+=7) { int y1=i%10,y2=i/10%10,y3=i/100; int cnt=0; if(y1!=d1)cnt++; if(y2!=d2)cnt++; if(y3!=d3)cnt++; ans=min(cnt,ans); if(ans==cnt) ans1=i; } } else { int d1=n%10,d2=n/10%10; for(i=14;i<105;i+=7) { int y1=i%10,y2=i/10%10; int cnt=0; if(y1!=d1) cnt++; if(y2!=d2) cnt++; ans=min(cnt,ans); if(ans==cnt) ans1=i; } } cout<<ans1<<endl; } } return 0; }
B. Minority
题意：给你一个只包含0和1的字符串，求该串的子串中0和1个数中最小的个数的最大的值是多少。
思路：其实很容易想到，就是为原串的时，他们包含的0和1个数最多，那么就能得到较少的那个值的最大值了，不过注意特判如果相等的时候，可以少取一位
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { string s1; cin>>s1; int cnt0=0,cnt1=0; for(int i=0;i<s1.length();i++) { if(s1[i]=='0') cnt0++; else cnt1++; } if(cnt0>cnt1) cout<<cnt1<<endl; else if(cnt1>cnt0) cout<<cnt0<<endl; else cout<<cnt0-1<<endl; } return 0; }
C. Kill the Monster
题意：其实就是炉石那种卡牌游戏，一个英雄有攻击力和防御力，同理还有一个怪兽有攻击力和防御力，然后你有k个硬币，每个硬币可以买w点攻击力或者买a点防御力，求是否英雄能打败怪兽，能则输出yes，否则为no
思路：可以注意所有测试样例k个硬币不超过2e5，所以直接暴力跑每个硬币是加攻击力还是防御力即可，因为非此即彼，选了就对我而言是优，然后算一下回合数，因为英雄先手，只要英雄打败怪兽的回合数大于等于怪兽打败英雄的回合数即可，注意除法要向上取整，这里用-1的操作。
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int n,i,j,t; cin>>t; while(t--) { int hc,dc,hm,dm,k,w,a; cin>>hc>>dc>>hm>>dm; cin>>k>>w>>a; int flag=0; for(i=0;i<=k;i++) { int t1,t2; t1=(hm-1)/(w*(i)+dc); t2=(hc+a*(k-i)-1)/(dm); if(t1<=t2) flag=1; } if(flag==0) { scNO; } else { scYES; } } return 0; }
D. Make Them Equal
题意：现在你有n个值为1的数，可以进行k次变化，每次变化可以把当前数的值变成值ai + ai/x ，x可以取任意值，并且你如果你有数能够变成bi，你就获得ci个金币，求获得金币的最大值
思路：其实只要把k次变化搞清楚，这道题就是个01背包的裸题了，其实不难发现这个变化是有最优的情况的，而且注意范围，对答案有贡献的bi范围很小，所以你暴力先找到从i到j所需要的的最少的操作数，可以通过两重for暴力跑出来，然后这就是你的01背包里的物品的体积。
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int maxn=5005; int sp[maxn],value[maxn],b[maxn],dp[maxn*maxn]; int main() { int n,i,j,t,k; for(i=1;i<=1001;i++) sp[i]=inf; sp[1]=0; for(i=1;i<=1001;i++) { for(j=1;j<=1001;j++) { sp[i+i/j]=min(sp[i+i/j],sp[i]+1); } } cin>>t; while(t--) { cin>>n>>k; for(i=0;i<n;i++) { cin>>b[i]; } for(i=0;i<n;i++) { cin>>value[i]; } for(i=0;i<=k;i++) dp[i]=0; for(i=0;i<n;i++) { for(j=k;j>=sp[b[i]];j--) { dp[j]=max(dp[j],dp[j-sp[b[i]]]+value[i]); } } cout<<dp[k]<<endl; } }
