Contestant~. Rank 316. Rating +66.
A. Dalton the Teacher
题意
给定一个序列，定义一次操作为任意交换两个数。
输出让所有 \(a_i \neq i\) 的最小操作数。
思路
显然，我们直接统计 \(a_i = i\) 的个数，这些数就是参与交换的。
我们推一下式子，最后答案就是 \(\frac{cnt + 1}{2}\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int cnt = 0;
for(int i=1;i<=n;i++){
int x;
cin >> x;
if(x == i) cnt ++;
}
cout << (cnt + 1) / 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}签到。这个式子已经有种经验感了（
B. Longest Divisors Interval
题意
给定一个整数 \(n\)，输出最长的区间 \([l, r]\) 的长度，满足对于所有 \(l \leq i \leq r\)，都有 \(n \bmod i = 0\)。
思路
显然，如果我们找到了某个合法的 \([l, r]\)，那么在 \([1, r - l + 1]\) 中，可以通过倍数关系知道所有数也都合法。
那么，我们直接令 \(l = 1\)，暴力枚举右端点，当 \(x \bmod i \neq 0\) 时，合法区间就是 \([1, x - 1]\)。
时间复杂度：\(O(\log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int ans = 0;
for(int i=1;;i++){
if(n % i == 0) ans ++;
else break;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}先乱猜再说
C1. Dual (Easy Version)
题意
给定一个长为 \(n\) 的序列 \(a\)，满足 \(n \leq 20, |a_i| \leq 20\)。
定义一次操作指定两个参数 \(i, j\)，其中 \(i\) 和 \(j\) 可以相等，将 \(a_j\) 加上 \(a_i\)。
输出一种操作数不大于 \(50\) 的方案，使序列不递减。
思路
首先，我们思考一下，我们在构造什么的时候，能得到一个不递减序列。
不难发现，我们在求非负数序列的前缀和的时候，得到的前缀和数组就是不递减的。
同样，我们在求非正数序列的后缀和的时候，得到的后缀和数组也是不递减的。
那么，我们就可以将所有正数变成负数，或将所有负数变成正数，然后 从右向左 或 从左向右 依次加上即可。
为了让变号的操作数尽可能少，我们以将负数变成正数为例，我们自然希望用最大的正数来进行赋值。
但是可能会出现正数太小的情况。这时，因为 \(2^5 = 32 \geq 20\)，所以我们最多只需 \(5\) 次操作即可让这个最大数 \(\geq 20\)。
如上，我们可以在 \(5 + 2(n - 1) \leq 43\) 次操作内完成此题。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n + 2);
bool f = true;
int mx = 1, mn = 1;
for(int i=1;i<=n;i++){
cin >> a[i];
if(a[i] < a[i - 1]) f = false;
if(a[i] > a[mx]) mx = i;
if(a[i] < a[mn]) mn = i;
}
if(f){
cout << 0 << '\n';
return;
}
vector<pii> ans;
if(a[mx] > 0) {
while (a[mx] <= 20) {
ans.pb(mx, mx);
a[mx] *= 2;
}
for (int i = 1; i <= n; i++) {
if (a[i] < 0) {
ans.pb(i, mx);
a[i] += a[mx];
}
}
for (int i = 2; i <= n; i++) {
if (a[i] < a[i - 1]) {
ans.pb(i, i - 1);
a[i] += a[i - 1];
}
}
}else {
while (a[mn] >= -20) {
ans.pb(mn, mn);
a[mn] *= 2;
}
for (int i = 1; i <= n; i++) {
if (a[i] > 0) {
ans.pb(i, mn);
a[i] += a[mn];
}
}
for (int i = n - 1; i >= 1; i--) {
if (a[i] > a[i + 1]) {
ans.pb(i, i + 1);
a[i] += a[i + 1];
}
}
}
cout << ans.size() << '\n';
for (auto [x, y]: ans) cout << x << ' ' << y << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}主打一个灵感乍现，但是怎么吃了两发罚时啊啊啊啊啊
D2. Dual (Hard Version)
题意
在 \(D1\) 的基础上，限制操作数最多 \(31\) 次。
思路
我们先考虑优化将绝对值最大的数变为 \(\geq 20\) 的操作。
我们以将最大值变为 \(\geq 20\) 为例。因为显然，我们有时候不需要将其变为 \(\geq 20\)，而是只需要将其变为大于最小值的绝对值。
那么，我们设此类操作需要执行 \(x1\) 次；同样的，在改变最小值的时候，此类操作需要执行 \(y1\) 次。
因为我们只需在 改变最大值 和 改变最小值 中选一个进行操作，因而 \(x1, y1\) 中，有一个操作数 因为不需要执行 而为 \(0\)，另一个操作数 因为需要执行 而最多为 \(5\) 。
也就是说，\(x_1 + y_1 \leq 5\)。
接下来，我们需要将这个正数最大值加到所有负数上去，设其需要 \(x2\) 次操作；同样的，设负数最小值加到所有正数上去的操作数为 \(y2\)。
显然，\(x2 + y2 \leq n \leq 20\)。
那么，我们可以得到 \(x1 + x2 + y1 + y2 \leq 25\)，因而，我们取操作数最小的操作，可得 \(\min(x1 + x2, y1 + y2) \leq \lfloor \frac{25}{2} \rfloor = 12\)。
最后，我们需要执行最初我们在 \(C1\) 所说的，类似于求前后缀和的操作，这个操作最多有 \(n - 1 \leq 19\) 次。
从而，按照这个写法，我们取两种操作方案的操作数最小值，可在 \(12 + 19 = 31\) 次内完成操作，从而通过本题。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a1(n + 2), a2(n + 2);
bool f = true;
int mx = 1, mn = 1;
for(int i=1;i<=n;i++){
cin >> a1[i];
a2[i] = a1[i];
if(a1[i] < a1[i - 1]) f = false;
if(a1[i] > a1[mx]) mx = i;
if(a1[i] < a1[mn]) mn = i;
}
if(f){
cout << 0 << '\n';
return;
}
vector<pii> ans1, ans2;
if(a1[mx] > 0) {
while(a1[mx] < -a1[mn]){
ans1.pb(mx, mx);
a1[mx] *= 2;
}
for (int i = 1; i <= n; i++) {
if (a1[i] < 0) {
ans1.pb(i, mx);
a1[i] += a1[mx];
}
}
for (int i = 2; i <= n; i++) {
if (a1[i] < a1[i - 1]) {
ans1.pb(i, i - 1);
a1[i] += a1[i - 1];
}
}
}
if(a2[mn] < 0){
while(a2[mn] > -a2[mx]){
ans2.pb(mn, mn);
a2[mn] *= 2;
}
for (int i = 1; i <= n; i++) {
if (a2[i] > 0) {
ans2.pb(i, mn);
a2[i] += a2[mn];
}
}
for (int i = n - 1; i >= 1; i--) {
if (a2[i] > a2[i + 1]) {
ans2.pb(i, i + 1);
a2[i] += a2[i + 1];
}
}
}
if(ans1.size() > ans2.size()) swap(ans1, ans2);
if(ans1.size() == 0) ans1 = ans2;
cout << ans1.size() << '\n';
for (auto [x, y]: ans1) cout << x << ' ' << y << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}结论是好猜的，证明是难写的，代码是乱交的
D. Earn or Unlock
题意
对于一个竖直放置的牌堆，从上到下给定每张牌的点数 \(a_i\)。每张牌有解锁和未解锁两个状态。
规定一次操作为选定任意一张解锁的牌 \(i\)，并执行下面两种操作任选其一：
从上往下依次解锁未解锁的牌 \(a_i\) 张；
获得这个牌的点数 \(a_i\).
当没有已解锁的牌，或者没有牌剩余，游戏结束。
输出游戏结束时最多的点数。
思路
我们用 \(bitset\) 维护使用了前 \(i\) 张牌的某些牌后，能拓展到的右端点。
我们记使用的 \(bitset\) 为 \(bs\)。
那么，如果我们使用 \(a_i\)，\(bs |= (bs << a_i)\)；不使用，\(bs |= bs\)。
为了方便不使用中间某张牌的推算，我们在使用第 \(i\) 个牌拓展右端点后，将 \(i\) 位置标记为不可达，这样即可将所有状态都判断全。
上述思路可以类比 \(01\) 背包。
最后，如果某个点可达，我们可以推得该点可以获得的最大点数是唯一确定的 \(sum[i] - i + 1\)，其中 \(sum\) 是前缀和。
时间复杂度：\(O(\frac{n^2}{64})\)
对应AC代码
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
bitset<N> bs;
int sum = 0, ans = 0;
bs[1] = 1;
for(int i=1;i<=n;i++){
sum += a[i];
if(bs[i]) ans = max(ans, sum - i + 1);
bs |= bs << a[i];
bs[i] = 0;
}
for(int i=n+1;i<=2*n;i++){
if(bs[i]) ans = max(ans, sum - i + 1);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) solve();
}听懂了吗，如懂。
其实这题 \(n^2\) 的解法挺多也挺好想，但放到 \(bitset\) 里还是太抽象了