• 等级
  • 42823 访问
  • 157 原创
  • 3 转发
  • 29285 排名
  • 40 评论
  • 86 获赞

codeforces #327 #333 Div1 总结

两场相对比较简单的codeforces策略上都反应了一些问题。#327总的来说在A、B两题上花的时间太多了。A题我认为我花这么久的原因在于我代码写的不够简洁。B题少要考虑边界情况,像这个题,我没有考虑起点和终点重合的情况导致WA。每次用到除法的地方要特别谨慎。C题这一类题要想清楚了再写。思路不清晰随便fst。D思博题。E这个题很强。首先AC自动机匹配的方法很灵活,感觉可以拓展...

2018-12-13 22:34:00

BJOI染色

我还是自己脑补了很久才理解。首先二分图全部相同即可。然后可以不停地剔除那些du为1的点,这些点对答案没有任何影响。然后我们发现我们对于一个环我们可以用三个点来直接把剩下的部分染上相间的颜色。一个推广是如果两个偶环有公共部分,且这两个环的每个环自己独有的部分长度至少为2的话,我们一定可以构造出一个合法解来cha掉。单独考虑每一个边双。这个结论的推论就是一个点如果度数超过3那么一定可以找...

2018-12-11 21:28:42

Topcoder TCO R2A Div1

A题范围要看清楚,不能够想当然。B题第一次fst是因为没有考虑直接把一个环首尾相接。C题构造题。不会捉。主要的难点在于三角形的三边关系需要满足。我们考虑如何满足这个限制。首先wxh的做法是,既然我们很难处理,那么我们就递归左右两边。左边已经帮我处理好了这样的情况。我们尽量最终的序列分成均匀的6段。s1,s2,s3的构造方案已经被给出,将s2,s3平移至s3,s4然...

2018-12-01 11:13:50

九省联考总贴

秘密袭击单独写了。详情见另一个博客。#include<bits/stdc++.h>usingnamespacestd;typedefunsignedintui;constintN=2e3+5;constintM=N*2;constuimod=64123;constintMAX=1e5+5;struct...

2018-11-30 07:30:30

2018.11.30 多项式

题目大意:求n个点的二分图,将其所有边都黑白染色后不同的图的数量,两个图不同当且仅当x-y这条边只在一个图中出现或者两张图中颜色不同。n1e5多项式模板题。首先我们考虑联通二分图的生成函数G容易知道答案F=e^G.联通二部图的数量的生成函数H=e^(2G)所以我们只需要计算出H然后多项式开根就是答案。H的n次项显然是sigmai=1-nC(n,i...

2018-11-29 08:01:13

LOJ#2473. 「九省联考 2018」秘密袭击(线段树合并+拉格朗日插值)

一个非常强的题。也许比较套路但是都比较生疏。主要使用两个思想。首先是把求第k大的权转化成枚举i从1-W计算最终的第k大大于等于i的和。然后就可以转化成一个DP。f[i][j][k]representsthesubtreeofthenodeiandweareconsideringthevalueofthekthnodeisnotle...

2018-11-27 22:32:54

HAOI2018

背包看出gcd的小trick之后就可以直接跑莫比乌斯反演了。以后这一类要查找一个数的因子的位置的题,可以用杜教筛记忆化的方法分两个数组记录。做莫比乌斯DP的时候可以直接暴枚哪些质因乘积这样可以减少复杂度。不过想要简洁的话预处理mu...

2018-11-19 22:24:37

codeforces 1055

比赛的时候C题卡了有一段时间。原因是边界情况,当b是a的倍数的时候不能够倍长。以后当要做一个事情的时候要思考这个事情成立的条件。避免心态崩了的情况。D题没有调出来,主要原因是我只考虑了那些应该被更改的字符串被改正确了。却没有保证剩下的字符串不被修改。下次要忽略某些干扰条件的时候,要考虑这些干扰条件何时成立,何时会对结果有影响。F题是Trie树卡空间,这个东西分层搞或者建出Tr...

2018-11-18 21:32:47

codeforces778

C求一个Trie树缩掉每种深度的一层之后的大小。n3e5这个题我直接像线段树合并那样暴力的合并过掉了。不知道复杂度为什么是对的。D一个1*2密铺的矩形每次可以选择一个仅包含两个12的正方形,旋转90度,问是否能用少于4*n*m达到目标状态。n,m50这个题又是构造题的典型套路,把所有的目标局面和初始局面都转化成一个好弄的特定局面,这题里这个局...

2018-10-20 21:12:25

codeforces 1054

D题意不说了转化成抑或前缀和然后相当于每一位能够取反求最少相同的对数、E这个题自己想出来的。300*300的矩阵每个位置一个01串,每次可以选择用一行或者同一列的两个格子把一个格子里的字符串的末尾元素删去插入到另一个格子里字符串的头部。问是否能从初始局面变化到目标局面。用不超过4*字符串总长次操作。总字符串长度1e5第三次遇见这一类构造题了,终于切出来了。具体...

2018-10-20 20:56:52

死法大全

10.18日死于(dp[x][1]*2+dp[x][0])爆int死于没有对拍。前一次死于没有开子文件夹。

2018-10-18 13:57:54

codeforces 1063

D这个题有点胖胖。题意是有一个环n1e11个小朋友k1e11颗糖分给他们,这n个小朋友排成一个圈,每个人要求得到1个或2个糖果,如果不足全拿完,已知现在从l开始发糖,顺时针一直发发到r号人结束,求最多有多少人要2颗糖。考试的时候一直在想如何二分答案。后来发现枚举圈数非常的方便,以后这种左右摇摆有边界的题直接周围稍微for一点只要不TLE。这类题目先列出方...

2018-10-15 22:30:42

AGC 028

C一道和以前做过的一道codeforces类似的题,但不大一样。题意:每个点两个权值L,R,要求把这些数排成一个环,相邻两点ab间的(处于逆时针方向的数为a)的代价为min(L[a],R[b]),求能构造的最小的环。n100000这个题自己做出来的。首先考虑如果说能分解成多个环的话,我们一定可以构造一个方案使得权值和为所有L,R从小到大排序的前n个数的权值和。那么我们...

2018-10-15 22:23:47

codeforces做题 记录

1033G题意是给n堆石子Alice和Bob游戏Alice每次可以在一堆中取出a枚石子,Bob可以在一堆中取出b枚石子,求对于a属于[1,m]b属于[1,m]有多少对<a,b>满足1)Alice必胜2)Bob必胜3)先手必胜4)后手必胜这一类博弈题考虑每堆对于(a+b)的余数即可,像这种双方在对手操作后总可以再进行一步操作达到...

2018-10-14 13:28:31

nowcoder提高组四 灭虫

题意:3000个在数轴上的点,对于每个点可以选择这个点向左延伸li长度的线段,或者这个点向右延伸ri长度的线段,问选择的方法使得最终覆盖的数轴长度最长,输入均在int以内。一个非常巧妙的DP题。首先这一类题目有重复的线段长度统计(或者是树上的可以相交的路径方案统计)或者其他内容有一个比较自然的做法:就是把每一段线段保留一段前缀或者后缀,将限制转化为最大值,然后要保证所有的线段不相交。这个题...

2018-10-07 21:55:36

Topcoder SRM 100 场计划

SRM550Div1250按题意模拟,注意判断边界是否被访问时,以后的路径不能算上SRM550Div1500一道找规律题,打个表SRM550Div11000矩阵快速幂题,每个位置是该位置需要多少次才能转到目标态,先让他转到目标态的贡献减去之后,剩下就只剩下自己转圈的贡献了,我们发现这样的贡献在每个位置都相同,就可以算出最大旋转次数.然后状态就是有多少个需要两步到...

2018-10-04 19:39:24

codeforces VK CUP 2016 R3 VP

A,B太水C题具有单调性可以二分做,也可以推一波式子用凸包,能写第一种尽量写,不容易错。D题大分类讨论题,要注意的有删除在所有操作之前,注意用set去重,最后一起加回来。中间部分对称的东西尽量对称写,能在首尾写的写在首尾。重复以及对称变量用一个变量存起来。E题这个题提供了一个好的思路:当我们一堆东西取max的时候利用min小于等于什么来DP,或min-max容斥有...

2018-07-11 22:24:51

LCT模板题2 最长链

树是任意两点间仅有一条路径的联通图,树上的一条链定义为两个点之间的路径。在本题中定义一条链的长度为链上所有点的权值和。现有一棵带点权树,要对它进行一些操作,请你在第一次操作前和每一次操作后输出这棵树的最长链。这题非常不错的虚边维护儿子信息的LCT,并且,利用LCTsplay维护的是链的性质,可以动态的利用最大子段和的方式进行合并,主要思想就是维护以x节点为根的子树所表示的链的从头开始的最大...

2018-03-07 22:04:15

博弈图BFS

从必败态开始BFS,每次把必败态的前趋标记为必胜态,把必胜态的前趋度数-1,当一个点度为0时,变为必败点,这样只有必胜点和必败点会被BFS出来。

2018-02-28 13:02:48

挑战NPC 一般图最大匹配

题意:n个球,放进m个盒子,每个盒子最多放三个球,每个球可以放的盒子是一个集合,半空的盒子是指盒子内的球个数<=1的盒子。求半空的盒子数目的最大值。一般图最大匹配。把每个盒子分成三个,三个间两两连边,每个点向他所能到的盒子的三个分点连边,跑最大匹配,最后的答案就是,maxmatch-n。这个证明比较容易,但是非常难想,我还需要研究一下这之间的思维过程。学了一下带花树算法...

2018-02-24 16:33:20

Timsei

关注
  • 中国
奖章
  • 持之以恒