ARC 149 C
考虑将奇数放一边，偶数放一边：
- 如果 \(2 \mid n\)：
构造 \(c = (n-1)(n+1) = n^2 - 1\)，于是对于每个奇数都可以有偶数对应。 - 如果不是：
所以需要两个奇合数 \(c_1 = n^2\)，\(c_2 = n^2 - 4\)（特判 \(n=3\)），而且红色相差 \(4\)。推个柿子就可以解决。
时间复杂度
显然为 \(\mathcal O(n^2)\)
点击查看代码
signed main() {
int n = read();
int a[1005][1005] = {};
if (n % 2 == 0) {
F(i, 1, n / 2 - 1) Fj
a[i][j] = 2 * (n * i + j) - 1;
Fj a[n / 2][j] = 2 * j - 1;
int c = n * n - 1;
F(i, n / 2 + 1, n) Fj a[i][j] = c - a[n + 1 - i][j];
a[n / 2 + 2][n] = n * n;
Fi writes(a[i], n);
} else if (n % 2 == 1)
if (n == 3) {
printf("%d %d %d \n"
"%d %d %d \n"
"%d %d %d \n"
, 5, 9, 1
, 3, 7, 8
, 6, 2, 4);
} else {
int c1 = n * n;
int f = n / 2, c = n / 2 + 1;
Fi
if (i <= c) a[c][i] = i * 2 - 1;
else a[f][i] = i * 2 + 1;
Fi
if (i <= c) a[c + 1][i] = c1 - a[c][i];
else a[f + 1][i] = c1 - a[f][i];
a[1][1] = c * 2 + 1;
int ans = n * 2 + 1;
F(i, 1, f) Fj if (!a[i][j])
a[i][j] = (ans += 2);
a[n][n] = n * n - a[1][1];
ans = c1 - (2 * n + 1);
F(i, c + 1, n) Fj if (!a[i][j])
a[i][j] = (ans -= 2);
Fi writes(a[i], n);
}
}
ABC 268 F
对于两个字符串，定义
\[X(s) = \sum_{c \in s} [c = \texttt{"X"}] \]\[\Sigma(s) = \sum_{c \in s} [c \ne \texttt{"X"}] \times c \]，设初始排列 \(\pi = (1,2,\dots,n)\)，对于一次修改 \(\pi' = (1,2,\dots,i+1,i,n)\)，得分增长了 \(\Sigma(s_{i+1})X(i) - \Sigma(s_i)X(i+1)\)，颓一下柿子：
\(\Sigma(s_{i+1})X(i) - \Sigma(s_i)X(i+1) > 0 \iff\)
\(\Sigma(s_{i+1})X(i) > \Sigma(s_i)X(i+1) \iff\)
\(\dfrac{\Sigma(s_{i})}{X(i)} > \dfrac{\Sigma(s_{i+1})}{X(i+1)}\)
所以保证 \(\dfrac{\Sigma(s)}{X(s)} \uparrow\) 可以得到最佳结果。
时间复杂度
显然为 \(\mathcal O((\sum |s| + n) \log n)\)
点击查看代码
bool cmp(string s, string t) {
int S = 0, SS = 0, x = 0, xx = 0;
for (char c : s)
if (c == 'X') x ++;
else S += c - '0';
for (char c : t)
if (c == 'X') xx ++;
else SS += c - '0';
return (ld)(S)/x < (ld)(SS)/xx;
}
int main() {
int n = read();
string s[200005] = {};
Fi cin >> s[i];
sort(s + 1, s + n + 1, cmp);
string awa = "";
Fi awa += s[i];
int got = 0;
ll ans = 0;
for (char c : awa)
if (c == 'X') got ++;
else ans += got * (c - '0');
writeln(ans);
return 0;
}
ABC 271 E
设 \(A_i \to B_i (L_i)\)。
发现到一条 good path 一定可以 dp，因为如果真的存在一条 good path，那么这条边的起点一定可以用 good path 联通（也就是说，这条边的起点一定被 dp 到了）
状态转移方程：
，滚动数组优化即可。
时间复杂度
每条边最多访问一次，故时间复杂度为 \(\mathcal O(n + m + k)\)。
ABC 272 E
显然有 \({\rm ans} \in [0, n]\)，且影响答案的 因素 也 \(\in [0, n]\)。
所以考虑 \(i \in [a, b] \iff a_x + xi \in [0, n]\)，对 \(\forall i \in [a, b]\) 枚举，并存进类似二维数组的结构当中，每次询问枚举答案即可
时间复杂度
\(|[a, b]| \le \lfloor \dfrac ni \rfloor + 1\)
\[\sum {\rm ans} \approx |二维数组| \le \sum\limits_{i=1}^n \lfloor \dfrac ni \rfloor + n = \sum\limits_{i=1}^n \lfloor \dfrac n{\lceil i \rceil} \rfloor + n = \int^{n}_{1} \lfloor \dfrac n{\lceil i \rceil} {\mathbf di} + n \rfloor \overset{\text{Lemma 1}}\le \int_1^n \dfrac ni {\mathbf di} + n = n \ln n + n \]\(\text{Lemma 1}: \lfloor \dfrac n{\lceil i \rceil} \rfloor \le \dfrac ni\)
Proof: \(\lfloor \dfrac n{\lceil i \rceil} \rfloor \le \dfrac{n}{\lceil i \rceil} \le \dfrac ni\)。