T20200824

Posted on Edited on In Word count in article: 2.5k Reading time ≈ 9 mins.
大东辰的测试

T1 基因合成

神奇的题面描述，这个不管

简言之，求通过给定操作，求到目标状态的最少操作次数

操作如下：

  • 在串的头部或尾部插入一个字符
  • 将串复制一次，逆序接在原串的后面

\(60\)分做法

先说说\(Dp\)，状态设计: \[ f(i,j)=min \begin{cases} f(i+1, j)+1 \\f(i,j-1)+1 \\f(i,mid)+1\quad\text{i到j长度为偶数，且这是回文串} \end{cases} \] \(60\)就到手了

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

using namespace std;

const int Maxn = 205;
int T, Dp[Maxn][Maxn];
char S[Maxn];

int main()
{
	scanf ("%d", &T);
	while (T--)
	{
		scanf ("%s", S);
		int len = strlen(S);
		for (int i = 0; i < len; ++i) Dp[i][i] = 1;
		for (int l = 1; l < len; ++l)
			for (int i = 0, j = i + l; j < len; ++i, ++j)
			{
				Dp[i][j] = min(Dp[i + 1][j], Dp[i][j - 1]);
				if (l & 1 == 1)
				{
					bool k(1);
					int le = i, re = j;
					for (; le < re; ++le, --re)
						if (S[le] != S[re]) k = 0;
					if (k) Dp[i][j] = min(Dp[i][j], min(Dp[i][le - 1], Dp[re + 1][j]));
                    //这里的话，le、re都跑过了，要往回走一步
				}
				Dp[i][j]++;
			}
		printf ("%d\n", Dp[0][len - 1]);	
	}
}

\(100\)分做法

再看看这道题，我们发现有一个性质：

  • 某个复制操作可能是被另一个复制操作所包含的，但是两个复制操作是不可能并列的

那么我们就可以找到每个长度为偶数的回文串，用\(f(i)\)表示在回文数下节点编号为\(i\)的回文串的最小生成步数，\(len(i)\)表示回文串长度

那么答案就可以这样更新\(ans=min(ans,n-len(i)+f(i))\)，因为回文串以外的字符只能选择插入了

考虑如何更新\(f(i)\)： \[ f(i)=\min\{f(j)+1,len(i)/2-len(tran(i))+1\} \] 其中\(tran(i)\)表示回文串\(i\)的某个能够通过最少次操作得到\(i\)的子串

这道题就差不多结束了

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

using namespace std;

const int Maxn = 1e5 + 10;
char S[Maxn];
int T, N, P, Q, Tot, Ans, Last, F[Maxn];
int Len[Maxn], Fail[Maxn], Tras[Maxn], Ch[Maxn][30];

inline void Init()
{
	Fail[0] = F[0] = Tot = 1, S[0] = Len[1] = -1;
	Last = Len[0] = 0;
	memset(Ch, 0, sizeof Ch);
	scanf ("%s", S + 1);
	N = Ans = strlen(S + 1);
}

inline int Newnode(int X)
{
	Len[++Tot] = X;
	return Tot;
}

inline int GetFail(int X, int N)
{
	while (S[N - Len[X] - 1] != S[N]) X = Fail[X];
	return X;
}

inline int HASH(char O)
{
	if (O == 'A') return 0;
	if (O == 'G') return 1;
	if (O == 'C') return 2;
	return 3;
}

inline void Build()
{
	Init ();
	for (int i = 1; i <= N; ++i)
	{
		int X = HASH(S[i]);
		P = GetFail (Last, i);
		if (!Ch[P][X])
		{
			Q = Newnode(Len[P] + 2);
			Fail[Q] = Ch[GetFail(Fail[P], i)][X];
			Ch[P][X] = Q;
			if (Len[Q] <= 2) Tras[Q] = Fail[Q];
			else 
			{
				int Temp = Tras[P];
				while (S[i - Len[Temp] - 1] != S[i] || (Len[Temp] + 2) * 2 > Len[Q]) Temp = Fail[Temp];
                Tras[Q] = Ch[Temp][X];
			}
		}
		Last = Ch[P][X];
	}
}

inline void BFS()
{
	queue <int> Q;
	Q.push (0);
	while (!Q.empty())
	{
		int x = Q.front();
		Q.pop();
		for (int i = 0; i < 4; ++i)
			if (Ch[x][i])
			{
				int t = Ch[x][i];
				F[t] = F[x] + 1;
				F[t] = min(F[t], Len[t] / 2 - Len[Tras[t]] + F[Tras[t]] + 1);
				Ans = min(Ans, N - Len[t] + F[t]);
				Q.push(t);
			}
	}
}

int main()
{
	scanf ("%d", &T);
	while (T--)
	{
		Build ();
		for (int i = 2; i <= Tot; ++i)
			if (Len[i] & 1) F[i] = Len[i];
		BFS();
		printf ("%d\n", Ans);
	}
}

T2 染色

给定一棵树，初始状态所有的点全为白点

有如下两种操作：

  • \(opt=1\)，将\(x\)染为黑色
  • \(opt=2\)，求所有黑点到\(x\)的简单路径长

\(30\)分做法

直接暴力跑，这个树是随机的，嗯就完了吧

\(100\)分做法

考虑根为\(1\)的树上，一对简单路径长度: \[ len = dis(u,1)+dis(v,1)-2\times dis(lca(u,v),1) \] 这个显然是正确的，那么所有黑点到\(x\)的距离为： \[ \begin{align*} Ans&=\sum_{i=1}^{cnt}(dis(u_i)+dis(x)-2\times dis(lca(u_i,x))) \\&=\sum_{i=1}^{cnt}dis(u_i)+cnt\times dis(x)-2\sum_{i=1}^{cnt}dis(lca(u_i,x)) \end{align*} \] 那么这个问题就变得相对简单了，\(dis(x)\)直接预处理，\(\sum_{i=1}dis(u_i)\)可以直接暴力加上去

那么问题就变成了求\(\sum_{i=1}dis(lca(u_i,x))\)，这个我们可以发现，\(lca(u,x)\)一定在\(u\)到根和\(x\)到根的路径上

就是说我们要求\(dis(lca(u,x))\)的话，可以直接求\(Dis(x)\)

即，每次插入一个黑点，将这个点到根的路径上的所有的边权的加入贡献，再求\(x\)到根经过的边的贡献之和

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
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 2e5 + 10;
int N, M, U, V, Cost, Opt, Q;
int Head[Maxn], Next[Maxn << 1], E[Maxn << 1], Cur, W[Maxn << 1], Arr[Maxn], Cnt;
int Son[Maxn], Dep[Maxn], Size[Maxn], F[Maxn], Top[Maxn], SE[Maxn], ID[Maxn];//树剖
ll Sum[Maxn << 2], Ans[Maxn << 2], Tag[Maxn << 2], Len[Maxn], A;//线段树
int Temp[Maxn];
bool Vis[Maxn];

int DFS(int X, int Fa)
{
	F[X] = Fa, Dep[X] = Dep[Fa] + 1, Size[X] = 1;
	for (int i = Head[X]; i; i = Next[i])
	{
		if (E[i] == Fa)continue;
		Size[X] += DFS(E[i], X);
		if (Size[E[i]] > Size[Son[X]]) Son[X] = E[i], SE[X] = W[i];
	}
	return Size[X];
}

void DFS(int X, int Tp, int Edge)
{
	Top[X] = Tp, ID[X] = ++Cnt, Arr[Cnt] = Edge, Len[X] = Len[F[X]] + Edge;
	if (Son[X]) DFS(Son[X], Tp, SE[X]);
	for (int i = Head[X]; i; i = Next[i])
	{
		if (E[i] == F[X] || E[i] == Son[X]) continue;
		DFS(E[i], E[i], W[i]);
	}
}

inline void PushUp(int X) 
{
	Sum[X] = Sum[X << 1] + Sum[X << 1 | 1];
	Ans[X] = Ans[X << 1] + Ans[X << 1 | 1];	
}

void Build(int L, int R, int X = 1)
{
	if (L == R) 
	{
		Sum[X] = Arr[L];
		return;
	}
	int Mid = (L + R) >> 1;
	Build (L, Mid, X << 1);
	Build (Mid + 1, R, X << 1 | 1);
	PushUp(X);
}

inline void Down(int X, ll Val)
{
	Tag[X] += Val;
	Ans[X] += Val * Sum[X];
}

inline void PushDown(int X)
{
	if (!Tag[X]) return ;
	Down (X << 1, Tag[X]);
	Down (X << 1 | 1, Tag[X]);
	Tag[X] = 0;
}

void UpDate(int L, int R, int Tl, int Tr, int Val, int X = 1)
{
	if (L >= Tl && R <= Tr)
	{
		Down(X, Val);
		return ;
	}
	PushDown(X);
	int Mid = (L + R) >> 1;
	if (Tl <= Mid) UpDate (L, Mid, Tl, Tr, Val, X << 1);
	if (Tr > Mid) UpDate (Mid + 1, R, Tl, Tr, Val, X << 1 | 1);
	PushUp(X);
}

ll Query(int L, int R, int Tl, int Tr, int X = 1)
{
	if (L >= Tl && R <= Tr) return Ans[X];
	PushDown(X);
	int Mid = (L + R) >> 1;
	ll Ans(0);
	if (Tl <= Mid) Ans += Query (L, Mid, Tl, Tr, X << 1);
	if (Tr > Mid) Ans += Query (Mid + 1, R, Tl, Tr, X << 1 | 1);
	return Ans; 
}

inline void UpDate(int U)
{
	while (Top[U] != 1)
	{
		UpDate (1, N, ID[Top[U]], ID[U], 1);
		U = F[Top[U]];
	}
	UpDate (1, N, ID[1], ID[U], 1);
}

inline ll Query(int U)
{
	ll Ans(0);
	while (Top[U] != 1)
	{
		Ans += Query (1, N, ID[Top[U]], ID[U]);
		U = F[Top[U]];
	}
	Ans += Query (1, N, ID[1], ID[U]);
	return Ans;
}

inline int Read()
{
	int X(0), O(getchar());
	while (O < '0' || O > '9') O = getchar();
	for (; O >= '0' && O <= '9'; O = getchar()) X = (X << 1) + (X << 3) + (O ^ 48);
	return X;
}

inline void AddEdge(int U, int V, int Cost)
{
	Next[++Cur] = Head[U];
	Head[U] = Cur;
	E[Cur] = V;
	W[Cur] = Cost;
}

int main()
{
	freopen ("color.in", "r", stdin);
	freopen ("color.out", "w", stdout);
	N = Read(), M = Read();
	for (int i = 2; i <= N; ++i) Temp[i] = Read() + 1;
	for (int i = 2; i <= N; ++i) AddEdge(Temp[i], i, Read());
	DFS(1, 0), DFS(1, 1, 0);
	Build(1, N);
	while (M--)
	{
		Opt = Read(), U = Read() + 1;
		if (Opt == 1 && !Vis[U]) UpDate(U), A += Len[U], Q++, Vis[U] = 1;
        //这里要注意一下，因为一个点只能被染色一次，所以如果已经是黑色了就不能在操作了
		else if (Opt == 2) printf ("%lld\n", A + Q * Len[U] - 2 * Query(U));
	}
}

T3 圈地游戏

这，我就懒得描述了

考场上没有思路，怎么设计状态？如何进行转移？

啥都没想到，都不会。。。

BUT

赛后诸葛。。。

我这里没有部分分做法

\(100\)分做法

状态设计\(f(x,y,state_t, state_b)\)，表示当前位置为\((x,y)\)，在路径内部的宝箱状态为\(state_t\)，路径障碍状态为\(state_b\)

规定射线垂直\(y\)轴，没有斜率方便表示

那么判定依据如下：

1
2
if ((New.X == Tx[i] - 1 && Now.X == Tx[i]) || (New.X == Tx[i] && Now.X == Tx[i] - 1)) 
    New.St ^= (1 << (i - 1));

就是没经过这条射线一次，就对这个宝箱/障碍进行一次亦或操作，因为异或操作有一个性质，相信大家都明白，就不细说的

这个就很好的满足了经过奇数条边，那么就在图形内，偶数条边就在图形外的条件

那么最难的部分就结束了

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

using namespace std;
const int Mx[] = {0, 0, 1, -1};
const int My[] = {1, -1, 0, 0};
int N, M, Sx, Sy;//起点坐标
int Tx[10], Ty[10], TVal[10], Tcnt;//宝藏坐标、价值、计数
int Bx[10], By[10], Bcnt;//陷阱坐标、计数
int F[21][21][256][256], Sum[256], Ans;
char Map[25][25];
struct Node
{
    int X, Y, St, Sb;
    Node () {}
    Node (int X, int Y, int St, int  Sb) : X(X), Y(Y), St(St), Sb(Sb) {}
};

inline void BFS()
{
    queue <Node> Q;
    F[Sx][Sy][0][0] = 0;
    Q.push(Node(Sx, Sy, 0, 0));
    while (!Q.empty())
    {
        Node Now = Q.front();
        Q.pop();
        for (int S = 0; S < 4; ++S)
        {
            Node New = Now;
            New.X += Mx[S];
            New.Y += My[S];//在图上随机游走
            if (Map[New.X][New.Y] != '.' && Map[New.X][New.Y] != 'S') continue;
            for (int i = 1; i <= Tcnt; ++i)
            {
                if (New.Y >= Ty[i]) continue;
                if ((New.X == Tx[i] - 1 && Now.X == Tx[i]) || (New.X == Tx[i] && Now.X == Tx[i] - 1))
                    New.St ^= (1 << (i - 1));//记录宝箱状态
            }
            for (int i = 1; i <= Bcnt; ++i)
            {
                if (New.Y >= By[i]) continue;
                if ((New.X == Bx[i] - 1 && Now.X == Bx[i]) || (New.X == Bx[i] && Now.X == Bx[i] - 1)) 
                    New.Sb ^= (1 << (i - 1));//记录陷阱状态
            }
            if (F[New.X][New.Y][New.St][New.Sb] <= F[Now.X][Now.Y][Now.St][Now.Sb] + 1) continue;
            F[New.X][New.Y][New.St][New.Sb] = F[Now.X][Now.Y][Now.St][Now.Sb] + 1;
            //更新答案，我们要求的是周长最小
            Q.push (New);
        }
    }
    for (int i = 0; i < (1 << Tcnt); ++i)
        for (int j = 1; j <= Tcnt; ++j)
            if (i & (1 << (j - 1))) Sum[i] += TVal[j];//统计每种情况下宝箱权值之和
    for (int i = 0; i < (1 << Tcnt); ++i)
        Ans = max(Ans, Sum[i] - F[Sx][Sy][i][0]);
    printf ("%d\n", Ans);
}

int main()
{
    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i) 
    {
        scanf ("%s", Map[i] + 1);
        for (int j = 1; j <= M; ++j)
        {
            if (Map[i][j] == 'S') Sx = i, Sy = j;
            else if (Map[i][j] >= '0' && Map[i][j] <= '9') 
                Tx[Map[i][j] - '0'] = i, Ty[Map[i][j] - '0'] = j, Tcnt++;//记录宝箱的位置
            else if (Map[i][j] == 'B') 
                Bx[++Bcnt] = i, By[Bcnt] = j;//记录陷阱的位置
        }
    }
    for (int i = 1; i <= Tcnt; ++i) scanf ("%d", TVal + i);
    memset (F, 0x5f, sizeof F);
    BFS();
}

这确实是非常好的一道状压\(\text{Dp}\)

这道题大家就栽在不知到如何用二进制表示宝箱、陷阱的状态

虽然题目对于路径内外有十分详细的描述，但是没有做过的话，还是不容易想到这种表示方法