路终会有尽头，但视野总能看到更远的地方。

题目大意

有一个$n\times m$的矩阵，有一些点不能经过，现在从第一行开始每一行选一个点，下一行选的点必须比上一行靠右，问不经过障碍点的方案数。

题目吐槽

暴力膜蛤不可取，膜蛤不当必被续。

题目大意

你每天可以讲一段长度为$x$的区间染色，每天有香港记者将一段区间染色，询问最少几天可以将区间全部染色。（每个点全部被染色）

题目吐槽

暴力膜蛤不可取，膜蛤不当必被续！

题目大意

给定两个正整数$n$和$G$，其中($1\le n,G\le 10^9$)，求下面表达式的值。

$$G^{\sum_{i\mid n}C_n^i}\bmod999999599$$

题目分析

与古代猪文几乎一样，双倍经验。

题目大意

远古时期猪王国有$n$个文字，现有的文字数量为远古时期的$\frac{1}{k}$（$k$是$n$的一个正约数），因为不知道是哪$\frac{1}{k}$，因此剩余的$\frac{n}{k}$有很多种情况，假设有$p$种情况，则研究这些文字的代价为$g^p$，求这个代价对 $999911659$取模后的结果。
$1\le n,g \le 10^9$

中国剩余定理解决线性同余方程组的方法，在数论中占据重要地位。

中国剩余定理（CRT）

若$m_1,m_2,\ldots,m_k$为互素正整数，则同余方程组：

有模$M=m_1\times m_2\times\cdots \times m_k$的唯一解。
解为：$(M_1M_1’a_1+M_2M_2’a_2+…+M_kM_k’a_k)\bmod M$
其中$M_i=\frac{M}{m_i}$,$M_i’$是$M_i$模$m_i$的乘法逆元。
因为模数必须互素，因此CRT的应用受到限制，如果模数不互素可以考虑拆成互素或使用扩展欧几里得求解线性同余方程组（即扩展中国剩余定理）

题目大意

有三个颜色，每个颜色的点数为$a,b,c$，现在在点之间连边，使得任意两个相同颜色的点间要么不存在路径要么路径长度$\ge 3$。

依然是酱油记，前几场打得太差不想发游记了。

比赛题目

A. The Artful Expedient

题目大意： 判断$a_i\,xor\,b_j$是否出现过。
题目分析： 好像可以直接输出Karen，我用的Hash，记得将Hash范围开大。

题目大意

Change k w：将第k条树枝上毛毛果的个数改变为w个。
Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。
由于毛毛虫很贪，于是他会有如下询问：
Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

阅读全文 »

题目大意

“量子态的字符串”非常顽固，只能先分割成若干个子串，然后再通过以下两种方式删除：
1、假设子串的所有字符的删除难度之和为x，消耗a*x^2+b的时间可以将子串扔进回收站。
2、若子串中出现次数最多的字符出现的次数不少于L次且不多于r次，那么采用“量子态的py自动机”算法可以消耗c*x+d的时间将子串扔进回收站。
Abwad自然知道最少用多少时间就能将字符串删去，因此，他希望你求出删去每个前缀[1,i]的最少用时。

题目分析

任意分割显然可以转化为分割一次，对原问题没有影响，那么我们便可以转化为子问题，可以用动态规划解决。

设$f[i]$表示删去前缀$[1,i]$的最少用时。
不难得出状态转移方程：

题目大意

给定一个n个点m条边的无向图，定义一条路径的长度为路径上最小边的权值。
定义dist(i,j)为起点为i，终点为j的长度最长的路径的长度。求出第k大的dist(i,j)(i\<j)。

题目分析

这道题似乎可以直接Kruskal的时候处理一下即可。
但是我比较喜欢Kruskal重构树。
关于Kruskal重构树可以看看这里。