比赛地址Codeforces Round #752 (Div. 2)
很容易看出,如果对第 $i$ 个执行插入操作,那么对 $i-n$ 个都会影响到,所以只需要找出偏移量最大的就行了
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
int res = 0;
for (int i = 1; i <= n; i ++ ) {
int x; cin >> x;
if (x <= i) continue;
res = max(x - i, res);
}
cout << res << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
奇偶分类讨论
假如是偶数的话,直接构造 $n$ 个 $1$ 即可。
受到启发,如果是奇数的话,直接构造 $n - 1$ 个 $1$ 即可,故只要存在 $a[i] >= a[i + 1]$ 就可以构造出来,否则就构造不出来。
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
if (n & 1) {
for (int i = 1; i < n; i ++ ) {
if (a[i] >= a[i + 1]) {
cout << "YES" << endl;
return ;
}
}
cout << "NO" << endl;
} else cout << "YES" << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
对着题意硬模拟就行,是不会T的,主要是 $lcm(1, 2, 3, … 23) > 1e9$ 故暴力也不会T。
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) {
if (a[i] % (i + 1) == 0) {
int j = i;
while (j > 1 && a[i] % (j + 1) == 0) j --;
if (a[i] % (j + 1) == 0) {cout << "NO" << endl; return ;}
}
}
cout << "YES" << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
构造题,也是分类讨论
首先容易看出,当 $x | y$ 的时候,直接输出 $x$ 即可
否则我们当 $x > y$ 的时候,输出 $x + y$,因为
$$(x + y)\mod x = y \mod x = y$$
$$y \mod (x + y) = y$$
最后一种是比较难想的,当 $x < y$ 的时候
最初的想法是找到一个 $x$ 到 $y$ 之间的数,使得其满足,最初的想法是 $\frac{x + y}{2}$,但是当 $y$ 比 $x$ 大好多的时候就不对了,所以尝试加一个系数。最终凑出了 $\frac{y + x * \lfloor\frac{y}{x} \rfloor}{2}$。
因为
$$\frac{y + x * \lfloor\frac{y}{x} \rfloor}{2} \mod x = \frac{y \mod x}{2}$$
$$y \mod \frac{y + x * \lfloor\frac{y}{x} \rfloor}{2} = y - \frac{y + x * \lfloor\frac{y}{x} \rfloor}{2} = \frac{y \mod x}{2}$$
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
LL x, y; cin >> x >> y;
if (y % x == 0) cout << x << endl;
else {
if (y < x) cout << x + y << endl;
else cout << y / 2 + y / x * x / 2 << endl;
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
考点:dp
若数组本身为非递减,则操作次数为0,否则一定存在 $a[i] > a[i + 1]$,从这个入手。
设 $1 \le b[1] \le b[2] \le …\le b[k] \le a[i + 1]$,其中 $b[1] + b[2] + …+b[k] = a[i]$
容易得出,$k \ge \lceil\frac{a[i]}{a[i + 1]}\rceil$,考虑到对前面数组的影响,故 $b[1]$ 越大越好,所以当 $k = \lceil\frac{a[i]}{a[i + 1]}\rceil$ 时,$b[i]$ 最大为 $\lfloor \frac{a[i]}{\lceil \frac{a[i]}{a[i + 1]} \rceil} \rfloor$,同时操作次数也最少为 $k - 1$
根据这个贪心,我们可以写出 $n^2$ 的一个算法,但是显然复杂度过高,需要优化。
状态设计,$dp[i][j]$ 表示以 $i$ 开头的,经过数字拆分后以 $j$ 开头子序列个数之和。
容易得到 $dp[i][\lfloor \frac{a[i]}{\lceil \frac{a[i]}{x} \rceil} \rfloor] = \sum dp[i + 1][x]$
注意到,这个转移的有效次数只有 $sqrt(1e5)$ 次,也就是 $\lfloor\frac{x}{1}\rfloor,\lfloor\frac{x}{2}\rfloor…\lfloor \frac{x}{x} \rfloor$ 的个数是 $sqrt(x)$ 级别的(类似数论分块)
所以实际上的复杂度是 $nsqrt(1e5)$ 级别的。
转移的同时统计答案,为 $ans += i * dp[i + 1][x] * (\lceil\frac{a[i]}{x}\rceil - 1)$
由于 $1e5*1e5$ 的空间存不下,而且每次转移只用到上一层的,所以考虑滚动数组
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
LL dp[2][N];
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
int mx = 0;
for (int i = 1; i <= n; i ++ ) cin >> a[i], mx = max(mx, a[i]);
for (int i = 0; i <= mx; i ++ ) dp[0][i] = dp[1][i] = 0;
vector<int> v[2];//存上一层有效转移过来的x
LL res = 0;
for (int i = n; i; i -- ) {
int p = i & 1;
v[p].push_back(a[i]);
dp[p][a[i]] = 1;
int last = a[i];
for (auto x : v[p ^ 1]) {
int k = (a[i] + x - 1) / x;
int j = a[i] / k;
res = (res + (k - 1) * dp[p ^ 1][x] % MOD * i % MOD) % MOD;
dp[p][j] = (dp[p][j] + dp[p ^ 1][x]) % MOD;
if (last == j) continue;
v[p].push_back(j), last = j;
}
for (auto x : v[p ^ 1]) dp[p ^ 1][x] = 0;//一定要重置,否则就不是“滚动”的了
v[p ^ 1].clear();
}
cout << res << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
数学场,新人喜提462分
加油hhhh
也是手速场hh