https://atcoder.jp/contests/abc311/tasks/abc311_h

Ex - Many Illumination Plans

N点，根为1，树

点有b[i],w[i],c[i]=0/1

Q(v) = $\max \sum b_i, i\in U$ ，其中U是，v的子树U, 任意多次 删除点 并将子点和父节点相连， 最终满足$\sum w_i \le X$ 且 所有边的端点的c不同

求$Q(1),Q(2),…,Q(N)$

n 200

$X \in [0,50000]$

$W_i \in [0,X]$

$B_i\in [0,10^{15}]$

3s

1024mb

我的思路

先考虑其中一次的问题求解,

也就是给定一个有 点b[i],w[i],c[i]=0/1的树

然后删除点，让sum b尽量大，且满足 颜色 和w和的条件

---

dp[v] = w->b 保留v, v以下的和为w, 能得到的最大b

根据限制 传递时 只和 w与v的颜色有关

这样的问题是，要转移的话，每个v需要的就是所有后继不同色的点，并且还要考虑 后继点的关系

---

改一改

dp[v][c] = map<> w->b v或以下对上颜色贡献为c 和为w, 能得到的最大b

这样就是3个分支

• 选择v，w[v] + dp[u][c[w]^1]的合并
• 不选择v，颜色=0 的 dp[u][0] 的合并
• 不选择y，颜色=1 的 dp[u][1] 的合并

状态数 $O(n X)$ ,但转移代价似乎有点大，可以启发式合并吗？

然后启发式合并的一点是 每次会有一个很大的状态是不变的，每次把新增的相对小的状态向大的状态里塞，而这里每次选择v的话，可能有一个大的偏移

而且如果w是1,2,4,8,这样的话，只需要16个,2^16=65536 就可以让状态是满的

---

一个想法是 能不能 强制 让 b随着w单调递增，这样即可以让状态是连续的，又可以保证非严格单调递增

用更小的w 对应更大的b 去覆盖了更大的b， 如果这样的到了答案，那么对应选择的w一定是大与等于 实际的w的，不会不合法？

那如果有最优方案，关心对应的同样的w，如果被其它覆盖了，那么b一定更大，且有对应的合法w方案

---

这样的话 每个 dp[v][c] = 一个非严格单调递增的数组w2b

需要合并n次? 如何高效的合并？ merge(A,B) = C, C[i] = max(A[j]+B[i-j],j=0..i)

单调递增也保证不了 变化程度

https://atcoder.jp/contests/abc310/tasks

Ex - Negative Cost

$h \in [1,10^{18}]$

p = 0

n个($[1,300]$) $c_i [-300,300]$,$d_i [1,10^9]$

每次可以 任选一个p(可重复选), 满足$p \ge c_i$, 然后 $p -= c_i$, $h -= d_i$

问最少多少次 让 $h \le 0$

3s

1024mb

我的思路

先预处理数据

sort pair{ci,di}

对于 $c_i \le c_j, d_i \ge d_j$, 舍去 {cj,dj}

因为首先单次ci代价越小,di越多越好

---

dp[i][t][p] = 前i个 操作t次, p的结束值 能消耗最大的h

dp[i][t+k][p-k*ci] = max dp[i-1][t][p]

显然空间都存不下

---

考虑预处理后的数据

排序后前部分的 -k*ci > 0

https://codeforces.com/contest/1844

G - Tree Weights

n个点 有边权(wi > 0权重未知)的树

给所有 i到i+1简单路径的长度di

求任意一个合法的边权方案,或者无方案

n 1e5

di [1,1e12]

5s

256mb

我的思路

根不影响点间距离和边长,因此直接把1选做根

首先 可以 n log n 算所有 i与i+1的 lca

$u_i = lca(i,i+1)$

$path(i,i+1) = path(i,u_i)+path(i+1,u_i) = dep_i + dep_{i+1} - 2 dep_{u_i}$

所以可以得到一个 $(n-1)$行$(n+1)$列(其中一列是增广列) 矩阵

尝试求正解即可

它是一个 系数矩阵非零项 不多于 $4(n-1)$

---

然而 并不会解稀疏矩阵, 还要把距离弄正

题解

跟我想的一样 也是 先去掉树变成单纯的线性代数问题

然后神奇的来了,

https://atcoder.jp/contests/arc058/tasks

E -  Iroha and Haiku

有多少个 长度n,值域 [1,10]整数的数组a 满足 子区间

sum a[x..y) = X

sum a[y..z) = Y

sum a[z..w) = Z

答案mod 1e9+7

n [1,40]

x [1,5]

y [1,7]

z [1,5]

4s

512mb

我的思路

范围这么小,可以打表!

想的还是 容斥暴力

总状态 =[5的实际状态][7的实际状态][5的实际状态]

考虑首个匹配在哪个位置,

sum (a[i…] 满足, a[<i…] 不满足)

问题是转移的话,似乎并不好转移

积木 BD202205

似乎测试数据太弱了

题意 给定a[1..10] <= 1e11, h <= 1e12

对于任意b, 求min(max(sum b[i] * i), h), b[i] \in [0,a[i]] b[i]是整数

2s

512mb

我的思路

似乎没官方题解

我最开始想的用bitmask, 去做 dp, 按照不同顺序，有贪心最多

但是实际上 h=10, a[2] = 3, a[3] = 3时

选2个2和2个3刚好拼成10, 而贪心 会是 3 * 2 + 1 * 3 或者 0 * 2 + 3 * 3 都无法达到最大

---

然后测试数据弱就过了，根据讨论区 说，只要所有加起来都能过测试，这是什么坑爹的出题人和数据，