TCO2014 - jcvb

TCO2014

jcvb posted @ 2015年3月27日 19:08 in 未分类 , 1590 阅读

做了10天。。除了final的1100pts都刷完了。。有一个题看了题解才明白trick,还有两个题是看了别人代码或是x大爷提醒的。。。。总之大部分是自己做的。。

可是打srm还是会爆负怎么办呀。。

省选课件:http://pan.baidu.com/s/1c0IrfJ6

1A:

250 写了DP。好像直接贪也是对的。

500 按字典序贪,检查时也是用贪。

1000 dp套dp 。。写的好麻烦。。。题解上的好像挺简洁

1B:

200 考你会不会编程

600 暴力枚举一维,剩下一维dp

900 我的dp状态是f[u][0]=u和u父亲都没填的概率,f[u][1]=u没填u父亲填了的概率

1C:

250 考你会不会编程

450 小学水平的容斥

950 直接裸三维状态的dp是O(n^3)就能过。用期望线性性可O(n^2)。O(n)不知道 没想过。

2A:

250 转化为最大化相邻格子高度差的绝对值的总和。贪心策略大概是高矮交错放。严格证明不大会

500 枚举中间次序不变的那一段,两边分别走到端点处再排好序走回来。但最后一个样例过不了,看题解发现漏了一种情况,可能有的狼从左端点一直跑到右端点的(题解里有张配图)。这时每只狼都至少到达过一个端点,中间一段狼到过两个端点,也是可以枚举的。

1000 难写。我是每次考虑能移到哪几个相邻位置结点再逐步扩展的。能移的条件大概有:子树有空位 或者 其他有两个子树分别有空位  或者 其他某一个子树里有两个分叉的空位。

2B:

350 按时间顺序贪。记录一下目前哪些点是两种状态都可能的。到不得不按的时候再按。

500 推理一下该满足的条件有哪些。。。然后可以nlogn筛

900 最后肯定得变为kW+1。。考虑一下怎么变过来的。。能推出一个形式,然后搜。  不知道复杂度,但跑的很快。

2C:

300 先考虑翻转的[l,r]满足s[l]!=s[r]的,这个显然可直接贪。然后s[l-1]==s[r+1]的话再一直往两边延伸

500 给每个团加个新点 都连向它。。。然后变成裸bfs   

900 先搞出每小段区间的最大值,然后判一下有没有包含同一个数的区间交集为空的情况。 然后变成个匹配一样的东西。。判有没有满流就行了。标解没有最大流,但应该差不多吧。

3A:

300 把下标按对k的余数分组。枚举总次数的奇偶性,然后每组里面贪。

500 最短路肯定是那两个联通块之间被加的新边 和 原各个联通块内的两点间最短路。状压当前已经连通的是哪些点 枚举新加哪条边。

1000 先搞出两两最短路。猜个结论:取到的硬币的顺序最多改变两次方向。。就是最多往右再往左然后一直往右。。总共就是三段,然后n^3的dp。不会证也不知道对不对。。反正能过

3B:

250 (k+1)进制。

500 等价的点组成的团先缩掉。发现剩下的每个连通分量都是链或圈,dp就好。想一想发现是能证的

1000 带边权的矩阵树定理。权为1就用字母x表示。然后行列式是一个多项式,代入几个数值然后插值搞出系数。

Celebrity:

250 小学奥数

450 若区间是[l,r],推推式子发现l和r是能分离的。。枚举右端点就好

1000 先二分。然后构2sat。一开始想怎么构造4选1。。后来发现做不了。。然后X大爷提醒给4个小等腰三角形分别建一个点,然后对角线异或为1就好了

Semifinal1:

250 不能要的点全去掉后剩下好多段,显然每段要么全取要么全不取。段数只有n/2,暴力枚举取哪些。

450 只有能表示成若干个阶乘数的乘积的才可以。估计是构造姿势不对,点数超了。。最后压到了199

1000 就是一堆圆和矩形的交再求和。。考虑四分之一圆会方便些,然后就水掉了

Semifinal2:

300 W能切成若干个极小的段(不能再分的)。每段的结构肯定是两边共有h列是竖着贯通的,中间夹着h个横着,其余也都是竖着的。(如果高度等于h那么也可以全是竖着的。。)

500 弄出边双连通分量,每个分量显然能互通。然后暴力枚举看有没矛盾

850 弄出递推式写成生成函数,然后可以O(D)。

Wildcard:

275 搞出所有2的幂次在哪(只包含一个1的),特征是所在的行刚好有2^{n-1}个1。然后就全部出来了。

750 先考虑naive的dp,f[n][m],总共有c^{nm}种,减掉其中不合法的话就需要枚举行有多少等价类列有多少等价类,大概就是乘上第二类斯特林数嘛,这样总共是n^4的。然后发现可以反演。。第二类反演过去就是第一类乘上-1的幂次。因为是二维的,得固定一维反演再反演另一维。这样就是n^2了。

1100 记到达每个点的剩余最大能量。。每个点拆成4个方向的点用来扩展,花样BFS可以搞到O(NM)。

Final:

350 考虑一下每一条边被走过的次数(有向的,正负抵消)。一个格子的转圈数就是它正上方的边的走过次数之和。。然后判每个点是否平衡。。然后再把各个连通块连起来

550 顺序肯定是加速度降序。。排好序的话答案是0.5\sum{x_i y_i}+\sum_{i<j}x_i y_j。一开始SB。。在最大割的路上愈走愈远。。。其实由于值域挺小,可以DP。按x/y(x>y)的升序加进去,那么始终是序列的中间一段,每次在左边或右边添加。状态是摆在分母的数字之和,记最大ans。

1100 好难啊。。。根本不会做。。题意大概是“一堆等长的区间。。。每个区间可以选中它的左端点或右端点   问排序后有多少种不同的ranking。。”然后就不知道怎么办了。。。。。。。弃疗大法好


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee