这是$ZGJ$升上高中之后，考得很好的一次比赛，虽然也有很多遗憾

阅读更多……

题目大意

有$m$条路径在一棵有$n$个节点的树上，问每个点恰为多少条路径起点出发$w_i$长度处

阅读更多……

$ZGJ$傻傻的参加了第一次$NOIP$提高组

阅读更多……

题目大意

给出一个$n$个节点的树，还有$m$条路径，并且保证边权$(t_i)$满足$0\leqslant t_i\leqslant 1000$

要求将任意一条边的边权变为$0$后，询问这$m$条路径上边权总和的最大值最小是多少

阅读更多……

题目大意

一共有$n$个城镇，第$i$个城镇到第$i+1$个城镇有一条收费$c_i$的单向道路

除此之外，再给出$m$个单向传送门，可以从传送门规定的起始地去往目的地，同样需要收费$w_j$

但它传送成功的概率只有$p_j$，失败会传送回起始地，并且无论成败，使用了传送门就需要花费$w_j$

现在若要从第$1$个城镇前往第$n$个城镇，询问最小期望花费

阅读更多……

$Day1$

进考场之后领了题目，密码是“题目很简单”，然而…

做题顺序$2-1-3-4$

$T1$,因为上课的时候一直在说线段树，所以做题的时候一直套进线段树里做，发现并不会合并区间，也没有意识到换一个思路，比如拆位来做会好得多，拿走$30$分

$T2$,由于题面上有说整个都是单向往后，所以我直接就想到了$dp$来做，$dp[i]$表示从起点走到$i$点的最小期望，所以通过判断是不是通过某个传送门到的这个点来转移状态，但是可能细节写错了，一分没拿，好伤…

$T3$,一开始看到［条件式收益］，就确定是最大权闭合子图。然后手画了一下，发现点上要记录两个值，伤害值和财富值。并没有意识到这就是建图的正负…反而困死在"&#%…两个值我怎么跑最小割!"的想法里。最后身手敏捷地避过了正解，暴力$10$分$get$

$T4$,不会做，暴力也不会写

$Day2$

做题顺序$2-4$

$T1$,看完题也不知道最优策略是啥，直接放弃

$T2$,看到这个数据范围就猜是不是数位$dp$啊！然后在纸上乱涂乱画写出了递推式，样例过了之后非常开心的以为今天好歹写得出一次正解，下午听讲评的时候发现正解也是数位$dp$，但是递推式和我写的相差甚远，然后知道自己写的三维可能写粗了，最后统计的时候会比标程麻烦得多，或许就是在那里写跪了，最后一分没拿

$T3$,似曾相识的题面 又是$m$算法，然而我不会做

$T4$,时间不够，草草打了个暴力，$10$分都不给我...

总结

这是初中最后一次koi了，年年都这么凄惨，不过可能年纪大了，会写几道题的正解了，但是两道都写粗了，真是拉低初三大老爷们的智商了，还是该整理代码风格多对拍…

题目大意

有$n$个程序$:p_1,p_2 \cdots p_n$，程序$p_i$已经占用了$a_i$个单位内存，还需要$b_i$个空闲内存就能结束运作，然后返还内存$a_i+b_i$

整台机子运作了$m$分钟，每分钟都有且只有一个程序改变了它的状态($a_i,b_i$),求在那一分钟至少需要多少空闲内存才能运作所有程序

阅读更多……

题目大意

给出一个数列$A:a_1,a_2,a_3 \cdots a_n$

执行$m$次询问，每次给出区间$[l,r]$

在$[a_l,a_r]$中选一个数$x$

在$[a_1,a_{l-1}]$或者$[a_{r+1},a_n]$中选一个数$y$

求$gcd(x,y)$最大

阅读更多……

【$T1$】金币

题目大意

国王给忠诚的$Saber$发工资，当连续的$n$天每天收到$n$枚金币时，$Saber$会在之后的$n+1$天每天收到$n+1$枚金币

询问在前$k$天一共怒领多少工资

数据范围

$1\leqslant k\leqslant 10000$

题解

考你会不会编程咯

【$T2$】扫雷游戏

题目大意

给出一个$n\times m$的矩阵，矩阵中每个地雷格位置已知，求每个非地雷格八个邻格上的地雷总数(左上左下右上右下正上正下正左正右)

数据范围

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 100$

题解

考你会不会编程咯

【$T3$】求和

题目大意

给出$n$个格子，编号是$1~n$，每个格子染了一种颜色$Colour_i$，而且写了一个数字$Number_i$

若有两个不同的格子编号$x,z$满足奇偶性相同，且格子颜色相同，则这个二元组对答案的贡献是$(x+z)\times (Number_x+Number_z)$

求最终答案除以10007所得余数

数据范围

$1\leqslant n,m,Number_i\leqslant 100000,1\leqslant Colour_i\leqslant m$

题解

$(x+z)\times (Number_x+Number_z)=x\times Number_x+x\times Number_z+z\times Number_x+z\times Number_z$

则每个格子$x$在每个合法的二元组($x,z$)对答案的贡献是$x\times Number_x+x\times Number_z$，然而时间复杂度是$O(n^2)$，怎么办呢？

可以记录集合$S$，使得在集合$S$中的格子两两可以组成一个合法的二元组，然后用$size$表示集合$S$的格子个数，$sum$表示集合$S$中的$\sum Number_i$，则集合$S$中的格子$x$对答案的独立贡献就可以表示为$$x\times Number_x\times (size-1)+x\times (sum-Number_x)$$

最后$O(n)$扫过去就好啦

【$T4$】推销员

题目大意

给出一个有$n$个数字的数列，数字的编号是$1-n$

选取k个数，假设其中编号的最大值为$m$，那么得到一个叫做疲劳值的东西，等价于$2\times m+k$个数的总和

询问当$1\leqslant k\leqslant n$时的$n$个当前最大的疲劳值

数据范围

$n\leqslant 10^5$

题解

用线段树维护数列最值，每当$k$增加，就取区间最值就好啦