A - 比赛新机制（前缀和、思维）

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
//https://ac.nowcoder.com/acm/contest/16520/A
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;

int T;

int n;
int a[N];
long long pre_sum[N];

int main()
{
	ios::sync_with_stdio(false);

	cin >> T;

	while (T--)
	{
		long long sum = 0;
		long long ans = 0;

		for (int i = 0; i <= n; i++) a[i] = 0, pre_sum[i] = 0;

		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];

			sum += a[i] * (n - i + 1);
			pre_sum[i] = pre_sum[i - 1] + a[i];
		}

		ans = sum;

		for (int i = 2; i <= n; i++)
		{
			sum += (pre_sum[n] - pre_sum[i - 1] + pre_sum[i - 2]);
			sum -= (n - 1) * a[i - 1];
			ans = min(ans, sum);
		}

		//逆序
		reverse(a + 1, a + n + 1);
		sum = 0;
		for (int i = 0; i <= n; i++) pre_sum[i] = 0;

		for (int i = 1; i <= n; i++)
		{
			sum += (a[i] * (n - i + 1));
			pre_sum[i] = pre_sum[i - 1] + a[i];
		}

		ans = min(ans, sum);

		for (int i = 2; i <= n; i++)
		{
			sum += (pre_sum[n] - pre_sum[i - 1] + pre_sum[i - 2]);
			sum -= (n - 1) * a[i - 1];
			ans = min(ans, sum);
		}

		cout << ans << endl;
	}

	return 0;
}

根据题目要求，要求从一个起点开始，正序或逆向按照下列公式计算：

n * a1 + (n - 1) * a2 + (n - 2) * a3 + (n - 3) * a4 + … + 1 * an

其中，a1是这n个数字中的任一起点，如果遍历每个起点必然会超时。

可以使用前缀和来优化，模拟这个公式。

同样遍历每个起点，共有2n种可能。

其中，正序部分：

n * a1 + (n - 1) * a2 + (n - 2) * a3 + (n - 3) * a4 + … + 1 * an

1 * a1 + n * a2 + (n - 1) * a3 + (n - 2) * a4 + 2 * an

2 * a1 + 1 * a2 + n * a3 + (n - 1) * a4 + … + 3 * an

…

(n-1) * a1 + (n - 2) * a2 + (n - 3) * a3 + (n - 4) * a4 + … + n * an

逆序部分同理。

通过观察，每次将系数右移，也就是将n左边和右边的系数+1，n的系数变为1。

（n右边的系数不断加1是因为按照题目模拟计算，左边之所以加1是因为这个序列是首尾相接的）

然后，通过前缀和实现系数+1和n的系数变为1，逆序部分则将数组转置，同样处理。

最后取所有方案和的最小值即答案。

C - 生命的游戏（模拟）

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
//https://ac.nowcoder.com/acm/contest/16520/C
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100 + 10;

typedef pair<int, int> PII;

int n, k;
int g[N][N];
int src[N][N];

int len = 0;
PII tmp[N * N];

int up(int x)
{
	if (x - 1 <= 0)	return x - 1 + n;
	else return x - 1;
}

int down(int x)
{
	if (x + 1 > n)	return x + 1 - n;
	else return x + 1;
}

int left(int x)
{
	if (x - 1 <= 0)	return x - 1 + n;
	else return x - 1;
}

int right(int x)
{
	if (x + 1 > n)	return x + 1 - n;
	else return x + 1;
}

int main()
{
	int T;

	cin >> T;
	while (T--)
	{
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				cin >> g[i][j];
				src[i][j] = g[i][j];
			}
				

		bool flag = true;
		for (int m = 1; m <= k; m++)
		{
			flag = true;
			len = 0;
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					int cnt = 0;
					if (g[left(i)][j] == 1)	cnt++;
					if (g[left(i)][up(j)] == 1)	cnt++;
					if (g[left(i)][down(j)] == 1)	cnt++;
					if (g[right(i)][j] == 1)	cnt++;
					if (g[right(i)][up(j)] == 1)	cnt++;
					if (g[right(i)][down(j)] == 1)	cnt++;
					if (g[i][up(j)] == 1)	cnt++;
					if (g[i][down(j)] == 1)	cnt++;

					if (cnt == 3 && g[i][j] == 0)	tmp[len++] = { i, j };
					if (g[i][j] == 1 && cnt > 3 || g[i][j] == 1 && cnt < 2)	tmp[len++] = { i, j };
				}
			}

			
			for (int i = 0; i < len; i++)
			{
				int x = tmp[i].first, y = tmp[i].second;
				g[x][y] = !g[x][y];
			}

			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					if (g[i][j] != src[i][j])
					{
						flag = false;
						break;
					}
				}
				if (!flag)	break;
			}
				
			if (flag)
			{
				cout << "YES" << endl << m << endl;
				break;
			}
		}

		if (!flag)	cout << "NO" << endl;
	}
	
	return 0;
}

模拟题，按照题目要求暴力模拟即可。

F - 飞马分隔符（思维）

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
//https://ac.nowcoder.com/acm/contest/16520/F
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int T;
bool feima[5];

int n;
char str[N];

int process(char str[])
{
	for (int j = 0; j < 5; j++)	feima[j] = false;

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (str[i] == 'F')	feima[0] = true;
		if (str[i] == 'e' && feima[0] == true)	feima[1] = true;
		if (str[i] == 'i' && feima[0] == true && feima[1] == true )	feima[2] = true;
		if (str[i] == 'M' && feima[0] == true && feima[1] == true && feima[2] == true)	feima[3] = true;
		if (str[i] == 'a' && feima[0] == true && feima[1] == true && feima[2] == true && feima[3] == true)
		{
			ans++;
			for (int j = 0; j < 5; j++)	feima[j] = false;

			i--;
		}
	}
    
	return ans;
}

int main()
{
	cin >> T;

	while (T--)
	{
		cin >> n >> str + 1;
		cout << process(str) << endl;
	}

	return 0;
}

即判定给定字符串中子序列FeiMa的个数。若子序列FeiMa出现，则a划给下一个字符串。

上面的代码使用模拟的做法，也可以直接在str中判断子序列FeiMa出现的次数。

H - 温暖的力量（思维）

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
//https://ac.nowcoder.com/acm/contest/16520/H
#include <iostream>

using namespace std;

int T;

int divide(int n)
{
	if (n <= 3)	return -1;

	return n / 2;
}

int main()
{
	cin >> T;

	while (T--)
	{
		int n;
		
		cin >> n;
		cout << divide(n) << endl;
	}

	return 0;
}

题目要求将给定的数字分解成n个质数的和，求这个n的最小值。

任意质数都可以使用p = 2x + 3y表示，因此n / 2即答案。

注意：题目要求答案大于1，否则无解，输出-1。