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。