10.5 Morning

Test

$T1$ ： $travel$

有$N$个城市围成一圈。第一次到达第$i$个城市时，得到$A[i]$块钱($A[i]$可能为负数)，从城市$i$到达下一个城市时（只能从$i$到$i+1$或者从$n$到$1$），需要花费$B[i]$元。一开始$LYK$有$c$元钱，并且从任意一个城市出发沿环走一圈并回到这个城市，要求旅途过程中保证钱非负。问从多少个点出发是可行的。

首先我们知道这个$B[i]$并没有什么卵用，由于$B[i]$非负，所以它完全是可以和$A[i]$合并的。那么首先我们可以设$V[i] = A[i] - B[i]$。然后复制一下N把圈变成一行，
$1.$ 第一种方法：直接暴力模拟，从每一个i开始跑一圈。复杂$O(N^2)$可以过$60$%

$2.$第二种方法：我们考虑对于一个$i$，以$i$为起点造出来一个前缀和，那么我们需要考虑的就是所有的前缀和$Sum[j]$中最小的那个，看它加上$C$是不是小于零。但是比较郁闷的就是这个前缀和的起点并不是固定的。因为这里你设的起点是i。那么我们要做的就是做一个把$i + 1$之后的前缀和做一个区间修改。那么考虑用线段树。时间复杂度为$O(NlogN)$可以$A$掉。

$3.$ 还是第二种方法前缀和，但是我们考虑到一个傻逼的事实。这个用线段树实现的区间修改给我的答案决定于哪个$j$有任何作用么？...没有。所以果断把刚才最小的前缀和修改掉下一个$i$进行判断就完了。

$T2$ : $pit$

$LYK$有一个$N\times N$的棋盘。它恰好有$2\times N$颗黑棋和$N$颗白棋，将其全部放到棋盘上，有这几个要求：
$1.$ 每个位置最多放一个棋
$2.$ 每行每列都恰好有$2$颗黑棋
$3.$ 每行每列都恰好有$1$颗白棋
求方案数 % $P$的大小。
对于$20$%的数据$n<=4$。
对于$40$%的数据$n<=6$。
对于$60$%的数据$n<=10$。
对于$80$%的数据$n<=50$。
对于$90$%的数据$n<=200$。
对于$100$%的数据$3<=n<=1000$，$2<=p<=10^9+9$。

首先，你需要一个$Oeis$（滑稽）。全分的做法太难了，这里只给出一个公式：$a[n]=(n-1)*(2*(n^3-2*n^2+n+1)*a[n-1]/(n-2)+((n^2-2*n+2)*$
$(n+1)*a[n-2] +(2*n^2-6*n+1)*n*a[n-3]+(n-3)$
$*(a[n-4]*(n^3-5*n^2+3)-(n-4)*(n-1)*(n+1)$
$*a[n-5])))/(2*n))$
看，是不是很简单（逃
我们一点一点来，先争取拿到一点部分分再说。我们知道第$N$的答案位数小于$10N$，可以高精度把$N$项的答案算出来再对P取模。
我们在知道棋子得一行一行放的情况下，先进行最暴力的Dp。先不计代价地设一个$Dp[i]$然后后面跟着一堆状态。我们进行行的枚举的时候，是强制一行有一个白棋，两个黑棋的，所以我们只要考虑列的情况。然后我们知道所有的情况是这样的：
$1.$ 0白 $0$黑
$2.$ 0白 $1$黑
$3.$ 0白 $2$黑
$4.$ 1白 $0$黑
$5.$ 1白 $1$黑
$6.$ 1白 $3$黑
一共有六种情况，所以我们只要考虑六种情况各出现了多少次就可以了，所以我们得出来了一个$7$维的$DP[i][a][b][c][d][e][f]$。时间复杂度为$O(N^7)$然后我们考虑消维。
我们知道对于$1$白和$0$白，是分别独立的。我们可以知道：
那么我们知道$a + b + c + d + e + f = N$则可以消掉f的状态。变到$O(N^6)$
我们知道一行放了$1$个白棋，我们枚举到第$i$行的时候自然有$i$个白棋。所以$d + e + f = i$ 所以我们又消掉了一维，然后$O(N^5)$。
我们还知道对于黑棋现在一共有$2 * i$个
所以$b + 2 * c + e + 2 * f = 2 * i$ 然后我们变成了$O(N^4)$的复杂度。这样是可以过掉$n <= 50$的数据，大概是可以得$80$%的分。
而至于满分做法。
...
...
去他妈的吧。

$T3$ : $holyshit$

你现在有$N$个数$A_{i}$，要求找出两端互不相交的区间，使得不存在任何一个数在这两段区间中总共出现的次数超过1次。求最大化这个区间长度。

并查集树 + $Dp$。
...
...
$Holyshit$,去他妈的吧。