觉得题解要换换样式了……

STOI补番队胡策 #1

A 抢糖果

给 n 个数，每次可以增加或删除一个数，求每次操作完有多少 xor 和为 0 的子集

$n \le 500$，$x \le 1000$，保证增加操作次数不超过 10

离线逆序操作，增加直接背包 $O(1024)$，删除则重建背包 $O(1024n)$

加强：无特殊限制

△不会

B 233的烦恼

给长度为 n 的序列 $A_i$，$Q$ 次询问 $\sum|A_i-A_j|~(1\le i<j \le r)$

$n \le 10000$，$Q \le 20000$

直接莫队+树状 $O(n \sqrt n log(n))$

STOI补番队胡策 #2

A YoShiNo loves pears

给 $n*m$ 棋盘，每格上面都有数，每次从 $(1,1)$ 出发走到 $(n,m)$，每格经过一次可以减 $K$，问最少出发次数

$n,m \le 500$

最小链覆盖=最长反链，然后DP

D Order

定义匹配为两字符串相同位置的字符一样；定义方便子串为两字符串中一段无法再往两边扩展的连续匹配段；给 $n$ 个相同长度的字符串，$Q$ 次询问区间 $[l,r]$ 中的字符串与字符串 $S_x$ 的方便子串且满足长度介于 $[L,R]$ 之间的个数总和

$n,Q \le 23333$，$Len \le 6$

离线询问，由于字符串最多才6位，枚举匹配段的位置然后Hash求出这个段上的所有子串，并对所有答案更新贡献，这样每个答案就能得到各个长度的连续匹配段数，然后容斥一发就可以求出满足无法再往两边扩展的连续匹配段数

STOI补番队胡策 #3

A 断了的项链

定义完美串为经过翻转+取反操作后依旧不变的01串；给长度为$n$的01串，求有多少个完美子串（本质相同重复计数）

$n \le 500000$

回文树一发

C 发电

$n$个变量，需满足两种约束条件：$L_i \le x_i \le R_i$，$x_u \le x_v+d$，求 $\sum F(i,x_i)=(A_ix_i^2 + B_ix_i + C_i)$ 的最大值

$n \le 50$，$-100 \le L_i \le R_i \le 100$

先求出每个变量在满足前者条件时的 $Fmax(i)$，然后设点 $(i,a)$ 建图

连边 $(i,a-1)-(i,a),~[Flow=Fmax(i)-F(i,a)]$ 表示是否让 $x_i=a$

连边 $(u,a)-(v,a-d),~[Flow=inf]$ 表示约束条件 $x_u \le x_v+d$

这样求出来的每种割对应一种取值方案，求最小割即可

无解有两种情况：单个约束条件二无法在约束条件一中找到可以满足的值（即建不了边）和多个约束条件二无法满足（最小割为 inf）

STOI补番队胡策 #4

C 三角形

给出平面上两个三角形，问其中一个是否能通过绕某定点 $A$ 旋转并以 $A$ 为中心缩放得到

将坐标表示成复数，以原点为中心旋转缩放相当于乘一个复数系数$k$

枚举三点对应关系，得到方程

\begin{cases} (a_1-A)*k=b_1-A  \\ (a_2-A)*k=b_2-A  \\ (a_3-A)*k=b_3-A  \\ \end{cases}

根据前两个解得$A,k$，然后代入第三条方程验算

Codeforces Manthan, Codefest 16

C. Spy Syndrome 2

给一个字符串，删去空格，全部转成小写字母，然后整串翻转，已知结果和字典求原先给定的字符串

字典弄棵Trie，然后在上面跑DP

D. Fibonacci-ish

给一堆数，在其中拿出最多的数，组成有斐波那契数列性质的数列

枚举前两个数，然后递推一发（需要注意到全部都是 0 的数据）

E. Startup Funding

首先，当 $l$ 固定的时候 $p(l,r)$ 是个上凸函数，二分找一下极值（我脑抽用成了三分）

然后就是组合数学时间辣

枚举最小的数，判断有多少种方案包含这个数，依次统计一下就行

F. The Chocolate Spree

给一棵树，求两条不相交的链使得包含的点的权值最大，$n \le 100000$

树DP，仔细讨论一下即可

G. Yash And Trees

裸链剖，线段树里面每个区间所包含的数就用 bitset 存一下就好了

H. Fibonacci-ish II

给一个序列，每次询问一段序列，求 $G=\sum F_i*a_i$，其中 $a_i$ 是询问序列按从小到大排序后的结果，$n,Q \le 30000$

莫队（在题解里看到了"Mo’s algorithm"十分感动）

首先，离散化后可以权值线段树维护，区间维护的是权值范围的 $G$，增减都是 $O(log~n)$

然后，从 $F_i*a$ 转化到 $F_{i+1}*a$ 可以弄个矩阵来操作：

$$\begin{matrix} 0 & 1 \\ 1 & 1 \\ \end{matrix} $$

Codeforces CROC 2016 - Elimination Round

D. Robot Rapping Results Report

$n$ 个点不断连有向边，问第几次连边后就能唯一确定各个点的大小关系

二分答案，然后拓扑排序看方案是否唯一

E. Intellectual Inquiry

给 $n$ 个字母，在后面加上 $m$ 个字母使得不同子序列总数最多

贪心加字母，每次加上最靠右出现的离右端最远的字母，然后序列自动机一发

F. Cowslip Collections

给 $n$ 个数，每次加一个数并询问其所有大小为 $k$ 的子集的gcd和

枚举gcd将所有能整除的数提出来，计算子集数，用 $\varphi()$ 算贡献

（证明：$\sum \varphi(\frac{n}{i})=n$）

新加一个数就更新一下其所有约数的贡献

计算所有数的约数时，可以循环枚举约数并枚举倍数然后存在vector里面，复杂度 $O(nlogn)$（DFS搜索约数会TLE）

Codeforces 8VC Venture Cup 2016 - Final Round

B. XOR Equation

给两个正整数的sum和xor，求有多少对数满足条件

方案数为 $2^g$（其中$g$为xor上1的个数），sum减去xor后判断能否由$2^a+2^a$构成（其中xor的第a位为0）

C. Factory Repairs

对于修理前的和修理后的，维护两个树状数组即可

D. Package Delivery

经典贪心问题

给一段路，有些无限量的油站在路上，价格不一，且油箱有最大容量，求全程最小代价

对于当前位于的点，查找范围内有没有价钱比当前点还便宜的，有的话就选最近一个前往且油买得刚刚好，否则选择最小价钱的点前往且油箱装满（模拟赛的时候前面部分脑残没想到）

E. Preorder Test

一棵树，选取根和子树的顺序使得DFS序的前K个的最小价值最大

首先二分答案，那么点权就变成0和1，要找的变成使得DFS序前K个都为1

而且假如一棵子树都是1，那么肯定是放在DFS序的前面

结合这些进行树DP，一遍DFS整理信息，一遍将根的信息转移至子树并统计

Codeforces Round #345 (Div. 1)

D. Zip-line

$n$ 个数，$m$ 个询问，每次单点修改，然后问你现在整个序列的最长严格上升子序列长度，修改完之后要修改回去

离线询问离散化后，预处理出以每个点为结尾的从左到右最长上升序列和从右到左最长下降序列，以及询问后的最长上升、下降序列，这样就可以得到修改后经过修改点的LIS。二分查找所以 $O(nlogn)$

然后对于每个询问，答案在经过和不经过修改点两种LIS中选择

若修改的点为关键点（就是删了这个点全局LIS就会减少），则求最大值的时候全局LIS要减一

关键点条件：经过点的LIS为全局LIS且点所处的层只有一个点

在线做的话就持久化线段树维护中间DP就行了（貌似是？）

E. Clockwork Bomb

给两棵树，对第一棵树轮流删边加边变成第二棵树，要求任意时刻不能成环，询问最少操作次数并输出方案

构造+并查集（正解是LCT动态MST）

首先预处理并查集：若某对点在两棵树上都有边直接连，则在并查集中合并两点。

从第一棵树的DFS顺序开始考虑，假如当前点是 $u$，其子树已经全部遍历完毕了，$v$ 是 $u$ 的父亲，如果边 $(u,v)$ 不在第二棵树，且 $u$ 在第二棵树的父亲为 $g$，我们就断 $(u,v)$ 连 $(u,g)$，若g已经遍历过了，则修改 $u=FindRoot(u)$ 并连边。（FindRoot为查找同个并查集中最浅的点）

Codeforces IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)

E. Bear and Forgotten Tree 2

$n$ 个点，$m$ 个限制，每个限制说 $(A_i,B_i)$ 之间不能连边，问你能否构造出一棵生成树，且1号点的度数恰好等于 $k$

首先去掉点1，若剩余的联通块不与点1相连，或联通块个数超过 $k$，或点1的出边小于 $k$ 则无解

反图直接DFS搜索有可能直接 $O(n^2)$，所以用set存下当前还没访问的点，每个点遍历时从中选取未访问点并询问之间有没有连边，有的话就将未访问点从set删除并加入待遍历队列中

Codeforces VK Cup 2016 - Round 1 (Div.1 Edition)

A. Bear and Forgotten Tree 3

给定节点数 $n$、直径 $d$ 和以点1为根时的最大深度 $h$，构造一棵满足要求的树

首先选择 $d+1$ 个点连成一条链，然后选择点1的位置，然后将剩余的点全部扔到直径左数第二个点即可

B. Bear and Polynomials

给一个多项式，修改其中一项的系数使得当x取2时多项式的值为0

设多项式的前 $n$ 项为 $Pre[n]$，后 $n$ 项为 $Suf[n]$，枚举修改第 $x$ 个系数，那么可以修改成 $-\frac{Pre[x-1]+Suf[x+1]}{2^x}$，然后判断这个数是否符合条件

C. Bear and Contribution

给$n$个数，加5需要代价$b$，加1需要代价$c$，求使$K$个数相同的最小代价

从小到大枚举最终相同的数（包括各个数加上$[0,4]$后的数），其中建个优先队列讨论就可以了

然而还要分类讨论最终相同的数模5的情况

BestCoder Round #74 (div.1)

1004.Deletion

给出一个$n$个点$m$条边的无向图$G$，每次你可以选择一些边从图中删掉，要求选出来的边构成的子图的每个连通块最多只有一个环，问最少需要删几次才能把所有边都删掉

把题目转化成给无向图定向使得最大出度最小，然后二分建图边左点右就变成网络流题辣

BestCoder Round #76 (div.1) 

1004.DZY Loves Sorting

给长度为$n$的数列，$m$次操作每次使一个区间升序排序或降序排序，求操作完下标为$k$的数是多少

二分答案一下，把数列中不小于当前答案的变成1，其余变成0，然后就变成01区间修改区间查询的线段树裸题了

Codeforces Educational Codeforces Round 10

E. Pursuit For Artifacts

给无向图，其中有些边是价值边，每条边只能经过一次，给起点和终点，问能不能找出一条经过价值边的路径

Tarjan求出割边后看价值边在dfs树上还是在双联通分量内，然后dfs一遍

F. Ants on a Circle

给 $n$ 只蚂蚁的运动方向和位置，相碰时方向都取反，求T秒后各自的位置

首先，相碰处理为顺时针的蚂蚁编号+1，逆时针的编号-1，这样就不用考虑方向取反的问题了

然后，先把周期为 $m$ 的处理掉，设顺时针的有 $X$ 人，逆时针的有 $Y$ 人，那么 $m$ 秒过后顺时针会碰撞 $2Y$ 次，逆时针会碰撞 $2X$ 次

然后对于最后剩下来的那几秒，就二分答案判断碰撞了多少次

STOI2016

C 锦标赛

有 $2^n$ 个人打淘汰赛，共 $n$ 轮，规定编号小的人每次都能打赢编号大的人；每人都有颜值，每场比赛的精彩程度为双方的颜值xor和，求 $2^n-1$ 场比赛的精彩程度和的数学期望

$n \le 18$

枚举 $A,B(A<B)$，求出有多少方案包含 $A$ 在第 $i$ 轮遇到 $B$ 并被打败的情况，这步可以通过组合数学求得；然后通过期望线性性就可以算出数学期望，$O(2^n*2^n)$

然后可以发现组合数学中 $B$ 可以前缀和优化，就只需枚举 $A$，压到$O(2^n)$

D 树

给棵 $n$ 个点的树，每个点有颜色，$m$ 次询问两点路径上 $\sum T_i^2*C_i$，其中 $T_i$ 是颜色 $C_i$ 在路径中出现次数

$n,m \le 50000$

裸·树上带修改莫队

把糖果公园改改就好了

[Offer收割]编程练习赛1-3

1-4 舰队游戏

将 $A,B,C$ 排序后贪心可得按A从大到小排，制空值越大的越先，伤害值同理，能放就放，不能放就空缺，求出空缺数后dfs找出所有合法方案，$O(\frac{16!}{5!5!6!})$

2-3 自行车架

将右边界用三位四进制状态表示，做个DP记录每个状态的最短长度，$O(50^3*4*4*4)$

△2-4 扫地机器人

3-4 子矩阵求和

首先我们可以知道一个矩阵往右下角移动时总和是加上 $n*m$ 的，所以枚举有经过中间分界线的矩阵，然后看能不能在加上若干个 $n*m$ 后总和为K倍数

CH Round #70 - 连续两大交易事件杯省选模拟赛

A 「艦これ市」70万幕后交易事件

给一列数 $A[~]$，每次可以将某个数移到队首或队末，问至少几次操作才能使数列变得有序

设排完序后的数组为 $B[~]$，那么答案等于 $n-LCS(A,B)$，其中A是子序列，B是子串，这步可以 $O(n)$ 实现

B 「NOIP市」神秘PY交易事件（前篇）

给无向图，每个点都有其价值，为每个点设置工资，距离为2以内的点对的工资大小关系需满足其价值大小关系，求最小总工资代价

对于距离为2的各个点我们也把边连上，但是这样边数又会太多，所以我们枚举点，把与其相连的所有点提出来排个序，然后相邻的点连上边，就可以避免过多的重复的边被新增了

C 「NOIP市」神秘PY交易事件（后篇）

树形DP，$F(x,ty)$ 表示点 $x$ 代表 $ty$ 的最小代价，然后传递用背包处理下就可以了，顺便记录方案

BestCoder Round #79 (div.1)

1004.Lady CA and the graph

$n$ 个点初始没边，每次给起点区间和终点区间并疯狂连边，求层次图最短路

区间加边的话，我们建两棵线段树A和B，在A上只能往上走，在B上只能往下走，且B的叶子能走到A叶子，建边就变成找对应区间然后连边，然后为了使边的数量变少，我们新建边节点，将起点区间连至边节点再连至终点区间，同时注意边要建两次（双向的原因）

最后在新图跑层次图最短路就可以了

BestCoder Round #80

1005.Road

给一棵树，折线定义为两端点 $x,y$ 没有祖先关系的路径，求第 $K$ 大折线

先算出折线数量，判断有没有解；然后二分答案，折线数量等于总路径数量减去非法路径数量，后者可以线性求得，前者就是点分了， $O(nlog^3n)$

然后优化复杂度，将点分中的排序（也就是第二层log）预处理一下，复杂度下降至 $O(nlog^2n)$

CROC 2016 - Final Round

△E. To Hack or not to Hack

CodeChef April Cook-Off 2016

Queries on a Binary Tree

求出LCA后移动LCA，计算出LCA移动一格时两点的移动幅度，确保两点还在树上

LCP Maximization

给两个字符串，每次询问分别将后缀，而且前者还可以通过映射进行变换，求经过映射后的最长公共前缀

对于每个后缀Hash一发，Hash的时候需要提前将字符映射好，例如第一个出现的字符映射为1，第二个为2，以此类推

然后就可以二分答案+Hash判断，然后LCP求出来后就判断那些字符有用到，没用到的贪心最小字典序映射

Bit Twister on a Tree

每一层的节点提取出来，每个询问对应某一层的某一区间的函数值，可以证得区间个数不会太多，所以我们可以离线排序后直接暴力做

Codeforces Round #348 (VK Cup 2016 Round 2, Div. 1 Edition)

C. Little Artem and Random Variable

给两个骰子，给出各个最大值和最小值的概率，求两个骰子扔出各个点的概率

设两个骰子扔出 $x$ 的概率分别为 $A[x],B[x]$，然后我们可以推出 $A[x]+B[x]=min[x]+max[x]$ 和 $\sum max[i]=(\sum A[i])*(\sum B[i])$，这相当于给两个数的乘积以及和后求两数，从左到右推一发即可

Wrong：答案要求总和的误差小于 $1e-6$，用系统内置开根函数（sqrt）的误差累计起来便很容易爆炸，所以手写二分开根

BestCoder Round #81 (div.1)

1003 Robot

有种东西叫做默慈金数……

$M_{n+1}=M_n+ \sum_{i=0}^{n-1}M_i M_{n-1-i} = \frac{(2n+3)M_n+3nM_{n-1}}{n+3}$

GDOI模拟赛 #1

A 房产承包

给定 $a$，求有多少 $b(1\le b \le n)$ 满足 $gcd(a^2+b^2,4ab) \ne 1$

$a \le 10^{12},n \le 10^{18}$

变形条件可以得到 $gcd(a,b) \ne 1~or~(a-b) \equiv 1 \pmod 2$

当 $a$ 是偶数的时候直接查找范围内和 $a$ 互质的数然后减掉，当 $a$ 是奇数的时候就还要判断奇偶性

查找互质个数时可以将 $a$ 分解出质因数然后容斥一发

GDOI模拟赛 #2

C 卡特琳娜打怪兽（？？？？）

$k$ 个武器，初始全部一级，$n$ 轮游戏，每次随机选择一把武器（设等级为 $a$），再随机一把新武器（等级范围为 $[1,a+1]$）若比当前优则淘汰原来武器，否则淘汰新武器，淘汰的武器的价值为其等级，问期望收入

$k \le 100,n \le 100000$，精度要求 $10^{-9}$

设F[i][j]为第 $i$ 轮等级为 $j$ 的期望收入，倒着dp一发，最后乘个 $k$

复杂度 $O(n^2)$，结合精度限制我们可以模拟等级到 $900$ 即可

GDOI模拟赛 #3

B 小B的涂色方案

一个环 $n$ 个格用 $m$ 种颜色染色，相邻不能同色，每种颜色都要用上，且能通过旋转变得一样的方案为本质相同，求本质不同的方案数

$n \le 10^9,m \le 1000$

设满足条件一、二的方案数为 $F(n,m)$，满足条件一的方案数为 $G(n,m)$，则可以推得

$$Ans=\frac{\sum_{L|n}\varphi(\frac nL)F(L,m)}{n}$$

$$F(n,m)=\sum G(n,i)\frac {m!}{i!K(m-i)}$$

$$K(0)=1,K(m)=-\sum \frac{K(m-i)}{i!}$$

$$G(n,m)=m(m-1)^{n-1}-G(n-1,m)$$

就外面弄个Burnside套个奇奇怪怪的函数再套个矩乘