codeforces round #626 题解

久违的更新……这次题难度差别好大喔

A. Even Subset Sum Problem

如果有一个偶数或两个奇数,输出即可

B. Count Subrectangles

讲个笑话,有人说“你的码风和黄学长好像”,我一时不知道Ta在夸我还是在骂黄学长(bushi
要是说代码结构好,其实我也有点羞耻,因为是vscode自动排版的……
比如这题,我用来存放连续块长度的数组名叫qwq,他吐槽我变量名太随心所欲……哎

首先分别预处理出长和宽所有的连续长度,升序排序后存放于qwq数组。
然后求出qwq数组的后缀和,放到hzh数组。
枚举面积k的所有可能长和宽,即l和r。只需要枚举l到sqrt(k)就可以了,特判一下l==r的情形。
答案=纵向能放下l的位置的数目*横向能放下r的位置的数目。
以纵向为例:假如有一块连续长度为100,现在放一个长为50的块,能放的位置数目=100-50+1=51个。
所以如果有一块长度为x,放一个l,能放下的数目为:x-l+1。
通过后缀和可以求出所有大于等于l的块长度,求和之后可以得到,总共能放下的数目:后缀和-后缀数目*(l-1)。
所以在代码中有:count = hzh[first] – (cnt – first + 1) * (l – 1);
遂得到答案:count1*count2

C. Unusual Competitions

C比B简单多了……
策略很简单,比如))((())(,要做的是把前四个变成(()),把后两个变成()
贪心就可以:当遇到多余的),说明当前位置是本次修改的左端点。而右端点必须满足该区间内的(的数量等于),又因为要求最小,所以找到第一个'(‘和’)’数目相等的位置,即为区间右端点。
写法:遇到'(‘将计数器cnt+1,遇到’)’将计数器cnt-1。如果本次修改使得cnt从0变成<0,那么说明这里是区间的起点,记录。如果本次修改使得cnt从<0变成0,说明这里是区间的终点,将答案加上区间长度即可。 判断-1:如果最终cnt!=0则不可能。

D. Present

->


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注