目录
⏰ 时间：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 的最小素数。
题解
暴力遍历即可。
#include<bits/stdc++.h>usingnamespace std;boolisPrime(int n){if(n <=1)returnfalse;if(n <=3)returntrue;if(n %2==0|| n %3==0)returnfalse;for(int i =5; i * i <= n; i +=6){if(n % i ==0|| n %(i +2)==0)returnfalse;}returntrue;}intmain(){int x;
cin >> x;while(!isPrime(x)){
x++;}
cout << x << endl;return0;}
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>usingnamespace std;using i64 =longlong;voidfind_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;}intmain(){int n;
cin >> n;
vector<i64>a(n +1);for(int i =1; i <= n; i++){
cin >> a[i];}find_min(n, a);return0;}
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>usingnamespace std;voidsolve(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;}intmain(){
string s;
cin >> s;int x, y;
cin >> x >> y;solve(s, x, y);return0;}
本文转载自: https://blog.csdn.net/raelum/article/details/141255987
版权归原作者 Iareges 所有， 如有侵权，请联系我们删除。
版权归原作者 Iareges 所有， 如有侵权，请联系我们删除。