D
评分2900,远高于C的难度
题目
https://atcoder.jp/contests/arc142/tasks/arc142_d
给你一个树,要上面放一些棋子
每个时间周期,所有棋子要向它相邻的任意一个点移动,确保移动时每条边最大负债1,移动后每个点最多棋子1个
且保证任意个时间周期的结果唯一
问所有合法放置方案数
范围
n 2e5
2s
1024mb
题解
我的思路
要唯一,考虑做树上dp
dp[from][to][tofa] 每个点2x2x2=8 最多8个状态
from表示根原来有或没, to表示移动一次后有或没, tofa表示移动一次以后对父节点是否有贡献
但转移感觉只有手动推一推, 不知道自动怎么算
题解
注意到是唯一的反复跳 u->v->u->v
那么实际上树是由多个不相交的链组成的
如果分叉角度说
a-b a-c a-d
a总有一轮是1, 两轮都是0是不可能的(这样有多个摆放方案
那么移动一次后一是到b,c,d中的一个
而下一次会移动回来
说明a至多和两个位置跳来跳去剩下的就是和a不相关的链了
那么1110110, 这样的看作两条链
问题就是如何划分链
potato167 的blog上画了很多方便理解的图
注意到每个独立的链都是 111110 的形式, 而不相交的相邻链是 1和0 相临的, 且独立的链最小长度为2
然后一条链的端点也不能和另一条链的中间点相邻, 但两条链的中点可以相邻
所以对于一个点来讲,它可以是头0,头1或者中间的1,
dp上 就考虑根的状态了
0 端点 ( 另一个端点是这个端点的后代
1 端点 ( 另一个端点不是这个端点的后代
2 非端点, 且连接父节点
3 非端点, 且连接两个子节点
这里的状态划分也不再关心是端点是0还是1,因为你只需要保证端点之和端点相邻(相邻的端点相互决定),这样只用关心有多少自由端点的个数n即可, $2^n$
手推4种状态
0: 1个子节点1/2, 剩余都是0
1: 所有子节点都是0
2: 1个子节点1/2, 剩余都是3
3: 2个子节点1/2, 剩余都是3
除了状态转移, 还需要统计自由度
中间的3 和 根的0 会让自由度+1
自由度+1, 相当于答案乘2, 所以直接统计答案比记录自由度更方便
计算
0:
一种方案是
sum (dp[v][1]+dp[v][2]) * ((sum dp[..][0]) - dp[v][0])
sum (dp[v][1]+dp[v][2]) * (sum dp[..][0]) - sum (dp[v][1]+dp[v][2]) * dp[v][0])
(sum1+sum2)*sum0 - sum( (v1+v2)(v0))
另一种按照循环增加的算法是
res = (res * dp[v][0]) + (dp[v][1] + dp[v][2])*(before all 0)
1: all0
2: 类似0的计算方法 采取循环子节点 的方法
res = (res * dp[v][3]) + (dp[v][1] + dp[v][2])*(before all 3)
3: 相当于双状态转移
res[2个满足子节点] = res[2] * dp3 + (dp1+dp2)*(before res[1])
res[1个满足子节点] = res[1] * dp3 + (dp1+dp2)*(before res[0] = before all 3)
最后记得3还要再乘2
当然注意到 1和2只有过程中的计算才是分开的, 父子之间处理是一起使用的, 还可以降低一个状态,虽然意义不大
代码
https://atcoder.jp/contests/arc142/submissions/32681890
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#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;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
vector<int> G[200010];
int main() {
int n = read();
rep(i,1,n){
int u = read() - 1;
int v = read() - 1;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> fa(n,-1);
vector<int> order={0};
rep(i,0,n) {
int u = order[i];
for(auto v:G[u]){
if(v == fa[u]) continue;
fa[v] = u;
order.push_back(v);
}
}
vector<vector<ll>> dp(n,vector<ll>(4));
per(i,0,n){
int u = order[i];
ll all0 = 1;
ll all3 = 1;
ll pre1 = 0;
for(auto v:G[u]){
if(fa[v]!=u) continue;
ll s12 = (dp[v][1]+dp[v][2])%MOD;
dp[u][0] = (dp[u][0] * dp[v][0] % MOD + all0 * s12 % MOD)%MOD;
dp[u][2] = (dp[u][2] * dp[v][3] % MOD + all3 * s12 % MOD)%MOD;
dp[u][3] = (dp[u][3] * dp[v][3] % MOD + pre1 * s12 % MOD)%MOD;
pre1 = (pre1 * dp[v][3] % MOD + all3 * s12 % MOD)%MOD;
(all0 *= dp[v][0]) %= MOD;
(all3 *= dp[v][3]) %= MOD;
}
dp[u][1] = all0;
(dp[u][3] *= 2) %= MOD;
}
printf("%lld\n",(dp[0][0] * 2 % MOD + dp[0][3])%MOD);
}
|
如果再压缩1和2的状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<vector<ll>> dp(n,vector<ll>(3));
per(i,0,n){
int u = order[i];
ll all0 = 1;
ll all3 = 1;
ll pre1 = 0;
for(auto v:G[u]){
if(fa[v]!=u) continue;
dp[u][0] = (dp[u][0] * dp[v][0] % MOD + all0 * dp[v][1] % MOD)%MOD;
dp[u][1] = (dp[u][1] * dp[v][2] % MOD + all3 * dp[v][1] % MOD)%MOD;
dp[u][2] = (dp[u][2] * dp[v][2] % MOD + pre1 * dp[v][1] % MOD)%MOD;
pre1 = (pre1 * dp[v][2] % MOD + all3 * dp[v][1] % MOD)%MOD;
(all0 *= dp[v][0]) %= MOD;
(all3 *= dp[v][2]) %= MOD;
}
(dp[u][1] += all0) %= MOD;
(dp[u][2] *= 2) %= MOD;
}
printf("%lld\n",(dp[0][0] * 2 % MOD + dp[0][2])%MOD);
|
E
n 个巫师,
ai 能力
打败 bi 怪物
对任意巫师增加任意次1能力
(i,j) is good when (a[i] >= bi and a[j] >= bj) or (a[i] >= b[j] and a[j] >= b[i])
相当于直接打败或交叉打败
给你m 个 (x,y)
要最小增加能力, 让所有(x,y) 是good
范围
n 100
ai bi [1,100]
题解
思路
如果自己打败自己,那很好算,但是不一定是答案,但是答案上界至少是
考虑结果总有个每个巫师的大小顺序
如果(a[i] - a[j])*(b[i]-b[j]) >= 0 , 且存在限制 (x,y) = (i,j)
那么 必然a[i] >= b[i] a[j] >= b[j] , 如果
因为如果(i,j) good ,也就是 min(a[i],a[j]) >= min(b[i],b[j]) , max(a[i],a[j]) >= max(b[i],b[j])
但是n是100 不可能去枚举顺序
题解
首先, a[x],a[y] >= min(a[x],a[y]) 这是必要的, 所以可以预处理掉这个
X 为 能力 小于 monter的 集合, 且在(x,y)中出现了的巫师
Y 是 其它的巫师
对于(x,y) 且 x属于X, y属于Y, 结果上期望 a[y] >= b[x] 或 a[x] >= b[x]
因为有预处理, 所以b[x] > b[y], 因为如果 b[x] <= b[y] 那么必然有 a[x] >= min(b[x],b[y]) = b[x], x不会属于X,
也就是X-Y的连接, 一定y中的b更小
b[x] > a[x] >= b[y] 的顺序, a[y] >= b[y]
对于Y-Y的连接,不需要考虑,因为a只会增大,原来满足增加后还是满足
对于X-X的链接,不会存在,因为有了预处理, 这两个a大于min(b), 所以一定有一个属于Y
回到X-Y
a[y] >= b[x] > a[x] >= b[y] 直接合法
b[x] > (a[x],a[y]) >= b[y] 考虑上面是让a[y] >= b[x] 还是 a[x] >= b[x]
建图
点:
S源,T汇
X每个x一个点
Y每个y,100个点(y,i = 1..100)
边
S -> x 权重b[x] - a[x]
(y,i) -> T 权重1
(y,i) -> (y,i-1) 权重无限大
x -> (y,b[x] - a[y]) 权重无限大
意义
先看假设只有一对
S-(bx-ax)->x-(无限)-> (y, b[x]-a[y])-(1)-> T, 然后还有些(y,i)->(y,i-1)的边
S->X这边限制了不会大于bx-ax, 右边限制了不会大于bx-ay
最小割一定是 S->x和(y,i)->T 中的边,不会是那些无限的边
而如果S->x 不在最小割里,说明右侧对应的(y,b[x]-a[y]) -> T, 以及更小的i的(y,i) 全部填满, 否则可至少可以再+1, 填满也就说明选择满足
这个最小割的建图,我也是真不会啊(最大流,最小割还是会写)
代码
https://atcoder.jp/contests/arc142/submissions/32759166
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #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;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
#define N 100
#define INF 0x3f3f3f3f
int n,m;
int a[N+10];
int b[N+10];
vector<int> p2[110];
int S = 0;
int T = 1;
int nodex(int x) {
assert(x >=0 && x< 100);
return 2+x;
}
int nodey(int y,int value) {
assert(y >=0 && y< 100);
assert(value >=1 && value <= 100);
return 101 + y*100 + value;
}
class MinCut{
int sz ;
vector<unordered_map<int,ll> > G;
vector<int> d;
public:
MinCut(int n):sz(n){
G = vector<unordered_map<int,ll> >(sz);
}
void path(int u,int v,ll w){
assert(u != v);
G[u][v] += w;
}
int dfs(int u,int en, ll s){
if (u == en)return s;
for(auto [v,w]:G[u]){
if(w == 0) continue;
if(d[v] != d[u]+1) continue;
int r = dfs(v,en,min(s,w));
if(r){
G[u][v] -= r;
G[v][u] += r;
return r;
}
}
d[u] = 0;
return 0;
}
bool bfs(int st,int en){
d = vector<int>(sz+10,-1);
vector<int> q = {st};
d[st] = 0;
rep(i,0,q.size()){
int u = q[i];
for(auto [v,w]: G[u]){
if(d[v] != -1) continue;
if(w == 0) continue;
d[v] = d[u] +1;
q.pb(v);
}
}
return d[en] >= 0;
}
ll calc(int st,int en){
int ans = 0;
while (bfs(st, en)) ans += dfs(st, en, INF);
return ans;
}
};
int main(){
n = read();
S = 0;
T = 1;
rep(i,0,n){
a[i] = read();
b[i] = read();
}
m = read();
int ans = 0;
rep(i,0,m){
int x = read() - 1;
int y = read() - 1;
int minv = min(b[x],b[y]);
ans += max(0,minv - a[x]);
a[x] = max(a[x],minv);
ans += max(0,minv - a[y]);
a[y] = max(a[y],minv);
p2[x].pb(y);
p2[y].pb(x);
}
MinCut mc(20000);
rep(i,0,n) {
if(a[i] < b[i]){
mc.path(S,nodex(i),b[i] - a[i]);
for(auto u:p2[i]){
if(a[u] >= b[i]) continue;
mc.path(nodex(i),nodey(u,b[i]-a[u]),INF);
}
}else{
rep(j,1,101){
mc.path(nodey(i,j),T,1);
if(j > 1){
mc.path(nodey(i,j),nodey(i,j-1),INF);
}
}
}
}
printf("%lld\n",ans + mc.calc(S,T) );
return 0;
}
|
总结
D
我突然觉得我的dp[from][to][tofa] 是不是也可能可以做?? 看起来是完全不同的思路
虽然想到反复横跳,但拆成链以及链的链接合法方式完全没想过
而且即使是拆成链,看了积分代码, 所做的树上dp也不相同, 能拆成这样四个也是很需要功力的
看potato167的代码学了一手非递归的树上dp, 通过先建立order,再逆序做
E
光是这个预处理就很厉害,解决了分类的问题, 能证明但完全没能自己挖掘出这个性质
然后这个建图我也是不会, 虽然学过最大流最小割,但是为啥这样想,没做过这种, 顺便整两个mincut板子
参考
官方题解
potato167 D