首页 > 笔记 > TC刷题记

TC刷题记

“如何快速提高姿势水平?” “刷100道TC的hard!”

现在做了

$$\Large \color{red} 1 \color{red} 9$$

大概就是一句话题解,代码不放了。(懒

假如有想要代码的,在下面评论吧

upd:最近比赛贼多,可能更新慢些

【SRM722】 首先不用管障碍,dp出来每一行的所有情况,每次把合法的状态转移到下一行,发现竖着的转移就是在上一行空出一些格子,所以转移的时候只用考虑横着的情况

【SRM721】 每一轮拆点,往能转移到的点和它自己连边,每两轮之间连流量为1的边,表示一个点最多有一个token,S往第一轮有token的连边,最后一轮没有token的往T连边,跑最大流即可。

【SRM720】 参照bzoj1937,每个边都有一个改后大小和改前大小,化出式子二分+网络流判断就可以了

【SRM719】 WC的时候听过,弃了

【SRM718】 考虑g(n - 1) = 1的时候,只要相邻两个之差不为1就行了,然后g(n - k) = 1的时候,归纳一下,只要min(|i - j| + |p[i] - p[j]|) >= k就可以了,直接爆搜

【SRM717】 辣鸡结论题,想了好久:http://codeforces.com/blog/entry/52995?#comment-370663

【SRM716】 分块乱搞就行了

【SRM714】 贪心就行,每次枚举要到的左端点,总是先走到最左边,再到最右边。可以求和判断正确性,但是在中间可能会有左右的微移,需要模拟下。

【SRM713】 神题啊。。规定每个物品重量不超过100那么我们就可以矩乘,还要求方案数的话,我们可以定义一个结构体,有两维(价值和次数),但是矩乘的话,需要满足结合律,我们重载一下,重载加法为:两种方案取最优,重载乘法为:将两种方案拼起来(方案数相乘,价值相加)。发现这样还是会t,所以还需要有一个小trick:预处理出所有$2^n$的矩阵,把询问二进制拆分后找出答案。

【SRM712】 这题有人当场写出来我吃*行吗。。写了一下午调了一晚上。。考虑相当于每个点上给一个标记。lca(p[a],p[b])=c相当于现在有两个渐进的限制:1、标记a和标记b必须在c的子树里,2、标记ab在c的不同的两个子树里。考虑限制1,对于每个标记i记一个belong[i]表示它应该在的子树。考虑放置标记的过程,我们现在遍历到了p点,那么对于所有belong为p的标记,我们把它放到p的有空的子树里,就满足的限制1。接着想放置标记的过程,首先我们知道belong为x的点和-1的点可以放在v这个点上,而且对于lca(p[a],p[b])=v,假如ab不在v点上,那么ab肯定在v的两个不同子树上,假如a或者b固定了,就已经在某个子树上了。所以我们就已知了一些限制关系:两个子树里空着的节点数目,这个标记是否能在两个子树间换(是否已经固定了),有几个不同的标记不能在同一个子树里面。我们可以用网络流或者背包来判断它的可行性。。跑完所有的节点还剩下的就可以随便放了。注意还要判非法点(恶心!!!)(lca(a,b)=c && lca(a,b)=d && c != d)。我tm代码写了10k+。。。。。

【SRM711】 首先求出g[i][j][k]为第i棵树拆的j边加到和第i+1棵树上,第i+1棵树上拆掉了k边,值为0表示不合法,1表示合法。这个可以暴力并查集求出来。设f[i][j]表示第i棵树拆掉j这条边合法的方案数。假如第一棵树拆掉了边p,那么递推过程就是f[0][p]=1,f[i][j] = sum(f[i - 1][k] && g[i - 1][k][j] == 1) ans[p] = sum(f[m - 1][i] && g[m - 1][i][p] == 1)总的答案就是sum(ans[0]...ans[n - 2])。这样太慢了。观察贡献找出f[i][j]得出f[i + 1][k],那么k肯定是在第i+1棵树上的e[j].x和e[j].y之间的路径上,这样我们可以在e[j].x和e[j].y的点上加f[i][j],在lca(e[j].x, e[j].y)上减去2*f[i][j]就可以了。答案记着按照深度向上总结。。

【SRM710】 这题想了一天= =。。。我们可以先搞出k=1的情况,虽然题目里面有限制不能相交,但是为了多维的情况,我们需要把所有的情况都搞出来。我们可以枚举所有$2^{m \choose 2}$种的相交情况(状压),考虑直接暴力所有的情况,可以把所有的序列想象成括号序列,每次我们可以新建一个括号团(需要把前面所有的左括号匹配完),在现在的括号团上加一个左括号,在现在的括号团上加一个右括号,最后就是$n \choose 括号团数量$乘上中间计算的一个系数(在新建括号团的时候计算贡献就好了)。这样还没有考虑标号,我们可以把m的全排列搞出来,代入标号再计算一下。假如得出了f[n],n的大小就是$2^{m \choose 2}$,这样就是k=1的情况。要计算k比较大的情况,也就是f的组合。它就是一个卷积的形式,而且这个是&卷积。也就是FWT的过程了。计算出点值形式然后直接k次方就可以了。最后答案就是f[0],也就是&出来为0为合法。复杂度分析一下,第一个暴力就是$O(catalan(m) * m! * 2^{2m})$,第二个标号就是$O(2^{m \choose 2} * m! * m)$,fwt的复杂度$O(log(2^{m \choose 2})2^{m \choose 2})$

【SRM709】 终于一个水题。。在序列中间打个标记,左边剩余的左括号等于右边剩余的右括号数。所以对于那么只在左半部分或者右半部分的数字可以随意指定它是左括号还是右括号;对于那些在两边都出现的数字,左边的这些数字出现为左括号的在右半部分必须为右括号。直接暴力就好了= =

【SRM708】 这个题想了挺久的,但是发现每次赌的时候钱相同的话状态是一样的,一个记搜就没啥问题了= =

【SRM707】 数据范围感觉很网络流,一开始的想法是把每个点拆点,假如有u到v的操作就u->u'费用0,v->v'费用0,u'->v'费用-1,这样跑最小费用,只要有一个满足了流量就会-1,最后答案操作数量减去最小费用,但是这样第一个样例都过不了,会形成负环。于是我们想拆一次点不够用的话可以拆很多次,每次只要有一个操作,我们就把这个两个点拆开,像刚才那样连边,最后把每个点最后拆的那个点连到T,就没有问题了,因为这样既满足了操作的独立性又满足了顺序性。还有一点是假如有费用为正的时候直接退出,因为这样会有一条-1的点倒着流了,不满足我们建图的初衷。

【SRM706】 假设当前长度n=2^k,那么每次处理前,前n/4的数字是符合要求的。处理之后前n/2是符合要求的。为方便说明,假设整个n分为四段,A,B,C,D,一开始A符合要求。且A中的奇数位置跟B的偶数位置满足不互质,A中的偶数位置跟B的奇数位置满足不互质。那么只要处理使得A中的奇数位置跟B的奇数位置满足不互质,A中的偶数位置跟B的偶数位置满足不互质即可。

【SRM705】 第一问明显线性基,第二问的话得出答案的二进制位,看看1多还是0多,哪一个少就暴力那个就行了,近似复杂度$O(\sqrt n 2^{n\over 2})$

【SRM704】 其实直接把k二进制拆分后连边就好了,证明比较简单。。

【SRM703】 发现同构图的时候度数为1的节点肯定是不动的,然后我们找到所有度为2的点,把这些路径连出来后删掉,得出的压缩过的图就只有大于等于3的度,这个图就只有最多10个点了,现在答案就是 树的同构 * 这些路径的同构的链接的形式 * 暴力找出度很多的联通块的自同构的方式 暴力的时候用hash来判重。。

【SRM702】 挺恶心的数据结构题。。明显是个二分答案k,check的时候先找出每个位置往前和往后最近的合法位置,不大形象就放个样例[8,1,10,2,9,7] k=2; le = [-1,-1,0,1,2,4], ri = [2,3,4,6,5,6],然后考虑一个函数判定一个区间(s,t)的长度>=m的子区间是不是全部都是非法区间。我们可以找到中间的一个位置p,假如它的左右指针都在现在的区间外,那么这个大区间就是非法的,这样的话我们就可以递归再找(s, p - 1), (p + 1, r)。假如每次从头到尾扫一遍区间这样还是O(n^2)的,因为每一层都有可能扫n个点才能出结果,但是我们可以从两头同时往中间扫,那么这样最坏情况是O(nlogn)的,具体证明也不会,但是我构造不出来比O(nlogn)更坏的情况。。(这个证明和dp争执了一下午。。)然后就是如何在O(nlogn)的时间找到这两个数组。我是写了个fhqtreap每个点有两维,权值和位置,维护一个位置的max,每次split权值为a[i]±mid的到一个树里,找到max就行。假如有相同的点要把那个点的位置改成现在的(现在的点的位置一定比它更优),反正最后是个O(nlog^2n)的复杂度,但是常数贼大,卡了很久才过去。


5 COMMENTS

  1. Zhihui_11222018-04-21 上午9:02

    qwq 好强啊

  2. Cansult2018-04-23 下午7:10

    学长封面换画风了qwq! 学长加油qwq!

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×