A - Rearranging a Sequence
签到题。从后到前遍历每个操作，如果当前操作数未输出，则输出并标记。最后遍历 1\dots n，输出未输出的数。
B - Quality of Check Digits
签到题。简单模拟即可。
C - Distribution Center
显然一条生产线能够收到的货物是来自连续的一段生产线，则只需要计算出能送到生产线 i 的最小生产线 \mathrm{up}_i 和 最大生产线 \mathrm{dn}_i，那么 i 能够收到的货物数量为 \mathrm{dn}_i-\mathrm{up}_i+1。初始 \mathrm{up}_i=\mathrm{dn}_i=i，将机械臂按 x 升序排序，更新 \mathrm{up} 和 \mathrm{dn} 即可。
D - Hidden Anagrams
先 O(n) 枚举子串长度，对于每一个长度 O(n\log n) 将 s_1 的该长度的所有子串的hash值存入一个set中，再枚举 s_2 中所有该长度的子串的hash并在set中查找。总复杂度 O(n^2\log n)。
E - Infallibly Crack Perplexing Cryptarithm
咕
F - Three Kingdoms of Bourdelot
咕
G - Placing Medals on a Binary Tree
咕
H - Animal Companion in Maze
咕
I - Skinny Polygon
设 w,h 为给定边界。构造一：用三角形，三个点分别为 (0,0),(w,h),(x,y)，则构成的三角形面积为 \frac{1}{2}|hx-wy|，令 g=\mathrm{gcd}(w,h)，则用exgcd可解出方程 hx-wy=g 的非负整数解，此时三角形面积为 \frac{g}{2}，当 g\le 50000 时满足题意。构造二：用凹四边形，四个点分别为 (0,0),(w-1,h),(w,h-1),(x,y)，其中 x=\frac{w}{g},y=\frac{h}{g}，此时四边形面积为 \frac{\sqrt{2}}{2}\sqrt{x^2+y^2}=\frac{\sqrt{2}}{2g}\sqrt{w^2+h^2}，由于 w,h\le 10^9，该构造在 g\ge 40000 时满足题意。综上，根据 g 分情况讨论即可。
J - Cover the Polygon with Your Disk
咕
K - Black and White Boxes
咕
Code
A - Rearranging a Sequence
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 200005
#define MAX_M 100005
using namespace std;
int n, m;
int a[MAX_M];
bool vis[MAX_N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", a + i);
}
for (int i = m; i >= 1; i--) {
if (!vis[a[i]]) {
printf("%d\n", a[i]);
vis[a[i]] = true;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
printf("%d\n", i);
}
}
}
B - Quality of Check Digits
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 15
#define MAX_L 10
using namespace std;
int ans = 0;
int a[MAX_L];
int w[MAX_N][MAX_N];
int gete() {
int res = 0;
for (int i = 1; i <= 4; i++) {
res = w[res][a[i]];
}
return res;
}
bool check(int x) {
for (int i = 4; i >= 1; i--) {
a[i] = x % 10, x /= 10;
}
a[5] = gete();
for (int i = 1; i <= 4; i++) {
if (a[i] != a[i + 1]) {
swap(a[i], a[i + 1]);
if (w[gete()][a[5]] == 0) {
return false;
}
swap(a[i], a[i + 1]);
}
}
for (int i = 1; i <= 5; i++) {
int t = a[i];
for (int r = 0; r < 10; r++) {
if (r != t) {
a[i] = r;
if (w[gete()][a[5]] == 0) {
return false;
}
}
}
a[i] = t;
}
return true;
}
int main() {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
scanf("%d", &w[i][j]);
}
}
for (int i = 0; i <= 9999; i++) {
if (!check(i)) {
ans++;
}
}
printf("%d\n", ans);
}
C - Distribution Center
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 200005
#define MAX_M 100005
#define pii pair<int, int>
using namespace std;
int n, m;
int up[MAX_N];
int dn[MAX_N];
pii p[MAX_M];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &p[i].first, &p[i].second);
}
sort(p + 1, p + 1 + m);
for (int i = 1; i <= n; i++) {
up[i] = dn[i] = i;
}
for (int i = 1; i <= m; i++) {
int t = p[i].second;
up[t + 1] = min(up[t + 1], up[t]);
dn[t] = max(dn[t], dn[t + 1]);
}
for (int i = 1; i <= n; i++) {
printf("%d ", dn[i] - up[i] + 1);
}
printf("\n");
}
D - Hidden Anagrams
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
#define MAX_N 4005
#define MAX_A 30
#define MOD1 19260817
#define MOD2 19491001
#define BASE 233
#define pii pair<int, int>
#define LL long long
using namespace std;
int n, m;
int pw1[MAX_A];
int pw2[MAX_A];
int cnt[MAX_A];
char s[MAX_N];
char p[MAX_N];
int main() {
pw1[0] = pw2[0] = 1;
for (int i = 1; i < 26; i++) {
pw1[i] = (LL)pw1[i - 1] * BASE % MOD1;
pw2[i] = (LL)pw2[i - 1] * BASE % MOD2;
}
scanf("%s%s", s + 1, p + 1);
n = strlen(s + 1), m = strlen(p + 1);
for (int len = min(n, m); len >= 1; len--) {
set<pii> st;
for (int i = 0; i < 26; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= len; i++) {
cnt[s[i] - 'a']++;
}
int hash1 = 0, hash2 = 0;
for (int i = 25; i >= 0; i--) {
hash1 = ((LL)hash1 * BASE + cnt[i]) % MOD1;
hash2 = ((LL)hash2 * BASE + cnt[i]) % MOD2;
}
for (int l = 1, r = len; r <= n; l++, r++) {
st.insert(pii(hash1, hash2));
if (r < n) {
int x = s[l] - 'a', y = s[r + 1] - 'a';
hash1 = (hash1 - pw1[x] + MOD1) % MOD1;
hash2 = (hash2 - pw2[x] + MOD2) % MOD2;
hash1 = (hash1 + pw1[y]) % MOD1;
hash2 = (hash2 + pw2[y]) % MOD2;
cnt[x]--, cnt[y]++;
}
}
for (int i = 0; i < 26; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= len; i++) {
cnt[p[i] - 'a']++;
}
hash1 = 0, hash2 = 0;
for (int i = 25; i >= 0; i--) {
hash1 = ((LL)hash1 * BASE + cnt[i]) % MOD1;
hash2 = ((LL)hash2 * BASE + cnt[i]) % MOD2;
}
for (int l = 1, r = len; r <= m; l++, r++) {
if (st.count(pii(hash1, hash2))) {
printf("%d\n", len);
return 0;
}
if (r < m) {
int x = p[l] - 'a', y = p[r + 1] - 'a';
hash1 = (hash1 - pw1[x] + MOD1) % MOD1;
hash2 = (hash2 - pw2[x] + MOD2) % MOD2;
hash1 = (hash1 + pw1[y]) % MOD1;
hash2 = (hash2 + pw2[y]) % MOD2;
cnt[x]--, cnt[y]++;
}
}
}
printf("0\n");
}
E - Infallibly Crack Perplexing Cryptarithm
F - Three Kingdoms of Bourdelot
G - Placing Medals on a Binary Tree
H - Animal Companion in Maze
I - Skinny Polygon
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define int long long
using namespace std;
int T, w, h;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld", &w, &h);
int g = gcd(w, h);
if (g <= 50000) {
int x, y;
exgcd(h, w, x, y);
int A = h / g, B = w / g;
int xmin = (x % B + B) % B;
int ymax = (g - h * xmin) / w;
if (ymax > 0) {
int t = ceil((double)ymax / A);
xmin += B * t, ymax -= A * t;
}
printf("3\n");
printf("0 0\n");
printf("%lld %lld\n", w, h);
printf("%lld %lld\n", xmin, -ymax);
} else {
printf("4\n");
printf("0 0\n");
printf("%lld %lld\n", w - 1, h);
printf("%lld %lld\n", w / g, h / g);
printf("%lld %lld\n", w, h - 1);
}
}
}
J - Cover the Polygon with Your Disk
K - Black and White Boxes