呐，人总是要有点梦想，万一实现了呢。
acm.sgu.ru@CodeForces
Part 1: $[100, 140)$
100. A+B
print(sum(map(int, input().split())))
101. Domino
给定 100 个骨牌，每个骨牌上写两个数。现在需要把骨牌横着排成一排，使得相邻两张骨牌相邻的数相同，输出方案。
Sol
欧拉回路。
#include <bits/stdc++.h>
using namespace std;
#define N 105
int n;
vector <pair<int, int>> E[7];
vector <int> odd, even;
bool vis[N];
vector <int> ans;
void dfs(int x) {
while (E[x].size()) {
pair <int, int> o = E[x].back();
E[x].pop_back();
if (vis[abs(o.second)]) continue;
vis[abs(o.second)] = 1;
dfs(o.first);
ans.push_back(-o.second);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
E[x].push_back({y, i});
E[y].push_back({x, -i});
}
for (int i = 0; i <= 6; i++) {
if (E[i].size() % 2 == 1) {
odd.push_back(i);
}
else if (E[i].size()) {
even.push_back(i);
}
}
if (odd.size() == 0) {
dfs(even[0]);
if (ans.size() == n) {
for (auto v : ans) {
printf("%d %c\n", abs(v), v > 0 ? '+' : '-');
}
}
else puts("No solution");
}
else if (odd.size() == 2){
E[odd[0]].push_back({odd[1], n + 1});
E[odd[1]].push_back({odd[0], -(n + 1)});
dfs(odd[0]);
if (ans.size() == n + 1) {
for (auto v : ans) if (abs(v) <= n){
printf("%d %c\n", abs(v), v > 0 ? '+' : '-');
}
}
else puts("No solution");
}
else puts("No solution");
}
102. Coprimes
print(phi(n))
103. Traffic Lights
$n$ 个路口，$m$ 条路，每个路口有一个红绿灯，两个灯同色时才能通行。给定每个灯的周期，询问起点到终点的最短路。
$n\leq 300, m \leq 14000, l, w \leq 100$
Sol
无论怎么说，到一个点的时间仍然是越早越好——即使可能会等一会儿。
考虑如何处理出每个边的可行区间。预处理不靠谱，因为最坏可能达到 $m \times w ^ 2$ 的复杂度。然而，考虑这个东西的要求是同色而不是同为绿灯，所以直接暴力复杂度是 $O(w)$ 的。注意处理永不可能通行的情况。
总复杂度 $O(\mathrm{Dijkstra} \cdot w).$
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int M = 14005;
int S, T, n, m;
int off[N], t[N][2], r[N];
char tmp[10];
struct Edge {
int v, w;
};
vector <Edge> E[N];
struct Node {
int x, d;
bool operator < (const Node &a) const {
return d < a.d;
}
};
priority_queue <Node> q;
int dis[N], fr[N];
void dij() {
memset(dis, 0x3f, sizeof dis);
dis[S] = 0; q.push({S, 0});
while (!q.empty()) {
Node o = q.top(); q.pop();
int x = o.x, d = o.d;
if (d != dis[x]) continue;
for (auto v : E[x]) {
int tt = 0;
while (tt < 300) {
int nt = tt + d;
if (((nt + off[x]) % (t[x][0] + t[x][1]) < t[x][0]) == ((nt + off[v.v]) % (t[v.v][0] + t[v.v][1]) < t[v.v][0])) {
break;
}
tt++;
}
if (tt < 300 && dis[v.v] > dis[x] + v.w + tt) {
dis[v.v] = dis[x] + v.w + tt;
fr[v.v] = x;
q.push({v.v, dis[v.v]});
}
}
}
}
int main() {
scanf("%d %d\n%d %d\n", &S, &T, &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s %d %d %d\n", tmp, r + i, t[i] + 0, t[i] + 1);
off[i] = t[i][0] + t[i][1] - r[i] - (tmp[0] == 'B' ? t[i][1] : 0);
}
for (int i = 1; i <= m; i++) {
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
E[u].push_back({v, l});
E[v].push_back({u, l});
}
dij();
if (dis[T] < 0x3f3f3f3f) {
printf("%d\n", dis[T]);
vector <int> ans;
int x = T;
while (x != S) {
ans.push_back(x);
x = fr[x];
}
printf("%d", S);
reverse(ans.begin(), ans.end());
for (auto v : ans) {
printf(" %d", v);
}
printf("\n");
}
else {
puts("0");
}
}
104. Little Shop of Flowers
$F$ 朵花依次放进 $V$ 个花瓶里，花瓶可以空着但花不能改变顺序。$a_{i, j}$ 为 $i$ 放进 $j$ 的给定价值，求最大价值和，输出方案。
Sol
DP
#include <bits/stdc++.h>
using namespace std;
#define N 105
int F, V;
int a[N][N];
int dp[N][N];
bool fr[N][N];
int main() {
scanf("%d%d", &F, &V);
for (int i = 1; i <= F; i++) {
for (int j = 1; j <= V; j++) {
scanf("%d", a[i] + j);
}
}
memset(dp, 200, sizeof dp);
dp[0][0] = 0;
for (int i = 0; i < F; i++) {
for (int j = 0; j < V; j++) if (dp[i][j] > -0x3f3f3f){
if (dp[i][j + 1] < dp[i][j]) {
dp[i][j + 1] = dp[i][j];
fr[i][j + 1] = 0;
}
if (dp[i + 1][j + 1] < dp[i][j] + a[i + 1][j + 1]) {
dp[i + 1][j + 1] = dp[i][j] + a[i + 1][j + 1];
fr[i + 1][j + 1] = 1;
}
}
}
printf("%d\n", dp[F][V]);
int x = F, y = V;
vector <int> ans;
while (x) {
if (fr[x][y]) {
ans.push_back(y);
x--;
}
y--;
}
reverse(ans.begin(), ans.end());
for (int i = 0; i < F; i++) {
printf("%d%c", ans[i], i == F - 1 ? '\n' : ' ');
}
}
105. Div 3
询问 $1, 12, 123, \cdots, 12345678910$ 这样的数字的前 $n$ 个有多少个被 $3$ 整除。
Sol
n = int(input())
print(n // 3 * 2 + int(n % 3 == 2))
106. The Equation
询问 $ax + by + c = 0$ 在 $x \in [x_1, x_2], y \in [y_1, y_2]$ 的解。
Sol
EXGCD
- 特判 0
- 取整
- 如果不转正，最后可能除负数导致区间反转
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) return x = 1, y = 0, a;
LL t = exgcd(b, a % b, y, x);
y -= a / b * x;
return t;
}
int main() {
LL a, b, c, x1, x2, y1, y2;
cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;
c = -c;
if (x1 > x2 || y1 > y2) return 0 * puts("0");
if (a == 0 || b == 0) {
if (a == 0 && b == 0)
cout << (c == 0 ? (x2 - x1 + 1) * (y2 - y1 + 1) : 0ll) << endl;
else {
if (b == 0) swap(a, b), swap(x1, y1), swap(x2, y2);
cout << (y1 <= c / b && c / b <= y2 ? x2 - x1 + 1 : 0ll) << endl;
}
return 0;
}
LL x, y, g;
g = exgcd(a, b, x, y);
if (c % g) return 0 * puts("0");
a /= g, b /= g, c /= g, x *= c, y *= c;
LL d1 = (x1 - x) / b, d2 = (x2 - x) / b;
if (x + d1 * b < x1) d1++;
if (x + d2 * b > x2) d2--;
LL e1 = (y1 - y) / a, e2 = (y2 - y) / a;
if (y + e1 * a < y1) e1++;
if (y + e2 * a > y2) e2--;
e1 = -e1, e2 = -e2;
if (d1 > d2) swap(d1, d2);
if (e1 > e2) swap(e1, e2);
cout << max(0ll, min(e2, d2) - max(e1, d1) + 1) << endl;
}
107. 987654321 problem
输出有多少个 $n$ 位数的平方的最后九位是 $987654321$。
Sol
打个表发现有 $8$ 个 $9$ 位数满足条件，所以 $n \geq 10$ 就有 $72 \times 10 ^ {n – 10}$ 个。
#include <bits/stdc++.h>
using namespace std;
int main() {
/*int x = 987654321;
for (int i = 30000; i < 1e9; i++) {
long long y = (long long)i * i % 1000000000;
if (y == 987654321) cout << i << endl;
}*/
int n; scanf("%d", &n);
if (n <= 8) puts("0");
else {
if (n == 9) putchar('8');
else {
putchar('7'), putchar('2');
while (n-- > 10) putchar('0');
}
puts("");
}
}
108. Self-numbers II
定义 $$
d(n) = n + \sum Digit_i(n)
$$ $$
S = \lbrace x | x \in [1, n], \lnot (\exists y, d(y) = x )\rbrace
$$ 询问 $|S|$ 以及 $S$ 中 $a_i$ 大的值。
$n \leq 10 ^ 7, K \leq 5000$
Time Limit 0.5s, Memory Limit 4M
Sol
内存很小，所以用 bitset 存 bool。
时间很紧，打表 $O(1)$ 算数位和。
Better: 加上数位和只会影响后 $9 \times \mathrm{Len}$ 个数，因此可以使用循环数组。
#include <bits/stdc++.h>
using namespace std;
#define N 10000
int n, K;
int b[N];
bitset <int(10000090 + 1)> G;
pair <int, int> a[N];
int ans[N];
int main() {
scanf("%d%d", &n, &K);
for (int i = 0; i < K; i++) {
scanf("%d", &a[i].first);
a[i].second = i;
}
sort(a, a + K);
for (int i = 0; i < N; i++) {
int su = 0, x = i;
while (x) su += x % 10, x /= 10;
b[i] = su;
}
int cur = 0, p = 0;
for (int i = 1; i <= n; i++) {
if (!G[i]) {
p ++;
while (p == a[cur].first) {
ans[a[cur].second] = i;
cur++;
}
}
int x = i + b[i / N] + b[i % N];
G[x] = 1;
}
printf("%d\n", p);
for (int i = 0; i < K; i++) {
printf("%d%c", ans[i], i == K - 1 ? '\n' : ' ');
}
}
109. Magic of David Copperfield II
一个 $n \times n(n \leq 100)$ 的网格图，最开始观众的手在 $(1, 1)$，每次魔术师可以让观众的手自行移动 $k_i$（互不相同且 $n \leq k_i \leq 3 \times n$）步，然后魔术师禁用一些格子。如此重复操作，直到所有观众的手都在同一个格子。构造满足条件的方案。
Sol
每次移动，观众都可以到这个图上任何一个奇偶性满足条件的格子，所以每次的移动必然是奇数。为了不破坏连通性，我们每次从角落的格子往里赶鸭子，角落定义为相邻至少两个坏格子的点。奇数这么做就好了，偶数需要在最后一步特判一下，留出一个空位来。
#include <bits/stdc++.h>
using namespace std;
#define N 103
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, off, d[N][N], id[N][N], I;
pair <int, int> pos[N * N];
vector <int> buc[2], now;
int L[2];
void clear(vector <int> &a) {
printf("%d", n + off);
off += 2;
for (auto v : a) {
printf(" %d", v);
for (int i = 0; i < 4; i++) {
int tx = pos[v].first + dx[i], ty = pos[v].second + dy[i];
if (--d[tx][ty] <= 2) {
d[tx][ty] = 1e9;
buc[(tx + ty) % 2].push_back(id[tx][ty]);
}
}
}
printf("\n");
a.clear();
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
id[i][j] = ++I;
pos[I] = {i, j};
for (int q = 0; q < 4; q++) {
int tx = i + dx[q], ty = j + dy[q];
d[tx][ty]++;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
L[(i + j) % 2]++;
if (d[i][j] <= 2) {
d[i][j] = 1e9;
buc[(i + j) % 2].push_back(id[i][j]);
}
}
}
for (int i = 0; i <= n + 1; i++) d[i][0] = d[i][n + 1] = d[0][i] = d[n + 1][i] = 1e9;
int cur = 1;
off = n & 1 ? 0 : 1;
while (L[0] + L[1] > 1) {
cur ^= 1;
if (L[cur] == buc[cur].size() && L[cur ^ 1] != 1) {
buc[cur].pop_back();
clear(buc[cur]);
clear(buc[cur ^ 1]);
break;
}
L[cur] -= buc[cur].size();
clear(buc[cur]);
}
}
110. Dungeon
给定 $n \leq 50$ 个球，一束光射向这些球，到表面反射。输出前 $10$ 个被射到的球。
Sol
几何方法难写，考虑三分。
这道题反向卡精度，$\mathrm{eps}$ 要开到 $10^{-8}$ 或更大。
#include <bits/stdc++.h>
using namespace std;
#define N 55
#define cp const point &
typedef double LD;
const LD eps = 1e-8, inf = 1e9;
struct point {
LD x, y, z;
point () {}
point (LD a, LD b, LD c) : x(a), y(b), z(c) {}
void read() {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
x = a, y = b, z = c;
}
point operator + (cp a) const {return {x + a.x, y + a.y, z + a.z};}
point operator - (cp a) const {return {x - a.x, y - a.y, z - a.z};}
point operator - () const { return {-x, -y, -z}; }
point operator * (const LD a) const {return {x * a, y * a, z * a};}
point unit() {
LD r = 1 / sqrt(x * x + y * y + z * z);
return {x * r, y * r, z * r};
}
LD len2() {
return x * x + y * y + z * z;
}
LD norm2() {
return sqrt(x * x + y * y + z * z);
}
} c[N], cur, dir;
LD dot(cp a, cp b) {
return a.x * b.x + a.y * b.y + a.z * b.z;
}
point project_to_line(cp a, cp bs, cp bt) {
return bs + (bt - bs) * (dot(a - bs, bt - bs) / (bt - bs).norm2());
}
int n;
LD R[N], t[N];
bool ban[N];
LD test(int id) {
LD l = 0, r = inf;
for (int i = 0; i < 200; i++) {
LD lmid = (l + l + l + r + r) / 5, rmid = (l + l + r + r + r) / 5;
point pl = cur + dir * lmid, pr = cur + dir * rmid;
if ((pl - c[id]).len2() < (pr - c[id]).len2()) r = rmid;
else l = lmid;
}
point now = cur + dir * l;
if (sqrt((now - c[id]).len2()) > R[id] + eps) return inf;
return l;
}
point get(int id, LD r) {
LD l = 0;
for (int i = 0; i < 200; i++) {
LD mid = (l + r) / 2;
point pmid = cur + dir * mid;
if ((pmid - c[id]).len2() >= R[id] * R[id]) l = mid;
else r = mid;
}
point ans = cur + dir * l;
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int r;
c[i].read();
scanf("%d", &r); R[i] = r;
}
cur.read(); dir.read();
dir = (dir - cur).unit();
vector <int> ans;
for (int q = 0; q < 11; q++) {
LD mint = inf;
int id = -1;
for (int i = 1; i <= n; i++) if(!ban[i]) {
t[i] = test(i);
if (t[i] < mint) {
id = i;
mint = t[i];
}
}
else ban[i] = 0;
if (mint == inf) break;
point on = get(id, t[id]);
point rp = (on - c[id]).unit();
point k = project_to_line(-dir, point(0, 0, 0), rp);
dir = k + k + dir;
cur = on;
ans.push_back(id);
ban[id] = 1;
}
for (int i = 0; i < min(10, (int)ans.size()); i++) {
if (i) printf(" ");
printf("%d", ans[i]);
}
if ((int)ans.size() > 10) printf(" etc.\n");
else printf("\n");
}
111. Very simple problem
输出 $\lfloor \sqrt n \rfloor (n \leq 10 ^ {1000}).$
Sol
Python 的 sqrt(n) 是对 $\mathrm{64-bit}$ double 的。
Python 的 Decimal 属实弟弟。
但是 Python 的 int 还是很快的。
n = int(input())
l, r = 1, 2
while r * r < n:
l *= 2
r *= 2
while l < r:
mid = (l + r + 1) >> 1
if mid * mid <= n:
l = mid
else:
r = mid - 1
print(l)
112. a^b – b^a
a, b = map(int, input().split(' '))
print(a ** b - b ** a)
113. Nearly prime numbers
输入格式搞我，PyPy 3 还搞我，心态崩了。
now_token = input().split()
now_token.reverse()
def nxt_token():
global now_token
if len(now_token) > 0:
ret = now_token[-1]
now_token.pop()
return ret
else:
now_token = input().split()
now_token.reverse()
return nxt_token();
n = int(nxt_token())
while n > 0:
n -= 1
x = int(nxt_token())
ans = False
i = 2
while i * i <= x:
if x % i == 0:
y = x // i
ans = (y > 1)
j = 2
while j * j <= y:
if y % j == 0:
ans = 0
break
j += 1
break
i += 1
if ans:
print("Yes")
else:
print("No")
114. Telecasting station
数轴上有一些城市，每个城市住着一些人，求一个集合点使得走到这个点的距离总和最短。
Sol
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 50001
#define NN N + 5
int n;
int c[NN];
LL pre[NN], sum[NN], ans[NN];
void work() {
pre[0] = sum[0] = 0;
for (int i = 1; i <= N ; i++) {
pre[i] = pre[i - 1] + c[i];
sum[i] = sum[i - 1] + (LL)c[i] * i;
}
for (int i = 1; i <= N; i++) {
ans[i] += pre[i] * i - sum[i];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, p;
scanf("%d%d", &x, &p);
c[x] += p;
}
work();
reverse(c + 1, c + N + 1);
reverse(ans + 1, ans + N + 1);
work();
reverse(c + 1, c + N + 1);
reverse(ans + 1, ans + N + 1);
LL Ans = 0x3f3f3f3f3f3f3f3f;
int id = 0;
for (int i = 1; i <= N; i++) {
if (ans[i] < Ans) {
Ans = ans[i];
id = i;
}
}
printf("%d\n", id);
}
115. Calendar
M = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n, m = map(int, input().split())
if (m < 1) or (m > 12) or (n < 1):
print("Impossible")
elif n > M[m]:
print("Impossible")
else:
d = 0
for i in range(1, m):
d += M[i]
d += n - 1
print(d % 7 + 1)
116. Index of super-prime
non-increasing
#include <bits/stdc++.h>
using namespace std;
#define N 10001
int p[N / 3], pcnt;
bool vis[N];
vector <int> a;
void init() {
vis[1] = 1;
for (int i = 2; i < N; i++) {
if (!vis[i]) {
p[++pcnt] = i;
if (!vis[pcnt]) a.push_back(i);
}
for (int j = 1, k; (k = i * p[j]) < N; j++) {
vis[k] = 1;
if (i % p[j] == 0) break;
}
}
}
int n;
int dp[N], fr[N];
int main() {
init();
scanf("%d", &n);
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (auto v : a) {
for (int i = v; i <= n; i++) {
if (dp[i] >= dp[i - v] + 1) {
dp[i] = dp[i - v] + 1;
fr[i] = v;
}
}
}
if (dp[n] < 0x3f3f3f3f) {
printf("%d\n", dp[n]);
while (n) {
printf("%d%c", fr[n], fr[n] == n ? '\n' : ' ');
n -= fr[n];
}
} else puts("0");
}
116. Counting
sgu 的数据好假，以后都粘 token 板子了。
now_token = []
def nxt_token():
global now_token
if len(now_token) > 0:
ret = now_token[-1]
now_token.pop()
return ret
else:
now_token = input().split()
now_token.reverse()
return nxt_token();
n = int(nxt_token())
m = int(nxt_token())
k = int(nxt_token())
cnt = 0
for i in range(n):
a = int(nxt_token())
if pow(a, m, k) == 0:
cnt += 1
print(cnt)
117. Digital root
$$
f(n) = \begin{cases} n, & n \leq 9 \\
f(\text{sum of digits of }n), & \text{otherwise}
\end{cases}
$$ 求 $$
f(a_1 + a_1 a_2 + \cdots + a_1 a_2 \cdots a_n)
$$ $a_i \leq 10 ^ 9, n \leq 1000$
Sol
懒狗流 python 卡常，249ms/250ms AC。
Better: 数位和不改变模 $9$ 的值，直接模然后判下 $0$ 就好了 ……我是憨憨
now_token = input().split()
now_token.reverse()
def nxt_token():
global now_token
if len(now_token) > 0:
ret = now_token[-1]
now_token.pop()
return ret
else:
now_token = input().split()
now_token.reverse()
return nxt_token();
N = 10000
NN = N * N * N * N
rt = [0]
for i in range(1, N):
rt.append((rt[i // 10] + i % 10))
def Sum(cur):
ans = 0
while cur > 0:
a = cur // N
ans += rt[cur - a * N]
cur = a
return ans
K = int(nxt_token())
while K > 0:
K -= 1
n = int(nxt_token())
cur = 0
l = []
for i in range(n):
l.append(int(nxt_token()))
l.reverse()
for a in l:
cur += 1
cur *= a
while cur >= 10:
ans = 0
while cur > 0:
a = cur // NN
ans += Sum(cur - a * NN)
cur = a
cur = ans
print(cur)
119. Magic Pairs
数有多少满足 $0 \leq a < n, 0 \leq b < n$ 的数对 $(a, b), $ 使得 $$
a_0 x + b_0y \equiv 0 \mod n \Rightarrow a x + b y \equiv 0 \mod n
$$ $n \leq 10000$
Sol
我的做法比较憨。注意到最小的 $$\Delta x = \frac {b_0} {\gcd (a_0, b_0)}, \Delta y = \frac {a_0} {\gcd (a_0, b_0)}$$ 那么必然有 $$a \frac {b_0} {\gcd (a_0, b_0)} – b \frac {a_0} {\gcd (a_0, b_0)} \equiv 0 \mod n$$ 那么枚举 $a_0$，解出所有可能的 $b_0$ 就行了。注意到这个条件必要但不充分，需要判一判是不是对于一组特解成立——而且特解还不是简单意义上的 exgcd 特解，因为 $n$ 可以不整除 $\gcd (a, b)$，因此当 $ax + by = \gcd(a, b)$ 时，特解为 $(x\frac n {gcd(n, a, b)}, y\frac n {gcd(n, a, b)})$。
事实上，$a_0 x + b_0y = n \Rightarrow a x + b y = n$ 当且仅当 $\exists k, (a, b) = (a k \bmod n, b k \bmod n)$。充分性显然，必要性的证明思路是：首先令 $b = 0, $，可得 $a | \gcd(a_0, n)$，同理 $b | \gcd(b_0, n)$；然后令 $a = b_0, b = a_0$，得证。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) return x = 1, y = 0, a;
LL t = exgcd(b, a % b, y, x);
y -= a / b * x;
return t;
}
LL n, a, b;
vector <pair<int, int>> ans, aa;
int main() {
cin >> n >> a >> b;
LL gg = __gcd(a, b), x, y;
if (gg == 0) {
printf("%d\n%d %d\n", 1, 0, 0);
return 0;
}
for (int i = 0; i < n; i++) {
LL ba0 = b / gg * i, g;
g = exgcd(a / gg, n, x, y);
if (ba0 % g) continue;
x *= ba0 / g;
x %= n / g;
while (x < n) {
if (x >= 0) ans.push_back({i, (int)x});
x += n / g;
}
}
exgcd(a, b, x, y);
x *= n / __gcd(n, gg), y *= n / __gcd(n, gg);
for (auto v : ans) {
if ((v.first * x + v.second * y) % n == 0) aa.push_back(v);
}
printf("%d\n", (int)aa.size());
sort(aa.begin(), aa.end());
for (auto v : aa) {
printf("%d %d\n", v.first, v.second);
}
}
120. Arhipelago
给定一个正 $n$ 边形上的两个点，按顺时针顺序输出所有点。
Sol
#include <bits/stdc++.h>
using namespace std;
#define cp const point &
#define N 155
struct point {
double x, y;
point () {}
point (double a, double b) : x(a), y(b) {}
point operator + (cp a) const {
return {x + a.x, y + a.y};
}
point operator - (cp a) const {
return {x - a.x, y - a.y};
}
point operator * (const double a) const {
return {x * a, y * a};
}
point unit() {
double l = len();
return {x / l, y / l};
}
point rot(double theta) {
return {x * cos(theta) + y * sin(theta), -x * sin(theta) + y * cos(theta)};
}
double len() {
return sqrt(x * x + y * y);
}
} p[N];
const double PI = 3.1415926535897932384626;
int n, n1, n2;
int main() {
scanf("%d%d%d", &n, &n1, &n2);
scanf("%lf%lf", &p[n1].x, &p[n1].y);
scanf("%lf%lf", &p[n2].x, &p[n2].y);
int dif = min((n2 - n1 + n) % n, (n1 - n2 + n) % n);
double theta = 2 * PI / n;
double l = (p[n1] - p[n2]).len(), a = l / 2;
double r = a / sin(theta / 2 * dif), d = r * cos(theta / 2 * dif);
point cen;
if ((n2 - n1 + n) % n == dif) {
cen = (p[n1] + p[n2]) * 0.5 + (p[n2] - p[n1]).unit().rot(PI / 2) * d;
}
else {
cen = (p[n1] + p[n2]) * 0.5 + (p[n1] - p[n2]).unit().rot(PI / 2) * d;
}
point cur = p[n1] - cen;
for (int i = n1 % n + 1; i != n1; i = i % n + 1) {
cur = cur.rot(theta);
p[i] = cur + cen;
}
for (int i = 1; i <= n; i++) {
printf("%.6lf %.6lf\n", p[i].x, p[i].y);
}
}
121. Bridges painting
给一个 $n$ 个点的图，询问边染色方案，使得每个点都有黑边白边相邻。
Sol
无向图的 DFS 树有这样的性质：只有返祖边没有横叉边；根的每棵子树之间没有边。这样，任取一个 DFS 树，树边按深度交替染色，非树边当做较深的那个的儿子处理，这样至多只有根不满足条件了，如果不满足条件的话考虑调整：
- 如果根的树上 $deg > 1$，那么随便选一个子树反色就好了；
- 如果根的 $deg = 1$，存在一个返祖边使得与非叶子响邻，那么这条边的颜色可以直接改；
- 如果 $1, 2$ 不满足，那么如果这个图是奇环是无解的；否则，随便找一个与根相邻的叶子，把 根->叶子->叶子的最深的 $deg > 2$ 的祖先 这条路径反色就可以了。
当然还有一种更骚一点的写法：如果全是偶度数那么直接交替染色，只有奇环无解；如果存在奇度数那么从奇度数开始交替染色必然有解。正确性我不太会证，但是够骚。
#include <bits/stdc++.h>
using namespace std;
#define N 105
int n;
vector <int> E[N], cur;
struct edge {
int x, y;
edge (int a, int b) {
if (a < b) x = a, y = b;
else x = b, y = a;
}
bool operator < (const edge &a) const {
return x < a.x || (x == a.x && y < a.y);
}
};
map <edge, bool> c;
bool vis[N];
void dfs(int x) {
vis[x] = 1;
cur.push_back(x);
for (auto v : E[x]) if (!vis[v]) dfs(v);
}
void dfsc(int x, int col) {
for (auto v : E[x]) if (!c.count(edge(x, v))){
c[edge(x, v)] = col;
col ^= 1;
dfsc(v, col);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
while (x) {
E[i].push_back(x);
scanf("%d", &x);
}
}
for (int x = 1; x <= 1; x++) if (!vis[x]) {
cur.clear();
dfs(x);
int rt = x;
for (auto v : cur) if (E[v].size() % 2) rt = v;
dfsc(rt, 0);
bool flag = 1;
for (auto v : cur) {
bool cc[2] = {0, 0};
for (auto i : E[v]) cc[c[edge(v, i)]] = 1;
if (E[v].size() > 1 && (!cc[0] || !cc[1])) flag = 0;
}
if (!flag) return 0 * puts("No solution");
}
for (int i = 1; i <= n; i++) {
for (auto v : E[i]) {
printf("%d ", c[edge(i, v)] + 1);
}
printf("0\n");
}
}
122. The book
$n \leq 1000$ 个点的图，每个点的度数 $\geq \lceil \frac n 2 \rceil$，求一条哈密顿回路。
Sol
人有多大胆，地有多大产 冲不过，自闭了。
这个图的性质叫做 ORE，我们可以构造性地证明这样的哈密顿回路必然存在。
首先，我们随便搞一个极长的链，这样链的起点终点都没有相邻的不在链上的点。我们讨论两种情况：
- 起点终点相邻
那么现在我们有一个环，如果没有做完的话，环上随便找一个出边不在环上的点，把环变成更大的链
- 起点终点不相邻
那么我们想把现在的链变成一个同样大的环，直接找两个在链上相邻的点，使得两个点分别与终点和起点相连，这样断开他们之间的边后与终点、起点相连，就可以得到一个环。
由于 ORE 性质，这样的算法每一步都必然可以进行下去。所以就搞完了。
最优实现是 $O(n ^ 2)$ 的，然而其实写成这个复杂度还是有很多细节的，我直接抄雷希拉姆的板子了。
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n;
int g[N][N];
int l[N], r[N], nx[N], la[N];
void cover(int x) {
l[r[x]] = l[x];
r[l[x]] = r[x];
}
int adj(int x) {
for (int i = r[0]; i <= n; i = r[i]) {
if (g[x][i]) return i;
}
return 0;
}
vector <int> solve() {
for (int i = 1; i <= n; i++) {
l[i] = i - 1;
r[i] = i + 1;
}
int h, t;
for (int i = 2; i <= n; i++) {
if (g[1][i]) {
h = 1, t = i, cover(h), cover(t);
nx[h] = t;
break;
}
}
while (1) {
int x;
while (x = adj(h)) {
nx[x] = h;
h = x;
cover(h);
}
while (x = adj(t)) {
nx[t] = x;
t = x;
cover(t);
}
if (!g[h][t]) {
for (int i = h, j ; i != t; i = nx[i]) {
if (g[h][nx[i]] && g[t][i]) {
for (j = h; j != i; j = nx[j]) la[nx[j]] = j;
j = nx[h];
nx[h] = nx[i];
nx[t] = i;
t = j;
for (j = i; j != h; j = la[j]) nx[j] = la[j];
break;
}
}
}
nx[t] = h;
if (r[0] > n) break;
for (int i = h; i != t; i = nx[i]) {
if (adj(i)) {
h = nx[i];
t = i;
nx[t] = 0;
break;
}
}
}
vector <int> ans;
for (int i = h; ; i = nx[i]) {
if (i == 1) {
ans.push_back(i);
for (int j = nx[i]; j != i; j = nx[j]) ans.push_back(j);
ans.push_back(i);
break;
}
}
return ans;
}
int main() {
scanf("%d\n", &n);
for (int i = 1; i <= n; i++) {
int x;
while (scanf("%d", &x)) {
g[i][x] = g[x][i] = 1;
int ch = getchar();
if (ch != ' ') break;
}
}
for (auto i : solve()) printf("%d%c", i, n-- == 0 ? '\n' : ' ');
}
123. The sum
n = int(input())
f = [0, 1, 1]
for i in range(3, n + 1):
f.append(f[-1] + f[-2])
s = 0
for i in range(1, n + 1):
s += f[i]
print(s)
124. Broken line
给定一个不自交的边平行于坐标轴的 $n\leq 10000$ 边形，求一个点是不是在这个 $n$ 边形内。
Sol
本身是个傻题，但是我写了个线段树，而且因为数据有退化（某条边是某个点到自己，讲道理不会影响但是会导致奇怪的问题）不明原因（在注释那里）挂了。很怪。
其实扰动射线法就完了。
#include <bits/stdc++.h>
using namespace std;
#define N 80212
#define L 10001
struct line {
int x, l, r;
line (int a, int b, int c) {
if (b > c) swap(b, c);
x = a, l = b, r = c;
}
bool operator < (const line &a) const {
return x < a.x || (x == a.x && l < a.l);
}
};
vector <line> a;
struct Node {
int l, r, v;
} t[N * 2];
int tcnt = 0;
int build(int l ,int r) {
int x = ++tcnt;
if (l < r) {
int mid = (0x200000 + l + r) / 2 - 0x100000;
t[x].l = build(l, mid);
t[x].r = build(mid + 1, r);
}
return x;
}
int qry(int x, int l, int r, int p) {
if (l == r) return t[x].v;
int mid = (0x200000 + l + r) / 2 - 0x100000;
if (p <= mid) return t[x].v + qry(t[x].l, l, mid, p);
else return t[x].v + qry(t[x].r, mid + 1, r, p);
}
void mod(int x, int l, int r, int ql, int qr, int v) {
if (l == ql && r == qr) {
t[x].v += v;
return;
}
int mid = (0x200000 + l + r) / 2 - 0x100000;
if (qr <= mid) mod(t[x].l, l, mid, ql, qr, v);
else if (ql > mid) mod(t[x].r, mid + 1, r, ql, qr, v);
else mod(t[x].l, l, mid, ql, mid, v), mod(t[x].r, mid + 1, r, mid + 1, qr, v);
}
int n;
int X1[N], Y1[N], X2[N], Y2[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
X1[i] = x1;
X2[i] = x2;
Y1[i] = y1;
Y2[i] = y2;
if (x1 == x2) {
a.push_back({x1, y1, y2});
}
}
build(-L, L);
int X, Y;
scanf("%d%d", &X, &Y);
for (int i =1; i <= n; i++) {
if (X == X1[i] && Y1[i] <= Y && Y <= Y2[i]) return 0 * puts("BORDER");
if (Y == Y1[i] && X1[i] <= X && X <= X2[i]) return 0 * puts("BORDER");
}
sort(a.begin(), a.end());
int cur = -0x3f3f3f;
int m = (int)a.size();
for (int i = 0, j; i < m; ) {
j = i;
int x = a[i].x;
int u = qry(1, -L, L, Y - 1), v = qry(1, -L, L, Y);
if (cur <= X && X < x) {
printf("%s\n", u + v /* == 2 */? "INSIDE" : "OUTSIDE");
return 0;
}
while (j < m && a[j].x == x) {
int y = qry(1, -L, L, a[j].l);
if (a[j].l < a[j].r) {
if (y) mod(1, -L, L, a[j].l, a[j].r - 1, -1);
else mod(1, -L, L, a[j].l, a[j].r - 1, 1);
}
j++;
}
i = j;
}
printf("OUTSIDE\n");
}
#include <bits/stdc++.h>
using namespace std;
#define N 10555
int n, X, Y, X1[N], Y1[N], X2[N], Y2[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
X1[i] = x1, X2[i] = x2, Y1[i] = y1, Y2[i] = y2;
}
scanf("%d%d", &X, &Y);
for (int i =1; i <= n; i++) {
if (X == X1[i] && Y1[i] <= Y && Y <= Y2[i]) return 0 * puts("BORDER");
if (Y == Y1[i] && X1[i] <= X && X <= X2[i]) return 0 * puts("BORDER");
}
int cnt = 0;
for (int i = 1; i <= n; i++) if (Y1[i] == Y2[i] && Y1[i] < Y && X1[i] <= X && X2[i] > X) cnt++;
puts(cnt % 2 ? "INSIDE" : "OUTSIDE");
}
125. Shtirlits
$n\times n(n \leq 3)$ 的网格，给你每个格子周围有多少个格子数比他大，构造方案。
Sol
DFS + 剪枝。
我假 AC 是：
- 按输入排序
- 按度数判可行（是否超过最大度数，是否有两个相邻的满度的点）
- 判存在 $0$
- 每一步用 $\leq$ 判最优化
当然是假的，但是因为所有卡人数据都这么构造的，于是我们与出题人的斗智斗勇便赢了一次。
#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n;
int a[5][5], id[5][5], cc[5][5], deg[5][5] = {{}, {0, 2, 3, 2}, {0, 3, 4, 3}, {0, 2, 3, 2}};
vector < pair<int, int> > c;
void dfs(int x) {
if (x == n * n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (cc[i][j] != a[i][j]) return;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d%c", 9 - id[i][j], j == n ? '\n' : ' ');
}
}
exit(0);
}
const int& u = c[x].first, v = c[x].second;
for (int i = !!a[u][v]; i < 9; i++) {
cc[u][v] = 0;
bool flag = 0;
for (int d = 0; d < 4; d++) {
int tx = u + dx[d], ty = v + dy[d];
if (id[tx][ty] < i) cc[u][v]++;
else if (id[tx][ty] < 0x3f3f3f3f && id[tx][ty] > i) {
if (++cc[tx][ty] > a[tx][ty]) flag = 1;
}
}
if (!flag && cc[u][v] <= a[u][v]) {
id[u][v] = i;
dfs(x + 1);
id[u][v] = 0x3f3f3f3f;
}
for (int d = 0; d < 4; d++) {
int tx = u + dx[d], ty = v + dy[d];
if (id[tx][ty] < 0x3f3f3f3f && id[tx][ty] > i) {
--cc[tx][ty];
}
}
}
}
int main() {
cin >> n;
memset(id, 0x3f, sizeof id);
memset(a, 0x3f, sizeof a);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
c.push_back({i, j});
}
sort(c.begin(), c.end(), [](pair<int, int> x, pair<int, int> y) {return a[x.first][x.second] < a[y.first][y.second];});
if (n == 3) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] > deg[i][j]) {
return 0 * puts("NO SOLUTION");
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == deg[i][j]) {
for (int d = 0; d < 4; d++) {
int tx = i + dx[d], ty = j + dy[d];
if (a[tx][ty] == deg[tx][ty]) return 0 * puts("NO SOLUTION");
}
}
}
}
}
if (a[c[0].first][c[0].second] == 0)dfs(0);
puts("NO SOLUTION");
}
卡掉数据如下：
3
0 3 0
3 3 3
0 3 0
正解就是按照一个好的顺序用 $=$ 最优化剪枝就行了。感受一下发现明显好一些。
126. Boxes
两个箱子，每次较小的箱子为 $a$ 较大的为 $b$，定义一步操作为 $(a, b) \rightarrow (2a, b – a)$，问能不能搞出 $(0, a + b)$。
Sol
感性理解一下是一个 $\text{log}$ 的过程，冲冲冲。
证明的话，倒推一下发现进行 $i$ 步可以把最小可区分单元为 $\frac {a + b} {2 ^ i}$ 的答案枚举到，所以当然是一个 $\text{log}$ 的。
a, b = map(int, input().split())
ans = 0
while a > 0 and b > 0:
if a > b:
a, b = b, a
b -= a
a += a
ans += 1
if ans > 1000:
ans = -1
break
print(ans)
127. Telephone directory
我是菜菜
K = int(input())
n = int(input())
a = []
for i in range(n):
x = int(input())
a.append(x)
a.sort()
last = -1
cnt = 0
ans = 2
for i in range(n):
if a[i] // 1000 == last and cnt < K:
cnt += 1
else:
last = a[i] // 1000
cnt = 1
ans += 1
print(ans)
128. Snake
给定 $n$ 个点，构造一个闭合折线，使得边平行于坐标轴，并且相邻两段是垂直的，并且长度最短。
Sol
这道题我最开始不会是因为没注意到必须垂直，似乎这样是个非常难的问题；不过垂直就简单很多了。
同一个 $x$ 上必然只会有孤立的几个 $y$ 的 pair，并且每个 pair 必定连边，否则题目条件无法满足。然后就是判可行，我是这么判的：
- 连通
- 每个点度数为 $2$
- 用扫描线判断不存在这种情况：
..*-*..
*-|-|-*
*-*.*-*
#include <bits/stdc++.h>
using namespace std;
#define N 10011
int n, e, ans = 0;
int f[N], d[N];
vector <int> X[N + N], Y[N + N];
map <pair<int, int>, int> G;
int getf(int x) {return f[x] == x ? x : f[x] = getf(f[f[x]]);}
struct op {
int x, y, k, d;
bool operator < (const op &a) const {
return x < a.x || (x == a.x && k < a.k);
}
};
vector <op> c;
void add(int x1, int y1, int x2, int y2) {
int p1 = G[make_pair(x1, y1)], p2 = G[make_pair(x2, y2)];
ans += abs(x2 - x1) + abs(y2 - y1);
d[p1]++, d[p2]++;
e++;
f[getf(p1)] = getf(p2);
if (x1 == x2) {
if (y1 > y2) swap(y1, y2);
c.push_back({x1, y1, 0, y2});
}
else {
if (x1 > x2) swap(x1, x2);
c.push_back({x1, y1, 1, 1});
c.push_back({x2, y1, 1, -1});
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= n; i++) {
int x, y; scanf("%d%d", &x, &y);
Y[N + x].push_back(y);
X[N + y].push_back(x);
G[make_pair(x, y)] = i;
}
for (int i = -10000; i <= 10000; i++) if (X[N + i].size()) {
if (X[N + i].size() % 2) return 0 * puts("0");
sort(X[N + i].begin(), X[N + i].end());
int m = (int)X[N + i].size();
for (int j = 0; j < m; j += 2) {
add(X[N + i][j], i, X[N + i][j + 1], i);
}
}
for (int i = -10000; i <= 10000; i++) if (Y[N + i].size()) {
if (Y[N + i].size() % 2) return 0 * puts("0");
sort(Y[N + i].begin(), Y[N + i].end());
int m = (int)Y[N + i].size();
for (int j = 0; j < m; j += 2) {
add(i, Y[N + i][j], i, Y[N + i][j + 1]);
}
}
bool flag = 0;
if (e == n) {
flag = 1;
for (int i = 1; i <= n; i++) flag &= (getf(i) == getf(1));
for (int i = 1; i <= n; i++) flag &= d[i] == 2;
sort(c.begin(), c.end());
set <int> yy;
for (auto i : c) {
if (!i.k) {
auto it = yy.upper_bound(i.y);
if (it == yy.end() || *it >= i.d);
else flag = 0;
}
else {
if (i.d == 1) yy.insert(i.y);
else yy.erase(i.y);
}
}
}
printf("%d\n", flag ? ans : 0);
}
129. Inheritance
给定一个凸包，多次询问一条线切过严格在这个凸包内的长度。
$n \leq 400, m \leq 1000$
Sol
复杂度很松所以直接暴力就行了。
需要判一下 det == 0 && dot == 0。
#include <bits/stdc++.h>
using namespace std;
#define N 405
#define cp const point &
const double eps = 1e-7;
int sgn(double x) {return (x > eps) - (x < -eps);}
struct point {
double x, y;
point () {}
point (double a, double b) {x = a, y = b;}
point operator + (cp a) const { return {x + a.x, y + a.y}; }
point operator - (cp a) const { return {x - a.x, y - a.y}; }
point operator * (const double z) const { return {x * z, y * z};}
point operator / (const double z) const { return {x / z, y / z};}
double len2() const {return x * x + y * y;}
};
double det(cp a, cp b) {return a.x * b.y - a.y * b.x;}
double dot(cp a, cp b) {return a.x * b.x + a.y * b.y;}
bool ts(cp a, cp b, cp cs, cp ct) {return sgn(det(a - cs, ct - cs)) * sgn(det(b - cs, ct - cs)) < 0;}
bool onseg(cp a, cp bs, cp bt) {
return sgn(det(a - bs, bt - bs)) == 0 && sgn(dot(bs - a, bt - a)) <= 0;
}
bool inj(cp as, cp at, cp bs, cp bt) {
if (onseg(bs, as, at) || onseg(bt, as, at)) return 1;
if (onseg(as, bs, bt) || onseg(at, bs, bt)) return 1;
return ts(as, at, bs, bt) && ts(bs, bt, as, at);
}
point inter(cp as, cp at, cp bs, cp bt) {
double s1 = det(at - as, bs - as);
double s2 = det(at - as, bt - as);
return (bs * s2 - bt * s1) / (s2 - s1);
}
int contain(const vector <point>& poly, cp p) {
int ret = 0, n = poly.size();
for (int i = 0; i < n; i++) {
point u = poly[i], v = poly[(i + 1) % n];
if (onseg(p, u, v)) return 1;
int x = sgn(det(p - u, v - u)), y = sgn(u.y - p.y), z = sgn(v.y - p.y);
if (x > 0 && y <= 0 && z > 0) ret++;
if (x < 0 && z <= 0 && y > 0) ret--;
}
return ret & 1 ? 2 : 0;
}
int n, m;
point base;
bool cmp(cp a, cp b) {
int d = sgn(det(b - base, a - base));
if (d) return d == 1;
return (a - base).len2() < (b - base).len2();
}
vector <point> a;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
a.push_back({x, y});
if (i == 0 || base.x > x) base = a.back();
}
sort(a.begin(), a.end(), cmp);
scanf("%d", &m);
while (m--) {
point s, t;
{
int x, y, z, w;
scanf("%d%d%d%d", &x, &y, &z, &w);
s = {x, y};
t = {z, w};
}
int qs = contain(a, s), qt = contain(a, t);
double ans = 0;
if (qs + qt >= 3) {
ans = sqrt((t - s).len2());
}
else {
if (qt == 2) swap(qs, qt), swap(s, t);
vector <point> inc;
for (int i = 0; i < n; i++) {
int j = i == n - 1 ? 0 : i + 1;
if (sgn(det(a[j] - a[i], t - s)) == 0 && sgn(det(a[j] - s, t - s)) == 0) {
inc.clear();
break;
}
if (inj(s, t, a[i], a[j])) {
inc.push_back(inter(s, t, a[i], a[j]));
}
}
if (qs == 2) {
assert(inc.size() > 0);
ans = sqrt((s - inc[0]).len2());
}
else {
for (int i = 1; i < (int)inc.size(); i++) {
ans = max(ans, sqrt((inc[i - 1] - inc[i]).len2()));
}
}
}
printf("%.2lf\n", ans);
}
}
130. Circle
应该练习 python 的，懒了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 33
int n;
LL f[N];
LL solve(int x) {
if (f[x]) return f[x];
LL &ret = f[x];
for (int i = 0; i < x; i++) ret += solve(i) * solve(x - 1 - i);
return ret;
}
int main() {
f[0] = 1;
cin >> n;
cout << solve(n) << " " << n + 1 << endl;
}
131. Hardwood floor
用 $1\times 2$ 或者 $2 \times 2$ 挖去一格的 L 形来覆盖 $n \times m$ 的地板。$n, m \leq 9$。
Sol
做法很显然，但是 $dfs$ 复杂度算起来很有意思。
一种可以考虑的计算复杂度的方式是，考虑 DP 中满足一行的话，我们有三种方法满足这一行的两格，三种方法是满足这一行的一格，那么如果我们不考虑下一行的不可行，这一行的方案是 $f$，有 $$ fn = 3f{n – 1} + 3f_{n – 2} $$ 而事实上复杂度远低于这个，因为还有另一行的限制，这样的话我们最多进 $3 ^ n$ 次 $dfs$。
我们还可以考虑用轮廓线来算，这样的话也是 $3 ^ n$ 的。
#include <bits/stdc++.h>
using namespace std;
#define N 10
int n, m, X;
int c[1 << (2 * N)];
void dfs(int x, int y, int z) {
if (x == X) {
c[z << n ^ y]++;
return;
}
for (int i = 0; i < n; i++) if (!(x >> i & 1)){
if (i < n - 1) {
if (!(x >> (i + 1) & 1)) {
dfs(x ^ 3 << i, y, z);
if (!(y >> i & 1)) dfs(x ^ 3 << i, y ^ 1 << i, z);
if (!(y >> (i + 1) & 1)) dfs(x ^ 3 << i, y ^ 2 << i, z);
}
if (!(y & 3 << i)) dfs(x ^ 1 << i, y ^ 3 << i, z);
}
if (i > 0 && !(y & 3 << (i - 1))) dfs(x ^ 1 << i, y ^ 3 << (i - 1), z);
if (!(y & 1 << i)) dfs(x ^ 1 << i, y ^ 1 << i, z);
return;
}
}
typedef long long LL;
LL dp[N][1 << N];
int main() {
scanf("%d%d", &n, &m);
X = (1 << n) - 1;
for (int i = 0; i <= X; i++) dfs(i, 0, i);
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j <= X; j++) if (dp[i][j]) {
int o = j << n;
for (int k = 0; k <= X; k++) {
dp[i + 1][k] += dp[i][j] * c[o ^ k];
}
}
}
printf("%lld\n", dp[m][0]);
}
132. Another Chocolate Maniac
放尽量少的骨牌使得已有坏点的 $m \times n $ 网格图不能再放骨牌。
$m \leq 70, n \leq 7$
Sol
可以搞 $mn3 ^ n$ 但是我懒了，写了 $m n 4 ^ n$，第一遍还忘 break 了，比较搞笑。
#include <bits/stdc++.h>
using namespace std;
#define M 75
#define N 7
int m, n, X;
int dp[M][1 << N][1 << N];
char s[N + 2];
void dfs(int x, int j, int k, int l, int v) {
if (dp[x + 1][k][l] <= v) return;
{
bool ok = 1;
for (int i = 0; i < n; i++) if (!(j >> i & 1) && !(k >> i & 1)) ok = 0;
for (int i = 0; i < n - 1; i++) if (!(j & 3 << i)) ok = 0;
if (ok) dp[x + 1][k][l] = v;
}
for (int i = 0; i < n; i++) {
if (i < n - 1 && !(j & 3 << i)) dfs(x, j ^ 3 << i, k, l, v + 1);
if (!(j >> i & 1) && !(k >> i & 1)) {
dfs(x, j ^ (1 << i), k ^ (1 << i), l, v + 1);
}
if (i < n - 1 && (j >> i & 3) != 3 && !(k & 3 << i)) dfs(x, j, k ^ 3 << i, l, v + 1);
if (!(j >> i & 1) && !(k >> i & 1) && !(l >> i & 1)) {
dfs(x, j, k ^ (1 << i), l ^ (1 << i), v + 1);
}
if (i) {
if (!(j & 3 << (i - 1))) return;
if (!(j >> (i - 1) & 1) && !(k >> (i - 1) & 1)) return;
}
}
}
int main() {
scanf("%d%d", &m, &n);
X = (1 << n) - 1;
memset(dp, 0x3f, sizeof dp);
dp[0][X][X] = 0;
for (int i = 0; i <= m + 1; i++) {
int S = 0;
if (i < m) {
scanf("%s", s);
for (int j = 0; j < n; j++) {
if (s[j] == '*') S ^= 1 << j;
}
}
else S = X;
for (int j = 0; j <= X; j++) for (int k = 0; k <= X; k++) if (dp[i][j][k] < 0x3f3f3f3f) {
dfs(i, j, k, S, dp[i][j][k]);
}
}
printf("%d\n", dp[m + 2][X][X]);
}
133. Border
#include <bits/stdc++.h>
using namespace std;
#define N 17777
int n;
pair <int, int> a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int l, r;
scanf("%d%d", &l, &r);
a[i] = {l, r};
}
sort(a + 1, a + n + 1);
int R = 0, ans = 0;
for (int i = 1; i <= n; ) {
int j = i;
while (j <= n && a[j].first == a[i].first) j++;
for ( ; i < j; i++) {
int r = a[i].second;
if (r < R) ans++;
else R = r;
}
}
printf("%d\n", ans);
}
134. Centroid
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define read(a) scanf("%d", &a)
#define N 16666
int n;
int siz[N], val[N], fa[N];
int ans = 0x3f3f3f3f;
vector <int> E[N], o;
void dfs(int x) {
siz[x] = 1;
for (auto v : E[x]) if (v != fa[x]) {
fa[v] = x;
dfs(v);
siz[x] += siz[v];
val[x] = max(val[x], siz[v]);
}
val[x] = max(val[x], n - siz[x]);
if (val[x] < ans) ans = val[x], o = {x};
else if (val[x] == ans) o.push_back(x);
}
int main() {
read(n);
for (int i = 1; i < n; i++) {
int u, v; read(u); read(v);
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1);
printf("%d %d\n", ans, (int)o.size());
sort(o.begin(), o.end());
for (auto v : o) printf("%d ", v);
}
135. Drawing Lines
n = int(input())
print(n * (n + 1) // 2 + 1)
136. Erasing Edges
给定一些中点，构造一个满足每条边的中点是给定中点的可退化多边形。
Sol
$n$ 为奇数时满秩，偶数时不满秩，满秩时解一下就好了。
#include <bits/stdc++.h>
using namespace std;
#define N 11000
int n;
double x[N], y[N];
vector < pair<double, double> > ans;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf%lf", x + i, y + i);
double xx = 0, yy = 0;
for (int i = 0; i < n; i++) {
if (i & 1) xx -= x[i], yy -= y[i];
else xx += x[i], yy += y[i];
}
ans.push_back({xx, yy});
for (int i = 0; i < n; i++) {
xx = 2 * x[i] - xx;
yy = 2 * y[i] - yy;
ans.push_back({xx, yy});
}
if (abs(ans[0].first - ans[n].first) > 1e-8 || abs(ans[0].second - ans[n].second) > 1e-8) puts("NO");
else {
puts("YES");
for (int i = 0; i < n; i++) printf("%.3lf %.3lf\n", ans[i].first, ans[i].second);
}
}
137. Funny Strings
给定一个数字列，把首位减一，末位加一后 shift 一定位置得到原列的列称为是 funny 的。问长度为 $n$ 总和为 $K$ 的数字列，保证 $\gcd(n, K) = 1$。
Sol
考虑一个 shift 后与原串等价的过程，相当于一系列合并。如果 shift 的长度与 $n$ 不互素，则有 $a_1 = a_n = a_1 -1 = a_n + 1,$ 显然不成立，所以 shift 的长度一定与 $n$ 互素。互素时，必有 $a_1 = a_n – 1$，其中按照 shift 的方式 $a_1$ 的后继与 $a_n$ 的后继分别与它们相同，并且由于 shift 的长度属于 $\mathbb Z_n^$，且显然后继段的长度也属于 $\mathbb Z_n^$，这中间必然存在着一个一一对应。由于题设条件因此答案存在，我们枚举 shift 的长度就可以了。
#include <bits/stdc++.h>
using namespace std;
int n, K;
int a[10111];
int main() {
scanf("%d%d", &n, &K);
int base = K / n, m = K % n;
for (int i = 1; i < n; i++) if (__gcd(i, n) == 1) {
int c = 0;
for (int j = n - 1; j != 0; j = (j + i) % n) c++;
if (c == m) {
for (int j = 0; j < n; j++) a[j] = base;
for (int j = n - 1; j != 0; j = (j + i) % n) a[j]++;
for (int j = 0; j < n; j++) printf("%d%c", a[j], j == n - 1 ? '\n' : ' ');
return 0;
}
}
assert(false);
}
138. Games of Chess
某一场比赛的胜者必须打下一场，给定每个人打了多少场，构造一个方案。
Sol
最开始我搞了一个做法：每次取出一个最大的，优先吃 1，然后吃剩下的最大的。这样听起来很靠谱，但
7
5 4 1 1 1 1 1
会挂，为什么会挂很显然。
所以，我们考虑修正这个算法：显然，1 是要吃的，但是不能把后面吃出一个 boss 出来。考虑让比赛场数少的人必败，且这样的人尽量少，这样有一个好，分界线处存在胜场的那个可能会有多的，但是这个可以被第一个人吃掉。我们可以证明这样做是对的。
#include <bits/stdc++.h>
using namespace std;
int n;
vector <pair<int, int>> ans;
pair<int, int> a[111];
int sum[111];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
a[i] = {x, i};
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].first;
int cur = 0, L = -1;
for (int i = n; i >= 1; i--) {
cur += i == n ? a[i].first : a[i].first - 2;
if (cur >= sum[i - 1]) {
L = i;
break;
}
}
vector < int > u;
for (int i = 1; i < L; i++) {
for (int j = 0; j < a[i].first; j++) {
u.push_back(a[i].second);
}
}
cur -= sum[L - 1];
for (int i = cur; i; i -= 2) {
ans.push_back({a[n].second, a[L].second});
a[n].first --, a[L].first --;
}
for (int i = n; i >= L; i--) {
while (a[i].first > 1 - (i == L)) {
ans.push_back({a[i].second, u.back()});
u.pop_back();
a[i].first --;
}
if (i > L) ans.push_back({a[i - 1].second, a[i].second}), a[i - 1].first --;
}
printf("%d\n", (int)ans.size());
for (auto i : ans) {
printf("%d %d\n", i.first, i.second);
}
}
139. Help Needed!
#include <bits/stdc++.h>
using namespace std;
#define N 4
int a[N][N];
int main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
scanf("%d", a[i] + j);
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
if (a[i][j] == 0) swap(a[i][j], a[i][j + 1]);
}
if (i < 3 && a[i][3] == 0) swap(a[i][3], a[i + 1][3]);
}
vector <int> b;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
b.push_back(a[i][j]);
int ans = 0;
for (int i = 0; i < 16; i++) {
for (int j = i + 1; j < 16; j++) {
ans ^= b[i] > b[j];
}
}
puts(ans ? "YES" : "NO");
}