一个人能建设一个公司网站吗,贵州省住房和城乡建设厅电话,网站的后台怎么做调查问卷,python 搭建wordpressCodeforces Round#853 div2 A-C
等了很久终于迎来了一场cf比赛#xff0c;白天出去玩了一圈#xff0c;晚上回来打比赛#xff0c;这次只出了A,B题。C题思路很巧妙#xff0c;赛时没做出来#xff0c;看了大佬学习到了#xff0c;还是很不错。
A.Serval and Mocha’s A…Codeforces Round#853 div2 A-C
等了很久终于迎来了一场cf比赛白天出去玩了一圈晚上回来打比赛这次只出了A,B题。C题思路很巧妙赛时没做出来看了大佬学习到了还是很不错。
A.Serval and Mocha’s Array 签到 题意这个题题目有点绕看了十分钟才明白意思就是给你一个数组判断能否重新排列数组使得数组前两项的最大公约数是否小于等于2。 思路数据范围小直接暴力枚举判断即可。
void Showball(){int n;cinn;vectorint a(n);for(int i0;in;i) cina[i];int ok0;for(int i0;in;i){for(int ji1;jn;j){int ggcd(a[i],a[j]);if(g2) {ok1;break;}}}if(ok) coutYESendl;else coutNOendl;
}B. Serval and Inversion Magic 题意给你一个只含0和1的字符串给你一个操作可以将区间[L,R]之间的字符0变成1,1变成0。问你能否通过一次操作将字符串变成回文串。 思路:因为我们只能够操作一段连续的区间。我们可以对比回文串对应的字符s[i]s[i]s[i]和s[n−i−1]s[n-i-1]s[n−i−1]如果出现不相同又相同又不相同的情况那么两端区间都需要操作但是不连续那么我们无法满足题意。所以进行标记判断这种情况即可。
void Showball(){string s,t;int n;cinn;cins;if(st) {coutYESendl;return;}int ok1;bool f1false,f2false;for(int i0;in/2;i){if(s[i]!s[n-i-1]) f1true;if(f1s[i]s[n-i-1]) f2true;if(f2s[i]!s[n-i-1]) {ok0;break;}}if(ok) coutYESendl;else coutNOendl;
}C. Serval and Toxel’s Arrays 思维 题意:给你一个数组AiA_iAi,并且进行m次操作每次操作都会将上一个数组中的第p个元素修改为v。得到新的数组。然后我们需要统计 所有AiA_iAi和AjA_jAj数组之间不同元素个数之和。 思路如果我们直接进行模拟在暴力计算无疑会超时。那么遇到这种题目我们就需要算贡献算贡献是一种计数类问题的经典套路。对于本题我们可以算出每个数对答案的贡献我们知道一共会有m1m1m1个数组对于数xxx,我们假设它在这m1m1m1个数组中出现的次数为cnt那么就可以分为两种情况第一种情况计算的两个数组中都含x那么x对答案的贡献是1这种情况一共有Ccnt2cnt∗(cnt−1)/2C_{cnt}^2cnt*(cnt-1)/2Ccnt2cnt∗(cnt−1)/2种情况对于计算的两个数组一个含x另外一个不含x那么他的贡献也是1这种情况一种有cnt∗(m−cnt1)cnt*(m-cnt1)cnt∗(m−cnt1)种对于计算的两个数组都不含x的情况那么x没有贡献则不用计算。 所以我们现在就只需要计算出每个数在所有数组中出现的次数以及在每次操作时维护好这个次数即可。 我们可以开一个map去记录每个数出现的次数一个比较好的思路就是一开始我们假定后面每个数都没有改变那么每个数出现的次数都是m1m1m1次那么在第i次操作时将a[p]a[p]a[p]变为了vvv那么a[p]a[p]a[p]的次数就会减少减少了多少呢很明显在这次操作之后的数组中都暂时不在含有a[p]a[p]a[p]也就是m−i1m-i1m−i1个。所以mp[a[p]]−(m−i1)mp[a[p]]-(m-i1)mp[a[p]]−(m−i1),同理vvv这个数出现的次数自然就暂时增加了这么多。 最后带入公式计算即可注意开long long。
void Showball(){int n,m;cinnm;vectorint a(n);mapint,LL mp;for(auto it:a){cinit;mp[it]m1ll;}for(int i1;im;i){int p,v;cinpv;mp[a[--p]]-m-i1;mp[v]m-i1;a[p]v;}LL ans0;for(auto [k,v]:mp){ansv*(v-1)/2ll(m-v1)*v;}coutansendl;
}
