hdu2021多校3

发表于 分类于 ，

链接

1001

题意

给定一棵树，有点权 $p_i$。

$q$ 次询问，每次询问给定从 $u$ 到 $v$ 的有向路径，以及权值 $k$。从 $u$ 到 $v$ 依次选择点权 $p_i$，若 $k\geq p_i$，则 $k$ 变为 $k-p_i$。输出最后的 $k$。

$n,q\le 10^5,p_i\le 10^9,\sum n,\sum q\le 8\times 10^5$。

题解

离线，然后树剖，将每条路径分成向上和向下共 $O(\log n)$ 条dfs序连续的段。变成序列上的操作。

用平衡树维护每个询问的当前答案。

每次遇到一个数 $p_i$，需要将平衡树内 $\geq p_i$ 的数都减去 $p_i$。

这个是平衡树的经典操作，分成 $[0,k - 1],[k,2k-1],\left [2k,+\infty \right )$。

程序

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=100010;

namespace Treap{
    int son[N][2],val[N],siz[N],rnd[N],tag[N],fa[N],rt;
    inline void init(int n)
	{
		rt=0;
		fo(i,1,n) son[i][0]=son[i][1]=val[i]=tag[i]=fa[i]=0,siz[i]=1,rnd[i]=rand();
	}
    inline void pushup(int u)
	{
		if(!u) return;
		siz[u]=1;
		if(son[u][0]) siz[u]+=siz[son[u][0]],fa[son[u][0]]=u;
		if(son[u][1]) siz[u]+=siz[son[u][1]],fa[son[u][1]]=u;
	}
	inline void pushdown(int u)
	{
		if(!u||!tag[u]) return;
		if(son[u][0]) tag[son[u][0]]+=tag[u],val[son[u][0]]-=tag[u];
		if(son[u][1]) tag[son[u][1]]+=tag[u],val[son[u][1]]-=tag[u];
		tag[u]=0;
	}
    int merge(int x,int y)
	{
        if(!x||!y) return x+y;
		pushdown(x); pushdown(y);
        if(rnd[x]<rnd[y]) {son[x][1]=merge(son[x][1],y); pushup(x);return x;}
        else              {son[y][0]=merge(x,son[y][0]); pushup(y);return y;}
    }
    void split_val(int u,int k,int &x,int &y)
	{
        if(!u) return void(x=y=0);
		pushdown(u);
        if(val[u]<=k) x=u,split_val(son[x][1],k,son[x][1],y);
        else y=u,split_val(son[y][0],k,x,son[y][0]);
        pushup(u);
    }
    void split_siz(int u,int k,int &x,int &y)
	{
        if(!u) return void(x=y=0);
		pushdown(u);
        if(k<=siz[son[u][0]]) y=u,split_siz(son[y][0],k,x,son[y][0]);
        else x=u,split_siz(son[x][1],k-siz[son[u][0]]-1,son[x][1],y);
        pushup(u);
    }
    int x,y,z,ans;
    inline void ins(int id,int v)
	{
		val[id]=v; tag[id]=0; son[id][0]=son[id][1]=fa[id]=0; siz[id]=1;
		split_val(rt,v,x,y);
        rt=merge(merge(x,id),y);
    }
	int st[1000],top;
	inline int push(int x)
	{
		int si=1,u;
		if(son[x][0]) si+=siz[son[x][0]];
		fa[rt]=0;
		for(top=0;fa[x];x=fa[x]) st[++top]=x;
		for(;top;top--)
		{
			u=st[top];
			pushdown(fa[u]);
			if(son[fa[u]][1]==u)
				si+=siz[son[fa[u]][0]]+1;
		}
		return si;
		
	}
    inline void del(int id,int &v)
	{
		int si=push(id);
        split_siz(rt,si-1,x,y);
        split_siz(y,1,y,z);
		v=val[y];
		fa[id]=0;
        rt=merge(x,z);
    }
	void dfs(int u,int k)
	{
		if(!u) return;
		pushdown(u);
		if(son[u][0]) dfs(son[u][0],k),son[u][0]=0;
		if(son[u][1]) dfs(son[u][1],k),son[u][1]=0;
		pushup(u);
		val[u]-=k;
		int w,e;
		split_val(rt,val[u],w,e);
		rt=merge(merge(w,u),e);
	}
    inline void work(int k)
	{
		split_val(rt,k-1,x,y);
		split_val(y,2*k-1,y,z);
		if(z) tag[z]+=k,val[z]-=k;
		rt=x;
		dfs(y,k);
		rt=merge(rt,z);
	}
}


int n,q,val[N];
int ver[N<<1],ne[N<<1],head[N<<1],tot;
inline void add(int x,int y)
{
	ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
}
int siz[N],fa[N],top[N],son[N],dep[N],dfn[N],tim,_dfn[N];
void dfs1(int u,int pre)
{
	dep[u]=dep[pre]+1; fa[u]=pre; siz[u]=1;
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=pre)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	dfn[u]=++tim;
	_dfn[tim]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u],v;i;i=ne[i])
		if(!top[v=ver[i]])
			dfs2(v,v);
}
inline int lca(int x,int y)
{
	for(;top[x]!=top[y];x=fa[top[x]])
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
	return dep[x]>dep[y]?y:x;
}
bool in[N];
vector<int> op[2][N];
inline void get(int x,int y,int id)
{
	for(;top[x]!=top[y];)
		if(dep[top[x]]>dep[top[y]])
			op[0][dfn[x]].pb(id),op[0][dfn[top[x]]-1].pb(id),x=fa[top[x]];
		else
			op[1][dfn[top[y]]].pb(id),op[1][dfn[y]+1].pb(id),y=fa[top[y]];
	if(dep[x]>dep[y]) op[0][dfn[x]].pb(id),op[0][dfn[y]-1].pb(id);
	else op[1][dfn[x]].pb(id),op[1][dfn[y]+1].pb(id);
}
int ans[N];
int main()
{
	CASET
	{
		tim=tot=0;
		n=read(); q=read();
		fo(i,1,n) head[i]=son[i]=fa[i]=dep[i]=top[i]=0;
		fo(i,1,n) val[i]=read();
		fo(i,0,n+1) op[0][i].clear(),op[1][i].clear();
		fo(i,1,n-1) add(read(),read());
		dfs1(1,0); dfs2(1,1);
		int x,y,z,k;
		fo(i,1,q)
		{
			x=read(); y=read();
			get(x,y,i);
			ans[i]=read();
		}
		Treap::init(q);
		fo(i,1,q) in[i]=0;
		fd(i,n,0)
		{
			ff(j,0,op[0][i].size())
			{
				k=op[0][i][j];
				if(in[k])
				{
					Treap::del(k,ans[k]);
					in[k]=0;
				}
				else
				{
					Treap::ins(k,ans[k]);
					in[k]=1;
				}
			}
			Treap::work(val[_dfn[i]]);
		}
		Treap::init(q);
		fo(i,1,q) in[i]=0;
		fo(i,1,n+1)
		{
			ff(j,0,op[1][i].size())
			{
				k=op[1][i][j];
				if(in[k])
				{
					Treap::del(k,ans[k]);
					in[k]=0;
				}
				else
				{
					Treap::ins(k,ans[k]);
					in[k]=1;
				}
			}
			Treap::work(val[_dfn[i]]);
		}
		fo(i,1,q) printf("%d\n",ans[i]);
	}
	return 0;
}

1003

题意

给定两个十进制的数字串 $S,T$，均有通配字符‘*’，对于每个 $i(0\le i \le |T|)$，问若能至多失配 $i$ 次，字符串 $S$ 中长度为 $T$ 的子串有多少个能与之匹配。

$|T|\le |S|\le 2\times 10^5$。

题解

含通配字符的通常可以用FFT去进行解决。设 $f_i$ 表示 $S[i,i+|T|-1]$ 与 $T$ 匹配的次数，算出 $f_i$ 即可。

这里将每个数字 $k$ 分开考虑，设 $a_i=[S_i==k],b_i=[T_i==k]$，对于该字符，$S[j,j+|T|-1]$ 与 $T$ 匹配的次数为 $\sum_{i=0}^{|T|-1}a_{i+j}b_i$。

将 $b_i$ 反串，然后FFT即可。

但是，对于通配字符，它们在每个数字中都会被统计到，统计多了 $10-1=9$ 次，于是再做一次跟通配字符相关的FFT，减去其 $9$ 倍的贡献即可。

时间复杂度 $O(11n\log n)$。

1006

题意

$n$ 个工人，$n$ 件物品要加工。第 $i$ 个人加工 $j$ 物品能获得 $a_i+b_j$ 的收益。

每个人只能加工最多一个物品，每个物品最多只能被一个人加工。

$m$ 条限制，每条限制形如 $i$ 工人不能加工 $j$ 物品。

对于每个 $i$，问加工 $i$ 个物品所能获得的最大收益，或者判断不可行。

$n\le 4000,m\le 10000$。

题解

显然是一个费用流的模型。

建立源点 $S$ ，向工人连边权为 $1$，费用为 $a_i$ 的边。

建立汇点 $T$，物品向 $T$ 连边权为 $1$，费用为 $b_i$ 的边。

工人向能加工的物品连一条边权为 $1$，费用为 $0$ 的边。

然后每次将权值加 $1$，跑费用流。

但是这样的边数是 $O(n^2)$ 的。

考虑一共 $n$ 次找增广路，每次增广时寻找一条路径，且起点终点都没有用过的点，并且要权值和要最大。

考虑模拟这个过程，但由于这是一个补图，采用在补图上做的经典套路，维护一个链表表示右边还未访问的节点。模拟费用流的过程，左边的节点从大到小开始寻找增广路，每次找到的点要么在原图中有连边，要么在链表中被删去，一次找到所有增广路的时间是 $O(n+m)$ 的。

于是总的时间复杂度 $O(n^2+nm)$。

1009

题意

$n\times n$ 的格子，每个格子有两个值 $a_{i,j},b_{i,j}$。

从 $(1,1)$ 开始，每步往下或往右走，走到 $(n,n)$。

求这样的路径中 $(\sum a_{i,j})\times (\sum b_{i,j})$ 的最大值。

$n\le 100,a_{i,j},b_{i,j} \le 10^6$。

数据随机。

题解

设 $f_{i,j,k}$ 表示走到 $(i,j)$ ，$\sum a =k$ 时 $b_{i,j}$ 的最大值。

对于同一个 $i,j$，若 $k_1\le k_2$ 且 $f_{i,j,k_1}\le f_{i,j,k_2}$，则 $k_1$ 完全没用。

在随机情况下，合法的 $k$ 大概只有几千。

于是复杂度为 $O(n^2k)$。