这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.

apio的第二题.其实是我做题顺序里的最后一道. 我的方法比较奇怪.对于p分开讨论.如果p>c那么直接建边,否则在图的旁边再建若干条链,把这个点连到链上去.然后再跑一下最短路. 卡一卡常数就过去啦.

看上去apio的成绩都出来了,那我就可以写题解喽. 这题比较水啊,尤其是在考试的时候允许多次提交,服务器还跑得飞快.强行bitset压位就好了. 按位从高向低贪心. 对于l=1的情况直接求最少的覆盖区间就好了. 对于剩下的情况,用f[i][j]表示前i个数能否用j个区间覆盖. 完了辣

之前觉得好神的题根本没有思路.刚才才发现ovo 发现这玩意其实就是一个堆而且堆里没有相同的元素.那么对于一个点它的方案数就是左右儿子的方案数的积再乘两边大小的组合数ovo 然后被坑了直到看到zyf的题解才想起有可能mod<n.然后得用一个pair来代替原来的数. 无语喽ovo

今天用apio赛制做别人的省选题ovo 第一题直接用O(n3)的dp加剪枝水过去了. 第二题数据结构题无聊ing 第三题比较有意思.首先你需要有足够强的直觉来推出sg函数的感觉,然后还要用高超的常数优化技巧来过题.各种ovo 晚上还有场tyvj有奖赛ovo

看上去像是插头dp啊.然后基尔霍夫矩阵也能做. 关键是模数不是质数,所以不能逆元,所以要用mhy的黑科技,碾转相除来做. mhy太强了ovo

最开始看了一下这是什么gui啊.然后仔细一看发现有玄机. 管aa[1][i]叫a[i]好了.那么b[i]j对答案产生贡献当且仅当a[i]=a[j]=1.b[i][i]对答案产生贡献当且仅当a[i]=1.c[i]对答案产生影响当且仅当a[i]=1. 然后看上去好玄妙啊.其实就是要决定哪些a[i]要选.那不是最大权闭合子图嘛? 数据范围有点大?实测一下飞快啊.

题目好长啊,像个阅读题一样.还是比较有意思的一道题.有点像gorgeous和我说的那个原创题的感觉啊. 首先如果没有加边的话那么答案就是∏indegreeu. 如果加了边之后还是dag那么无影响. 如果加了边之后存在一个scc,那么答案就要减去∑(环*∏其它点的indegree).这个东西可以用随随便便的dp来解决.

无语的智商题啊.居然没人写题解. 首先dp打个表.cnt[i]表示大小为i的二叉树的总个数.当然这个就是catlan数.然后son[i]表示大小为i的所有不同构的二叉树的叶子数的和. 然后经过找规律(翻oeis)发现son[i] = C(2n-2,n-1). 于是就没有于是了.推一下组合数发现answer=n2(n+1) / (n2) / (n*2-1). 代码好无语.

比较基础的期望+高消的题.为了说明一下高消是what,我决定写一发题解. 首先题意是有个n个点m条边的无向图.有两个人初始位置是a和b.每个时刻每个人在一个点有p_i的概率不动,否则等概率移动到相邻的点.只有在同一时刻在同一个顶点上才算相遇.相遇了他俩就玩去了.求在第i号点相遇的概率. 首先方程很好列.定义一个状态f[i][j]表示第一个人在i,第二个人在j的概率.那么f[i][j] = ∑ f[k][l] * ptrans(k,i) * ptrans(j, l),其中ptrans(a,b)表示从a移动到b的概率. 然后这个东西就用高消嘛.(upd:才发现它叫gauss而不是guess.捂脸ing) 高消就是说每次把剩下的方程里的第一个系数不为0的未知数的系数全部通过减某一个方程来把这个系数都消成0.当然被减的方程得留下系数过会再用于推答案.然后就可以不管这个被留下的方程了. 换句话说,如果把方程组看成t*(t+1)的矩阵的话,其实就是消成一个右上三角. 然后再倒着推出每个未知数的值. 这个直接算比例就完了嘛.然后有一种情况是当前a[i][i]已经为0了,那么减不掉?反正所有方程的顺序没有关系啊.你就随便找一个不是0的到前面来消就好了啊.如果剩下方程的这一个系数都是0,那这个未知数取啥就无关了.也无所谓啦. 详见代码.