https://codeforces.com/contest/1942

E. Farm Game(2s,256mb)

在 区间[1,l]整数点上 放 ABABAB…或者BABABA… 一共n组AB或BA, 坐标不一定相邻

• 玩家X可以选择任意多个X(和玩家ID相同),和一个方向（左或右），把所有选中的A沿着这个方向移动
• A先B后
• 移动过程中字母不能重叠 不能出[1,l]范围，如果无法移动则输掉

问 给定$l,n$ 有多少个初始状态 玩家A获胜

我的思路

很像nim的游戏之类的

那么考虑 每个AB之间的空位的和，如果空位和为奇数，那么总可以移动那个位置让AB之间的空位和减1,而对于空位和是偶数，不一定能增大，也不一定能减少，但只要是能操作则结果也是奇数，

如果一轮操作后 空位和不变（否则变小），那么对应位置整体向同一个方向移动了两个字母

所以 获胜状态 = 所有AB间隔 空隙和=奇数

那么 l个位置 去掉 2n个占用位置，实际是切割成2n+1个 >=0 的段

也就是 l-2n长度线段切割成 2n+1个 >=0整数段 且 偶数index的段的长度和=奇数

考虑所有段+1

(l-2n)+(2n+1) 段 切割成 2n+1个 >=1 整数段,且偶数index的段的长度和 = 奇数+n

考虑 做顺序的置换，把所有偶数index段直接移动到最前，则方案还是一一对应

(l-2n)+(2n+1) 段 切割成 2n+1个 >=1 整数段,且前n段的长度和 = 奇数+n

1
2
3
4
5
6

for 前n段的长度和 = i:
 if i % 2 == (n+1) % 2:
  ans += (i 切割 n)段 * (l+1-i 切割成 n+1) 段, 每个切割段 >=1

长度 x 切割成y个>=1整数段，相当于 x-1个切割点中选择y-1个切割点
cut(x,y) = binom(x-1,y-1)

最后答案 AB和BA反向需要乘上2

然而 pretest1都没过 https://codeforces.com/contest/1942/submission/256178349

然后我发现读错题了，是 一次可以移动任意多个同方向，而不是一次一个

那么思路也完全一样，就是 去挤压另一个

所以 如果 存在 > 0 个奇数空位，则A 总能 把这些 奇数空位全变偶数（0个奇数空位）

如果 存在 0 个奇数空位，则全为偶数空位，则操作不确定，且操作后至少一个奇数空位

所以 方案 = 所有方案 - 全偶数空位方案

一样的

l-2n个位置切割2n+1个>=0整段，其中偶数index的长度全偶数

(l-2n)+(2n+1)=l+1个位置切割2n+1个>=1整段，其中偶数index的长度全奇数

l+1个位置切割2n+1个>=1整段，其中前n段的长度全奇数

1
2
3
4
5
6
7

for 前n段长度和为i, i % 2 = n * 1 % 2:
 把 前n段每个长度+1, 则 前半
  i+n长度 切割成 n 个 >= 2的偶数段 (那么每2个看成一个)
  (i+n)/2 长度 切割成 n 个 >= 1的整数段
  也就是 cut((i+n)/2,n)
 cnt += cut((i+n)/2,n)*cut(l+1-i,n+1)
  

ans = (binom(l,2n)-cnt)*2

https://codeforces.com/contest/1942/submission/256179100

https://atcoder.jp/contests/abc347

G - Grid Coloring 2

n * n

a[i][j] \in [0,5]

可以把0改为 1~5

所有操作后

代价=4临的差的平方和

求 最小代价的具体方案

n 20

2s

1024mb

我的思路

一个是插头dp 但是边界状态是 $5^n$

不知道怎么利用15,因为只关心差，可以变换成 `-22`但没感觉有什么帮助

有想网络流，但是不知道怎么表示 选与代价的关系。

$(x-y)^2=x^2-2xy+y^2$ 感觉就是这个2xy不知道怎么处理

https://codeforces.com/contest/1943

D1,D2 Counting Is Fun

如果数组 每次可以 选择连续长度大于1的区间 同时减去1,操作多次以后 所有值变为0,则该数组是好（good）数组

对于 长度n,值范围[0,k]的 $(1+k)^n$个数组有多少个是好数组 $\mod p$

n D1(400),D2(3000)

$\sum n^2$, D1(2e5),D2(1e7)

$k \le n$

$p\in[10^8,10^9]$ 是质数

3s

1024mb

我的思路

good的充要条件？

首先 两端 不大于a1

如果出现连续3个$a < b > c$

要$b-a\le c$ (b,c同时下降 直到b变为a)或$b-c\le a$ (a,b同时下降 直到b变为c)

都是$b\le a+c$

所以 如果good 一定满足 上面的 两端 和 单峰的条件

那么如果满足 两端 和 单峰条件

对于单峰从左到右, 下降，每个前面的不影响后面的，

因此 这个条件是充要

就dp吧

dp[i][x][y]= 前i-1个位置合法，第i-1个位置是x,后一个是y的方案数

从第二项开始

然后 ans = sum dp[n][>=x][x]

对于$x\le y$

dp[i+1][x][y] = sum dp[i][...][x]

对于$x > y$

dp[i+1][x][y] = (sum dp[i][t][x], x <= t+y )=sum dp[i][>=x-y][x]

所以

dp[i+1][x][y] = sum dp[i][>=x-y][x], 其中 dp[i][<0][x]=0

用 后缀和可以 均摊 O(1) 计算每个x,y

所以有一个 $n n^2$的方法，感觉能过D1, 然后D2 明显TLE

感觉就是需要再次优化效率，然而上面的似乎并不能nxn的矩阵的矩阵乘法

然而 并没有成功优化

https://atcoder.jp/contests/abc345

E - Colorful Subsequence

n个球 一排，有价值vi,颜色ci

问 恰好删除k 个且 剩余球 相邻不同色，vi和最大值

或不可能输出-1

n 2e5

k 500

v [1,1e9]

5s

1024mb

我的思路

可行性，首先同色连续t个，那么至少删除t-1个，那么留最大的

做完操作后满足了 相邻不同色，再看 恰好删除k个

只需要从两侧删除就可以满足恰好k个了

所以先处理所有连续 变为不同色

然后 不知道怎么搞，感觉需要 nk的复杂度的， 但只想到 nk2的

dp[i][t] = 前i个第i个保留，一共删除t个且合法的最优方案

dp[i][t] = a[i] + max(dp[i-1-d][t-d]) 表示从i-1向前连续删除了 d个的方案, 其中 c[i] != c[i-1-d]

处理边界只需要 两端塞入 {v=0,c=max color+1/+2} 即可

然而上面是 nk的状态 和 k倍的转移代价，所以时间上是 nk2的

两端塞了以后 0 [1...n] 0

ans = dp[n+1][k] = f[n+1][n+1-k]

一个想法是

令 dp[i][0<=t<=i] = f[i][i-t]

f[i][i-t] = a[i] + max(f[i-1-d][i-1-t]), a[i] != a[i-1-d]

还是不知道怎么处理这个不等，而且 这样转换的话，第二个维度的值会很大

但 如果对应到 二维 定义域平面上的话

1
2
3
4
5
6
7
8

            x
           x
          x
         x
t+      x
^      x
|     x
 -> i+

其中

a[i]!=a[i-1-d] 的处理？？？？

https://ac.nowcoder.com/acm/contest/76652

D S 老师的虚树

给n点定树T，边有颜色

对于 点集S,包含点集S的最小连通点集V’对应的树为生成树T’

w(S)=T’中不同颜色边个数

对于 i=1..n

计算 |S|=i的w的期望Exp(w(S)),结果mod 998244353

n 2e5

2s

512mb

我的思路

感觉就是算贡献，对于点为i的 点集合，对于颜色c的所有边来说，如果有横跨 边的两个点，那么贡献1,否则贡献0

那么考虑不跨边更简单，也就是 贡献i,c=所有情况 - 不跨边

$= \binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$ 其中 blk是按照指定颜色切割的块

那么 $ans_i= C\binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$,其中C是颜色总个数,blk是所有颜色独立的切割

那么问题来了，每个颜色切割的块数 = 当前颜色边数+1,

所以右侧有 n+C个 <=2n, 但是直接计算，对于每个i来说复杂度也是 $O(n)$的,总的复杂度会tle

生成函数我也想过没想过怎么简化