Codeforces Round 347(Div.2)[cf#664]

前两天病了所以看起来有一段时间没更新了=。=

英文题面戳[这里]喵~

A题:Complicated GCD

给定两个数a, b求[a,b]这一段闭区间中所有数的最大公约数。

输入一行为两个数a, b \(1 \le a \le b \le {10^{100}}\)

输出一行为这些数的最大公约数。


一看1e100的数据范围吓了我一大跳,后来一看……

10行以内代码就能搞定。

只要判断一下这两个数相不相等就行了,相等就输出它本身,不相等输出1。

时间复杂度O(loga+logb), 空间复杂度O(loga+logb);

以下是代码(真的需要代码么)

B题:Rebus

给定一个形如? + ? - ? + ? + ? = n形式的表达式(也就是等号左边由一些个?用+号和-号连接组成,右边由一个数n组成的等式)。求一个方案把所有?填上1~n的正整数使得等式成立。

输入一行为原表达式 \((0 < n \le {10^6})\) ,并且总问号数不超过100,保证第一个问号前无任何符号。

输出第一行如果有这样的方案为"Possible",没有就是"Impossible"

第二行如果有这个方案的话输出这个方案,要求与输入格式一致。


我的做法是读入的时候不管问号,只统计加号和减号的数量(记为pn和mn,注意加号个数初始值为1,因为第一个数是正的),这样题目就是要让pn个绝对值不超过n的正数和mn个绝对值不超过n的负数之和等于n。

显然有这样一个方案的充分必要条件是 \(pn - mn*n \le n \le pn*n - mn\) ,因此我们可以很快的判断是否有方案。

接下来只要输出方案就可以了。我的做法是二分判断负数的总和,找到任一个满足条件的负数总和(同时也就求出了正数总和),然后暴力填数就可以了,代码中是填了可行的最大的数。

时间复杂度O(logn+q),空间复杂度O(q)

代码部分

[更新1.0.1]C题:International Olympiad

“国际缩写奥赛”(简称IAO)是一场奇怪的比赛=。=,他从1989年开始,每一年的比赛都有一个IAO'y形式缩写,其中y是那一年的一个后缀,并且是没被使用过的后缀中最短的一个。例如前三年(1989,1990,1991)的缩写分别是IAO'9, IAO‘0, IAO’1。2015年的缩写是IAO'15(因为5已经在1995年用过了)。

输入第一行为n,表示接下来有n组数据 \((1 \le n \le 1000)\) ,接下来每行分别是一个IAO'y形式的缩写(保证y不超过9位)。

对于每组数据,输出一行一个整数,表示那一年是多少。


我觉得这是一道乱搞题=。=反正乱搞一下就过了。我的做法是这样的。对于一个缩写i设dp(i)为i的答案,那么dp(i)就等于大于dp(i去掉最高位)的最小的具有后缀为i的年份(描述起来好费劲QAQ,希望能看懂)。然后就可以递归解决啦~显然递归层数不会超过9。

时间复杂度O(n),空间复杂度O(1)。

代码部分:

[更新1.0.3(?)]D题:Graph Coloring

(上周的坑补上=。=)

现在有个n个点m条边的无向图,每条边都有一个颜色(不是红色就是蓝色),现在可以进行这样一个操作,就是选择一个点并把连接这个点的所有边颜色反转(红色变成蓝色,蓝色变成红色),要求进行最少的操作使所有边的颜色相同。

输入第一行两个整数 \((1 \le n, m \le {10^5})\) ,代表点数和边数。

接下来的m行每行两个整数和一个字符,分别代表第i条边的两个端点和它的颜色(红色是R,蓝色是B)

输出第一行为一个整数,代表最少的操作次数。

接下来的一行为一个合法的操作序列。


首先我们发现两个问题,第一个问题是操作的顺序对于我们的答案并没有影响,第二个是对于一个点我们进行两次操作和没进行操作效果是一样的,因此这就变成了一个2-SAT问题,对于一个点如果对他进行操作这个点的值就为true,否则为false。假设我们现在要把所有边染成红色(待会对于蓝色我们可以在操作一遍),那么如果两个点之间连了一条红色边,则表示a xor b = false,如果是蓝色边,则表示a xor b = true;这样就可以O(n)的解决了。

然而还有一个小问题(看了官方题解仍不明白),就是要求操作最少(即取值为true的点数最少),然而我的2SAT算法并不能保证这一点(他只能保证一个合法解),于是欢迎会的神犇留言~

以下是我的WA代码=。=

注意以下代码是WA的!

[更新1.0.2]E题:To Hack or not to Hack

这个题面看起来相当复杂。

假设你现在正在进行一场cf常规比赛,这一场比赛只有3道题,并且你知道一个几乎就是最终结果的得分板。为什么说是“几乎”呢,因为现在你还可以进行一些操作(然而别人并不能),你可以hack一些人的代码(你知道谁的代码可以hack而且你的hack必定会成功)。对于每个人每道题他的分数是这样确定的(注意这个和常规cf比赛并不一样):

假设一共n个人参加了比赛,其中有k个人AC这道题,那么这道题的基础分数

\[s = \left\{ \begin{array}{l}500(n < 2k \le 2n)\\1000(n < 4k \le 2n)\\1500(n < 8k \le 2n)\\2000(n < 16k \le 2n)\\2500(n < 32k \le 2n)\\3000(32k \le n)\end{array} \right.\]

一个人要是没有AC这道题(或者被hack了),那么他得0分,如果在t时刻AC了这道题,那么他的得分为 \(\frac{{s(250 - t)}}{{250}}\)

每个人的总分等于3道题的得分总和加上hack数乘以100(只有你能hack)。

每个人的排名等于总分严格大于该人总分的人数+1。

输入第一行为一个整数n \((1 \le n \le 5000)\) ,为参赛者总数(你是1号参赛者)。

接下来n行每行3个整数 \({a_i},{b_i},{c_i}(\left| {{a_i},{b_i},{c_i}} \right| \le 120)\) ,每个整数的绝对值代表该选手AC该题的时刻,如果该整数为正,代表你不能hack他,如果该整数为负,代表你可以hack他,如果该整数为0,代表他没有AC这道题。

输出一行一个整数,代表你的最好名次。

(注意不是单纯的hack越多越好,因为题目的总分会随着你的hack而改变,具体见样例1)


参考了一下官方题解=。=[我是传送门]因此并没有代码。

首先呢,我们需要发现一个问题,就是每个人的得分不会超出9000分,因此无论如何只要你hack了90次或以上就可以保证你取得第一名,这样我们的n就可以直接缩小到90了(这一点相当重要)。

对于每道题的基础分数是多少,我们可以 \(O({6^3})\) 暴力一下,这样我们就能得到最多能hack多少次,然后就能直接求出总分。

我们的目标只是总分比我们hack后的总分还高的人,需要通过hack他们使他们的得分低于我们,这可以dp来解决。

设dp[p][i][j][k]表示排名前p的人中我们通过hackA题i次,B题j次,C题k次后能使总分低于我们的最大人数。

那么对于每一个状态,我们 \(O({2^3})\) 枚举一下hack哪几道题,并更新他的后继状态(假设我们hackA题和C题)

\[dp[p + 1][i + 1][j][k + 1] = \max (dp[p + 1][i + 1][j][k + 1],dp[p][i][j][k] + 1)\]

就可以解决这道题啦。

时间复杂度O(谜),空间复杂度 \(O(n + n{'^4})(n' < 90)\)

(事实上时间复杂度应该是 \(O(n + n'abc*{2^3}*{6^3})\) ,其中a,b,c分别是该题可以hack的数量,然而这个时间复杂度最大是113374080000根本跑不完,但事实上常数相当小并且可以通过一些剪枝之类的(比如算到第1名就直接结束程序),使得我们的算法可以在1秒内跑完)

发表评论