文章目录
- A Maximize?(模拟/枚举)
- B Prefiquence(贪心/双指针)
- C Assembly via Remainders(构造)
- D Permutation Game (枚举/贪心)
- E Cells Arrangement(构造)
A Maximize?(模拟/枚举)
题意:
给定
x
x
x,找一个
y
y
y(
1
≤
y
≤
x
1 \leq y \leq x
1≤y≤x),使得
g
c
d
(
x
,
y
)
+
y
gcd(x,y)+y
gcd(x,y)+y尽量大。
思路1: 枚举
y
y
y,找满足条件的最大值。
思路2: 输出x-1即可。
标程1:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
int x; cin >> x;
int ans = 0, y = 0;
for (int i = 1; i < x; i++) {
if (__gcd(x, i) + i > ans) {
ans = __gcd(x, i) + i;
y = i;
}
}
cout << y << "\n";
}
return 0;
}
标程2:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
int x; cin >> x;
cout<<x-1<<"\n";
}
}
B Prefiquence(贪心/双指针)
题意:给定字符串
a
a
a
b
b
b, 要使
a
a
a的前
k
k
k项,恰好是
b
b
b的子序列,请问
k
k
k最大是多少?
思路: 用
j
j
j遍历字符串
b
b
b,只要
b
j
b_j
bj中跟
a
i
a_i
ai相等,则优先选择此
i
i
i,
j
j
j,同时
i
+
+
i++
i++看是否还存在相等的。
标程1:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
int n, m, ans = 0;
cin >> n >> m;
string a, b;
cin >> a >> b;
int i = 0, j = 0;//a字符串 b字符串
for (; i < n && j < m; j++ ) {
if(b[j] == a[i]) {
i++;
}
}
cout << i << "\n";
}
return 0;
}
C Assembly via Remainders(构造)
题意:给定数组
x
2
,
x
3
.
.
.
x
n
x_2,x_3...x_n
x2,x3...xn,构造一个数组
a
1
,
a
2
.
.
.
a
n
a_1,a_2...a_n
a1,a2...an,使得
a
i
a_i
ai %
a
i
−
1
=
x
i
a_{i-1} = x_i
ai−1=xi。
思路:
x
i
x_i
xi范围是0~500,因为要取模运算,所以
a
i
>
500
a_i > 500
ai>500,我们把第1项设为501,剩下的可倒推,余数
x
i
x_i
xi+模
a
i
−
1
a_{i-1}
ai−1 =
a
i
a_i
ai。
标程1:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
int n, last = 501;
cin >> n ;
cout << 501 << " ";
for(int i = 2; i <= n; i++){
int t; cin >> t;
last += t;
cout << last << " ";
}
cout << '\n';
}
return 0;
}
D Permutation Game (枚举/贪心)
题意:给定排列
p
p
p,数组
a
a
a,和两个人的初始位置,玩k轮游戏,问两人胜负情况,假设二人足够聪明。每轮游戏定义如下:玩家在位置
x
x
x,获得
a
x
a_x
ax分,然后选择留在原地或者跳到
p
z
p_z
pz位置。
思路: 枚举所有情况,计算最大的分,比较二人分数。 因为
p
p
p是一个排列,可以跳一圈回来,也就是最终会在一个好位置上一直原地跳,所以枚举这个好位置即可,也就是可能在
p
b
p_b
pb位置跳
k
k
k次,也可能在
p
b
p_b
pb位置跳1次再到下一个位置跳
k
−
1
k-1
k−1次…
标程:
#include <bits/stdc++.h>
using namespace std;
long long p[200005], a[200005];
int main(){
int q;
cin >> q;
while(q--) {
int n, k, pb, ps;
cin >> n >> k >> pb >> ps;
for(int i = 1; i <= n;i ++) cin >> p[i];
for(int i = 1; i <= n;i ++) cin >> a[i];
long long zq1 = 1, i1 = pb, max1 = a[pb] * k, sum1 = a[pb];
i1 = p[i1];
while(i1 != pb&& k > zq1){
max1 = max(max1, sum1 + (k-zq1)*a[i1]);
zq1++, sum1 += a[i1];
i1 = p[i1];
}
long long zq2 = 1, i2 = ps, max2 = a[ps] * k, sum2 = a[ps];
i2 = p[i2];
while(i2 != ps && k > zq2){
// cout << i2 << '*';
max2 = max(max2, sum2 + (k-zq2)*a[i2]);
zq2++, sum2 += a[i2];
i2 = p[i2];
}
// cout << max1 << " " << max2 << '\n' ;
if(max1 > max2) cout << "Bodya\n";
if(max1 < max2) cout << "Sasha\n";
if(max1 == max2) cout << "Draw\n";
}
return 0;
}
E Cells Arrangement(构造)
题意:给定
n
×
n
n\times n
n×n的矩阵,寻找
n
n
n个点,使得任意两点曼哈顿距离构成的非重复集合数量最大。
思路: 按照对角线选点
(
1
,
1
)
,
(
2
,
2
)
.
.
.
.
,
(
n
,
n
)
(1,1),(2,2)....,(n,n)
(1,1),(2,2)....,(n,n),则任意两点构成的距离集合
0
,
2
,
4
,
6......
n
+
n
−
2
{0,2,4,6......n+n-2}
0,2,4,6......n+n−2,能表示所有偶数距离,但不是最大数量,因此可以把(2,2)换成(1,2),则集合是
0
,
1
,
3
,
4
,
5
,
6.....
{0,1,3,4,5,6.....}
0,1,3,4,5,6.....,
标程1:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
int x; cin >> x;
int ans = 0, y = 0;
for (int i = 1; i < x; i++) {
if (__gcd(x, i) + i > ans) {
ans = __gcd(x, i) + i;
y = i;
}
}
cout << y << "\n";
}
return 0;
}