A

原题链接

给定两个正整数 n,c ,再给定两个长度为 n 的数组 x 与 y ,在满足 a 与 b 都是整数且 a+b=c 的条件下,求使得 \(∑_{i=1}^n(x_i−a)×(y_i−b)\) 最大的 a 和 b

直接化简要求的式子,化成二次函数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int x[N], y[N];
signed main()
{
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> x[i], x[i] += x[i - 1];
for (int i = 1; i <= n; i++) cin >> y[i], y[i] += y[i - 1];
int t = (n * c - y[n] + x[n]) / (2 * n), ans = n * t * (c - t) - t * y[n] - (c - t) * x[n];
if (n * (t + 1) * (c - t - 1) - (t + 1) * y[n] - (c - t - 1) * x[n] > ans) t = t + 1;
cout << t << " " << c - t;
return 0;
}

B

原题链接

给定一张 n个点的图,编号为 1 到 n ,初始没有边,任意两个点满足其中至少有一个点的编号为质数的条件即可连边,代价为两个数的差的绝对值,问将整张图连通的代价最小是多少。

一开始想到从小到大依次插入节点,分为素数和非素数插入,将非素数先保存到一个数组中,到遇到下一个素数的时候再判断该数和前一个素数连还是后一个素数连

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
#include <iostream>
#include <deque>

using namespace std;
#define int unsigned long long
const int N = 1e7 + 10;
int prime[N], cnt;
bool st[N];
void get_prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; j++)
{
st[i * prime[j]] = true;//st为true 说明是合数,为false 说明是质数
if (i % prime[j] == 0) break;
}
}
}
signed main()
{

int n; cin >> n;
if (n == 1)
{
cout << 0;
return 0 ;
}
if (n == 2)
{
cout << 1;
return 0;
}
get_prime(n);
//n >= 3的情况
int count = 1, last_prime = 2;
deque<int> left;
for (int i = 3; i <= n; i++)
{
if (!st[i])//如果是素数
{
if(left.empty()) count += 1;//直接加到图的后面
else
{
int sum = left.size(), t = left[sum / 2];
count += i - last_prime;
while (left.size())
{
if(left.front() != t) count += min(left.front() - last_prime, i - left.front());
left.pop_front();
}
}
last_prime = i;
}
else//如果不是素数
{
left.push_back(i);
}
}
while (!left.empty())
{
count += left.front() - last_prime;
left.pop_front();
}
cout << count;

return 0;
}

本来以为上一个方式TLE了,所以又写了一种方法

直接遍历素数,根据判断除了2和3,其他所有的素数之间隔得都是奇数个数(因为奇数加奇数等于偶数,偶数不可能是素数),所以可以想像成先让中间的数分别和两个素数相连,然后让大的数和大的素数相连,小的数和小的素数相连,又因为数都是连续的,所以只用算中间那个数的右边那个数到大的素数的距离,然后用公差为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
#include <iostream>
using namespace std;
#define int long long
const int N = 1e7 + 10;
int prime[N], cnt;
bool st[N];
void get_prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; j++)
{
st[i * prime[j]] = true;//st为true 说明是合数,为false 说明是质数
if (i % prime[j] == 0) break;
}
}
}
signed main()
{
int n; cin >> n;
if (n == 1)
{
cout << 0;
return 0;
}
if (n == 2)
{
cout << 1;
return 0;
}
get_prime(n);
int count = 1;
for (int i = 0; i < cnt - 1; i++)//遍历素数
{
int last_prime = prime[i], next_prime = prime[i + 1];
count += next_prime - last_prime + (next_prime - (next_prime + last_prime + 2) / 2 + 1) * (next_prime - (next_prime + last_prime + 2) / 2);
}
if (n > prime[cnt - 1])
{
count += (n - prime[cnt - 1] + 1) * (n - prime[cnt - 1]) / 2;
}
cout << count;
return 0;
}

C

原题链接

多组数据,每组数据给你一个字符串,你可以删除任意次,每次删除一个长度大于等于 2 的回文串,问能否删空整个字符串。

利用递归,分为两边能否删除和两边相等中间能否删除进行判断

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
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int N = 350;
int f[N][N];
char s[N];
int dfs(int l, int r)
{
//递归结束条件
if (l == r) return 0;//只有一个,不能删除
if (l > r) return 1;//删除完成
if (l + 1 == r) return s[l] == s[r];//有两个,判断是否相等
if (~f[l][r]) return f[l][r];//记忆化搜索,如果之前存过,直接用

int t = 0;
//判断左右两个子段是否可以删除
for (int i = l ; i < r; i++)
{
t |= dfs(l, i) && dfs(i + 1, r);
}
//如果边界相等,判断内部是否可删除
if (s[l] == s[r])
{
t |= dfs(l + 1, r - 1);
//以i为中心判断回文字符串
for (int i = l + 1; i < r; i++)
t |= dfs(l + 1, i - 1) && dfs(i + 1, r - 1);
}
return f[l][r] = t;
}
signed main()
{
int t;
cin >> t;
while (t--)
{
memset(f, -1, sizeof f);//记忆化搜索
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i];
cout << (dfs(1, n) ? "YES" : "NO") << '\n';
}
return 0;
}