Lijinrui299792458

不做沉底的木做举重若轻的船。

做题记录-省选2021A

发表于

P7514 卡牌游戏

首先，翻面的一定是左边连续一段和右边连续一段。

那么假设我都翻的右面，现在把翻的机会一个个移向左边。提前处理掉一定不会翻的卡牌，可以发现有两个区间：$[\min b_r,a_r]$ 和 $[a_l,\max b_l]$。前者用 ()，后者用 [] 表示，{} 为下一个 []，<> 是上一个。两个区间只会向左移。

答案一定是下述情况：可翻卡牌数饱和；)]}；[({)]}；<([)>]；[()] 的最小值。除最后一种情况都可直接指针扫。而最后一种情况每次事实上是维护一段最值，每次从最前删除，最后加入，可维护一单调队列。

非常笨拙然而是 $O(n)$ 的。

P7515 矩阵游戏

显然有 $n+m-1$ 个自由元，那就设在第一行和第一列。显然每一组自由元的取值唯一对应了一个矩阵。

考虑两个矩阵，他们仅有一个自由元不同。为了保证其它自由元不变，矩阵的变化一定是：在该行或列的元素应依次 $+c,-c,+c,\cdots$。

有一个例外：$a_{1,1}$。如果改变他，则所有的非自由元都会改变。为了统一我们修改第一行和第一列的所有元素。如果再对其他自由元修改使其回复原值，那么所造成的修改就是它应有的修改。

那么钦定这些自由元是 0，求出矩阵原始值。然后进行一些操作：对某一行或某一列（特殊地，第一行和第一列由同一变量控制）进行上述操作。

调整一下符号，可以化为 $nm$ 个不等式，对于 $a_{i,j}$，
$$
l_{i,j}\le x_i-y_j\le r_{i,j}
$$
即可差分约束。

P7516 图函数

一个转化

将题目中 $f(u,G)$ 能够是 cnt+1 的情况称为 $u\rightarrow v$ 。

一定存在 $u,v$ 之间路径，其上所有的点 $w$，有 $u\nrightarrow w$ 或 $w>v$。

如果不存在路径使得 $w>v$，那么一定存在路径上的点，$u\nrightarrow w$，$w<v$。

那么路径上其他点一定满足 $u\nrightarrow t$ 或 $t>v>w$。

进而存在符合要求的 $u,w$ 双向路径。矛盾。

故 $u\rightarrow v$ 等价于存在 $u,v$ 之间路径，其上的点都满足 $w>v$。

思路

我们可以从大到小向图中加入节点，在新加入节点 $u$ 时统计 $v\rightarrow u$ 的答案。

求 $u,v$ 间路径上边的编号的最小值的最大值，由于我们从小到大删边，就可以查分了。

于是你就可以 $O(n^3)$Floyd 了。（能过就离谱，某卡常大师跑的比 $O(nm)$ 快更离谱）

然而这不同于一般的最短路。我们发现：可以从大到小枚举边：如果某一时刻加入这条边后某个节点忽然连通那么它的答案就是新加入边的编号而且以后不会变了。这样就不会反复更新一个点，如 Floyd 那样浪费时间。

拿边更新的时候，如果入点已求过就正常了。如果没求过呢？

那么我保留所有现在更新不了但以后可能更新的边。当新更新一个点时在这些边上进行 BFS，显然一个节点只会更新一次。容易分析此时复杂度为 $O(n(n+m))$。

Code

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
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;

inline void read(int &x)
{
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
}

struct edge
{
	int fr,to,nxt;bool dir;
}e[200005];int t[1005],cnt;
inline void ad(int u,int v)
{
	bool flag=0;int mu=min(u,v);
	if(u>v)flag=1;
	e[++cnt].to=v,e[cnt].nxt=t[mu],t[mu]=cnt,e[cnt].dir=flag,e[cnt].fr=u;
}

struct EDGE
{
	int nxt,to;
}E[200005];int T[1005],CNT;
inline void AD(int u,int v)
{
	E[++CNT].to=v,E[CNT].nxt=T[u],T[u]=CNT;
}
int q[1005],l,r;
void bfs(int x,int *tima)
{
	l=r=1,q[1]=x;
	int _;
	while(l<=r)
	{
		_=q[l++];
		for(int i=T[_];i;i=E[i].nxt)if(!tima[E[i].to])tima[E[i].to]=tima[x],q[++r]=E[i].to;
	}
}

int n,m;
int tim[200005];
int f[1005],timb[1005],timc[1005];
bool fl[200005];

int main()
{
	read(n),read(m);
	for(int x,y,i=1;i<=m;i++)
	{
		read(x),read(y);
		ad(x,y);
	}
	for(int i=n-1;i;i--)
	{
		memset(timb,0,sizeof(timb));memset(T,0,sizeof(T));CNT=0;timb[i]=inf;
		for(int j=t[i];j;j=e[j].nxt)if(!e[j].dir)fl[j]=1;
		for(int j=m,x,y;j;j--)if(fl[j])
		{
			x=e[j].fr,y=e[j].to;if(timb[y])continue;
			if(timb[x])timb[y]=j,bfs(y,timb);
			else AD(x,y);
		}
		for(int j=t[i];j;j=e[j].nxt)fl[j]=e[j].dir;
		memset(timc,0,sizeof(timc));memset(T,0,sizeof(T));CNT=0;timc[i]=inf;
		for(int j=m,x,y;j;j--)if(fl[j])
		{
			x=e[j].to,y=e[j].fr;if(timc[y])continue;
			if(timc[x])timc[y]=j,bfs(y,timc);
			else AD(x,y);
		}
		for(int j=t[i];j;j=e[j].nxt)if(!e[j].dir)fl[j]=1;
		for(int j=n;j>i;j--)if(timb[j]&&timc[j])tim[min(timb[j],timc[j])]++;
	}
	tim[m+1]=n;
	for(int i=m;i>=1;i--)tim[i]=tim[i]+tim[i+1];
	for(int i=1;i<=m+1;i++)printf("%d ",tim[i]);
	return 0;
}

P7518 宝石

如果我给颜色按收集顺序重新编号，那么我就是在求最长的序列 1,2,…

如果在链上，可以想到用 $f[i]$ 表示下一个颜色为 $col[i]+1$ 的位置。那么我可以倍增求出从该位置向后拓展 $x$ 位的最短长度，倍增求出区间中第一个 1，即可倍增求解。

现在在树上。路径分两段：上去的和下来的。对于上去的可以直接树上倍增。对于下来的向下走不太方便可以二分答案反向倍增，现在问题转化为 $x$ 的祖先中深度最深的颜色为 $c$ 的节点。可以用主席树。

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

Code

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
#include<bits/stdc++.h>
using namespace std;

inline void read(int &x)
{
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
}

int n,m,c;
struct tree
{
	int nxt,to;
}e[400005];int t[200005],cnt;
void ad(int u,int v)
{
	e[++cnt].to=v,e[cnt].nxt=t[u],t[u]=cnt;
	e[++cnt].to=u,e[cnt].nxt=t[v],t[v]=cnt;
}
int cmap[50005],col[200005];
struct segmenttree
{
	int ls,rs,val;
}tr[8000000];int siz,rt[200005];
void upd(int x)
{
	tr[x].val=max(tr[tr[x].ls].val,tr[tr[x].rs].val);
}
void insert(int &u,int v,int key,int val,int l,int r)
{
	u=++siz;
	if(l==r)
	{
		tr[u].val=val;
		return;
	}
	int mid=l+r>>1;if(v)tr[u]=tr[v];
	if(key<=mid)insert(tr[u].ls,tr[v].ls,key,val,l,mid);
	else insert(tr[u].rs,tr[v].rs,key,val,mid+1,r);
	upd(u);
}
int query(int u,int key,int l,int r)
{
	if(!u)return 0;
	if(l==r)return tr[u].val;
	int mid=l+r>>1;
	if(key<=mid)return query(tr[u].ls,key,l,mid);
	return query(tr[u].rs,key,mid+1,r);
}

int dep[200005],up[200005][20],down[200005][20],fa[200005][20];
void dfs(int x,int fath)
{
	dep[x]=dep[fath]+1,fa[x][0]=fath;
	insert(rt[x],rt[fath],col[x],x,1,c);
	if(col[x]>1)down[x][0]=query(rt[x],col[x]-1,1,c);if(col[x]<c)up[x][0]=query(rt[x],col[x]+1,1,c);
	for(int i=1;up[x][i-1];i++)up[x][i]=up[up[x][i-1]][i-1];
	for(int i=1;down[x][i-1];i++)down[x][i]=down[down[x][i-1]][i-1];
	for(int i=1;fa[x][i-1];i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=t[x];i;i=e[i].nxt)if(e[i].to!=fath)dfs(e[i].to,x);
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	for(int i=17;i>=0&&dep[u]>dep[v];i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
	if(u!=v)
	{
		for(int i=17;i>=0;i--)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
		u=fa[u][0];
	}
	return u;
}

int Down(int stpos,int edpos)
{
	for(int i=17;i>=0&&dep[stpos]>dep[edpos];i--)if(dep[down[stpos][i]]>=dep[edpos])stpos=down[stpos][i];
	return stpos;
}
int binary(int cl,int l,int r,int stpos,int edpos)
{
	int mid,d,fm;
	while(l<=r)
	{
		mid=l+r>>1;
		fm=query(rt[stpos],mid,1,c),d=0;
		if(dep[fm]>=dep[edpos])d=Down(fm,edpos);
		if(d&&col[d]<=cl)l=mid+1;
		else r=mid-1;
	}
	return r;
}

int main()
{
	read(n),read(m),read(c);
	for(int i=1,p;i<=c;i++)read(p),cmap[p]=i;
	for(int i=1,w;i<=n;i++)read(w),col[i]=cmap[w];
	for(int i=1,u,v;i<n;i++)read(u),read(v),ad(u,v);
	dfs(1,0);
	
	int q;read(q);
	for(int s,f1,T,lc,cl,a;q;q--)
	{
		read(s),read(T),
		lc=lca(s,T);
		f1=query(rt[s],1,1,c);
		for(int i=17;i>=0&&dep[f1]>dep[lc];i--)if(dep[up[f1][i]]>=dep[lc])f1=up[f1][i];
		if(col[f1]==c)
		{
			printf("%d\n",c);
			continue;
		}
		cl=(dep[f1]>=dep[lc])?(col[f1]+1):1;
		if(T==lc)
		{
			printf("%d\n",cl-1);
			continue;
		}
		a=binary(cl,cl,c,T,lc);
		printf("%d\n",a);
	}
	return 0;
}

P7519 滚榜

如果我们知道了最终排名，那么很容易贪心求出最少的过题数。

那么如果我们确定了排名的后 $x$ 位，现在还剩 $y$ 道题可以切，上一位是 $z$，封完榜又切了 $k$ 道题，枚举这一位是谁，他至少要切多少题，才能保有他的位置。那么这就是 $O(2^nm^2n)$ 的。

考虑优化：我们在求完这一位至少切这么多题之后，由于封榜后切的题数不降，因此我们先让剩下的人都切这些题，判断大小的时候相当于谁都一道题没切。我们在可供切的题数中减去这部分即可，这样减去一维（这好像叫费用提前计算？反正叫什么无所谓），空间 $O(2^nmn)$，时间 $O(2^nmn^2)$。

Code

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void read(int &x)
{
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
}

int n,m,a[14];
int f[8193][501][13],g[8193];

inline int lowbit(int x){return x&(-x);}

int dfs(int x,int s,int left,int lst)
{
	if(left<0)return 0;
	if(x==n)return 1;
	if(f[s][left][lst]>=0)return f[s][left][lst];
	f[s][left][lst]=0;
	int ss=s,y,nb;
	while(ss)y=lowbit(ss),
	nb=max(0,a[lst]-a[g[y]]+(g[y]>lst)),
	f[s][left][lst]+=dfs(x+1,s^y,left-nb*(n-x),g[y]),
	ss^=y;
	return f[s][left][lst];
}

int main()
{
	memset(f,-1,sizeof(f));
	read(n),read(m);
	int ma=0;ll ans=0;
	for(register int i=0,j=1;i<n;i++,j<<=1)g[j]=i;
	for(register int i=0;i<n;i++)
	{
		read(a[i]);
		if(a[i]>a[ma])ma=i;
	}
	int o=(1<<n)-1;
	for(register int i=0,j=1,nb;i<n;i++,j<<=1)nb=a[ma]-a[i]+(i>ma),ans+=1LL*dfs(1,j^o,m-nb*n,i);
	printf("%lld",ans);
	return 0;
}

P7520 支配

可以发现在一个节点 $u$ 的支配集中两个节点一定有支配关系。又因为支配关系有传递性和反对称性，一定存在唯一的一个节点，使得除了 $u$ 所有支配 $u$ 的节点都支配 $v$。那么我们建一棵树，$v$ 是 $u$ 的父亲。一个节点的支配集即该节点的所有祖先。可以 $n^2$ 暴力建树。

现加入一条边 $s\to t$，如果一个节点的支配集变化它的子树中所有节点的支配集一定都变化。那么找到支配集变化的最高的节点；它的父亲支配集不变，那么一定是父亲不再支配他了。

此时一定有 $1\to s\to t\to x$ 不经过 $\text{fa}(x)$。那么 $s$ 不在 $\text{fa}(x)$ 子树中，且 $t\to x$ 不经过 $\text{fa}(x)$。可以预处理；然而从某节点出发到达另一节点不经过到达节点的父亲限制不统一，那么可以建反图，变成一个节点不经过其父亲能到达哪些节点。

时间 $O(n^2+nq)$。

Code

暴力到连 lca 都是暴力求的，反正数据范围小。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x)
{
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
}

struct edge
{
	int nxt,to;
}e[6010],d[6010];int t[3005],tt[3005],cnt;
void ad(int u,int v)
{
	e[++cnt].to=v,e[cnt].nxt=t[u],t[u]=cnt;
	d[cnt].to=u,d[cnt].nxt=tt[v],tt[v]=cnt;
}

int n,m,Q;

vector <int> dom[3005];int siz[3005];
int q[3005],l,r;
bool vis[3005];
void solv(int x)
{
	memset(vis,0,sizeof(vis));
	q[1]=1,l=r=1,vis[1]=1;
	int _;
	while(l<=r)
	{
		_=q[l++];
		for(int i=t[_];i;i=e[i].nxt)if(e[i].to!=x&&(!vis[e[i].to]))q[++r]=e[i].to,vis[e[i].to]=1;
	}
	for(int i=2;i<=n;i++)if(!vis[i])dom[i].push_back(x);
}

int fa[3005];vector <int> son[3005];
int s[3005],dep[3005];
void dfs(int x)
{
	s[x]=1;
	for(int i:son[x])dep[i]=dep[x]+1,dfs(i),s[x]+=s[i];
}

bool con[3001][3001];
void vlos(int x)
{
	memset(vis,0,sizeof(vis));
	q[1]=x,l=r=1,vis[x]=1;
	int _;
	while(l<=r)
	{
		_=q[l++];
		for(int i=tt[_];i;i=d[i].nxt)if(d[i].to!=fa[x]&&(!vis[d[i].to]))q[++r]=d[i].to,vis[d[i].to]=1;
	}
	for(int i=2;i<=n;i++)if(!vis[i])con[i][x]=1;
}

int dfs2(int x,int y,int z)
{
	if((!con[y][x])&&fa[x]!=z)return s[x];
	int ret=0;
	for(int i:son[x])
	ret+=dfs2(i,y,z);
	return ret;
}

int main()
{
	read(n),read(m),read(Q);
	for(int i=1,x,y;i<=m;i++)read(x),read(y),ad(x,y);
	for(int i=2;i<=n;i++)
	{
		solv(i);dom[i].push_back(1);
	}
	for(int i=2;i<=n;i++)siz[i]=dom[i].size();siz[1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j:dom[i])if(siz[j]==siz[i]-1)
		{
			fa[i]=j,son[j].push_back(i);
			break;
		}
	}
	dfs(1);
	for(int i=2;i<=n;i++)vlos(i);
	for(int S,T,x,y,ans;Q;Q--)
	{
		read(S),read(T);
		x=S,y=T;
		if(dep[x]>dep[y])swap(x,y);
		while(dep[x]<dep[y])y=fa[y];
		while(x!=y)x=fa[x],y=fa[y];
		if(dep[T]<=dep[x]+1)
		{
			puts("0");
			continue;
		}
		ans=0;
		for(int i:son[x])
		ans+=dfs2(i,T,x);
		printf("%d\n",ans);
	}
	return 0;
}