Codeforces 573C Bear and Drawing

题意

你要在两条平行直线之间画一棵有n个节点的树,树必须是可平面的(意思就是不能有两条链发生相交的情况)。给出你若干个连边(他们已经组成一棵树),问你是否可能画出符合要求的树。

思路

通过小数据找规律,可以要想把一棵树的安排在两条平行直线上,这棵树需要满足以下几个条件:

  • 首先我们在树上找到一条主链
  • 凡是在主链上的点,它的度数没有限制
  • 与主链直接相连的点,它的度数最大为3
  • 剩下的点,度数最大为2

知道了这些,接下来就是实现的问题了。这里有一种很聪明的实现方法。

  • 首先,统计所有节点的度数。
  • 在每一个叶子节点都发动一次DFS,在DFS过程中若遇到的一切度数小于等于2的点,进入,并做删除标记,否则返回。这一步的目的是清除掉所有叶子节点所属的链(不能直接修改度数,否则会导致删掉整棵树)。
  • 重新统计每个节点的度数,因为刚才只是做标记,没有改变度数。
  • 接下来对于所有曾经为3度现在为1度的点打删除标记,这种点是与主链直接相连的点。
  • 重新统计每个点的度数。
  • 现在每个节点的度数都理应小于3了,因为我们刚才去掉了叶子节点所在的链,如果这棵树正确,一定会删到主链上。接下来又去掉了曾经3度删完1度的节点,这相当于完全去掉了支链。这个时候整棵树理应只剩一条链了,不可能再有度数大于2的节点了。

如果理解有困难,不妨尝试画图帮助理解。

代码

 

CodeForces 236A Boy or Girl

题意

判断字符串长度是奇数还是偶数。

思路

代码

 

Codeforces 589A Email Aliases

题意

给出了一堆电子邮件地址,要你按照一定的规则分类,然后一类一类地输出。

思路

模拟。

只要正确地理解了题意基本不会有问题,在实现方面,可以考虑使用map的迭代器轻松地完成分类操作,令map的key为邮件地址的Hash(其实就是按照题目规则把等价但不同的邮件地址处理成同一个字符串),value为set<string>用来当作不同形态的邮件地址的容器。

代码

 

Codeforces 515B Drazil and His Happy Friends

题意

Translated by paryerhgq

Drazil有很多朋友,他们中有些人是快乐的,有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是,他发明了以下的计划。
在他的朋友中,有n个男孩和m个女孩。我们把男孩从0到n-1编号,女孩从0到m-1编号。在第i天,Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭(注意i从0开始)。如果两个人之中有一个是快乐的,那么另外一个也会变得快乐,否则,这两个人的心情状态不会改变。一个人一旦成为快乐的人(或者他原本就是快乐的),他能保持永远快乐。
Drazil想知道他是否可以使用该计划,使得他所有的朋友都变得快乐。

思路

注意到问题规模比较小,所以我们直接模拟就好了但是我们要至少操作2*nm次才可以。

有一种不暴力的解法,我们发现我们最后能够变快乐的人的编号x一定满足x = a (mod gcd(boy,girl)),其中boy是男生人数,girl是女生人数,a是某个一开始就快乐的人的编号,这样我们只要扫一遍所有快乐的人,在模gcd(boy,girl)的完全剩余系里标记一下就搞定了。

代码

暴力:

数学:

 

CodeForces 583A Asphalting Roads

题意

修路,一次选定一个横排一个竖排,如果横排竖排都没修,就把横排和竖排都修好,否则不用管。给出你若干修路尝试,问你哪些尝试最终执行了。

思路

照着题意简单模拟一下就好了。

代码

 

Codeforces 461B Appleman and Tree

题意

给你一颗树,上面有黑色节点,也有白色节点,现在你要做的事情是,在这棵树上选出几条边,去掉,这样的话这棵树就会变成好多小树,这些小树一定要含且只含一个黑色点。问你有多少种不同的方法删边来满足要求。

思路

树形DP。往DP方面去想是因为原始的大问题可以进行剖分,即如果我们想要知道将整棵树按要求切割的方案个数,我们可以去考虑它的子树按要求切割的方案个数,对于子树也是同样地进行剖分。确定了将问题剖分的方向之后,就是确定状态了。

我们发现,要想从一颗树的子树的分割情况得到整棵树的分割情况,我们不仅要知道子树符合要求的分割情况,也要知道子树不符合要求的分割情况,这样才能覆盖全部情况。因此我们设定状态为dp[a][0/1],其中dp[a][0]存值为将以a为根节点的子树进行分割,而且与当前的子树根节点相连的节点中没有黑色节点方法个数;dp[a][1]存值为将以a为根节点的子树进行分割,而且与当前的子树根节点相连的节点中有且仅有一个黑色节点方法个数。

这里一定要清楚,0/1表示的是与根节点联通的节点中是不是有黑色的节点,已经断开的地方,我们不用关心。

接下来讨论状态的转移:

  • 如果当前节点已经是叶子节点,节点编号是a
    • 如果是黑色节点:
      • dp[a][0] = 0 因为黑色节点为根部的子树不可能不含有黑色节点。
      • dp[a][1] = 1 因为只有黑色节点一个点,只有一种分割方式就是把节点自己当作一颗树。
    • 如果是白色节点:
      • dp[a][0] = 1 因为白色叶子节点的子树中只有他自己一个白色节点,不可能含有黑色节点了,分割方式也只有一种就是把自己当成子树。
      • dp[a][1] = 0 因为白色叶子节点的子树中不可能含有黑色节点。
  • 如果当前节点不是叶子节点,节点编号是a,它的孩子节点们的编号为b_{i}:
    • 如果是白色节点:
      •  dp[a][0] = \prod( dp[b_{i}][0]+dp[b_{i}][1]),我们逐一检查每一个孩子节点,我们想得到的结果是当前节点直接相连的联通块里面不存在黑色节点,那么:
        • 如果当前检查的孩子节点是黑色的,我们考虑切开还是不切开同这个孩子节点连接的边:
          • 不切开的话,要求连接的孩子部分一定不可以有黑色节点,这显然是不可能的,不过黑色节点的dp[a][0] = 0始终是0,所以没关系。
          • 切开的话,就要求切开之后的孩子部分自己可以满足要求,这样的话有dp[b_{i}][1]种方法。
        • 如果当前检查的孩子节点是白色的,我们考虑切开/不切开同孩子连接的边:
          • 切开的话,孩子部分自己要满足要求,这样的话有dp[b_{i}][1]种方法。
          • 不切开的话,孩子部分与根节点直接相连的部分一定不可以包含黑色节点,这样的话有dp[b_{i}][0]种方法。
      •  dp[a][1] =dp[a][1]*(dp[b_{i}][0]+dp[b_{i}][1])+dp[a][0]*dp[b_{i}][1] ,这个方程的计算必须和上面的dp[a][0]同步进行。这个有一点不好懂,其实可以这么想:
        • dp[a][1]*(dp[b_{i}][0]+dp[b_{i}][1]) 这一部分,我们要想的过程是将一个已经连接好了黑点的根部,讨论是不是要和当前的孩子相连的过程:
        • 如果当前检查的节点是黑色节点,我们还是考虑切开/不切开:
          • 不切开的话不满足要求,不过黑色节点的dp[a][0] = 0始终是0,所以没关系。
          • 切开的话,连接上去的孩子部分一定要满足要求,有且只有一个黑点,所以有dp[b_{i}][1]种方法。
        • 如果当前检查的是白色节点,切开/不切开:
          • 不切开的话,还是不满足要求,但是如果这个时候在根节点上已经有带黑点的联通块连上去了,这个时候只要令连接上去的部分没有黑点就可以了,所以有dp[b_{i}][0]种方法。
          • 切开的话,孩子部分要自己保持成立,有且只有一个黑点,所以有dp[b_{i}][1]种方法。
        • dp[a][0]*dp[b_{i}][1] 这一部分,想法是当前依然不成立的根部,和带有一个黑点的孩子部分连接。
    • 如果是黑色节点:
      • dp[a][0] = 0 因为黑色节点为根部的子树不可能不含有黑色节点
      • dp[a][1] = \prod (dp[b_{i}][0]+dp[b_{i}][1]) 我们逐一检查每一个孩子节点,既然我们想得到的结果是当前节点直接相连的联通块里面只有一个黑色节点,那么:
        • 如果当前检查的孩子节点是黑色的,我们考虑切开还是不切开同这个孩子节点连接的边:
          • 切开的话,没有问题,因为当前考虑的子树的根节点已经是黑的了,而且还要让让切开之后切出来的孩子的那一部分保持成立,要想做到这一点的话有dp[b_{i}][1]种方法。
          • 不切开的话,显然是不行的,因为这样就有了两个黑色节点,不过黑色节点的dp[a][0] = 0始终是0,所以加进去也没关系。
        • 如果当前检查的孩子节点是白色的,我们考虑切开/不切开同孩子连接的边:
          • 切开的话,还要保证切除的孩子部分也成立,因此孩子部分有dp[b_{i}][1]种方法。
          • 不切开的话,因为当前节点是黑色的,链接孩子节点之后,连接上的部分不可以含有黑色节点,孩子节点能做到这样的方法有dp[b_{i}][0]种。

写了一堆废话其实就是为了理清思路,思维能力太弱只能这样了。DP的思路搞定之后,具体的操作就非常简单,利用DFS深入叶子,在返回的过程中进行对孩子的考察和对自身的更新,最后在根节点上读取答案。

代码

 

CodeForces 484B Maximum Value

题意

给你一串数,让你找出一组(i,j),使得在保证第i项大于等于第j项的同时,第i项mod第j项最大,求这个最大值。

思路

要有一种转换的思维,余数最大的话,可以另一个方向进行考虑,a%b=c的话,a可以看成是kb+c,这个里面b,c是已知的,这个k可以枚举,这样就把求余数这个事情转换成了枚举/搜索,换一个思路问题可能就突破了。

对给出的数列sort一下,unique一下,erase一下,这样就有效的避免了重复数据的干扰(如果你不unique可能会被这个题的某组坑数据给弄T),而且sort完才能做。sort好之后,我们挨个数枚举,对于每个数k,我们考虑这个数列上0~k,k~2k,2k~3k,…这些个小区段,每个小区段中最大的那个数 mod k可能是最大的,我们挨个数挨个区段去枚举就可以了。
但是暴力枚举是过不了的,我们就把在数列中找k,2k,…这个过程改成二分搜索,这样复杂度降为nlogn就行了。

代码

 

 

Codeforces 118D Caesar's Legions

题意

给你两种士兵,n1个A和n2个B,同种士兵是一样的,不分先后,然后你最多能把k1个A排到一起k2个B排到一起,问你有多少种有效排法。

思路

动态规划,建一个三维dp数组,其实是一个二维的表,每个格子有两个值,dp[i][j]表示截至目前只使用i个A,j个B来进行排列,dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数,之后我们来转移状态,对于当前的以A结尾的排列,我们可以再其末尾加1~k2个B,构成新的以B结尾的排列,所以我们就可以把dp[i][j+k][1]更新了(k表示加几个B)。同样的,用B结尾排列个数的值更新之后的A结尾排列个数的值,把这个表这样逐步打好,最后输出dp[n1][n2][0]+dp[n1][n2][1]即可。

接下来上代码

 

CodeForces 347C Alice and Bob

题意

两个人互相玩,他们先搞一个集合,里面几个不同的数,接下来随便挑俩作差,如果差的绝对值集合里没有,就给这个差的绝对值加进去,直到集合加不进去值为止,没招的那位就跪了。

思路

写几个数模拟一下就会发现,游戏结束时,集合里面是所有的初始几个值的最大公约数的倍数,举个例子init={2,6,8},gcd=2,final={2,4,6,8},利用这个规律我们就可以知道最终集合有几个元素,最终元素个数减去初始元素个数就是这场比赛将在多少手之后结束,接下来判断奇偶就可以判断谁赢了。

接下来上代码

 

CodeForces 484B Maximum Value

在lower_bound之后如果加入了多余的判断(判断pos的位置等等),就会T,如果没有用unique来压缩输入,就会T。

总觉得很寸,应该是数据做的有漏洞。

解法的思路就是先从小到大排序,然后从第一项开始,借用素数筛法的思路,对于每个数检查以这个数的倍数为终点的各个区间,然后找出每个区间之内离终点最近的数,更新答案。找终点的过程使用了二分搜索,STL自带的lower_bound和upper_bound就能很好地工作,使用upper_bound的话还有一个小窍门就是把搜索目标设成目标-1,这样的话搜索完落在的点就和lower_bound是一样的了。

Scroll to top