T20200529

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

单词(words)

Description

给你两个由小写字母组成的单词\(A\)和\(B\)，我们称一个单词为幸运单词，当且仅当它是由\(A\)的某个非 空前缀和\(B\)的某个非空后缀拼接而成的（\(A\)的前缀在\(B\)的后缀的前面）。

例如，当单词\(A\)为\(tree\)，单词\(B\)为\(heap\)时，\(trap\)就是一个幸运单词，而\(traep,aptr\)则不是。 请问对于给定的单词\(A\)和\(B\)，共有多少个不同的幸运单词？

Input

输入包含两行，第一行为单词\(A\)，第二行为单词\(B\)。

Output

输出一个整数，表示幸运单词的总个数。

Examples

Input Output
tree
heap		 14

数据范围

对于\(20\%\)的数据，单词\(A\)的长度\(length_A\)和单词B的长的\(length_B\)满足，\(1\le length_A, length_B\le 100;\)

对于\(40\%\)的数据， \(1\le length_A, length_B\le 10^3;\)

对于\(100\%\)的数据，\(1\le length_A, length_B\le 10^5;\)

其实答案因该和\(length_A\times length_B\)有关

但是看\(treap\)， 他可以看成\(tre+ap\)和\(tr+eap\)

就是说如果直接按照上面直接乘的话，\(treap\)是被计算了两次的

所以可以一记录一下A，B串中除了首位字符，有多少个重复的字符，就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10;
char A[Maxn], B[Maxn];
ll CntA[30], CntB[30], Temp, Ans;
ll LenA, LenB;

int main()
{
	freopen ("words.in", "r", stdin);
	freopen ("words.out", "w", stdout);
	scanf ("%s %s", A, B);
	LenA = strlen(A), LenB = strlen(B);
	for (int i = 0; i < LenB - 1; ++i) CntB[B[i] - 'a']++;
	for (int i = 1; i < LenA; ++i) CntA[A[i] - 'a']++;
	Ans = LenA * LenB;
	for (int i = 0; i < 26; ++i) Ans -= CntA[i] * CntB[i];
	printf ("%lld\n", Ans);
}

距离(distance)

Description

给你一个由\(0\)和\(1\)组成的\(n × m\)大小的矩阵\(A\)，其中第\(i\)行第\(j\)列\(\left(1\le i\le n, 1 \le j \le m\right)\)的元素的坐标 为\(\left(i, j\right)\)。

请输出一个\(n × m\)大小的矩阵\(B\)。该矩阵第\(i\)行第\(j\)列\(\left(1\le i\le n, 1 \le j \le m\right)\)的元素表示的是，矩阵\(A\)中坐标为\(\left(i, j\right)\)的元素到矩阵\(A\)中欧几里得距离最近的\(1\)的欧几里得距离。

对于位置\(\left(x, y\right)\)和位置\(\left(a, b\right)\)，它们的欧几里得距离定义为\(\left(x - a\right)^2 + \left(y - b\right)^2\)。

Input

输入的第一行包括两个正整数\(n, m\)。

接下来有\(n\)行\(01\)字符串，每一行字符串的长度为\(m\)，表示矩阵\(B\)。

Output

请输出\(n\)行，每一行有\(m\)个整数，表示矩阵\(B\)。

Examples

Input Output
3 4
1000
0000
0010		 0 1 4 5
1 2 1 2
4 1 0 1

数据范围

对于\(20\%\)的数据， \(1\le n，m\le 100\)

对于100%的数据 \(1\le n， m\le 1000\)

对于这个问题，我们可以先看作是对于每一个\(1\)只对它右下方的\(0\)有约束作用

那么这道题会变得非常简单啊，就是一个\(n^2\)暴力就完了，\(O(10^6)\)还是可以接受的

但是理论上所有的\(1\)对所有的\(0\)都有约束作用，那么转一下，跑四遍 \(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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e3 + 5;
int N, M;
char Input[Maxn];
int Dp[Maxn][Maxn], Temp[Maxn][Maxn];//权值
pair <int , int> Pos[Maxn][Maxn], TP[Maxn][Maxn];//位置

inline int Pow(int X, int Y)
{
	return (X - Y) * (X - Y);
}

inline void Upt(int X, int Y, int Nx, int Ny)
{
	if ((Pos[X][Y].first | Pos[X][Y].second) == 0) return;
	int NAns = Pow(Nx, Pos[X][Y].first) + Pow(Ny, Pos[X][Y].second);
	if (NAns < Dp[Nx][Ny])
	{
		Pos[Nx][Ny] = Pos[X][Y];
		Dp[Nx][Ny] = NAns;
	}
}

inline void Rotate()
{
	for (int j = 1; j <= M; ++j)
		for (int i = N; i >= 1; --i)
		{
			Temp[j][N - i + 1] = Dp[i][j];
			TP[j][N - i + 1].first = Pos[i][j].second;
			TP[j][N - i + 1].second = N - Pos[i][j].first + 1;
		}
			
	N ^= M ^= N ^= M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j) Dp[i][j] = Temp[i][j], Pos[i][j] = TP[i][j];
}

inline void Print()
{
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j) printf ("%d ", Dp[i][j]);
		puts("");
	}
}

inline void Work()
{
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
		{
			if (i > 1) Upt (i - 1, j, i, j);
			if (j > 1) Upt (i, j - 1, i, j);
			if (i > 1 && j > 1) Upt (i - 1, j - 1, i, j);
		}
}

int main()
{
	freopen ("distance.in", "r", stdin);
	freopen ("distance.out", "w", stdout);
	memset (Dp, 0x3f, sizeof Dp);
	scanf ("%d %d", &N, &M);
	for (int i = 1; i <= N; ++i)
	{
		scanf ("%s", Input + 1);
		for (int j = 1; j <= M; ++j)
			if (Input[j] - '0')Dp[i][j] = 0, Pos[i][j].first = i, Pos[i][j].second = j;
	}
	for (int i = 0; i < 4; ++i, Rotate()) Work();
	Print();
}

然后\(std\)给的方案是从四个方向分别跑一遍斜率优化\(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
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
typedef pair<int, int> point;
typedef long long LL;
const int maxn = 1005;
int n, m, f[maxn][maxn], a[maxn][maxn], tmp[maxn][maxn], d[maxn];
char s[maxn][maxn];
point Q[maxn];
point operator-(point a, point b) {
	return point(a.X - b.X, a.Y - b.Y);
}
LL cross(point a, point b) {
	return 1LL * a.X * b.Y - 1LL * a.Y * b.X;
}
LL cross(point a, point b, point c) {
	return cross(b - a, c - a);
}
int calc(point p, int k) {
	return p.Y - 2 * k * p.X;
}
void solve() {
	memset(d, 0, sizeof d);
	for (int i = 1; i <= m; ++i)
		d[i] = 2000;
	for (int i = 1; i <= n; ++i) {
		int h = 0, t = 0;	
		for (int j = 1; j <= m; ++j) {
			if (s[i][j] == '1') d[j] = 0;
			else ++d[j];
			
			point now = make_pair(j, j * j + d[j] * d[j]);
			while (h + 1 < t && cross(Q[t - 1], Q[t], now) <= 0) --t;
			Q[++t] = now;
			while (h + 1 < t && calc(Q[h + 1], j) > calc(Q[h + 2], j)) ++h;
			a[i][j] = calc(Q[h + 1], j) + j * j;
		}
	}
}
int main() {
	freopen("distance.in", "r", stdin);
	freopen("distance.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= m; ++j)
			tmp[i][j] = s[i][j];
	}
	
	//1
	solve();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			f[i][j] = a[i][j];
	
	//2
	for (int i = 1; i <= n; ++i)
		reverse(s[i] + 1, s[i] + m + 1);
	solve();
	for (int i = 1; i <= n;++i)
		for (int j = 1; j <= m; ++j)
			f[i][j] = min(f[i][j], a[i][m - j + 1]);
	
	//3
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) 
			s[i][j] = tmp[n - i + 1][j];
	solve();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			f[i][j] = min(f[i][j], a[n - i + 1][j]);
	
	//4
	for (int i = 1; i <= n; ++i)
		reverse(s[i] + 1, s[i] + m + 1);
	solve();
	for (int i = 1; i <= n;++i)
		for (int j = 1; j <= m; ++j)
			f[i][j] = min(f[i][j], a[n - i + 1][m - j + 1]);
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			printf("%d%c", f[i][j], j == m ? '\n' : ' ');
	}
}

又臭又长的\(std\)

树(Tree)

Description

鼹鼠们在底下开凿了 \(n\) 个洞，由 \(n-1\) 条隧道连接，对于任意的$ i>1$，第 \(i\) 个洞都会和第 \(\frac{i}{2}\)（取下整）个洞间有一条隧道，第 \(i\) 个洞内还有 \(c_i\) 个食物能供最多 \(c_i\) 只鼹鼠吃。一共有 \(m\) 只鼹鼠，第 \(i\) 只鼹鼠住在第 \(p_i\) 个洞内。

一天早晨，前 \(k\) 只 鼹鼠醒来了，而后 \(n-k\) 只鼹鼠均在睡觉，前 \(k\) 只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的 \(c_i\) 均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的 \(1\le k \le m\)，输出最小的鼹鼠行动 路径的总长度，保证一定存在某种合法方案。

Input

第一行两个数 \(n,m\)，表示有 \(n\)个洞，\(m\)只鼹鼠。 第二行 \(n\)个整数 \(c_i\) 表示第 \(i\)个洞的食物数。 第三行 \(m\) 个整数 \(p_i\)表示第 \(i\)只鼹鼠所在洞 \(p_i\)。

Output

输出一行\(m\)个整数，第\(i\)个整数表示当\(k = i\)时鼹鼠的最小行动路径长度。

Input Output
5 4
0 0 4 1 1
2 4 5 2		 1 1 2 4

数据范围

$1n,m^5,; 0c_im,;1 p_in $

所以第一想法就是贪心，这是毫无疑问的

但是考虑到后面的鼹鼠用剩余的点来贪心的话显然是不正确的

怎么办呐?

于是就可以借用网络流的反悔机制

这是\(1\)(黑)吃了上面的\(1\)的情况，显然如果\(2\)要吃饭了的话，\(1\)时占据了\(2\)的坑位的

所以其实\(2\)其实应该吃的是\(1\)上面的点，但是我们看见的\(2\)现在能吃的只是\(1\)下面的点了

让如果我们让这个时候的\(2\)经过\(1\)吃的点的时候的边权为\(-1\)就等价于\(1\)吃的是下面的点，而\(2\)吃的是\(1\)上面的点了

就是让后来的鼹鼠按相反的方向经过了之前的鼹鼠经过的边时，加上\(-1\)的边权即可

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

using namespace std;

typedef long long ll;
const int Maxn = 1e6, INF = 1e9;

inline bool Check(int &X, int Y)
{
    return Y < X ? (X = Y , 1) : 0;
}

int N, M, S;
int Dis[Maxn], C[Maxn], Pos[Maxn], Flow[Maxn];//规定向上走flow + 1，向下走flow - 1，方便记录方向，以便确定边权
inline int LenU(int X) {return Flow[X] < 0 ? -1 : 1;}
inline int LenD(int X) {return Flow[X] > 0 ? -1 : 1;}

inline void UpDate(int X)
{
    Dis[X] = INF, Pos[X] = 0;
    if (C[X]) Dis[X] = 0, Pos[X] = X;
    if (Check(Dis[X], Dis[X << 1] + LenD(X << 1))) Pos[X] = Pos[X << 1];
    if (Check(Dis[X], Dis[X << 1 | 1] + LenD(X << 1 | 1))) Pos[X] = Pos[X << 1 | 1];
}

int main()
{
    freopen ("tree.in", "r", stdin);
    freopen ("tree.out", "w", stdout);
    scanf ("%d %d", &N, &M);
    memset (Dis, 0x3f, sizeof Dis);
    for (int i = 1; i <= N; ++i) scanf ("%d", C + i);
    for (int i = N; i >= 1; --i) UpDate(i);//先记录每个点的到子树中最近的洞及距离
    int Ans = 0;
    while (M--)
    {
        scanf ("%d", &S);
        int Cost(INF), Now(0), T(0);
        for (int X = S; X != 0; X >>= 1)//从这个点到1更新相当于遍历了整棵树
        {
            if (Check(Cost, Now + Dis[X])) T = X;
            Now += LenU(X);//更新点S到X的距离
        }
        int Target = Pos[T];//这是目标食物的位置
        Ans += Cost;
        for (int X = S; X != T; X >>= 1) Flow[X]++;//从X向上走flow应该+1
        for (int X = Target; X != T; X >>= 1) Flow[X]--;//向下走的flow应该-1
        C[Target]--;//又被拿走一个，更新一下
        for (int X = Target; X != T; X >>= 1) UpDate(X);
        for (int X = S; X != 0; X >>= 1) UpDate(X);//走过的路径都要更新子树信息
        printf ("%d ", Ans);
    }
}