12/16
11:39
OI

THUWC/SC 乱做

在美妙的数学王国中畅游

这题给了泰勒展开确不给求导,emmmm…这两个应该是一起学的吧…

考虑泰勒展开,然后用LCT维护链上的系数和。

选择合适的位置展开是很重要的。我们可以无视ax+b,直接按x展开,然后带入ax+b应用二项式定理。

发现展开很多次之后精度就满足了要求,于是我们只需要维护一个前一些项(15次左右)的多项式即可。

随机二分图

考虑一个状压DP。f_{s_1,s_2}表示左右分别为s_1,s_2的方案数。

如果只有t=0,可枚举加入哪条边计算。每条边的边权是\frac{1}{2}

t=1,把两条边分别加入。发现如果只有一条边对答案产生了贡献,是正确的。然而一起选的时候会边少,可以考虑加入一条“边”,强制一次把两条边都选上,边权为\frac{1}{4}

对于t=3,是-\frac{1}{4}

发现状态存不下。冷静分析一下, 有用的状态不多,记搜就行了。

大葱的神力

神仙乱搞题,告辞。


补退选

Trie树,每个点开个vector存一下第一次达到某状态的时间。

成绩单

一开始yy了一个DP:定义f_{l,r,k}表示[l,r],选了k次。O(n^5)转移。

然后发现是假的,两次选的区间不一定交。

热动分析发现转移代价只和\min , \max有关。那么定义f_{l,r,a,b}表示[l,r],删了一些,现在\min, \max分别为a,b的答案。

再定义g_{l,r}[l,r]的答案。

f_{l,r, \min \lbrace a, w_r \rbrace, \max \lbrace b, w_r \rbrace} \leftarrow f_{l,r – 1,a,b}

f_{l,r,a,b} \leftarrow f_{l,k,a,b} + g_{k+1,r}

g_{l,r} \leftarrow f_{l,r,a,b} + A + B(b-a)^2

星露谷物语

神仙题,溜了溜了qaq


巧克力

二分一下中位数,给大于小于的分别赋一个略大一点,略小一点的值,求最小方案即可判断。

考虑如果颜色很少怎么做。要会斯坦纳树。然后就可以暴力状压了。

如果颜色很多,把颜色随机映射到[1,k],随机很多次的正确率是很高的。

杜老师

遇到完全平方考虑出现次数是奇数的因子。线性基直接做,如果线性基里有x个元素,答案就是2^{r-l+1-x}

但是线性基直接做会TLE。那么根据套路应该考虑根号,大于根号的因子只会出现一次,维护有没有在线性基里出现过。小的做暴力线性基。

换桌

明显是网络流,可以把可以到达的点都暴力连边。

题目是区间操作,自然想到线段树优化。

具体来说,每个位置的座位建两棵线段树,分别表示向左向右走。

大魔法师

既然是区间操作,线段树维护。线段树标记的特性之一就是可以合并。题目中的操作都很简单,可以用矩阵维护,而矩阵有结合率。

如果奇迹有颜色

是橙色!!!

不会BM也不会Polya,告辞

宇宙广播

不会计算几何,告辞


异或运算

发了个洛谷题解233

异或k大问题当然是一位一位算啦~枚举每一位,算可能的答案中这一位有多少0有多少1就好。

发现结果和行,列都有关,且n很小,可以考虑枚举行,计算这一行有多少满足要求的。

Y建一棵可持久化Trie,询问的时候每一行维护一下走到了Trie的哪里,根据01数量决定走哪边就好了。

平方运算

模数给了这么多很有意思,乱搞平方会进入循环(\rho形),循环节都不长。打表(看题解)可知,循环节的\rm{lcm} \leq 60,于是可以考虑维护区间的整个循环节。对于进入循环节与没进入循环节分类讨论,乱搞就行了。

解密运算

可以把原串变成环,然后对于一个字符,确定它前面的字符是什么。

题目给出的信息可以让我们知道两件事,一是这个数是什么,二是这个数的下一个数的排名是多少。

假装所有字符都不一样,那么每个字符的排名确认,就很好做了。我们对输入排序,从0按排名跳。

如果存在相同字符,考虑如何区分排名。当首字母相同的时候,我们比较下一个字母。考虑两个相同字符,一个在另一个前面,那么在排序的时候它的串一定比另一个串小。于是按第二关键字是输入顺序排序就做完了。