Codeforces Round #579 (Div. 3)Codeforces Round #579 (Div. 3)

59 阅读 0 评论 39 点赞

我是靠谱客的博主清爽紫菜，最近开发中收集的这篇文章主要介绍Codeforces Round #579 (Div. 3)Codeforces Round #579 (Div. 3)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Codeforces Round #579 (Div. 3)

A
顺时针、逆时针模拟即可。

B
先用一个桶计数，如果某个长度的边的数量是奇数，显然NO，那么在都是偶数的情况下，把4n个点变成2n个点后塞入一个vector内，排序后显然第一项和最后一项的乘积才有可能是这些矩阵的共同面积，那么暴力匹配搜索即可。

C
求一串数的公约数的个数。线筛+求gcd(a1, a1, …, an)的所有因子的个数即可。
值得一提，我用的线筛板子是把prime[0]作为计数器，是素数的确切个数！而不是平常惯用的尾后指针！

E
~~我的代码是在是丑陋十足…虽然最后是AC了但是还是不要多嘴了~~
学习一下rank1的E题代码：设置last变量记录体重的最远距离。将数组排升序后遍历：

int last=0,ans=0;
for(int x:a){
if(x-1>last){
++ans;
last=x-1;
}else if(x-1==last){
++ans;
last=x;
}else if(x==last){
++ans;
last=x+1;
}
}

D1
数据范围200，三重循环爆搜即可。

D2
~~我觉得挺难想的…我不太会做…~~
题解的办法是：构造一个rg数组，rg[i]表示使得字符串t[i; |t|]是字符串s[x; |s|]的子串的最大的x的值。这样子预处理之后，我们从前往后遍历s数组，同时用pos记录当前可以跟t数组匹配的长度，每一次遍历的时候先考虑将i到后面某一个位置删去，可以发现，能删的最远点就是目前的rg[pos] - 1，那么距离就是rg[pos] - i（当然了，如果pos == d2，那么就可以删到d1 - 1了）；再用if语句比较后不断更新pos的位置。

F1
晚上做的时候觉得是一个很朴素的贪心，大概写了写后wa掉了…当时把change按照降序排好后一个个取，但是这样子其实是不对的，比如test1: (r = 10)8,-1; 10, -2就直接把我卡死了。
题解的办法是，对于change严格大于0的情况，就按照require不减的顺序排这些任务，挨个完成即可；对于change小于0的情况，我们先预处理一下ai < -bi的情况，令ai = max(ai, -bi)（这样子的合理性是显然的），之后我们对ai + bi按照不增的顺序排序。在这种状况下我们说，ai + bi是完成当前任务后具有的最小的rank，我们想要让这个最小rank尽可能的大，那么之后显然有更多的任务可以被完成，所以这是一种最优的策略。

F2
pos的情况与F1一样，先用pos得到最大的r之后，再用背包的思想处理neg的情况。
但是。
为什么这道题的“01背包”必须要按照ai + bi排好序之后才能开始遍历…
我前前后后大概wa了10发还是不得其解。。罢了罢了。