Codeforces Round #603


A – Sweet Problem

题意

有三种颜色的糖果,分别 \(r,b,g\) 颗,要求每天必须吃两颗不同颜色的糖,求最多吃多少天。

分析

我们不妨假设 \(r\le b\le g\)

  • 如果 \(r+b>g\) 一定存在一种方案可以吃完他们(如果是偶数的话,奇数必定有一颗剩下)
  • 如果 \(r+b<g\) 一定是 \(r,b\) 尽可能和 \(g\) 搭配,所以能够吃 \(r+b\) 天

B – PIN Codes

题意

给出 \(n\) 个长度为 \(4\) 的字符串,要求修改最少的次数,使得每个字符串都不同。

分析

首先,最小的修改次数一定是所有相同数的每一类数量 \(-1\) 的总和。

因为,对于相同的一类,如果有 \(n\) 个数,至少需要修改 \(n-1\) 个数。

因为最多只有 \(10\) 个字符串,所以无论怎么改都不大会冲突。

于是就可以暴力的改,枚举每一位修改成 \(0,1,2,\cdots 9\) 以后这样的数是否存在,一定修改到不存在的数,停止即可,这样每个数最多只会修改一位。

总的复杂度是 \(O(40Tn)\) ,而显然是跑不满的。

C – Everyone is a Winner!

题意

给定 \(n\) ,对于任意的正整数 \(k\) ,求 \(\left \lfloor \frac{n}{k} \right \rfloor\) 有多少不同的取值。

分析

题目要求输出了,显然不会很多。

于是就直接枚举了。枚举 \(k\) ,考虑每次都要让 \(k\) 变化成 \(\left \lfloor \frac{n}{k} \right \rfloor\) 下一个取值的位置。

假设 \(\left \lfloor \frac{n}{k} \right \rfloor =x\) ,显然对于结果为 \(x\) 的最大的 \(k\) 取值为 \(\left \lfloor \frac{n}{x}  \right \rfloor\) ,于是让 \(k\) 每次变成 \(\left \lfloor \frac{n}{x}  \right \rfloor+1\) 即可。

D – Secret Passwords

题意

两个字符串是等价的,一定从下面两条规则得到:

  • 一个字母同时属于两个字符串;
  • 如果 \(A,B\) 等价而且 \(B,C\) 等价,那么 \(A,C\) 等价。

分析

对于每个字符串中有的字母,将当前字符串的编号加入那个字母的集合。

对于同一个字母集合中的所有编号之间连边。

很显然答案就是联通块的数量。

直接用并查集维护即可。

E – Editor

题意

要求支持光标的移动和插入小写字母/括号,动态的输出每一次修改以后括号是否匹配,如果匹配的话,嵌套最多次数的括号对数。

分析

可以把 ( 看作 \(1\) ,把 ) 看作 \(-1\) ,显然一个括号序列匹配需要满足下面的要求:

  • 最小前缀和 \(\ge 0\) ,即不存在前缀 ) 多于 ( 的情况;
  • 整个的和 \(=0\) ,即左括号与右括号数量相等。

那么嵌套的最深层数,很显然就是最大的前缀和。

于是我们用线段树维护每一个位置的前缀和,然后每次修改都相当于是一次后缀区间的修改。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 16,270

Categories

Archive

Comments