https://atcoder.jp/contests/abc326

G -  Unlock Achievement

n个技能 初始等级1

m个成就

第$i$个成就需要 $\forall j, \mathrm{level_j} \ge L_{i,j}$ 就可达成，获得$A_i$奖励

而第i个技能的 每升级一级等级需要$C_i$代价

求最大 奖励减去代价

n,m 50

$L_{i,j} \leq 5$

$A_i,C_i\in [1,10^6]$

2s

1024mb

我的思路

如果确定了成就达成，那么对应的技能提升也就是 对应的技能等级的max

也就是给定了成就达成，需要O(NM) 完成计算 奖励减去代价

而注意到 ai都是正数，所以 如果指定了成就， 即使升级技能达成了额外成就，这样只会比当前的 结果更大，

如果 for 所有成就达成组合， ans=max(ans,计算代价()), 那么忽略额外达成的成就不会影响结果

然后发现这里没有用到的是 Li,j <= 5

然而似乎li,j = 1 or 2都没有特别的思路

如果n更小，且 lij被限制在1/2, 那么

可以dp[前i个成就][mask 技能] = 最大收入和

而n 现在范围有50,而且 lij 是[1,2,3,4,5] 所以 这种 状态会有

dp[前i个成就][技能需求state 5^n] = 最大收入和

1

5^50 = 88817841970012523233890533447265625

1

2^25 = 3355'4432

https://atcoder.jp/contests/abc324

G -  Generate Arrays

给定一个 1~n的排列p

S[0] = p

q个操作

• 1类，选定S[s_i]把 idx>= x_i的删除
• 2类，选定S[s_i]中 所有 值 > v_i的删除
• 操作后 让S[i]=删除的原顺序的序列，并输出S[i]的长度

n 2e5

q 2e5

6s

1024mb

我的思路

二维平面点 (i,p[i]) 然后 每个序列对应一个矩形

每个操作对应一次矩形分割

用 vector<map>的fenwick

但是 似乎多写了一层二分，多了log 导致acx36,tle x25

我这个似乎是$Q(\log N)^3+N(\log N)^2$

https://atcoder.jp/contests/abc323

G - Inversion of Tree

给定一个 1~n的排列p

1
2

for k = 0..n-1:
	求 对于n点树，满足((边端点 点的idx大小 和 p[点idx]大小 是相反的) 的边的个数 == k) 的树的个数 mod 998244353

n 500

4s

1024mb

我的思路

因为这里要的相反不是 父子和p相反，而是index和p[index]相反， 所以如果要选根，选1就行

然后问题是 如果在树上做dp,不光要记录满足树和子树的点树，还需要记录哪些点已经用了，感觉这状态有点多

注意到$n\le 500$是有点小的，可能有$n^2,n^3$的考虑的方向，但实际上这里还有一个k,所以可能是$nk,n^2k,nk^2$一类的

但直接的思路还是没有

然后就是插入新点的想法

如果有一个n-1点的方案，那么对于 p[1]...p[n-1]需要把所有大于$p[n]$的p进行减1,这样就是规模减1的子问题，

但是问题是，这样的话，并没有看出n-1到n的转移

首先钦定了根是1，所以(n,p(n))不是根，如果它是叶子，那么 一个n-1树上原来叶子p[叶] >= p[n] 都会贡献到对应的k+1, 而原来p[叶] < p[n] 会贡献到k

那还不用说非叶子的，光是这里，就需要记录叶子的p和更大的p之间的关系的个数，那么更小的层数时要记的关联太多了

似乎连一个暴力的计数法都没有

然后 如果 == k难求，可以考虑求 $\le k$ 然后做相邻相减

https://atcoder.jp/contests/abc321

G - Electric Circuit

3种点

n个 part点

m个红点

m个蓝点

给定每个 颜色点连到一个part点

然后红点和蓝点的直接连线 需要单射且满射，那么有m!种

对于所有连法 求 Exp(连接后的连通块个数)

n 17

m 1e5

3s

1024mb

我的思路

n 很小想用bitmask

首先根据 n来整理，变成 有n个点，每个点有ri个红色，bi个蓝色

然后要把所有红蓝相连，求连通块的个数期望

1
2
3
4
5
6
7
8
9

f[mask] = mask内连成一个连通块 且无剩余蓝红的方案数
g[mask] = mask内无剩余蓝红的方案数
ans[s] = sum s的所有方案的连通块个数
ans[s] = for mask, mask 包含最小点
		f[mask] * ans[s-mask] 两边互不影响计算右边贡献
		+ f[mask] * g[mask] 计算左边贡献

g[mask] = sum红! , 满足sum红==sum蓝
f[mask] = g[mask] - sum f[submask]*g[mask-submask], submask包含mask中最小的

似乎就AC了

https://atcoder.jp/contests/abc320

G - Slot Strategy 2 (Hard)

n个只包含’0’-‘9’的长度m的字符串在旋转

对于一个时刻 最多停止一个字符串旋转，字符串展示字符s[i][t%m]

问 最少多少时刻 让所有字符串停止，且展示的字符一样， 或无方案

n 100

m 1e5

2s

1024mb

我的思路

注意到 只包含数字，而数字只有10个，所以可以指定数字比较方案优劣

那么对于给定数字以后，每个字符串将变成一个0/1 bool串，其中 true表示 对应位置是要指定的结果数字

有一点想搞可反悔的dp

首先如果每个字符串都有指定数字才有可能，这样就是依次来都是一个方案，只是可能不是最短时间

但实际上可以变成二分图

首先 左侧是 字符串id, 右侧是可以逐步增加点的的时刻, 只要有对应位置就建立一条边

这样如果有 ans = |n| 就是答案， 这样最坏的情况是 n*m个右侧点，也就是所有字符串都集中在一个循环时刻上了

这里可以优化一下 右侧增点的过程，把与左侧无连接的点直接预处理掉，变成 [offset,vector<int>left]

那么每次增加 至少增加一次连边，

想用hall定理，也就是什么时刻 左侧的任意点的右向连接数一定大于左侧点数， 这个量级的上限

因为每循环一轮，所有左侧点连的点个数 至少增1,所以 总边数不会超过n^2

似乎就没了， 然而TLE了2个点