这两天有幸参加了CQOI 2018，觉得非常的——，就来更一发博客。 今年的CQOI怕不是历年最惨的一次，题目全是一眼题以至于进队全靠NOIP？ Day1T1一眼BSGS，模板题，没有任何意思。 T2一眼矩阵树，模板题，没有任何意思。 T3一眼数学题，推一推发现了一个$O(n)$的算法，然后发现模数小没有逆元，就把质因子提出来预处理了一发。感觉$n=10^7$卡着$1s$非常的抖，觉得卡卡常应该 ...

【CQOI2014】通配符匹配问题描述 几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号“*”，可以匹配0个即以上任意的字符；另一个是问号“?”，可以匹配恰好一个任意字符。 现在需要你编写一个程序，对于给定文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。 输入格式 第一行是一个由小写字母和上述通配符组成的字符串。 第二行 ...

【CQOI2014】数三角形问题描述 给定一个$n\times m$的网格，请计算三个点都在格点上的三角形共有多少个。下图为$4\times 4$的网格上的一个三角形。 注意三角形的三点不能共线。 输入格式 输入一行，包含两个空格分隔的正整数m和n。 输出格式 输出一个正整数，为所求三角形的数量。 样例输入： 1 1 样例输出： 4 提示 对于30%的数据，1<=m,n ...

【CQOI2014】危桥问题描述 Alice和Bob居住在一个由N个岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路都是双向的，但是一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。 Alice希望在岛屿a1和a2之间往返an次(从a1到a2再从a2到a1算一次往返)。同时，Bob希望在岛屿b1和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其 ...

【HAOI2017】供给侧改革问题描述 Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。 为了提高供给品质.你调查了某个产业近来 $ n $ 个时期的供求关系平衡情况.每个时期的情况都用 $ 0 $ 或 $ 1 $ 中的一个数字来表示.于是这就是—个长度为 $ n $ 的 $ 01 $ 字符串 $S$ 。为了更好的了解这一些数据.你需要解决一些询问.我们令 ...

【JSOI2016】扭动的回文串问题描述 JYY 有两个长度均为 $N$ 的字符串 $A$ 和 $B$。 一个「扭动字符串」$S(i,j,k)$ 由 $A$ 中的第 $i$ 个字符到第 $j$ 个字符组成的子串与 $B$ 中的第 $j$ 个字符到第 $k$ 个字符组成的子串拼接而成。比如，若 $A=$’XYZ’，$B=$’UVW’，则扭动字符串 $S(1,2,3)=$’XYVW’。 JYY 定义 ...

【BJOI2017】魔法咒语问题描述 Chandra 是一个魔法天才。 从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。 直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。 根据火之魔法规则，禁咒的构成单位 ...

首先求出$[L,R]$中有多少个数比$F[i]$大，这个用主席树来处理就行。 然后问题就转化成了有$n$个数，其中有$k$个满足条件的数，然后随机取$x$个数，$x$随机产生，问选出的所有数都是满足条件的数的概率。 考虑枚举$x$，那么令$P[x]$表示选$x$个数都满足条件的概率,那么 $$Ans=\frac{1}{n}\sum_{x=1}^{k}P[x]=\frac{1}{n}\sum_{ ...

这题感觉比较奥妙重重，标解给了一个麻烦的状压dp，但是好像直接将每个位置的期望值代进去算行列式的值就行了。 具体原理大概是因为各个位置都是相互独立的随机变量，那么他们的期望可加也可乘，那么就可以直接将行列式求期望值的式子展开成各个位置的期望再求行列式了。 代码： 12345678910111213141516171819202122232425262728293031323334353637 ...

这个题比较简单，考虑先找到树中最高的节点$x$，那么水位有两种情况，要么各个子树的水位都不超过$H[x]$，要么大于$H[x]$就会让所有点的水位的一样，因此可以直接递归处理出子树的方案数$F[sub]$， 那么$F[x]=\prod F[sub]+m-H[x]$，直接暴力分治下去就行了。 这题可以用排序并查集或者一种快速查找区间最大值的数据结构优化成$O(n\log n)$，但是数据范围小， ...