目录

1. 第一题2. 第二题3. 第三题

⏰ 时间：2024/08/10

🔄 输入输出：ACM格式

⏳ 时长：2h

本试卷还有选择题部分，但这部分比较简单就不再展示。

1. 第一题

小O有一个正整数

x

x

x，他想知道，第一个不小于

x

x

x 的素数是几，请你帮帮他吧。

输入描述

输入包含一行一个正整数

x

(

1

<

x

<

1

0

8

)

x\,(1<x< 10^8)

x(1<x<108)，表示小O拥有的正整数。

输出描述

输出包含一行一个正整数，表示不小于

x

x

x 的最小素数。

题解

暴力遍历即可。

<code>#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n) { -- -->

if (n <= 1) return false;

if (n <= 3) return true;

if (n % 2 == 0 || n % 3 == 0) return false;

for (int i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0) return false;

}

return true;

}

int main() {

int x;

cin >> x;

while (!isPrime(x)) {

x++;

}

cout << x << endl;

return 0;

}

2. 第二题

小O面前有

n

n

n 堆糖果，编号从

1

1

1 到

n

n

n，Alice和Bob将轮流拿走编号最小的糖果堆中的所有糖果，具体的：Alice 首先会拿走第一堆，然后Bob拿走第二堆，然后Alice拿走第三堆…直到

n

n

n 堆糖果全都被拿完为止。

小O现在希望 Alice 和 Bob 两人的糖果数量之差尽可能小（即如果Alice糖果数量为

x

x

x, Bob糖果数量为

y

y

y，他想使得

∣

x

−

y

∣

|x-y|

∣x−y∣ 的值尽可能小)，为此他可以最多提前拿走一堆糖果（当然拿走后，位于这堆糖果之后的所有糖果编号也会减一）。

请你帮他求出这个最小值吧。

输入描述

第一行输入一个整数

n

(

1

≤

n

≤

2

⋅

1

0

5

)

n\,(1\leq n\leq 2\cdot 10^5)

n(1≤n≤2⋅105) 代表糖果的堆数。

第二行输入

n

n

n 个整数

a

1

,

a

2

,

.

.

.

,

a

n

(

1

≤

a

i

≤

1

0

9

)

a_1,a_2,...,a_n\,(1\leq a_i\leq10^9)

a1​,a2​,...,an​(1≤ai​≤109) 代表每一堆糖果的数量。

输出描述

在一行上输出一个整数，代表两人糖果数量之差的最小值。

题解

在小O拿走之前，Alice的序列是1、3、5、7等，为奇数序列，Bob的序列是2、4、6、8等，为偶数序列。

考虑一个

n

=

9

n=9

n=9 的简单情形，假设小O拿走第

5

5

5 个，那么剩下的糖果堆为

12346789

1 2 3 4 6 7 8 9

12346789，Alice的序列为

1368

1 3 6 8

1368，Bob的序列为

2479

2 4 7 9

2479，可以发现，以

5

5

5 为分界点，Alice的序列中

5

5

5 左边的取的都是奇数，

5

5

5 右边的都是偶数。Bob序列中

5

5

5 左边的都是偶数，

5

5

5 右边的都是奇数。即无论是Alice还是Bob，位于分界点两边的元素下标奇偶性相反。

很显然我们需要遍历小O的位置，那么留给我们处理的时间就只有

O

(

log

⁡

n

)

O(\log n)

O(logn)了，我们可以利用「前缀和」的思想，预处理出四个数组：

left_odd[i] 代表的是 [1, i] 区间，所有下标为奇数的元素和。left_even[i] 代表的是 [1, i] 区间，所有下标为偶数的元素和。right_odd[i] 代表的是 [i, n] 区间，所有下标为奇数的元素和。right_even[i] 代表的是 [i, n] 区间，所有下标为偶数的元素和。

在遍历小O的位置

i

i

i 时，Alice的糖果数量为 left_odd[i]+right_even[i]，Bob的糖果数量为 left_even[i]+right_odd[i]。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void find_min(int n, vector<i64>& a) {

if (n == 1) {

cout << 0 << endl;

return;

}

if (n == 2) {

cout << min({ a[0], a[1]}) << endl;

return;

}

vector<i64> left_odd(n + 2);

vector<i64> left_even(n + 2);

vector<i64> right_odd(n + 2);

vector<i64> right_even(n + 2);

for (int i = 1; i <= n; i++) {

left_odd[i] = left_odd[i - 1];

left_even[i] = left_even[i - 1];

if (i % 2) left_odd[i] += a[i];

else left_even[i] += a[i];

}

for (int i = n; i; i--) {

right_odd[i] = right_odd[i + 1];

right_even[i] = right_even[i + 1];

if (i % 2) right_odd[i] += a[i];

else right_even[i] += a[i];

}

i64 min_diff = LLONG_MAX;

for (int i = 1; i <= n; i++) {

i64 a = left_odd[i] + right_even[i];

i64 b = left_even[i] + right_odd[i];

min_diff = min(min_diff, abs(a - b));

}

cout << min_diff << endl;

}

int main() {

int n;

cin >> n;

vector<i64> a(n + 1);

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

find_min(n, a);

return 0;

}

3. 第三题

小O有一个数字串，小O希望把这个数字串分割成两个不含前导零的数字串，使得前半部分可以被

x

x

x 整除，后半部分可以被

y

y

y 整除。请你帮助小O找到一种分割方法。

输入描述

第一行输入一个长度不小于

2

2

2、不超过

1

0

5

10^5

105，且仅由数字字符构成的字符串

s

s

s。

第二行输入两个整数

x

x

x 和

y

(

1

≤

x

,

y

≤

1

0

5

)

y\,(1\leq x,y\leq 10^5)

y(1≤x,y≤105) 代表题中所述的除数。

输出描述

在一行上输出两个数字串

t

1

t_1

t1​ 和

t

2

t_2

t2​，第一个数字串表示分割出的前半部分，第二个数字串表示分割出的后半部分，且满足

s

=

t

1

+

t

2

s=t_1+t_2

s=t1​+t2​。

如果不存在这样的分割方法，直接输出

−

1

-1

−1。

如果有多种合法答案，您可以输出任意一种。

题解

假设下标从

1

1

1 开始。

和第二题一样，同样是遍历分割的位置，我们同样要在

O

(

log

⁡

n

)

O(\log n)

O(logn) 的时间内完成计算。如果使用py的切片计算，必然会超时。我们可以使用第二题的思想，即开一个前后缀数组。prefix[i] 代表的是 s[1..i] 构成的数字除以

x

x

x 的余数，suffix[i] 代表的是 s[i...n] 构成的数字除以

y

y

y 的余数。因此位置

k

k

k 是合理的分割当且仅当 prefix[k]==0 且 suffix[k+1]==0。

#include <bits/stdc++.h>

using namespace std;

void solve(string& s, int x, int y) {

int n = s.length();

s = " " + s;

vector<int> prefix(n + 2);

vector<int> suffix(n + 2);

int cur = 0;

for (int i = 1; i <= n; i++) {

cur = (cur * 10 + (s[i] - '0')) % x;

prefix[i] = cur;

}

cur = 0;

int multi = 1;

for (int i = n; i; i--) {

cur = (cur + (s[i] - '0') * multi) % y;

suffix[i] = cur;

multi = (multi * 10) % y;

}

for (int i = 1; i < n; i++) {

if (prefix[i] == 0 && suffix[i + 1] == 0) {

cout << s.substr(1, i) << ' ' << s.substr(i + 1) << endl;

return;

}

}

cout << -1 << endl;

}

int main() {

string s;

cin >> s;

int x, y;

cin >> x >> y;

solve(s, x, y);

return 0;

}