https://codeforces.com/contest/1854

B - Earn or Unlock

想了半天,bitset就过了??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

卧槽 200000^2/64 = 6'2500'0000.0 也能跑进3秒的吗?

https://codeforces.com/contest/1854/submission/216347777

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
ll a[200010];
ll sa[200010];
int main(){
  int n = read();
  rep(i,1,n+1) a[i]=read();
  int OFF=n;
  ll ans = a[1];
  rep(i,1,n+OFF+1) sa[i] = sa[i-1] + a[i];
  bitset<200010> ok; // [1,n]
  ok[1] = 1;
  rep(i,1,n+OFF+1) {
    if(ok[i]) ans = max(ans, sa[i]-(i-1));
    ok |= (ok << a[i]);
    ok[i] = 0;
  }
  printf("%lld\n",ans);
  return 0;
}

总结

B

常数优化完全不会, n*bitset(n/64) n = 2e5可以跑进3秒!?

有人rust的也是bitset, https://codeforces.com/contest/1854/submission/216290617

pypy: https://codeforces.com/contest/1854/submission/216353273

C

参考

官方题解

https://atcoder.jp/contests/abc312/tasks/abc312_h

Ex - snukesnuke

N个字符串s[i]

1
2
3
4
5
6
7
8

t = set<string>
for i := 1..n
	k_i = 1
	while s[i] * k_i in t:
		k_i++
	t.insert(s[i] * k_i)

求 所有 k_1..n

$\sum |S_i| \le 2\cdot 10^5$, 小写英文字母

2s

1024mb

我的思路

如果不同字符串之间互不影响，那么相同si的ki对应的值就是1,2,4,5,6,7…

那么问题就是如果不同的字符串之间有影响

$k_i\cdot s_i = k_j\cdot s_j, s_i \neq s_j$

若$k_i = 1$,也就是 $s_i$会是$s_j$的重复序列， 首先重复序列的长度一定是 $s_i$长度的因数，这样可以 额外$O(|s_i| log|s_i|)$ 的把所有处理成

$(s_i,repeat)$ 的形式

根据字符串的循环结的理论，显然 一个字符串有一个最小循环单位，且其它循环都是它的倍数

1
2
3
4
5
6
7
8
9

引理 简单证明
最小循环节   l0 [.....][.....]
非倍数循环结 l1 [.........]

可以得到 (长度l1中，起始长度l0循环平移相等) -> F(l1,l0)

而 F(a,b) 当 a%b!=0时 可以得到 -> F(b,a%b)

这就是 gcd的过程，是有限的，所以总可以得到更小的循环节，矛盾

若 $k_i,k_j$均不为1,且$gcd(k_i,k_j) = 1$,那么用到上面引理类似的

不失一般性，设 $|s_i| > |s_j|$

1
2
3
4
5

[s_i......][s_i......][s_i......][s_i......][s_i.....]
[s_j....][s_j....][s_j....][s_j....][s_j....][s_j....]
得到 $F(len(s_i), len(s_j))$ 

所以它们一定有更小的循环节

综上，首先把所有的字符串拆成最小循环节和repeat, 然后对所有 最小循环结做hash

似乎就没了

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)$

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

题解

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

然后神奇的来了,