A Add Three
模拟和直接计算均可。
模拟：
void solve() {
int n;
cin >> n;
int p = 0;
while (p + 3 <= n) p += 3;
cout << p << endl;
}
直接计算：
void solve() {
int n;
cin >> n;
cout << n / 3 * 3 << endl;
}
B Maximize The Count
$$a_i-a_j=p_i-p_j\Rightarrow a_i-p_i = a_j-p_j$$
记录一下每个数字值与下标之差，取最大即可。
void solve() {
int n, mx = 0;
cin >> n;
unordered_map<int, int> c;
for (int i = 1, x; i <= n; ++i) cin >> x, c[x - i]++;
for (auto [u, v] : c) mx = max(mx, v);
cout << mx << endl;
}
C Permutation Swapping
不难发现当 $n\geq 4$ 的时候可以选择任意 $k\neq i,k\neq i+1$ ，进行 $(i\ k)(i+1\ k)(i\ k) = (i\ i+1)$ 的置换，因此必然有解。
剩下的情况特判一下相等即可，$n=3$ 的时候还需要特判一下是否是逆序。
void solve() {
int n;
cin >> n;
bool f = 1, nf = 1;
for (int i = 1, x; i <= n; ++i) {
cin >> x;
if (x != i) f = 0;
if (x != n - i + 1) nf = 0;
}
if (f || n >= 4 || n == 3 && nf)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
D Two Options
由于两个操作对于总值的影响分别为 $+1$ 和 $+0$ ，因此最终的和必然大于等于初始的 $sum$ ，那么最优解显然是取最终值为 $p = \lceil\frac{sum}{n}\rceil$ ，又因为必然大于等于，所以减少的次数一定小于增加的次数，于是我们可以把所有减少的次数都与增加的次数绑组，贪心修改即可。本题需要注意负数的上取整处理。
void solve() {
int n;
ll sum = 0;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i];
ll p = sum > 0 ? (sum + n - 1) / n : sum / n, chg = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < p) chg += p - a[i];
}
cout << chg << endl;
}
E Not Equal
我们需要求解序列 $a’$ ，使得对于所有 $1\leq i<n$ ，都有 $a’_i\neq a’_{i+1}$ ，修改的代价为：
- 如果 $a’_i>a_i$ ，由于每次加 $1$ 花费 $b_i$ ，总代价为 $(a’_i−a_i)\times b_i$ 。
- 如果 $a’_i<a_i$ ，由于每次减 $1$ 花费 $c_i$ ，总代价为 $(a_i−a’_i)\times c_i$ 。
- 如果 $a’_i=a_i$ ，代价为 $0$ 。
直观来看，修改某个数是为了让它避开与相邻元素的冲突。假设某位置的最优取值为 $a’_i$ ，如果它距离初始值 $a_i$ 非常远（例如 $∣a’_i−a_i∣\geq 3$ ），那么在离 $a_i$ 更近的方向上，比如正数区间 $max(1,a_i−2)$ 到 $a_i+2$ 之间，必然存在某个值既不等于 $a’_{i−1}$ 也不等于 $a’_{i+1}$ ，因为这 $5$ 个数的候选区间里，左右相邻元素最多只会占据 $2$ 个名额，至少剩下 $3$ 个合法的候选值可选。
因此，将 $a’_i$ 调整到离 $a_i$ 更近的合法值，可以严格减小（或维持）修改该元素的代价，同时不破坏相邻不相同的约束。
根据以上结论，我们使用动态规划进行求解，用 $dp[i][j]$ 表示处理前 $i$ 个数，且第 $i$ 个数的最终值为 $v_i$ 中的第 $j$ 个候选值时，所需的最少总花费。有：
$$dp[i][j] = cost(i,v_i[j])+\min\{dp[i-1][k]\ |\ v_{i-1}[k]\neq v_i[j]\}$$
用滚动 $\text{dp}$ 实现。
void solve() {
int n;
cin >> n;
vector<ll> a(n), b(n), c(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
for (int i = 0; i < n; ++i) cin >> c[i];
array<ll, 5> v{}, dp{};
int siz = 0;
for (int i = 0; i < n; ++i) {
array<ll, 5> nv{}, ndp{};
int nsiz = 0;
for (ll j = a[i] - 2; j <= a[i] + 2; ++j) {
if (j >= 1) {
nv[nsiz++] = j;
}
}
for (int j = 0; j < nsiz; ++j) {
ll V = nv[j], cost = 0;
if (V > a[i])
cost = (V - a[i]) * b[i];
else if (V < a[i])
cost = (a[i] - V) * c[i];
if (i == 0) {
ndp[j] = cost;
} else {
ll mn = INF;
for (int k = 0; k < siz; k++) {
if (v[k] != V) {
mn = min(mn, dp[k]);
}
}
ndp[j] = mn + cost;
}
}
for (int j = 0; j < nsiz; ++j) {
v[j] = nv[j];
dp[j] = ndp[j];
}
siz = nsiz;
}
ll ans = INF;
for (int j = 0; j < siz; ++j)
if (dp[j] < ans) ans = dp[j];
cout << ans << endl;
}
F Alone
我们先考虑任意一个格子 $(i,j)$ ，如果它是孤立点，那么剩下的 $(n-1)\times(m-1)$ 的格子能够自由染色。这些格子组成了独立于第 $i$ 行和第 $j$ 列的一个大矩形。因此，有 $2^{(n-1)\times(m-1)}$ 种方法来填充这部分 。
然后我们考虑预设点：
对于我们选定的 $(i, j)$ ：
- 如果某个预设点 $(x, y)$ 位于第 $i$ 行或第 $j$ 列，但不是 $(i, j)$ 本身，那么它与 $(i, j)$ 的孤立配置是矛盾的。这种情况下，$(i, j)$ 永远不可能成为孤立点，贡献为 $0$ 。
- 如果所有 $k$ 个预设点都不与 $(i, j)$ 的孤立配置矛盾，那么这些预设点就必须满足它们各自的条件。
- 每个位于 $(n-1)\times (m-1)$ 自由区域内的预设点，都必须是黑色。这个要求将该区域的自由度减半。
- 如果 $(i, j)$ 本身就是一个预设点，它的黑色要求与孤立配置一致，不产生矛盾。
设有 $xx$ 个不同行， $yy$ 个不同列有预设点。
对于每一个不是预设点的格子，一共有 $(n-xx)\times (m-yy)$ 个格子。对于其中任何一个格子 $(i, j)$ ，它的孤立配置与 $k$ 个预设点都不矛盾。这 $k$ 个点全部落在 $(n-1)\times (m-1)$ 的自由区域内。为了满足这 $k$ 个点的黑色要求，自由区域的填法从 $2^{(n-1)\times(m-1)}$ 种减少到了 $2^{(n-1)\times(m-1) – k}$ 种。
- 此部分贡献 $= (n-xx) \times (m-yy) \times 2^{(n-1)\times (m-1) – k}$ 。
对于每一个是预设点，且不冲突的格子，记一共有 $K$ 个这样的格子。它的孤立配置与其他的 $k-1$ 个预设点都不矛盾。这 $k-1$ 个点全部落在 $(n-1)\times (m-1)$ 的自由区域内。为了满足这 $k-1$ 个点的黑色要求，自由区域的填法从 $2^{(n-1)\times (m-1)}$ 种减少到了 $2^{(n-1)\times (m-1) – (k-1)}$ 种。
- 此部分贡献 $= K \times 2^{(n-1)\times (m-1) – k + 1} = K \times 2\times 2^{(n-1)\times (m-1) – k}$
总贡献即为：$((n-xx)\times(m-yy)+K \times 2)\times 2^{(n-1)\times (m-1) – k}$ 。
其中 $(n-1)\times(m-1)$ 可能达到 $10^{18}$ 量级，需要用费马小定理进行优化。
$$a^{p-1}\equiv 1\pmod p$$
所以
$$a^e=a^{k(p-1)+r}=(a^{p-1})^ka^r\equiv a^r\pmod p$$
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<PII> a(k);
unordered_map<int, int> X, Y;
for (int i = 0; i < k; ++i) cin >> a[i].fi >> a[i].se, X[a[i].fi]++, Y[a[i].se]++;
int xx = X.size(), yy = Y.size();
int K = 0;
for (auto [x, y] : a)
if (X[x] == 1 && Y[y] == 1) K++;
ll mod = 998244352;
cout << (Z(1) * (n - xx) * (m - yy) + Z(2) * K) * ksm(Z(2), ((n - 1) * (m - 1) % mod - k + mod) % mod) << endl;
}
头文件
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
cout << fixed << setprecision(15);
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
自动取模
constexpr int MOD = 998244353;
template <class T>
constexpr T ksm(T a, ll b) {
T res = 1;
while (b) {
if (b & 1) res *= a;
b >>= 1;
a *= a;
}
return res;
}
template <int P>
struct MInt {
int x;
constexpr MInt() : x() {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) { Mod = Mod_; }
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const { return x; }
explicit constexpr operator int() const { return x; }
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return ksm(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr istream &operator>>(istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr ostream &operator<<(ostream &os, const MInt &a) { return os << a.val(); }
friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};
template <>
int MInt<0>::Mod = 998244353;
template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
using Z = MInt<MOD>;