AtCoder Beginner Contest 475

碎碎语真的真的好久没打过atcoder了自从自己去考研到现在上岸不知不觉间已经接近一整年没打过算法比赛了这次突然下定决定打atcoder是想看看自己这么久没打了自己到底有多菜。os:其实是发现自己的老队友在本科毕业上班后仍然保持着代码竞赛的训练心生羡慕于是便开始了从零开始的atcoder生活这次真的是新号新的开始希望自己可以在研一这么多课的情况下坚持下来吧A.mnclr水题一道不过长时间不学英语看这题面还真有点难受呢。本题本质上就是在除了最后的字母之外都在后面添加o即可#includebits/stdc.husingnamespacestd;intmain(){string s,ans;cins;intnums.size();for(inti0;inum;i){if(i!0)couto;couts[i];}return0;}B.Change水题一道但是这题干写的真的不够清楚我刚开始读完题干以为是每次剩下来的钱下次购物也能继续去花我甚至在想以什么样的顺序去支付才能达到最少的零钱数量不过有一说一我自己脑补修改后的题感觉确实挺好的本题本质上就是每次购物前我都有无数张面额为1000的日元货币统计每次购物后我的零钱总数量简单统计一下就可以。#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];a[i]%1000;}intnum10,num20,num30;for(inti0;in;i){if(a[i]0)continue;intnow1000-a[i];num1num1now/100;num2num2(now%100)/10;num3num3now%10;}coutnum3 num2 num1endl;return0;}C.Walk the Line可能是我长时间没做题的缘故我现在已经大胆到N8000我也敢直接dfs搜索所有情况了O(2^N)我真乃神人也后面比赛结束的时候我突然就悟道了这个题的数据可以直接O(N*N) 那不直接就是枚举我们以S为起点最左边可以到到L最右边可以到达R然后求解在不超过总代价cost的情况下[L,R]之间最多有多少个点的问题嘛又因为我们的村子都是在一条直线上面所以我们计算从S出发经历过LR之间所有点的代价就是1.S-》L-》R 2。 S-》R-》L这两种情况.也就是我们的代价cost L-R minS-R, L-S后面又简单思考了一下其实没必要直接O(N*N)的毕竟第二次我们的N只需要找到第一个代价比M高的村子就行而且我们从S出发到右边村子的距离是不断变大的符合单调性所以我们的右端点可以直接二分因此我们的代码可以优化到O(NlogN)后面我又问了一下 GPT发现甚至还能把 O(Nlog N) 优化成 O(N)仔细想一下其实我们在枚举左端点 (L) 的时候每次都重新二分右端点 ® 是有点浪费的。假设当前区间是 ([L,R])从起点 (S) 出发访问完整个区间的最小代价为[cost dist(L,R)min((dist(S,L),dist(S,R))]现在我们把左端点从 (L) 向右移动到 (L1)。此时 (S) 到左端点的距离一定会变小而 (S) 到右端点 ® 的距离没有发生变化因此访问 [L1,R])的代价只可能变小不可能变大。也就是说如果 ([L,R]) 是合法的那么 ([L1,R]) 一定也是合法的。因此当我们枚举到下一个左端点时右端点根本没必要重新从 (S) 开始找更不需要重新二分。之前能够到达的 ® 一定仍然能够到达我们只需要尝试继续把 ® 向右扩展即可。于是两个端点都只会单调地向右移动L → → → → S R → → → → N每个左端点 (L) 最多移动 (N) 次而右端点 ® 在整个过程中也最多移动 (N) 次不会出现回退因此总复杂度就从[O(Nlog N)]进一步优化到了[O(N)]最开始枚举左右端点后来发现固定左端点后代价关于右端点具有单调性所以可以二分再进一步发现随着左端点不断右移最大的合法右端点本身也是单调不减的于是连二分都可以省掉直接用双指针维护即可。算法这东西真的是学无止境有时候 AC 只是第一步继续想一想“这个状态有没有单调性”“这个指针有没有必要回退”可能还能把复杂度再降一个档次。#includebits/stdc.husingnamespacestd;#definelllonglongconstintN1e45;// O(n^2) solutionintmain(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n,S,L,ans1;cinnSL;vectorlla(n1),qa(n1,0);for(inti2;in;i){cina[i];qa[i]qa[i-1]a[i];}for(ll i1;iS;i){for(ll jS;jn;j){ll xqa[S]-qa[i];ll yqa[j]-qa[S];ll sumxymin(x,y);if(sumL)ansmax(ans,j-i1);}}coutansendl;return0;}#includebits/stdc.husingnamespacestd;#definelllonglongconstintN1e45;// O(nlogn) solutionintmain(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n,S,L,ans1;cinnSL;vectorlla(n1),qa(n1,0);for(inti2;in;i){cina[i];qa[i]qa[i-1]a[i];}for(ll i1;iS;i){ll costLqa[S]-qa[i];if(costLL)continue;ll lS,rn,mid0,res1;while(lr){mid(lr)/2;ll costRqa[mid]-qa[S];ll sumcostLcostRmin(costL,costR);if(sumL){resmax(res,mid-i1);lmid1;}elsermid-1;}ansmax(ans,res);}coutansendl;return0;}#includebits/stdc.husingnamespacestd;#definelllonglongconstintN1e45;// O(n) solutionintmain(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n,S,L,ans1;cinnSL;vectorlla(n1),qa(n2,0);for(inti2;in;i){cina[i];qa[i]qa[i-1]a[i];}ll jS;for(ll i1;iS;i){ll costLqa[S]-qa[i];ll costRqa[j]-qa[S];ll sumcostLcostRmin(costL,costR);if(sumL)continue;while(jncostLqa[j]-qa[S]min(costL,qa[j]-qa[S])L)j;ansmax(ans,j-i);}coutansendl;return0;}D. Alphametic Prime题目本意是给你一个字符串长度不大于7然后让你把这个字符串转换成一串数字数字的要求是相同字母对应 的数字要保持一致并且我们最后的数字必须得是素数其实这个题关键的部分就是字符串的长度不大于7因此即使我们枚举所有字母对应数字的可能性也仅仅只有 10987654也就1e6左右的复杂度即使算上我们的判断素数我估计也就是1e7左右的复杂度完全可行因此这个题在我看来就是在10个数中选着若干个数然后把这几个数代替到我们的字符串中其中不要忘记判断素数这个判断素数我还是用的埃氏筛其实是忘记可以直接判断素数然后选到答案就可以直接跳出了甚至这样也能够过所以这题时间很宽松。#includebits/stdc.husingnamespacestd;constintN1e710;string str,s;intnum,ans;boolst[10],prime[N];mapchar,intmp;voidisprime(){prime[0]true;prime[1]true;for(inti2;iN;i)if(!prime[i])for(intjii;jN;ji)prime[j]true;}voiddfs(intpos){if(posnum){intans0;if(mp[str[0]]0)return;for(autox:str)ansans*10mp[x];if(!prime[ans]){coutansendl;exit(0);}return;}for(inti0;i10;i){if(st[i])continue;st[i]true;mp[s[pos]]i;dfs(pos1);mp[s[pos]]-1;st[i]false;}}intmain(){isprime();cinstr;setcharkind;for(autox:str)kind.insert(x);numkind.size();for(autox:kind)sx,mp[x]-1;dfs(0);cout-1endl;return0;}