比赛链接:https://codeforces.ml/contest/1759
A题:大意是给出一个字符串,每个字符串是否能够被Yes识别到。设字符串长度为n,则主串为n个Yes,求是否存在输入的字符串。
读题还是挺麻烦的,心态有点崩。 做起来很简单,需要注意如果不存在s.find()的返回为npos
code:
void solve() { string s; cin>>s; string c=""; for(int i=0;i<s.size();i++){ c+="Yes"; } if(c.find(s)!=s.npos){ cyes; }else cno; }
B题:大意是给出两个数m和s,给出m个数,求是否可以通过增加和为s的若干个数,使得存在一个排列。
解决方法:每个元素很小可以直接暴力是否存在sum+s的排列数,从m个元素中的最大的开始枚举一定的范围即可。
code:
void solve() { mem(a); ll m,s; cin>>m>>s; ll maxt=0,mint = 999; ll sum = 0; for(int i=1;i<=m;i++){ cin>>a[i]; maxt = max(a[i],maxt); mint = min(a[i],mint); sum+=a[i]; } sort(a+1,a+m+1); for(int i=1;i<m;i++){ if(a[i]==a[i+1]){ cno; return; } } for(int i=1;i>=1;i--){ for(int j=maxt;j<100;j++){ if(b[j]-b[i-1]==sum+s){ cyes; return; } } } cno; return; }
C题:大意是给出l和r,跟一个限制x。给出a和b在l与r范围内,求至少需要多少次可以使得a=b。a的改变必须大于等于x。
直接列出所有的情况,对其进行一一判断,我们易知,最多存在3次可以达到b。否则-1
code:
void solve() { ll l,r,x; cin>>l>>r>>x; ll a,b; cin>>a>>b; if(a<b){ if(b-a>=x) cout<<1<<endl; else if(a-l>=x||r-b>=x) cout<<2<<endl; else if(a-l>=x&&r-l>=x&&r-b>=x||r-a>=x&&r-l>=x&&b-l>=x) cout<<3<<endl; else cout<<-1<<endl; }else if(a>b){ if(a-b>=x) cout<<1<<endl; else if(r-a>=x||b-l>=x) cout<<2<<endl; else if(a-l>=x&&r-l>=x&&r-b>=x||r-a>=x&&r-l>=x&&b-l>=x) cout<<3<<endl; else cout<<-1<<endl; }else{ cout<<0<<endl; } }
D题:大意是给出商品的价格n和最大倍数m。求将价格乘以多少倍,可以使其后缀0最多,如果存在多个输出数值最大的那个。
一个数学规律,如果想要相乘产生0,跟存在的5的倍数和2的倍数有关。可以先去遍历5的倍数再去遍历2的倍数。剩下的直接令这个数乘以10产生0。
只要保证在m的范围内即可。
code:
void solve() { ll n,m; cin>>n>>m; ll tn = n; ll k = 1; while(tn%10==0) tn/=10; while(tn%5==0&&k<=m){ tn/=5; k*=2; } while(tn%2==0&&k<=m){ kn/=2; k*=5; } while(k*10<=m) k*=10; ll ans = k*n; cout<<ans<<endl; }
E题:很不错的一道题。大意是给出n个人的能量,给出恶魔的能量。如果恶魔的能量大于某个人,他可以吸收他的能量的一半。它有两次机会使得能量*2,还有一次机会使得能量*3。求最多可以吸收多少人的能量。
解决方法:首先,我们易知,如果我们想最优策略使得答案最优,需要先吸收能量少的人,这样自身的能量多,翻倍时才有可能产生更大的能量。
那么现在还面临着一个问题就是,先吸收2还是先吸收3,吸收2可以不浪费3。但是某种程度上讲,吸收3可以使得之后有更多的机会去吸收能量。
这个数值比较小,显然(虽然我没有看出来┭┮﹏┭┮)我们可以直接爆搜,我们也可以直接全排列。
整个程序的复杂度不过n*6的大小。
code:
void solve() { ll n,h; cin>>n>>h; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); vector<ll> ve={2,2,3}; ll c1 = 2,c2 = 1; ll ans = 0; do{ ll th = h; ll p = 0; ll cnt=0; for(int i=1;i<=n;i++,cnt++){ if(h>a[i]) th+=a[i]/2; else{ while(th<=a[i]&&p<3) th*=ve[p],p++; if(th<=a[i]){ break; }else{ th+=a[i]/2; } } } ans = max(ans,cnt); }while(next_permutation(ve.begin(),ve.end())); cout<<ans<<endl; }