Dalton the Teacher
给定序列 \(a_{1 \sim n}\) ，定义一次操作为交换序列中的某两个数，求使得 \(\forall i, a_i \not = i\) 的最少操作次数
对于所有数据，\(n \leq 10^5\)
计算出 \(a_i = i\) 的位置数量 \(sum\) ，若 \(sum\) 为偶数，则让其两两配对交换即可；否则会剩下一个数，在其他数字中选一个合法的交换即可。答案即为 \(\lceil \dfrac{sum}{2} \rceil\)
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int a[N];
int T, n;
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d", &n);
int sum = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
sum += a[i] == i;
}
printf("%d\n", (sum + 1) >> 1);
}
return 0;
}
Longest Divisors Interval
给定整数 \(n\) ，求 \(1 \sim n\) 中的最长区间 \([l, r]\) 使得 \(\forall x \in [l, r], x | n\) ，输出区间长度
对于所有数据， \(n \leq 10^{18}\)
注意到对于区间 \([l, r]\) ，则对于 \([1, r - l + 1]\) 内的所有数， \([l, r]\) 中一定有一个是其倍数，可通过剩余系抽屉原理证明，于是我们只要从 \(1\) 开始枚举数判断是否是 \(n\) 的因数即可
因为前缀 \(\operatorname{lcm}\) 增长速度很快，所以每次询问可以视作常数级别
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
signed main() {
int T;
scanf("%d", &T);
for (ll n; T; --T) {
scanf("%lld", &n);
bool flag = false;
for (ll i = 1; i <= n; ++i)
if (n % i) {
printf("%lld\n", i - 1);
flag = true;
break;
}
if (!flag)
printf("%lld\n", n);
}
return 0;
}
Dual (Easy/Hard Version)
定义一次操作为选定 \(x, y\)， 将 \(a_y\) 加到 \(a_x\) 上，即 \(a_x \leftarrow a_x + a_y\) ，求使得序列单调不下降的最小操作次数
对于所有数据，\(1 \leq n \leq 20\) ，\(-20 \leq a_i \leq 20\)
设操作次数为 \(k\) ，Easy Version：\(k \leq 50\) ；Hard Version：\(k \leq 31\)
如果只有正数与 \(0\) ，则直接做前缀和即可；若只有负数与 \(0\) ，则直接做后缀和即可
如果正负数都有，考虑转化为上述情况。若正数最大值的绝对值大于负数最小值的绝对值，记 \(maxn\) 为正数最大值的绝对值，我们可以把其加到所有的负数上面转化为上述情况，这样需要保证负数个数最多 \(12\) 个
若负数个数超过 \(12\) 个，考虑让绝对值最大的负数自增（不会超过 \(5\) 次）直至小于 \(-20\) ，此时再将所有正数转化为负数即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e1 + 7;
vector<pair<int, int> > ans;
int a[N];
int T, n;
inline void add(int x, int y) {
a[x] += a[y], ans.push_back(make_pair(x, y));
}
inline void solve1() {
for (int i = 2; i <= n; ++i)
if (a[i - 1] > a[i])
add(i, i - 1);
}
inline void solve2() {
for (int i = n - 1; i; --i)
if (a[i] > a[i + 1])
add(i, i + 1);
}
inline int check() {
bool flag1 = true, flag2 = true;
for (int i = 1; i <= n; ++i)
flag1 &= a[i] >= 0, flag2 &= a[i] <= 0;
return flag1 && flag2 ? 666 : (flag1 ? 1 : (flag2 ? -1 : 0));
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
ans.clear();
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
if (check() > 0)
solve1();
else if (check() < 0)
solve2();
else {
int pos1 = -1, pos2 = -1, num1 = 0, num2 = 0;
for (int i = 1; i <= n; ++i) {
num1 += a[i] > 0, num2 += a[i] < 0;
if (a[i] > 0 && (pos1 == -1 || a[i] > a[pos1]))
pos1 = i;
if (a[i] < 0 && (pos2 == -1 || a[i] < a[pos2]))
pos2 = i;
}
if (a[pos1] > -a[pos2]) {
if (num2 <= 12) {
for (int i = 1; i <= n; ++i)
if (a[i] < 0)
add(i, pos1);
solve1();
} else {
while (a[pos2] > -20)
add(pos2, pos2);
for (int i = 1; i <= n; ++i)
if (a[i] > 0)
add(i, pos2);
solve2();
}
} else {
if (num1 <= 12) {
for (int i = 1; i <= n; ++i)
if (a[i] > 0)
add(i, pos2);
solve2();
} else {
while (a[pos1] < 20)
add(pos1, pos1);
for (int i = 1; i <= n; ++i)
if (a[i] < 0)
add(i, pos1);
solve1();
}
}
}
printf("%d\n", ans.size());
for (pair<int, int> it : ans)
printf("%d %d\n", it.first, it.second);
}
return 0;
}
Earn or Unlock
给定 \(n\) 张卡牌，每张卡牌上有一个数字 \(a_i\) ，最初只有最上面的卡牌解锁，每次可以使用一张已经解锁的牌 \(i\) 解锁未解锁的前 \(a_i\) 张卡牌并丢弃 \(i\) 卡牌，定义最终得分为所剩的已解锁的卡牌，求最大得分
对于所有数据，\(2 \leq n \leq 10^5\)
设最终包括 \(1\) 号卡片总共解锁了 \(k\) 张卡片，则所获得的分数就是 \((\sum_{i = 1}^k a_i) - k + 1\) ，所以我们只要判断是否存在一中方案使得恰好解锁 \(i\) 张卡片
设 \(dp_i\) 表示是否存在一中方案使得恰好解锁 \(i\) 张卡片。对于每一张卡片 \(i\) ，若存在一种方案使得恰好解锁 \(j\) 张卡片，则我们可以用掉这张卡片解锁 \(j + a_i\) 张卡片，于是
\[dp_j \leftarrow dp_j \or dp_{j - a_i} \]直接写会 TLE ，考虑将 \(dp\) 数组定义为 bitset ，则转移方程为 dp |= (dp << a[i])
转移完成后要将 \(dp_i \leftarrow 0\) ，因为此时已经遍历过前 \(i\) 张卡片了，接下来枚举的卡片已经超出了前 \(i\) 张卡片的范围，此时我们只解锁了前 \(i\) 张卡片，不能使用编号大于 \(i\) 的卡片）。为方便查询，可以先用别的数组记录 \(dp_i\) 的值
注意 \(dp\) 数组要开两倍大小（有可能多解锁）
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;
bitset<N> dp, f;
ll s[N];
int a[N];
int T, n;
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
s[i] = s[i - 1] + a[i];
}
dp[1] = 1;
for (int i = 1; i <= n; ++i) {
dp |= dp << a[i];
f[i] = dp[i], dp[i] = 0;
}
for (int i = n + 1; i <= n * 2; ++i)
f[i] = dp[i], s[i] = s[i - 1];
ll ans = 0;
for (int i = 1; i <= n * 2; ++i)
if (f[i])
ans = max(ans, s[i] - i + 1);
printf("%lld", ans);
return 0;
}
Expected Destruction
给定大小为 \(n\) 的正整数集合 \(S\)，\(S\) 中的每个数在 \(1\sim m\) 之间。
每一秒进行如下操作：
- 从 \(S\) 中等概率随机选择一个数 \(x\)。
- 将 \(x\) 从 \(S\) 中删去。
- 若 \(x + 1\leq m\) 且 \(x + 1\notin S\)，则将 \(x + 1\) 加入 \(S\)。
求 \(S\) 变成空集的期望时间，对 \(10 ^ 9 + 7\) 取模。
\(1\leq n\leq m \leq 500\)，\(1\leq S_1 < S_2 < \cdots < S_n \leq m\)。
把集合转化成一个 \((n+1)\) 行 \((m+1)\) 列的矩阵，其中第 \(i\) 行第 \(S_i\) 列处有一个方块。对这个方块进行操作就是让其移动到同行第 \(S_i+1\) 列上，如果这一列上早已存在一个方块，就将后一个移动的方块消除。目标即为让所有方块都在 \(m+1\) 列中，则该集合为空，即到达最终结果
考虑计算一对相邻方块使其到达同一列的期望时间，设 \(d p_{i, j}\) 表示方块 \(x\) 在第 \(i\) 列且方块 \(x+1\) 在第 \(j\) 列时，这两个方块到达同一列的期望时间，于是
\[d p_{i, j}=\frac{d p_{i+1, j}+d p_{i, j+1}+1}{2} \]答案即为 \(\sum_{i=1}^{n-1} d p_{S_i, S_{i+1}}\)
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7, inv2 = 500000004;
const int N = 5e2 + 7;
int dp[N][N];
int a[N];
bool vis[N][N];
int n, m, ans;
inline int dfs(int x, int y) {
if (x == y)
return m - x + 1;
else if (y == m + 1)
return 0;
else if (vis[x][y])
return dp[x][y];
else
return vis[x][y] = true, dp[x][y] = 1ll * (dfs(x + 1, y) + dfs(x, y + 1)) % Mod * inv2 % Mod;
}
signed main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
ans = (ans + m - a[i] + 1) % Mod;
}
for (int i = 0; i < n - 1; ++i)
ans = (ans - dfs(a[i], a[i + 1])) % Mod;
printf("%d", (ans + Mod) % Mod);
return 0;
}
Michael and Hotel
求出环上一段可以接受的长度的点，倍增即可
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 7;
vector<int> ans;
bool vis[N];
int n;
inline void append(int p) {
ans.push_back(p), vis[p] = true;
}
inline int query(int u, int k, vector<int> S) {
cout << "? " << u << " " << k << " " << S.size() << " ";
for(int it : S)
cout << it << " ";
cout << endl;
cin >> u;
return u;
}
inline int suc(int u, int k) {
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
vector<int> S;
for (int i = l; i <= mid; ++i)
S.push_back(i);
if (query(u, k, S))
r = mid;
else
l = mid + 1;
}
return l;
}
signed main() {
cin >> n;
int p = suc(1, 1064);
append(p);
for (int i = 1; i <= 63; ++i) {
p = suc(p, 1);
if (vis[p])
break;
append(p);
}
int aim = 64;
for (int aim = 64; aim <= ans.size(); aim <<= 1) {
vector<int> S = ans;
for (int i = 1; i <= n; ++i)
if (!vis[i] && query(i, aim, S))
append(i);
}
for (int i = 1; i <= n; ++i)
if (!vis[i] && query(i, n, ans))
append(i);
cout << "! " << ans.size() << " ";
for(int it : ans)
cout << it << " ";
cout << endl;
return 0;
}