Eternity

Until The End

2021 CSP-S 第二轮

发表于 更新于 分类于
本文字数： 19k 阅读时长 ≈ 17 分钟

考场成绩： $95pt+0+48pt+0=143pt$

现成绩： $100pt+100pt+100pt+65pt=360pt$

P7913 [CSP-S 2021] 廊桥分配

实力贪心，当初真考的时候在我们学校，我当时坐在 B003 时有一份代码，我就替那个人交了，结果那人爆零。然后洛谷就一直留着这道题，后来清题的时候就把这道题给做了。所以留有印象。

分开计算，首先将使用 $1\sim n$ 的国内廊桥能最多停多少和 $1\sim n$ 的国外廊桥能停放多少。然后计算答案则是 $ans=\max(res_{in}[i]+res_{out}[n-i]),0\leq i\leq n$ 。这一步是能够想到的。

对于计算过程，使用两个优先队列，一个 $lQueue$ 来记录一个二元组 $(x,y)$ 表示当前停靠飞机的离开时间和停靠的廊桥编号。另一个 $wQueue$ 来记录当前空闲的廊桥编号，至于为什么是优先队列，因为整个过程秉承“先到先得”的原则，且让廊桥编号尽可能大。最后统计前缀和即可。

好吧，事实上，今天上午并没有做出了这道题，只是翻出了之前的代码，然后贺了上去，虽然之后在摆烂的时候把代码完全搞懂了。但总归不是自己做出来的。
AC 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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int MAXM=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
typedef pair<int,int>Pir;
int N,M_in,M_out;
struct Air
{
	int arrive,leave;
    #define ain(i) In[i].arrive
    #define aout(i) Out[i].arrive
    #define lin(i) In[i].leave
    #define lout(i) Out[i].leave
}In[MAXM],Out[MAXM];
inline bool cmp(Air a,Air b)
{
	return a.arrive<b.arrive;
}
int Res_in[MAXM],Res_out[MAXM];
inline void calc(Air *t,int M,int *res)
{
	priority_queue<Pir,vector<Pir>,greater<Pir> >lQ;
	priority_queue<int,vector<int>,greater<int> >wQ;
	for(int i=1;i<=N;++i) wQ.push(i);
	for(int i=1;i<=M;++i)
	{
		while(!lQ.empty()&&t[i].arrive>=lQ.top().first)
		{
			wQ.push(lQ.top().second);
			lQ.pop();
		}
		if(wQ.empty()) continue;
		int Dist=wQ.top();
		wQ.pop();
		++res[Dist];
		lQ.push(make_pair(t[i].leave,Dist));
	}
	for(int i=1;i<=N;++i) res[i]+=res[i-1];
}
int main()
{
//     freopen("airport.in","r",stdin);
//     freopen("airport.out","w",stdout);
    read(N,M_in,M_out);
    for(int i=1;i<=M_in;++i) read(ain(i),lin(i));
    for(int i=1;i<=M_out;++i) read(aout(i),lout(i));
    sort(In+1,In+1+M_in,cmp);
    sort(Out+1,Out+1+M_out,cmp);
    calc(In,M_in,Res_in);
    calc(Out,M_out,Res_out);
    int Ans=0;
    for(int i=0;i<=N;++i)
    {
    	int res=Res_in[i]+Res_out[N-i];
    	checkMax(Ans,res);
    }
    printf("%d",Ans);
    return 0;
}
/*
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
*/

这道题还有一个思路，是 $\text{LuckyLeaves}$ 的考场思路，用线段树维护廊桥数量的最大停靠数，然后用线段树二分，统计答案时差分即可。

两种思路差不多，线段树二分就相当于是手写了一个优先队列。总的思路还是模拟题意。

P7914 [CSP-S 2021] 括号序列

神仙分讨区间 $\text{Dp}$ ，当初参考的是一个不太复杂的做法：

记状态：$Dp[l][r][6]$ ，表示区间 $[l,r]$ 的 $6$ 种情况。

（说实话，能够把题读懂已经够呛了）这 $6$ 种情况表示了六种超级括号序列的表示。

  1. $Dp[l][r][0]$ 表示形如 $\ast\ast\dots\ast\ast$ 的括号序列，即全部都是 $\ast$ 的括号序列；
  2. $Dp[l][r][1]$ 表示形如 $(\cdots)$ 的括号序列，即正好被包裹的情况；
  3. $Dp[l][r][2]$ 表示形如 $(\cdots)\ast\ast(\cdots)\ast\ast$ 的括号序列，即左边为完整括号，右边为 $\ast$ 的情况；
  4. $Dp[l][r][3]$ 表示形如 $(\cdots)\ast\ast(\cdots)\ast\ast(\cdots)$ 的括号序列，即左右为括号，但不为同一组括号；
  5. $Dp[l][r][4]$ 表示形如 $\ast\ast\ast(\cdots)\ast\ast(\cdots)$ 的括号序列，即 $Dp[l][r][2]$ 的左右翻转；
  6. $Dp[l][r][5]$ 表示形如 $\ast\ast(\cdots)\ast(\cdots)\ast\ast$ 的括号序列，即左右皆为 $\ast$ ，但中间有完整括号。

然后就是转移，令函数 $cmp(l,r)$ 进行判断，$S[l],S[r]$ 是否能够配对成括号，如果能，返回 $1$ ，否则返回 $0$。

  1. $Dp[l][r][0]$ 直接暴力转移，枚举 $Dp[l][r-1][0]$ 是否存在，按位与即可。
  2. $Dp[l][r][1]=(Dp[l+1][r-1][0]+Dp[l+1][r-1][2]+Dp[l+1][r-1][3]+Dp[l+1][r-1][4])\times cmp(l,r)$
  3. $\displaystyle Dp[l][r][2]=\sum_{i=l}^{r}Dp[l][i][3]\times Dp[i+1][r][0]$
  4. $\displaystyle Dp[l][r][3]=\sum_{i=l}^{r-1}(Dp[l][i][2]+Dp[l][i][3])\times Dp[i+1][r][1]+Dp[l][r][1]$
  5. $\displaystyle Dp[l][r][4]=\sum_{i=l}^{r}(Dp[l][i][4]+Dp[l][i][5])\times Dp[i+1][r][1]$
  6. $\displaystyle Dp[l][r][5]=\sum_{i=l}^{r-1}Dp[l][i][4]\times Dp[i+1][r][0]+Dp[l][r][0]$

其实吧，主要在于能不能把所有的情况全部想到并分类表示，然后转移其实就简单了，$n\leq 500$ 乱搞都可以，实际时间复杂度 $\mathcal O(6n^3)$ ，跑不满。

虽然要取模，但是还是要开 long long 。

AC 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
#include<bits/stdc++.h>
#define int long long
const int MAXN=5e2+10;
const int Mod=1e9+7;
int N,K,Dp[MAXN][MAXN][10];
char S[MAXN];
inline bool cmp(int a,int b)
{
    return (S[a]=='('||S[a]=='?')&&(S[b]==')'||S[b]=='?');
}
signed main()
{
    scanf("%lld%lld%s",&N,&K,S+1);
    for(int i=1;i<=N;++i) Dp[i][i-1][0]=1;
    for(int len=1;len<=N;++len)
        for(int l=1;l<=N-len+1;++l)
        {
            int r=l+len-1;
            if(len<=K) Dp[l][r][0]=Dp[l][r-1][0]&&(S[r]=='*'||S[r]=='?');
            if(len>=2)
            {
                if(cmp(l,r)) Dp[l][r][1]=(Dp[l+1][r-1][0]+Dp[l+1][r-1][2]+Dp[l+1][r-1][3]+Dp[l+1][r-1][4])%Mod;
                for(int k=l;k<=r-1;++k)
                {
                    Dp[l][r][2]=(Dp[l][r][2]+Dp[l][k][3]*Dp[k+1][r][0])%Mod;
                    Dp[l][r][3]=(Dp[l][r][3]+(Dp[l][k][2]+Dp[l][k][3])*Dp[k+1][r][1])%Mod;
                    Dp[l][r][4]=(Dp[l][r][4]+(Dp[l][k][4]+Dp[l][k][5])*Dp[k+1][r][1])%Mod;
                    Dp[l][r][5]=(Dp[l][r][5]+Dp[l][k][4]*Dp[k+1][r][0])%Mod;
                }
            }
            Dp[l][r][5]=(Dp[l][r][5]+Dp[l][r][0])%Mod;
            Dp[l][r][3]=(Dp[l][r][3]+Dp[l][r][1])%Mod;
        }
    printf("%lld",Dp[1][N][3]);
    return 0;
}
/*
10 2
???(*??(?)
*/

P7915 [CSP-S 2021] 回文

考场暴力，居然只是 T 和 M ，比较顺利。

暴力思路

直接 $dfs$ 或者 $bfs$ ，对于一些优化，我后来思考了一下。因为我们要查找的是字典序最小的，所以肯定是优先 $L$ 才会使用 $R$ 。而对于 $bfs$ 而言，大部分的答案都是一并算出来的，所以在比较答案是必须要全部比较，十分消耗时间。而在使用 $dfs$ 的时候，我们可以在前几次搜索时就搜出了一个备选答案，然后可以在中间段的时候就比较当前搜出的答案和原有答案，减少之后的搜索，可能会有一定优化。

后来发现两个方法的得分是一样的。

还有，我在此以磐岩起誓，再不用 string。考场上用了 string ，然后就快快乐乐地 $CE$ 了。起飞， $\text{Dev-C++}$ 还没报错。

一定要用字符数组，方便又快捷。

48pt by dfs 
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<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,N,Num[MAXN],pos1,pos2;
struct Que
{
	int l1,r1,l2,r2;
	string res;
	Que(int l1=0,int r1=0,int l2=0,int r2=0,string res="\0"):
		l1(l1),r1(r1),l2(l2),r2(r2),res(res){}
};
string ans;
int pos[MAXN],tot=0;
void dfs(int l1,int r1,int l2,int r2,string res)
{
	if(!ans.empty()&&res[res.size()-1]>ans[res.size()-1]) return ;
	if(res.size()==N/2)
	{
		string str=res;
		tot=0;
		int l=l1+1,r=r1-1,ls=0,rs=N+1,Cnt=N/2;
		for(int i=1;i<=Cnt;++i)
		{
			if(str[i-1]=='L') pos[++tot]=Num[++ls];
			else pos[++tot]=Num[--rs];
		}
		for(int i=1;i<=Cnt;++i)
		{
			int now=N+1-(i+Cnt);
			if(Num[l]==pos[now])
			{
				str+="L";
				++l;
			}
			else if(Num[r]==pos[now])
			{
				str+="R";
				--r;
			}
			else return ;
		}
		if(str.size()!=N) return ;
		if(ans.empty()) ans=str;
		else
		{
			for(int i=0;i<N;++i)
			{
				if(ans[i]>str[i])
				{
					ans=str;
					return ;
				}
				else if(ans[i]<str[i]) break;
			}
		}
		return ;
	}
	if(Num[l2-1]==Num[l1+1]) dfs(l1+1,r1,l2-1,r2,res+"L");
	if(Num[r2+1]==Num[l1+1]) dfs(l1+1,r1,l2,r2+1,res+"L");
	if(Num[l2-1]==Num[r1-1]) dfs(l1,r1-1,l2-1,r2,res+"R");
	if(Num[r2+1]==Num[r1-1]) dfs(l1,r1-1,l2,r2+1,res+"R");
}
int main()
{
//     freopen("palin.in","r",stdin);
//     freopen("palin.out","w",stdout);
    read(Test);
    while(Test--)
    {
    	read(N);
    	ans.clear();
    	memset(pos,0,sizeof(pos));
    	N<<=1;
    	for(int i=1;i<=N;++i) read(Num[i]);
		for(int i=1;i<=N;++i)
		{
			if(Num[i]==Num[1]&&i!=1) pos1=i;
			if(Num[i]==Num[N]&&i!=N) pos2=i;
		}
    	dfs(1,N+1,pos1,pos1,"L");
    	if(ans.empty()) dfs(0,N,pos2,pos2,"R");
    	if(ans.empty()) printf("-1\n");
    	else cout<<ans<<endl;
    }
    return 0;
}
/*
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
*/
48pt by bfs 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,N,Num[MAXN],pos1,pos2;
struct Que
{
	int l1,r1,l2,r2;
	string res;
	Que(int l1=0,int r1=0,int l2=0,int r2=0,string res="\0"):
		l1(l1),r1(r1),l2(l2),r2(r2),res(res){}
};
string ans;
int pos[MAXN],tot=0;
inline void bfs()
{
	queue<Que>Q;
	Q.push(Que(1,N+1,pos1,pos1,"L"));
	Q.push(Que(0,N,pos2,pos2,"R"));
	while(!Q.empty())
	{
		Que u=Q.front();
		Q.pop();
		if(!ans.empty()&&u.res[u.res.size()-1]>ans[u.res.size()-1]) continue;
		if(u.res.size()==N/2)
		{
			string str=u.res;
			tot=0;
			int l=u.l1+1,r=u.r1-1,ls=0,rs=N+1,Cnt=N/2;
			for(int i=1;i<=Cnt;++i)
			{
				if(str[i-1]=='L') pos[++tot]=Num[++ls];
				else pos[++tot]=Num[--rs];
			}
			for(int i=1;i<=Cnt;++i)
			{
				int now=N+1-(i+Cnt);
				if(Num[l]==pos[now])
				{
					str+="L";
					++l;
				}
				else if(Num[r]==pos[now])
				{
					str+="R";
					--r;
				}
				else continue;
			}
			if(str.size()!=N) continue;
			if(ans.empty()) ans=str;
			else
			{
				for(int i=0;i<N;++i)
				{
					if(ans[i]>str[i])
					{
						ans=str;
						continue;
					}
					else if(ans[i]<str[i]) break;
				}
			}
			continue;
		}
		if(u.l1>u.l2||u.r1<u.r2) continue;
		if(Num[u.l2-1]==Num[u.l1+1]) Q.push(Que(u.l1+1,u.r1,u.l2-1,u.r2,u.res+"L"));
		if(Num[u.r2+1]==Num[u.l1+1]) Q.push(Que(u.l1+1,u.r1,u.l2,u.r2+1,u.res+"L"));
		if(Num[u.l2-1]==Num[u.r1-1]) Q.push(Que(u.l1,u.r1-1,u.l2-1,u.r2,u.res+"R"));
		if(Num[u.r2+1]==Num[u.r1-1]) Q.push(Que(u.l1,u.r1-1,u.l2,u.r2+1,u.res+"R"));
	}
}
int main()
{
//     freopen("palin.in","r",stdin);
//     freopen("palin.out","w",stdout);
    read(Test);
    while(Test--)
    {
    	read(N);
    	ans.clear();
    	memset(pos,0,sizeof(pos));
    	N<<=1;
    	for(int i=1;i<=N;++i) read(Num[i]);
		for(int i=1;i<=N;++i)
		{
			if(Num[i]==Num[1]&&i!=1) pos1=i;
			if(Num[i]==Num[N]&&i!=N) pos2=i;
		}
    	bfs();
    	if(ans.empty()) printf("-1\n");
    	else cout<<ans<<endl;
    }
    return 0;
}
/*
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
*/

正解

还是得明知，我们所求的方案必是字典序最小的。而且每当我们取一个数，就会有另一个数被定下。且有 $b_1=\{a_1,a_{2n}\}$ ，那么对于这两个数的数目的另一个数，记作 $a_x$ ，则必有 $b_{2n}=a_x$ ，这样想的话其实应该会很容易，读者可以自行模拟。

那么，这道题的正解，就是四指针法。

用作两个指针 $l_1,r_1$ 表示 $b$ 数组的头指针指在的是 $a$ 数组的左端和右端。也就表示区间 $[l_1,r_1]$ 还没有被取到过。而另外两个指针 $l_2,r_2$ 则是 $b$ 数组同理的尾指针，表示区间 $[l_2,r_2]$ 之内的数正好是已经被取到过的数的末尾，可以认为是类似于双向 bfs 那样运作的。那么，整个过程满足 $l_1\leq l_2\leq r_2\leq r_1$，当 $l_1=l_2,r_1=r_2$ 时，表示所有数都被取完，则统计答案。

那如何字典序最小呢，因为一次会记录两个位置，所以有 $LL<LR<RL<RR$ 。对应的情况可以自行思考。当然，前提是转移的两个位置记为 $nxt_1,nxt_2$ 必定满足 $a_{nxt_1}=a_{nxt_2},nxt_1\neq nxt_2$ ，才能够转移，否则不存在答案。我们可以用一个数组 $back[i]$ 表示位置 $i$ 的数 $a_i$ 值的另一个位置在 $back[i]$ 那么，当 $back[nxt_1]=nxt_2$ 或者 $back[nxt_2]=nxt_1$ 时，即可转移。当然，上述两个条件必然是同时满足的，易证。

这道题的复杂度应该是 $\mathcal{O}(kn)$ ，其中，$k$ 是不超过 $10$ 的常数。

AC 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
126
127
128
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,N,Num[MAXN];
int pos[MAXN],back[MAXN];
char ans[MAXN];
inline bool work(int l1,int r1,int l2,int r2)
{
	for(int i=2;i<=N/2;++i)
	{
		if(l1<l2&&back[l1]==l2)
		{
			ans[i]=ans[N-i+1]='L';
			++l1,--l2;
		}
		else if(l1<r2&&back[l1]==r2)
		{
			ans[i]='L',ans[N-i+1]='R';
			++l1,++r2;
		}
		else if(r1>l2&&back[r1]==l2)
		{
			ans[i]='R',ans[N-i+1]='L';
			--r1,--l2;
		}
		else if(r1>r2&&back[r1]==r2)
		{
			ans[i]=ans[N-i+1]='R';
			--r1,++r2;
		}
		else return 0;
		/*printf("%d %d %d %d\n",l1,r1,l2,r2);
		for(int i=1;i<=N;++i) printf("%c",ans[i]);
		puts("");*/
	}
	return 1;
}
inline void print(int x)
{
	if(x) for(int i=1;i<=N;++i) printf("%c",ans[i]);
	else printf("-1");
	puts("");
}
inline void solve()
{
	int posL,posR;
	for(int i=1;i<=N;++i)
	{
		if(Num[i]==Num[1]&&i!=1) posL=i;
		if(Num[i]==Num[N]&&i!=N) posR=i;
		if(!pos[Num[i]]) pos[Num[i]]=i;
		else back[i]=pos[Num[i]],back[pos[Num[i]]]=i;
	}
	ans[1]=ans[N]='L';
	bool flag=work(2,N,posL-1,posL+1);
	if(flag)
	{
		print(1);
		return ;
	}
	ans[1]='R',ans[N]='L';
	flag=work(1,N-1,posR-1,posR+1);
	if(flag) print(1);
	else print(0);
}
int main()
{
//     freopen("palin.in","r",stdin);
//     freopen("palin.out","w",stdout);
    read(Test);
    while(Test--)
    {
    	read(N);
    	N<<=1;
    	for(int i=1;i<=N;++i) read(Num[i]);
		memset(pos,0,sizeof(pos));
		memset(back,0,sizeof(back));
		solve();
    }
    return 0;
}
/*
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
*/

P7916 [CSP-S 2021] 交通规划

第一次考的时候甚至连题都不想读，然后第二次考的时候做了一下，发现还是可以稍稍做一点部分分的。

纳米暴力，小子

当时想到的，结果还写挂了，不如写网络流。

因为一共有 $nm$ 个点需要我们来染色，那么，一共就有 $2^{nm}$ 种染色方案，暴力跑一遍后求出最小权值即可，时间复杂度 $\mathcal O(nm2^{nm})$ ，目测能跑过 $10pts$ ，结果写挂了，爆蛋。

不贴代码，没意义。

纳米网络流，小子

可以想到，我们需要使两端颜色不同的边权值和最小，也就意味着要使颜色相同的边权值最大，可以想到最小割，考虑建图：

  1. 连接超级源点和初始颜色为黑色的点，容量为 $inf$ ；
  2. 连接超级汇点和初始颜色为白色的点，容量为 $inf$ ；
  3. 连接应该连接的所有边，边权为应该有的边权。

然后跑最大流即可。

但是，点数 $NM+K$ ，边数更是无法计算。

更何况，每一次询问还要单独建图，所以还需要重置询问。

不过，还是有 $65pts$ ，似乎实测 $\operatorname{CCF}$ 只有 $60pts$ 。

TLE 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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
#define re register
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int MAXV=25e4+60,MAXE=5e6+10;
const int INF=0x3f3f3f3f;
int Test,N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXE<<1],EdgeCopy[MAXE<<1];
int Head[MAXV],HeadCopy[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,w};Head[v]=Total;
}
inline int getId(int i,int j)
{
    return M*(i-1)+j;
}
inline int getBack(int p)
{
    int x,y;
    if(p<=M) x=1,y=p;
    else if(p<=N+M) x=p-M,y=M;
    else if(p<=N+M+M) x=N,y=N+M+M+1-p;
    else x=N+N+M+M+1-p,y=1;
    return getId(x,y);
}
int Fl[MAXV];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    std::queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("traffic.in","r",stdin);
    // freopen("traffic.out","w",stdout);
    read(N,M,Test);
    for(re int i=1;i<=N-1;++i)
        for(re int j=1,x;j<=M;++j)
        {
            read(x);
            addEdge(getId(i,j),getId(i+1,j),x);
        }
    for(re int i=1;i<=N;++i)
        for(re int j=1,x;j<=M-1;++j)
        {
            read(x);
            addEdge(getId(i,j),getId(i,j+1),x);
        }
    int TotCopy=Total;
    memcpy(HeadCopy,Head,sizeof(Head));
    memcpy(EdgeCopy,Edge,sizeof(Edge));
    while(Test--)
    {
        Total=TotCopy;
        memcpy(Head,HeadCopy,sizeof(HeadCopy));
        memcpy(Edge,EdgeCopy,sizeof(EdgeCopy));
        int K;read(K);
        S=0,T=N*M+K+1;
        for(re int i=1,col,ex,val;i<=K;++i)
        {
            read(val,ex,col);
            addEdge(getBack(ex),N*M+i,val);
            if(col) addEdge(S,N*M+i,INF);
            else addEdge(N*M+i,T,INF);
        }
        write(Dinic()),puts("");
    }
    return 0;
}
/*
2 3 3
9 4 7
3 8
10 5
2
19 3 1
17 9 0
*/

纳米正解，小子

已经想到了要在网格图上求最小割，那么就考虑优化网络流。

先考虑网络流的本质：把颜色不同的点隔开。

就需要一个新的知识——对偶图。（这个东西比较抽象，之后再写篇笔记，先搁着）对偶图是网络在网格图上的一个变形图，使得可以使用 $\text{Dijkstra}$ 在 $\mathcal O(n\log m)$ 的时间复杂度内求出最小割。

构造关键点（可以证明关键点一定是附加点），然后用 $Dist[i][j]$ 储存两两关键点之间的最短路径，可以证明最有构造方案中的路径一定不交叉。

有这个性质，还有 $k\leq 50$ ，考虑区间 $\operatorname{Dp}$ 来求解（今年居然把考点考得这么重，两道贪心，两道区间 $\text{Dp}$）。

相关文章