bzoj屯题计划
bzoj3162 独钓寒江雪 题解+吐槽

codeforces补全计划

Recursion posted @ 2015年3月03日 17:19 in 题解 with tags codeforces , 883 阅读

虽然最近没怎么打比赛但题目还是要补全的

完成数:15

round295div1a 一道需要想一想的A题,然后发现符合条件的串一定是由出现次数最多的字母构成的,统计一下,快速幂就行了(其实不用快速幂也能过...)。

round295div1b 感觉这题比A题还一眼...用set和priority_queue维护一下就行了,但是细节比较麻烦。

round295div1c 看到这种数学题就头疼,果断去膜拜题解。然后发现这题好像也不是很难,考虑每一位在不同的10的幂次上的贡献就行了。然后组合数算一算。算阶乘的逆元要用拓展欧几里得,然后我已经忘了...

round295div1e (今天闲着没事看了看这次cf的d和e,然后发现e很水的样子...)虽然通过的人很少依然不改其水题的本质。首先我们发现三条不相交的路径等价于两个有公共边的环,于是直接dfs判断联通块是不是仙人掌就行了。输出路径比较麻烦,可以找到一个环将所有的点标记一下这个环的起点和终点,然后如果标记了两次就说明找到了解。

round296div1a A题出一道set强搞的题有意思?

round296div1b sb题。容易发现就是给你很多线段,问最多有多少条不两两相交。排个序贪心就行了。

round299div1a 直接二分就行了。

round299div1b kmp乱搞。

round302div1a 一眼dp。

round302div1b bfs,枚举公共部分。其实就是一个小斯坦纳树?

round302div1d d题怎么会有这么sb的树形dp...

round305div1d 每一行每一列相邻的点连边,二染色。

round309div1a [tex]f_i[/tex]表示前[tex]i[/tex]种颜色的方案数,每次乘一个[tex]C^{c_i-1}_{c_1+c_2...+c_i-1}[/tex]就行了。

round309div1b 注意到合法的置换必须是单个或是连续两个递减的数。方案数显然是fibonacci数列,从前往后依次判断每一位就行了。

round309div1c 先把love边用并查集缩起来,然后判断hate边是否是二分图,如果是,答案为[tex]2^{k-1}[/tex],[tex]k[/tex]为联通块数量。

 

Avatar_small
SanSiroWaltz 说:
2015年3月03日 19:54

拓展欧几里得想不起来可以写快速幂

Avatar_small
Recursion 说:
2015年3月03日 20:10

@SanSiroWaltz: 有道理


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter