最后一年了, 一年不到, 为了可爱的学长们, 为了自己, 要拼命了啊.
\(\text{[AGC048D]Pocky Game}\)
\(\color{green}{\text{[EASY]}}\)
怎么这都做不出来, 废物啊.
显然石子越多赢面越大, 看到这个范围就想到区间 \(dp\) .
那么可以设 \(f_{i,j}\) 表示剩下 \([i,j]\) 时, 左边先手, \(a_i\) 至少要为多少才能获胜, 类似的定义 \(g_{i,j}\) .
考虑怎么转移, 以 \(f_{i,j}\) 为例, 如果拿完这样一堆就赢, 即 \(g_{i+1,j}>a_j\) , 那么 \(f_{i,j}=1\) ; 否则就是要两个人一个一个取, 慢慢耗, 如果先手的石子数量小于 \(f_{i,j-1}\) 时, 后手全拿完就赢了, 同理如果后手的石子数量小于 \(g_{i+1,j}\) 时先手全拿完就赢了. 先手一共会拿 \(a_j-g_{i+1,j}+1\) 轮, 也就是至少需要这么多的石子, 同时还要保证后手无法胜利, 所以 \(f_{i,j}=f_{i,j-1}+a_j-g_{i+1,j}+1\) .
时间复杂度 \(\mathcal{O}(Tn^2)\) .
\(\text{[ARC141D]Non-divisible Set}\)
\(\color{blue}{\text{[NORMAL]}}\)
很套路, 小奥套路, 被爆杀了.
\(1\) 到 \(2m\) 之间, 有 \(m\) 个奇数, 所有的数都可以以这些奇数为底乘上 \(2\) 的幂次构成一个等价类, 显然一个等价类里要选一个.
接下来就更套路了, 一个等价类能选的一定是一个连续的段, 考虑一个冲突, \(a=kb\) , 其中 \(a\) 和 \(b\) 为等价类的奇数基底代表, \(k\) 为一个正整数, 那么 \(b\) 等价类中选的数一定大于 \(a\) 等价类中选的数.
那么我们可以贪心的取得每个等价类的上界和下界, 时间复杂度 \(\mathcal{O}(n\log{n})\) .
\(\text{[ARC124E]Pass to Next}\)
\(\color{blue}{\text{[NORMAL]}}\)
\(too\; hard\; for\; me\) , 人均会就我不会.
我学会了, \(\prod\limits_{i=1}^{n}{x_i}\) 也有组合意义, 每个人拿一个球出来.
考虑拿出的球是自己的还是上一个人给的, 设 \(f_{i,0}\) 表示第 \(i\) 个人的球是自己的, 考虑前 \(i-1\) 个人的方案数, \(f_{i,1}\) 表示第 \(i\) 个人的球是别人给的, 考虑前 \(i\) 个人的方案数.
\[f_{i+1,0}=f_{i,0}\sum_{j=mi}^{a_i}{(a_i-j)}+f_{i,1}\sum_{j=mi}^{a_i}{1}\\ f_{i+1,1}=f_{i,0}\sum_{j=mi}^{a_i}{j(a_i-j)}+f_{i,1}\sum_{j=mi}^{a_i}{j} \]\(mi\) 是为了保证 \(\min\{c_i\}=0\) , \(c_i\) 是第 \(i\) 个人给后面人的数量, 注意他是个环所以要处理初始值是 \(f_{1,0}\) 还是 \(f_{1,1}\) .
时间复杂度 \(\mathcal{O}(n)\) .
\(\text{[ARC117F]Gateau}\)
\(\color{red}{\text{[HARD]}}\)
显然可以二分答案, 变成可行性问题, 区间是个半圆, 那限制就相当于对于 \([1,n]\) 的每个位置有个 \([l_i,r_i]\) 的做法.
那我们考虑确定一个位置, 然后贪心放, 假设我们确定了 \(sum_n\) , 贪心策略为,
- 如果 \(l_i\leqslant sum_{i-1+n}-sum_{i-1}\leqslant r_i\) , 那么 \((sum_{i},sum_{i+n})=(sum_{i-1},sum_{i-1+n})\) .
- 如果 \(sum_{i-1+n}-sum_{i-1}<l_i\) , 那么 \((sum_{i},sum_{i+n})=(sum_{i-1},sum_{i-1}+l_i)\) .
- 如果 \(sum_{i-1+n}-sum_{i-1}>r_i\) , 那么 \((sum_i,sum_{i+n})=(sum_{i-1+n}-r_i,sum_{i-1+n})\) .
由贪心策略可知, 只要 \(sum_{n-1}\leqslant sum_n\) , 并且 \(sum_{2n-1}\leqslant x\) , 则合法, 并且如果令 \(sum_1=a,sum_n=b\) , 那么如果 \(a\leqslant a',b\leqslant b'\) , 则 \(sum_{n-1}\leqslant sum'_{n-1},sum_{2n-1}\leqslant sum'_{2n-1}\) .
所以, 当 \(sum_{n}\) 足够大的时候一定能满足 \(sum_{2n-1}\leqslant x\) , 当 \(sum_{n}\) 足够小时 \(sum_{n-1}\leqslant sum_n\) .
再二分即可 \(sum_n\) 即可, 时间复杂度 \(\mathcal{O}(n\log^2{A})\) .
\(\text{[ARC117E]Zero-Sum Ranges 2}\)
\(\color{blue}{\text{[NORMAL]}}\)
如果一层有 \(x\) 个点, 那么该层就有 \(\frac{x(x-1)}{2}\) 的合法方案.
从上层往下 \(dp\) , 并不关注前缀值是多少, 注意到前缀和相等的位置不相邻, 两个位置之间一定是峰或者洞, 洞则下一层一定要填.
记 \(f_{i,j,k}\) 表示从上往下有 \(i\) 个, 形成了 \(j\) 对, 有 \(k\) 个洞, 不算两侧的, 转移考虑枚举下一层加多少数, \(f_{i,j,k}\rightarrow f_{i+x,j+\frac{x(x-1)}{2},x-(k+2)}\) , 转移系数为 \(\binom{x-1}{k+1}\) , 插板法.
答案除了 \(f_{2n,k,0}\) 还有上下两种合并的, \(f_{i,j,l}f_{2n+1-i,k-j,l-1}\) , 时间复杂度 \(\mathcal{O}(n^5)\) .
\(\text{[ARC100C]Or Plus Max}\)
\(\color{green}{\text{[EASY]}}\)
高维前缀和, 记录最大和次大值即可, 时间复杂度 \(\mathcal{O}(n2^n)\) .
\(\text{[ARC078F]Mole and Abandoned Mine}\)
\(\color{green}{\text{[EASY]}}\)
删的边权和最小等于保留边权和最大, 并且 \(1\) 到 \(n\) 的路径上一定都是桥, 路径上的点可以连接一个连通块, 注意到 \(n\) 的范围, 考虑状压.
设 \(f_{S,x}\) 表示目前和 \(1\) 连通的点集为 \(S\) , 并且 \(1\) 到 \(n\) 的路径上最后的点为 \(x\) , 转移考虑练个连通块或者往后延伸路径.
时间复杂度 \(\mathcal{O}(n3^n)\) .
\(\text{[ARC068F]Solitaire}\)
\(\color{green}{\text{[EASY]}}\)
发现序列是 \(V\) 形的, 那删除序列就可以拆成两个可以为空的单调下降序列, 且后面 \(n-k\) 个数的最大值小于两个序列结尾的最大值.
设 \(f_{i,j}\) 表示前 \(i\) 个数较小的结尾的数是 \(j\) 的方案数, 转移考虑下一个数与 \(j\) 的大小关系, 若 \(x < j\) , 则 \(f_{i,j}\rightarrow f_{i+1,x}\) , 若 \(x > j\) , 则 \(f_{i,j}\rightarrow f_{i+1,j}\) .
最后没删的 \(n-k\) 个数有 \(2^{n-k-1}\) 种, 时间复杂度 \(\mathcal{O}(n^2)\) .
\(\text{[ARC088E]Papple Sort}\)
\(\color{green}{\text{[EASY]}}\)
不难知道出现次数为奇数的大于 \(1\) 无解, 不难发现最左和最右配对, 不难想到只移动一个端点.
时间复杂度 \(\mathcal{O}(n\log{n})\) .
\(\text{[ARC101E]Ribbons on Tree}\)
\(\color{green}{\text{EASY}}\)
看到计数和数据范围, 大概猜到是个平方复杂度的 \(dp\) .
先考虑直接容斥 \(\sum\limits_{S\sube E}{(-1)^{|S|}f(S)}\) , 其中 \(f(S)\) 表示去掉 \(S\) 的边集之后匹配的方案数, 一个连通块大小是奇数显然方案数是 \(0\) , 偶数即为 \((siz-1)(siz-2)\cdots3\cdot1\) .
那大概就可以猜出 \(dp\) 状态了, 设 \(f_{i,j}\) 表示以 \(i\) 为根的子树内连通块大小为 \(j\) 的方案数, 带着容斥系数转移, 转移即为背包转移, 特别的, \(f_{i,0}\) 表示断掉 \(i\) 与 \(fa_{i}\) 的父亲边, 有 \(f_{x,0}=-\sum\limits_{i=1}^{siz_i}{f_{x,i}\times g_i}\) .
时间复杂度 \(\mathcal{O}(n^2)\) .
倒计时开始~
标签：Atcoder,试题,color,text,sum,Part3,mathcal,复杂度,leqslant From： https://www.cnblogs.com/Lonely923/p/16732581.html