TCO2014 - jcvb

TCO2014

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

做了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。。”然后就不知道怎么办了。。。。。。。弃疗大法好

BSNL Recharge Plans 说:
2022年8月09日 10:15

You may check the specific daily prepaid recharge offers, one year plan of Bharat Sanchar Nigam Limited introduced in circles like Tamilnadu, Kerala, Karnataka, Gujarat, Maharashtra etc BSNL Recharge Plans and also find BSNL all India free roaming facility including Mumbai and Delhi by allowing new prepaid mobile plan with unlimited data and calls, free SMS, even in roaming, and to attract more customers into their web.

AP 2nd Inter Botany 说:
2022年9月08日 20:19

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 2nd Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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