JOISC2022 Day1 题解

First Post:

Last Update:

体感难度 : T3 < T1 < T2

T3 成了最近板刷唯一做出来的题。

T1 是“刚好会做”和“刚好不会做”的题。

T2 非常强大，有些启发。

loj3687 D1T3 错误拼写

题意：计数满足如下要求的字符串 ：

  2. 设 表示将 中第 个字符删去后得到的字符串。给出两个长度为 的数组 ，要求 满足 （$$ 是字典序小于等于）。

。

考虑一个 代表什么。

显然，这个大小关系等价于 与 的大小关系。

对每一位进行比较，就相当于比较 和 。

这启发我们根据 中的连续相等段进行 DP。

设 表示 是 中某个极长相等段的右端点，， 是小于 还是大于 。枚举 的那个连续段 ，尝试从 转移，然后考虑 带来的限制。

如果存在 满足 ，说明 必须小于 （因为状态中定义 ）。

同理，如果存在 满足 ，那 。

如果这两个条件满足则不能从 转移到 。

否则，不满足和只满足一个的 肯定是一段区间，而这些区间的转移是相同的。进行一些前缀和优化即可做到 。

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
#include <bits/stdc++.h>
using namespace std;
namespace FastIO{
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;
const int N = 5e5 + 5,P = 1e9 + 7,C = 26;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m;
int a[N],b[N];
bool tp[N];
int Mxr[2][N];
int L[N],R[N]; // 有限制的转移区间，[Ri+1,i-1] 是没有限制的转移区间
int f[N][C][2],sum[N][C][2];
int ST[2][20][N],lg[N];
inline int Qmax(int (*ST)[N],int l,int r)
{
	int k = lg[r - l + 1];
	return max(ST[k][l],ST[k][r-(1<<k)+1]);
}
int main()
{
	read(n);read(m);
	for(int i = 1;i <= m;i++) read(a[i]),read(b[i]);
	for(int i = 1;i <= m;i++)
		if(a[i] < b[i]) Mxr[0][a[i]] = max(Mxr[0][a[i]],b[i] - 1);
		else Mxr[1][b[i]] = max(Mxr[1][b[i]],a[i] - 1);
	
	lg[0] = -1;
	for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1;i <= n;i++) ST[0][0][i] = Mxr[0][i],ST[1][0][i] = Mxr[1][i];
	for(int j = 1;j < 20;j++)
		for(int i = 1;i + (1 << j) - 1 <= n;i++)
			ST[0][j][i] = max(ST[0][j - 1][i],ST[0][j - 1][i + (1 << j - 1)]),
			ST[1][j][i] = max(ST[1][j - 1][i],ST[1][j - 1][i + (1 << j - 1)]);
	for(int i = 1;i <= n;i++)
	{
		int v1,v2;
		int lef = 0,righ = i;
		while(lef < righ)
		{
			int mid = lef + righ + 1 >> 1;
			if(Qmax(ST[0],mid,i) >= i) lef = mid;
			else righ = mid - 1;
		}
		v1 = lef;
		lef = 0;righ = i;
		while(lef < righ)
		{
			int mid = lef + righ + 1 >> 1;
			if(Qmax(ST[1],mid,i) >= i) lef = mid;
			else righ = mid - 1;
		}
		v2 = lef;
		L[i] = min(v1,v2);
		R[i] = max(v1,v2) - 1;
		if(v1 < v2) tp[i] = 1; else tp[i] = 0;
		// printf("L,R,tp:%d,%d,%d,%d,%d\n",L[i],R[i],tp[i],v1,v2);
	}

	f[0][0][0] = f[0][1][1] = sum[0][0][0] = sum[0][1][1] = 1;
	for(int i = 1;i <= n;i++)
	{
		if(R[i] < i)
		{
			int ss[C];
			memset(ss,0,sizeof ss);
			for(int j = 0;j < C;j++)
			{
				ss[j] = sum[i - 1][j][0];
				if(R[i] >= 0) Plus(ss[j],P - sum[R[i]][j][0]);
				j ? Plus(ss[j],ss[j - 1]) : void();
			}
				
			for(int j = 1;j < C;j++)
				Plus(f[i][j][0],ss[j - 1]),Plus(f[i][j][1],ss[j - 1]);
			memset(ss,0,sizeof ss);
			for(int j = C - 1;j > 0;j--)
			{
				ss[j] = sum[i - 1][j][1];
				if(R[i] >= 0) Plus(ss[j],P - sum[R[i]][j][1]);
				j != C - 1 ? Plus(ss[j],ss[j + 1]) : void();
			}
			for(int j = 0;j < C - 1;j++)
				Plus(f[i][j][0],ss[j + 1]),Plus(f[i][j][1],ss[j + 1]);
		}
		if(R[i] >= 0 && L[i] <= R[i])
		{
			int ss[C];
			memset(ss,0,sizeof ss);
			for(int j = 0;j < C;j++)
			{
				Plus(ss[j],sum[R[i]][j][0]);
				if(L[i] > 0) Plus(ss[j],P - sum[L[i] - 1][j][0]);
				if(j) Plus(ss[j],ss[j - 1]);
			}
			for(int j = 1;j < C;j++)
				Plus(f[i][j][tp[i]],ss[j - 1]);
			memset(ss,0,sizeof ss);
			for(int j = C - 1;j > 0;j--)
			{
				Plus(ss[j],sum[R[i]][j][1]);
				if(L[i] > 0) Plus(ss[j],P - sum[L[i] - 1][j][1]);
				if(j != C - 1) Plus(ss[j],ss[j + 1]);
			}
			for(int j = 0;j < C - 1;j++)
				Plus(f[i][j][tp[i]],ss[j + 1]);
		}
		for(int j = 0;j < C;j++)
			sum[i][j][0] = sum[i - 1][j][0],Plus(sum[i][j][0],f[i][j][0]),
			sum[i][j][1] = sum[i - 1][j][1],Plus(sum[i][j][1],f[i][j][1]);
	}
	int ans = 0;
	for(int j = 0;j < C;j++)
		Plus(ans,f[n][j][0]);
	cout << ans << endl;
	return 0;
}

loj3685 D1T1 监狱

题意 : https://loj.ac/p/3685

这种一眼难有多项式做法的题，一般是需要发掘一些性质的。

我们断言一个囚犯如果开始走，就不会在中途停留，会一直从 走到 。

感性理解一下，考虑路径 如果中途停留在了某个点 ，说明有些路径的 在 到 的路径上上（所以要走到 使得它们可以走过来），有些路径的 在 到 的路径上。但是此时，我们先走那些 在 到 的路径，再走当前这条，再走 在 到 上的路径，效果是一样的，且没有中间停留。

这个结论出来了之后，我们就可以直接考虑两条路径的关系。对于 和 ，如果 在 到 的路径上，说明 比 要先走，如果 在 到 的路径上，说明 比 要后走。

把这个二元关系建个图跑拓扑排序就能拿到 分。

我都想到了这里，但没有想到，接下来的事情只需一个倍增优化建图即可。

优化建图的具体细节可以看代码。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 5,Sz = N * 44,M = 4e7 + 5;
int n,m;
vector<int> G[N];
int s[N],t[N];
int anc[20][N],up[20][N],down[20][N],dep[N];
int deg[Sz];
int fir[Sz],nxt[M],to[M],ect = 0;
inline void addedge(int u1,int v1) { nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;++deg[v1];}
int idcnt;
void dfs0(int x,int f)
{
	anc[0][x] = f;dep[x] = dep[f] + 1;
	for(int i = 1;i <= 19;i++) anc[i][x] = anc[i - 1][anc[i - 1][x]];
	for(auto y : G[x])
		if(y != f) dfs0(y,x);
}
int jump(int x,int y)
{
	for(int i = 19;i >= 0;i--)
		if(dep[anc[i][x]] > dep[y]) x = anc[i][x];
	return x;
}
int lca(int x,int y)
{
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = 19;i >= 0;i--)
		if(dep[anc[i][x]] >= dep[y]) x = anc[i][x];
	if(x == y) return x;
	for(int i = 19;i >= 0;i--)
		if(anc[i][x] != anc[i][y])
			x = anc[i][x],y = anc[i][y];
	return anc[0][x];
}
void work()
{	
	ect = 0;
	for(int i = 1;i <= idcnt;i++)
		fir[i] = deg[i] = 0;
	idcnt = 0;
	cin >> n;
	for(int i = 1;i <= n;i++) G[i].clear();
	for(int i = 1;i < n;i++)
	{
		int a,b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cin >> m;
	for(int i = 1;i <= m;i++)
		cin >> s[i] >> t[i];
	idcnt = m;
	for(int i = 1;i <= n;i++)
		for(int j = 0;j < 20;j++) anc[j][i] = 0;
	dfs0(1,0);
	for(int i = 1;i <= n;i++)
		up[0][i] = ++idcnt,down[0][i] = ++idcnt;
	for(int j = 1;j < 20;j++)
		for(int i = 1;i <= n;i++)
		if(dep[i] >= (1 << j))
		{
			up[j][i] = ++idcnt;down[j][i] = ++idcnt;
			if(j)
			{
				addedge(up[j - 1][i],up[j][i]);addedge(up[j - 1][anc[j - 1][i]],up[j][i]);
				addedge(down[j][i],down[j - 1][i]);addedge(down[j][i],down[j - 1][anc[j - 1][i]]);
			} 
		}
	for(int i = 1;i <= m;i++)
	{
		int x = s[i],y = t[i];
		addedge(i,up[0][x]);addedge(down[0][y],i);
		x = lca(s[i],t[i]) == s[i] ? jump(t[i],s[i]) : anc[0][s[i]];

		if(dep[x] < dep[y]) swap(x,y);
		for(int j = 19;j >= 0;j--)
			if(dep[anc[j][x]] >= dep[y])
				addedge(up[j][x],i),x = anc[j][x];
		if(x == y) addedge(up[0][x],i);
		else
		{
			for(int j = 19;j >= 0;j--)
			if(anc[j][x] != anc[j][y])
				addedge(up[j][x],i),addedge(up[j][y],i),
				x = anc[j][x],y = anc[j][y];
			addedge(up[0][x],i);addedge(up[0][y],i);
			addedge(up[0][anc[0][x]],i);
		}	
	
		x = s[i];y = lca(s[i],t[i]) == t[i] ? jump(s[i],t[i]) : anc[0][t[i]];

		if(dep[x] < dep[y]) swap(x,y);
		for(int j = 19;j >= 0;j--)
			if(dep[anc[j][x]] >= dep[y])
				addedge(i,down[j][x]),x = anc[j][x];
		if(x == y) addedge(i,down[0][x]);
		else
		{
			for(int j = 19;j >= 0;j--)
			if(anc[j][x] != anc[j][y])
				addedge(i,down[j][x]),addedge(i,down[j][y]),
				x = anc[j][x],y = anc[j][y];
			addedge(i,down[0][x]);addedge(i,down[0][y]);
			addedge(i,down[0][anc[0][x]]);
		}	
	}
	queue<int> Q;
	for(int i = 1;i <= idcnt;i++) if(!deg[i]) Q.push(i);
	while(!Q.empty())
	{
		int x = Q.front();Q.pop();
		// printf("Q:%d\n",x);
		for(int i = fir[x],y;y = to[i],i;i = nxt[i])
			if(!(--deg[y])) Q.push(y);
	}
	for(int i = 1;i <= idcnt;i++) if(deg[i]) return puts("No"),void();
	puts("Yes");
}
int main()
{
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}

loj3686 D1T2 京都观光

题意： https://loj.ac/p/3686

直接 DP 可以拿到 10 分的高分。我们仍然需要挖掘一些性质。

考察两行 ，两列 ，假设我们不会中间拐弯。

先横再竖的代价是

先竖再横的代价是 。

那么我们选择先走横当且仅当 。

这启示我们答案路径的选择和斜率有关。

既然涉及到了斜率，就不能只考察二元关系了。

考察三行 ，两列 。

蓝色路径减红色路径的代价是

蓝色路径减绿色路径的代价是 。

如果这两个值不都小于 ，说明 这一列就没啥用了。

上面的式子小于 当且仅当 。

下面的式子小于 当且仅当

那么我们发现，当对于任意 ，都有 时， 才可能有用，说明有用的 一定形成一个凸包。 同理。

把两个序列的凸包求出来之后，我们要根据这两个凸包求答案。

这个时候可以直接做个闵可夫斯基和，也就是对凸包中的直线进行一个归并排序。再换句话说，就是每次根据最开始的那个 与 的大小关系，决定先走横还是先走竖。这个过程可以导出唯一解，且任意其他的解都可以通过不断调整得到这个解，所以这就是个最优解。

具体细节可以看代码。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m,a[N],b[N];
inline double slopeA(int x,int y) { return 1.0*(a[y] - a[x]) / (y - x);}
inline double slopeB(int x,int y) { return 1.0*(b[y] - b[x]) / (y - x);}
int ha[N],cnta; 
int hb[N],cntb;
// a,b 两边的凸包
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= m;i++) cin >> b[i];
	ha[cnta = 1] = 1;
	for(int i = 2;i <= n;i++)
	{
		while(cnta > 1 && slopeA(ha[cnta - 1],ha[cnta]) > slopeA(ha[cnta],i))
			--cnta;
		ha[++cnta] = i;
	}
	hb[cntb = 1] = 1;
	for(int i = 2;i <= m;i++)
	{
		while(cntb > 1 && slopeB(hb[cntb - 1],hb[cntb]) > slopeB(hb[cntb],i))
			--cntb;
		hb[++cntb] = i;
	}
	long long ans = 0;
	int i = 1,j = 1;
	while(i < cnta && j < cntb)
		if(slopeA(ha[i],ha[i + 1]) <= slopeB(hb[j],hb[j + 1]))
			ans += 1ll * b[hb[j]] * (ha[i + 1] - ha[i]),++i;
		else ans += 1ll * a[ha[i]] * (hb[j + 1] - hb[j]),++j;
	while(i < cnta) ans += 1ll * b[hb[j]] * (ha[i + 1] - ha[i]),++i;
	while(j < cntb) ans += 1ll * a[ha[i]] * (hb[j + 1] - hb[j]),++j;
	cout << ans << endl;
	return 0;
}
≡