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
对于两个字符串，定义
，设初始排列 \(\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\)
\(\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\)。
ABC 273 E
方法 \(1\)
发现是一个可持久化数组，用主席树维护即可。
时间复杂度
\(\mathcal O(q \log q)\) 加常数
较为方便的实现
Ext 模板库中提供了一种名为 \(\texttt{std::rope}\) 的容器，内部实现为可持久化平衡树，可以极为方便的解决本题。
使用 rope 小心野指针（map<int, rope*> 的未赋值部分是 nullptr）
点击查看代码
using R = rope<int>*;
map<int, R> f;
int main() {
int q = read(), L = 0;
f[0] = new rope<int>;
while (q --) {
string s;
cin >> s;
if (s == "ADD") {
int x = read();
f[0]->push_back(x);
} else if (s == "DELETE") {
if (f[0]->size()) f[0]->erase(f[0]->size()-1, 1);
} else if (s == "SAVE") {
int x = read();
f[x] = new rope<int>(*f[0]);
} else {
int x = read();
if (f[x] == nullptr) f[x] = new rope<int>;
f[0] = new rope<int>(*f[x]);
}
if (f[0]->size()) write((*f[0])[f[0]->size()-1]);
else write(-1);
putchar(' ');
}
return 0;
}
方法 \(2\)
进入正解。
本题的操作相当于维护树上的指针。
设当前的指针为 \(p\)。
- \(\tt ADD\) 操作：为 \(p\) 添加一个子节点，其点权为 \(x\)。
- \(\tt DELETE\) 操作：将 \(p\) 返到 \(p\) 的父亲那里。
- \(\tt SAVE\) 操作：记录 \(p\) 这个指针。
- \(\tt LOAD\) 操作：将 \(p\) 赋值为记录（若无此记录，赋值为根节点）
ARC 148 C
显然按两次按钮等价于不按。
于是函数 \(f : \mathscr P(n) \to \mathscr P(n)\)，其中 \(f(S)\) 代表 \(\forall x \in S, 操作(x)\)，是单射。考虑证明满射性：如果需要亮起灯 \(x\)，则 \(T = \{x\} \cup son(x)\) 是一个满足条件的序列。于是有
，其中 \(\bigtriangleup\) 为对称差。
于是我们证明了 \(f\) 是双射。或者说，不存在输出 \(\tt -1\) 或非平凡的多组解。
考虑每个点都会在什么情况下被操作。操作 \(x,fa_x \iff\) 操作到 \(x\)。于是若 \(x\) 与 \(fa_x\) 共同存在，则两个抵消，或 \(-2\)，答案为：
。
原文地址：http://www.cnblogs.com/lhx-oier/p/16760462.html
