「幻术世界有什么不好，现实太残酷，只会让这空洞越来越大。」
— 带土 · 火影忍者
A. Simple Sequence
题意
用 n 个数构造一个排列，使其满足
思路
既然可以等于，那就都等于，直接构造 n, n – 1, n – 2, … 1，有一个例外，当 x = 2 时，2 mod 1 = 0，但仍满足大于等于的条件
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
for (int i = n; i >= 1; --i) {
cout << i << " ";
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
B. Simply Sitting on Chairs
题意
给出由 n 个数组成的排列 p，其代表的含义是有 n 把椅子，最开始都没有被标记过，对于第 i 把椅子：
如果已被标记，则结束游戏；
你可以选择坐，离开时标记第 p_i 把椅子；
你也可以选择不坐，则跳到第 i + 1 把椅子
问 n 把椅子遍历完后，所坐的最多椅子数
思路
我当时是猜的结论，现在仍未证明出来。如果 p_i > i ，则不坐，反之，则坐
你可以大概感觉一下，如果前面的数指向后面的座位，那么后面的数也相对会指向前面的座位，如果你前面就坐了的话，很容易提前结束游戏，不优，所以不妨等一等，后面指向前面一定是安全的，这样可以遍历完所有的座位
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
LL n;
cin >> n;
vector<LL> a(n + 1, 0);
LL ans = 0;
for (LL i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] <= i) {
++ans;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
C1. A Simple GCD Problem (Easy Version)
题意
给出两个数组 a ，b ，对于 a_i ，在满足任意的 1<= l <= r <= n，gcd(a_l, a_i + 1, …a_r) = gcd(a_l, a_l + 1, …m a_r`)的条件下,你可以使其变为 m(m <= b_i)，问最多可以操作的次数
思路
局部最优即是全局最优，意思就是，对于 来说，只要满足 ，那向左向右延展， 任意区间的 都不会变化
eg.
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
LL gcd(LL a, LL b) {
if (b) {
return gcd(b, a % b);
}
return a;
}
LL lcm(LL a, LL b) {
return (a * b / gcd(a, b));
}
void solve() {
LL n;
cin >> n;
vector<LL> a(n + 2, 0), b(n + 1,0), c(n + 1, 0);
LL con;
for (LL i = 1;i <= n; ++i) {
cin >> a[i];
if (i == 1) {
con = a[i];
}
else {
con = gcd(con, a[i]);
}
}
for (LL i = 1; i <= n; ++i) {
cin >> b[i];
}
LL ans = 0;
a[0] = con, a[n + 1] = con;
for (LL i = 1; i <= n; ++i) {
LL p1 = gcd(a[i], a[i - 1]);
LL p2 = gcd(a[i], a[i + 1]);
c[i] = lcm(p1, p2);
}
for (LL i = 1; i <= n; ++i) {
if (a[i] >= c[i]) {
++ans;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}