前行 - NOI2020同步赛 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

前行 - NOI2020同步赛

发表于 更新于 分类于 Valine：

国集神犇果然还是国集神犇，我见得太少了QwQ

# Part1. 纪

第一次打 NOI，离省队比较遥远只能打同步赛。

CCF的管理员开小差去了，同步赛延时了十多分钟才开，刚打开又没有题面，有了题面又没有大样例……

还是先把题目从头到尾看完了，感觉到应该是按照难度排序的，所以先攻第一题。看到 $T$ 极大而 $n$ 极小就想到大概要矩阵加速，然后就按照之前的思路从（我能想到的）最暴力的DP开始优化。f[t][u][i] 表示第 $t$ 天时，还有 $i$ 天到达点 $u$ 的最大美味值，暂时没有考虑美食节。

然后想了20min没有优化出来，回来看题目才看到 $t$ 只有 $5$，一时心头生艹，就开始码代码。写着写着想起还有美食节，看时间还比较可控，就又停下想美食节。于是就联想到 NOI Online 的一道几乎一样的题——把DP过程分段；回忆那道题的解题思路，很快就把 $O(tn^3\log n)$ 优化到 $O(tn^2\log n)$ 了，调程序花了 30min……

跑大样例感觉有点卡常，最后回头再加了些 register 之类的东西。

然后T2想了10min感觉“不可做”，然后就想骗分。暴力显然就不管它，然后看 $m$ 很小就想要状压，推式子发现要或卷积，整个人都懵了，最后写了个最水的暴力走人……

T3看到题目的时候笑了一发（这个出题人在造梗）。初步整理思路肯定要扫描线，然后写了一个主席树来处理矩阵求和，把暴力分得了。一开始读题没有看到每列有且只有一个点……后面看到了才知道之前想的莫队复杂度是对的 QwQ 时间不太多了，最后莫队常数巨大跑不出来……

Day1 打完 13:30（虽然CCF延长了15min），然而多校赛 12:00 开始……就去打多校了，感觉聚聚都去NOI了，这一场多校的中学格外的少。

Day2什么东西，不想写……

# Part2. 解&补

- D1T1. 美食家(delicacy)

先从暴力DP考虑，要处理一下某个时刻处于一条边上还没有走完的情况，$f_{t,u,i}$ 表示时刻 $t$ 正在前往 $u$，还剩 $i$ 天到达 $u$（如果 $i=0$，则表示已经到了 $u$）。

转移是：

因为一条边花费的时间 $t_e$ 只有 $5$，我们发现第三维只有 $0\sim4$ 的取值，所以干脆把一个点 $u$ 按时间拆成 $u_0,u_1,\dots,u_4$，$5n$ 仍然很小，可以支持矩阵加速。

然后就是处理美食节。注意到只有美食节当天的转移会发生变化，于是可以把美食节作为阶段的划分点，一个阶段内的转移方程是不变的，可以矩阵加速。

此时复杂度是 $O((5n)^3\log nk)$（$k$ 为美食节数量），过不了。但是在 NOI Online 里面有一个一模一样的操作——$O(n^3\log n)$ 预处理转移矩阵的 $2^0,2^1,2^2\dots$ 次幂，做转移时可以用储存当前状态的单列矩阵做 $\log n$ 次乘法，这样做一次复杂度是 $O((5n)^2\log n)$ 的，于是优化到 $O((5n^3)\log n+(5n)^2k\log n)$ 可过。

- D1T2. 命运(destiny)

方法很多，可以容斥，也有不容斥的做法。我采用的是不容斥的。

> Tab. 下文直接说成“黑白边染色”了，即要求给定路径上要有黑边。

先考虑 DP。对于一条边定义其深度为较深的一个端点的深度，则先预处理出每个点 $u$ 作为路径的下端点时，至少在多深必须要染黑边。比较显然，如果有多条路径的下端点是 $u$，则上端点的深度取 $\max$，记这个值为 $pre_u$（若 $u$ 不是路径下端点，则 $pre_u=0$）。另外记 $dep_u$ 表示 $u$ 的深度。

根据这个限制进行黑白染色：定义DP状态 $f_{u,d}$ 表示节点 $u$ 上方的第一条黑边的深度是 $d$ 的合法方案数。

从子树 $v$ 到当前节点 $u$ 的转移只需考虑边 $(u,v)$ 是否染黑，即：

又要求 $u$ 满足作为 $pre_u$ 的限制，上式的 $d\in[pre_u,dep_u]$。实际代码实现时，我们可以把 $d\in[pre_u,dep_u]$ 的 $f_{u,d}$ 的初值赋为 $1$，其余为 $0$。

这样就得到了一个 $O(n^2)$ 的 DP，接下来要用到线段树合并进行优化——

我们发现之前DP进行的操作：

  • 赋初值：区间修改（区间加）；
  • $(f_{v,d}+f_{v,dep_v})$：区间加；
  • $\prod(f_{v,d}+f_{v,dep_v})$：按位乘。

于是线段树需要支持这些操作。

可以维护一个 pair（代码中为 DATA）作为懒标记 $(a,b)$，其意义为 $x\times (a,b)=ax+b$。

这样的话区间加容易处理，按位乘需要线段树合并——一直递归到线段树的叶子节点（注意因为是动态开点，所以叶子节点不一定是缩成一个点的线段），然后乘法合并。懒标记的乘法合并直接推导一下就行了。

$v$ 子树内的点在参与合并后就没用了，可以 restore 一下节省空间。

- D2T1. 制作菜品(dish)

> Linked 另外写了一篇博客

# 源代码

- D1T1 delicacy.cpp

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define reg register int
#define cs const int &
typedef long long ll;
const int N=55,M=505,SIZ=260;
//还剩i时刻到达u
#define hsh(u,i) ((u)*5-(i))
#define upd(a,b) (a=max(a,b))

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}

int n,m,T,Q,siz;
int val[N];
int fest[M][3],festid[M];

struct MATRIX{
	int r,c;
	ll mat[SIZ][SIZ];
	inline void Init(cs R,cs C){
		r=R,c=C;
		for(reg i=1;i<=R;i++)
			for(reg j=1;j<=C;j++)
				mat[i][j]=-1;
	}
}ini,now,tmp,pini[32];
MATRIX Mul(const MATRIX &A,const MATRIX &B){
	MATRIX res;res.Init(A.r,B.c);
	for(reg i=1;i<=A.r;i++)
		for(reg j=1;j<=B.c;j++)
			for(reg k=1;k<=A.c;k++)
				if((~A.mat[i][k]) && (~B.mat[k][j]))
					upd(res.mat[i][j],A.mat[i][k]+B.mat[k][j]);
	return res;
}

struct GRAPH{
	int head[N],to[M],nxt[M],tim[M],ncnt;
	inline void AddEdge(cs u,cs v,cs t){
		int p=++ncnt;
		nxt[p]=head[u],to[p]=v,tim[p]=t;
		head[u]=p;
	}
	inline int operator [](cs u){return head[u];}
}Gr;

bool cmp(cs a,cs b){return fest[a][0]<fest[b][0];}
int main(){
	freopen("delicacy.in","r",stdin);
	freopen("delicacy.out","w",stdout);
	n=Read(),m=Read(),T=Read(),Q=Read();
	siz=n*5;
	for(reg i=1;i<=n;i++) val[i]=Read();
	for(reg i=1;i<=m;i++){
		int u=Read(),v=Read(),t=Read();
		Gr.AddEdge(u,v,t);
	}
	ini.Init(siz,siz);
	for(int u=1;u<=n;u++){
		for(reg i=4;i>=1;i--)
			upd(ini.mat[hsh(u,i-1)][hsh(u,i)],0ll);
		for(reg it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it],t=Gr.tim[it];
			upd(ini.mat[hsh(v,t-1)][hsh(u,0)],(ll)val[u]);
		}
	}
	pini[0]=ini;
	for(reg t=1;t<32;t++)
		pini[t]=Mul(pini[t-1],pini[t-1]);
	now.Init(siz,1);now.mat[hsh(1,0)][1]=0;
	for(reg i=1;i<=Q;i++){
		festid[i]=i;
		for(reg j=0;j<3;j++)
			fest[i][j]=Read();
	}
	sort(festid+1,festid+1+Q,cmp);
	int las=0;
	for(reg i=1;i<=Q;i++){
		int tim=fest[festid[i]][0],pos=fest[festid[i]][1],ext=fest[festid[i]][2];
		int bet=tim-las;las=tim;
		for(reg j=0;j<=30;j++)
			if(bet>>j&1){
				tmp=now;
				now=Mul(pini[j],tmp);
			}
		if(~now.mat[hsh(pos,0)][1])
			now.mat[hsh(pos,0)][1]+=ext;
	}
	int bet=T-las;
	for(reg j=0;j<=30;j++)
		if(bet>>j&1){
			tmp=now;
			now=Mul(pini[j],tmp);
		}
	if(~now.mat[hsh(1,0)][1]) printf("%lld\n",now.mat[hsh(1,0)][1]+val[1]);
	else printf("-1\n");
	return 0;
}

- D1T2 destiny.cpp

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}

const int N=5e5+10,MOD=998244353;
#define cs const int &
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}

struct GRAPH{
	int head[N],to[N<<1],nxt[N<<1],ncnt;
	void AddEdge(cs u,cs v){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
		nxt[q]=head[v],to[q]=u,head[v]=q;
	}
	inline int operator [](cs u){return head[u];}
}Gr;

struct DATA{
	int a,b;
	//dp * (a,b) = a * dp + b
	//in fact, b is equal to the dp value, as initial dp value is 0
	DATA(){}
	DATA(cs A,cs B):a(A),b(B){}
	//merge two lazy-tag
	inline friend DATA operator *(const DATA &A,const DATA &B){return DATA(Mul(A.a,B.a),Add(B.b,Mul(A.b,B.a)));}
	inline DATA operator *=(const DATA &B){return (*this)=(*this)*B,*this;}
	inline friend bool operator ==(const DATA &A,const DATA &B){return A.a==B.a && A.b==B.b;}
};

//the empty lazy tag
const DATA NIL(1,0);

struct SEGTREE{
	int nxt[N<<6][2],mem[N<<6],rt[N],nmem,nspr;
	DATA key[N<<6];
	int NewNode(const DATA &val){
		int p=nmem? mem[nmem--]:++nspr;
		nxt[p][0]=nxt[p][1]=0;
		key[p]=val;
		return p;
	}
	void PushDown(cs u){
		if(key[u]==NIL) return;
		if(!nxt[u][0]) nxt[u][0]=NewNode(key[u]);
		else key[nxt[u][0]]*=key[u];
		if(!nxt[u][1]) nxt[u][1]=NewNode(key[u]);
		else key[nxt[u][1]]*=key[u];
		key[u]=NIL;
	}
	void Modify(cs u,cs le,cs ri,cs Le,cs Ri,const DATA &now){
		if(Le>Ri) return;
		if(Le<=le && ri<=Ri){
			key[u]*=now;
			return;
		}
		PushDown(u);
		int mi=(le+ri)>>1;
		if(Le<=mi) Modify(nxt[u][0],le,mi,Le,Ri,now);
		if(mi<Ri) Modify(nxt[u][1],mi+1,ri,Le,Ri,now);
	}
	//query dp[po]
	int Query(cs u,cs po,cs le,cs ri){
		if(le==ri) return key[u].b;
		PushDown(u);
		int mi=(le+ri)>>1;
		if(po<=mi) return Query(nxt[u][0],po,le,mi);
		else return Query(nxt[u][1],po,mi+1,ri);
	}
	int Merge(int &u,int &v){
		if(!nxt[u][0] && !nxt[u][1]) swap(u,v);
		//dp[u][i]*=dp[v][i]
		if(!nxt[v][0] && !nxt[v][1]) return key[u]*=DATA(key[v].b,0),u;
		PushDown(u),PushDown(v);
		nxt[u][0]=Merge(nxt[u][0],nxt[v][0]);
		nxt[u][1]=Merge(nxt[u][1],nxt[v][1]);
		return u;
	}
	void Restore(int &u){
		if(!u) return;
		Restore(nxt[u][0]),Restore(nxt[u][1]);
		mem[++nmem]=u;
		u=0;
	}
	inline int& operator [](cs u){return rt[u];}
}Se;

int n,m;
int dep[N],pre[N];

void DP(cs u,cs fa){
	pre[u]=max(pre[u],pre[fa]);
	Se[u]=Se.NewNode(DATA(0,0));
	/*
	the first edge can be chosen from (pre[u],dep[u]]
	dp[ pre[u]+1~dep[u] ] += 1
	*/
	Se.Modify(Se[u],1,n,pre[u]+1,dep[u],DATA(0,1));
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		DP(v,u);
		/*
		the initial transport is "f[u][i]=prod(f[v][i]+f[v][dep[v]])";
		we can firstly let f[v][i]:=f[v][i]+f[v][dep[v]];
		and then f'[u][i]=f[u][i]*f[v][i]
		*/
		Se[u]=Se.Merge(Se[u],Se[v]);
		//restore the nodes in segment-tree[v]
		Se.Restore(Se[v]);
	}
	if(u!=1){
		int tmp=Se.Query(Se[u],dep[u],1,n);
		//dp[ 1~dep[u]-1 ] += dp[dep[u]]
		Se.Modify(Se[u],1,n,1,dep[u]-1,DATA(1,tmp));
	}
}

void DFS(cs u,cs fa){
	dep[u]=dep[fa]+1;
	for(int it=Gr[u];it;it=Gr.nxt[it])
		if(Gr.to[it]!=fa)
			DFS(Gr.to[it],u);
}
int main(){
	freopen("destiny.in","r",stdin);
	freopen("destiny.out","w",stdout);
	n=Read();
	for(int i=1;i<n;i++) Gr.AddEdge(Read(),Read());
	m=Read();
	DFS(1,0);
	for(int i=1;i<=m;i++){
		int u=Read(),v=Read();
		pre[v]=max(pre[v],dep[u]);
	}
	DP(1,0);
	printf("%d\n",Se.Query(Se[1],1,1,n));
	return 0;
}

THE END

Thanks for reading!

> Linked 零和 Zero-Sum-Bilibili