传送门：Gym 102501
A - Environment-Friendly Travel
首先对于两个车站，如果它们之间有边，由于距离相同，显然只保留单位排放量最小的交通方式。设 f[i][j] 表示走到车站 i，已经走过的路程为 j，此时的最小二氧化碳排放量。转移方程为 f[k][j+d]=\min(f[k][j+\mathrm{dist}(i,k)],f[i][j]+c\cdot \mathrm{dist}(i,k))，其中 k 为 i 的后继，c 为单位排放量。总复杂度 O(N\cdot B\cdot 100)。
B - Biodiversity
签到题，map统计出现次数即可。
C - Ants
签到题。显然答案一定在 [0,N] 之间，所以对于大于 N 的数直接舍弃，然后暴力统计即可。
D - Gnalcats
显然对于一个基因序列来说，其产生的复杂氨基酸的种类数不超过该基因序列长度。对于每种新产生的复杂氨基酸，用map维护其唯一编号，分别模拟然后判断产物序列是否相等即可。
E - Pixels
设 x_{i,j} 表示按钮 (i,j) 按不按，a_{i,j} 表示 (i,j) 的目标颜色，行数和列数分别为 n,m，令 n\ge m。若要保证第一行结果正确，则对于 \forall j\in[1,m]，需要满足 x_{1,j}\oplus x_{1,j-1}\oplus x_{1,j+1}\oplus x_{2,j}=a_{1,j}，移项得 x_{2,j}=x_{1,j}\oplus x_{1,j-1}\oplus x_{1,j+1}\oplus a_{1,j}，这样就将第二行的所有 x_{2,j} 用 x_{1,1}\dots x_{1,m} 以及一个常数表示了出来，同理可以依次处理下面的每一行。当我们表示完了最后一行时，前 n-1 行的结果正确性已经保证，只有最后一行待确定，对于 \forall j\in[1,m]，若要保证 (n,j) 的结果正确，则要保证 x_{n,j}\oplus x_{n,j-1}\oplus x_{n,j+1}\oplus x_{n-1,j}=a_{n,j}，其中所有的 x 都可以用 x_{1,1}\dots x_{1,m} 表示，即方程 \sum_{k=1}^m c_{j,k}\cdot x_{1,k}，这样的方程共 m 个，高斯消元解异或方程组即可得到 x_{1,1}\dots x_{1,m}，顺着往下推出每一行的答案即可。总复杂度 O(nm\cdot\min(n,m))。
F - Icebergs
签到题，暴力计算多边形面积即可。
G - Swapping Places
原题等价于，不断地选一个位置 i 且该位置的物种为 s_i，将该物种与前面的物种不断交换，并最终添加到答案队列的末尾。由于不是朋友的物种之间最终的相对位置关系不变，对于位置 i 的物种 s_i，如果物种 s_i 与 t 不是朋友，则对于所有在位置 i 之后的位置 j，若满足 s_j=t，则显然只有当 s_i 加入答案之后，s_j 才有可能加入答案，这样就形成了一个拓扑关系。由于同物种之间不能互换，所以只需要找到 i 之后的第一个物种等于 t 的位置 j，从 i 向 j 连一条边，然后跑一遍字典序最小的拓扑排序即可。总复杂度 O(N\cdot S)。
H - Pseudo-Random Number Generator
显然序列 S 存在循环节，用Floyd's Tortoise and Hare环检测算法找出循环节位置 [L,R]=[350125310,532254518]，同时分段打表打出所有 i=k\cdot 5\times 10^6 的 S(i) 值以及 S(0)\dots S(i) 中偶数值的个数，以及子段 S(L)\dots S(R) 中偶数值的个数为 91029304 个。当 n\ge R 时直接将 n 化为 n=k\cdot 5\times 10^6\lt R，同时计算丢弃的若干个循环节所产生的贡献。然后再向后暴力处理不超过 5\times 10^6 位即可。
I - Rats
签到题，按给定公式计算即可。
J - Counting Trees
这题面真就英语阅读题，看了半天没看懂......翻译一下：有一棵 n 个节点的二叉树，给出其中序遍历的节点权值序列，问你有多少种二叉树满足该中序遍历，且有小根堆的性质（父节点权值小于子节点）。
先找出原序列中的最小值构成的子序列，设其长度为 k，该子序列一定先构成一棵顶端的二叉树，种类个数即为卡特兰数 C_k=\frac{1}{k+1}C(2n,n)。并且该子序列将原序列分成了若干子段，这些子段同样将分别构成二叉树，正好接在刚刚的二叉树下面（刚刚的二叉树下有 k+1 个位置可接，而子段恰好也有 k+1 个），递归处理即可，答案即为若干个卡特兰数相乘。
我们继续观察可以发现，对于所有的拥有相同权值，且不被更小权值分割的长度最大化的子序列，设长度为 |s|，最终答案即为所有这样的 |s| 之积。利用单调栈即可在 O(n) 时间内求解。
K - Birdwatching
原题等价于：问你在连向 T 的点中，有多少个点到 T 的路径唯一。将原图中所有和 T 相连的边去掉，此时如果一个点是答案，当且仅当该点能够达到的 T 的后继的个数为1，即它自己。所以将去掉边之后的图反向，从原图中每个 T 的后继开始dfs，维护每个点能够到达的 T 的后继的集合。有剪枝：当前点的集合大小大于等于2时，直接退出dfs，可以保证每个点最多被访问两次，使dfs的总复杂度为 O(n)。
L - River Game
每个湿区可以产生若干个观察区，由于每个湿区必与网格左右边界相连，且湿区大小不超过 2n，因此对于 n=10 有观察区的大小 S\le 20。同时由于湿区之间的距离不小于3，所以不同湿区产生的观察区互不影响。对于每一个观察区可视为一个有向图游戏，并且可以在 O(S\cdot 2^S) 的时间复杂度内求出其所有状态的SG函数值。总游戏为若干个观察区的组合游戏，用SG定理解决即可。
Code
A - Environment-Friendly Travel
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#define MAX_T 105
#define MAX_B 105
#define MAX_N 1005
#define INF 0x3f3f3f3f
#define sqr(x) ((double)(x) * (x))
#define int long long
using namespace std;
struct Edge {
int t, w;
Edge() {}
Edge(int _t, int _w) : t(_t), w(_w) {}
};
int xs, ys;
int xd, yd;
int T, B, n;
int C[MAX_T];
int x[MAX_N], y[MAX_N];
int md[MAX_N][MAX_N];
int f[MAX_N][MAX_B];
vector<Edge> e[MAX_N];
int dist(int xa, int ya, int xb, int yb) {
return (int)ceil(sqrt(sqr(xa - xb) + sqr(ya - yb)));
}
void chkmin(int &x, int y) {
x = min(x, y);
}
void add(int x, int y, int m) {
if (!md[x][y]) {
md[x][y] = m;
} else {
if (C[m] < C[md[x][y]]) {
md[x][y] = m;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin >> xs >> ys;
cin >> xd >> yd;
cin >> B;
cin >> C[0];
cin >> T;
for (int i = 1; i <= T; i++) {
cin >> C[i];
}
cin >> n;
for (int i = 0; i < n; i++) {
int t, to, mode;
cin >> x[i] >> y[i] >> t;
for (int j = 1; j <= t; j++) {
cin >> to >> mode;
add(i, to, mode);
add(to, i, mode);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && md[i][j]) {
int d = dist(x[i], y[i], x[j], y[j]);
e[i].push_back(Edge(j, C[md[i][j]]));
}
}
}
memset(f, 0x3f, sizeof(f));
for (int i = 0; i < n; i++) {
int d = dist(xs, ys, x[i], y[i]);
if (d <= B) {
f[i][d] = C[0] * d;
}
}
for (int j = 0; j <= B; j++) {
for (int i = 0; i < n; i++) {
if (f[i][j] < INF) {
for (Edge ed : e[i]) {
int d = dist(x[i], y[i], x[ed.t], y[ed.t]);
if (j + d <= B) {
int cost = ed.w * d;
chkmin(f[ed.t][j + d], f[i][j] + cost);
}
}
}
}
}
int ans = INF;
int nd = dist(xs, ys, xd, yd);
if (nd <= B) {
ans = nd * C[0];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= B; j++) {
if (f[i][j] < INF) {
int d = dist(x[i], y[i], xd, yd);
if (j + d <= B) {
int cost = C[0] * d;
chkmin(ans, f[i][j] + cost);
}
}
}
}
if (ans < INF) {
cout << ans << endl;
} else {
cout << -1 << endl;
}
}
B - Biodiversity
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
int n;
map<string, int> mp;
int main() {
ios::sync_with_stdio(false);
cin >> n;
string s;
for (int i = 1; i <= n; i++) {
cin >> s;
mp[s]++;
}
int mx = 0;
for (auto p : mp) {
if (p.second > mx) {
mx = p.second, s = p.first;
}
}
if (2 * mx > n) {
cout << s << endl;
} else {
cout << "NONE" << endl;
}
}
C - Ants
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int n;
map<int, int> mp;
int getint(string s) {
reverse(s.begin(), s.end());
int sgn = 1;
if (s.back() == '-') {
s.pop_back(), sgn = -1;
}
reverse(s.begin(), s.end());
int ans = 0;
for (int i = 0; i < s.size(); i++) {
ans = ans * 10 + s[i] - '0';
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
if (s.size() <= 8) {
mp[getint(s)]++;
}
}
for (int i = 0;; i++) {
if (!mp[i]) {
cout << i << endl;
break;
}
}
}
D - Gnalcats
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define pii pair<int, int>
using namespace std;
int cnt = 0;
string s[2];
map<pii, int> mpp;
map<int, pii> mpi;
vector<int> vf(1, -1);
vector<int> solve(const string &s, vector<int> v) {
for (char c : s) {
if (c == 'C') {
v.push_back(v.back());
} else if (c == 'D') {
v.pop_back();
} else if (c == 'L') {
int a = v.back();
v.pop_back();
if (mpi.count(a)) {
v.push_back(mpi[a].first);
} else {
return vf;
}
} else if (c == 'P') {
int a = v.back();
v.pop_back();
int b = v.back();
v.pop_back();
if (mpp.count(pii(a, b))) {
v.push_back(mpp[pii(a, b)]);
} else {
mpp[pii(a, b)] = ++cnt;
mpi[cnt] = pii(a, b);
v.push_back(cnt);
}
} else if (c == 'R') {
int a = v.back();
v.pop_back();
if (mpi.count(a)) {
v.push_back(mpi[a].second);
} else {
return vf;
}
} else if (c == 'S') {
int a = v.back();
v.pop_back();
int b = v.back();
v.pop_back();
v.push_back(a);
v.push_back(b);
} else {
int a = v.back();
v.pop_back();
if (mpi.count(a)) {
v.push_back(mpi[a].second);
v.push_back(mpi[a].first);
} else {
return vf;
}
}
}
return v;
}
int main() {
ios::sync_with_stdio(false);
cin >> s[0] >> s[1];
cnt = max(s[0].size(), s[1].size()) + 5;
vector<int> v;
for (int i = cnt; i >= 1; i--) {
v.push_back(i);
}
vector<int> vr[2];
vr[0] = solve(s[0], v);
vr[1] = solve(s[1], v);
if (vr[0].size() != vr[1].size()) {
cout << "False" << endl;
return 0;
}
for (int i = 0; i < vr[0].size(); i++) {
if (vr[0][i] != vr[1][i]) {
cout << "False" << endl;
return 0;
}
}
cout << "True" << endl;
}
E - Pixels
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 320
#define MAX_P 100005
using namespace std;
int n, m;
char s[MAX_P][MAX_N];
int w[3][MAX_N][MAX_N];
int a[MAX_N][MAX_N];
int ans[MAX_P][MAX_N];
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (n >= m) {
cin >> s[i][j];
} else {
cin >> s[j][i];
}
}
}
bool flag = true;
if (n < m) {
swap(n, m), flag = false;
}
for (int j = 1; j <= m; j++) {
w[1][j][j] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m + 1; k++) {
w[(i + 1) % 3][j][k] = w[i % 3][j][k];
if (j - 1 >= 1) w[(i + 1) % 3][j][k] ^= w[i % 3][j - 1][k];
if (j + 1 <= m) w[(i + 1) % 3][j][k] ^= w[i % 3][j + 1][k];
if (i - 1 >= 1) w[(i + 1) % 3][j][k] ^= w[(i + 2) % 3][j][k];
}
w[(i + 1) % 3][j][m + 1] ^= (s[i][j] == 'B');
}
}
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m + 1; k++) {
a[j][k] = w[n % 3][j][k];
if (j - 1 >= 1) a[j][k] ^= w[n % 3][j - 1][k];
if (j + 1 <= m) a[j][k] ^= w[n % 3][j + 1][k];
if (n - 1 >= 1) a[j][k] ^= w[(n + 2) % 3][j][k];
}
a[j][m + 1] ^= (s[n][j] == 'B');
}
for (int i = 1; i <= m; i++) {
if (!a[i][i]) {
int t = -1;
for (int j = i + 1; j <= m; j++) {
if (a[j][i]) {
t = j;
break;
}
}
if (t != -1) {
for (int j = 1; j <= m + 1; j++) {
swap(a[i][j], a[t][j]);
}
} else {
continue;
}
}
for (int k = i + 1; k <= m; k++) {
if (a[k][i]) {
for (int j = 1; j <= m + 1; j++) {
a[k][j] ^= a[i][j];
}
}
}
}
for (int i = m; i >= 1; i--) {
if (a[i][i]) {
ans[1][i] = a[i][m + 1];
for (int k = 1; k < i; k++) {
if (a[k][i]) {
a[k][i] ^= a[i][i];
a[k][m + 1] ^= a[i][m + 1];
}
}
} else {
if (a[i][m + 1]) {
cout << "IMPOSSIBLE" << endl;
return 0;
} else {
ans[1][i] = 0;
}
}
}
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m + 1; k++) {
w[1][j][k] = 0;
}
w[1][j][j] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m + 1; k++) {
w[(i + 1) % 3][j][k] = w[i % 3][j][k];
if (j - 1 >= 1) w[(i + 1) % 3][j][k] ^= w[i % 3][j - 1][k];
if (j + 1 <= m) w[(i + 1) % 3][j][k] ^= w[i % 3][j + 1][k];
if (i - 1 >= 1) w[(i + 1) % 3][j][k] ^= w[(i + 2) % 3][j][k];
}
w[(i + 1) % 3][j][m + 1] ^= (s[i][j] == 'B');
for (int k = 1; k <= m; k++) {
ans[i + 1][j] ^= w[(i + 1) % 3][j][k] * ans[1][k];
}
ans[i + 1][j] ^= w[(i + 1) % 3][j][m + 1];
}
}
if (flag) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (ans[i][j]) {
cout << "P ";
} else {
cout << "A ";
}
}
cout << endl;
}
} else {
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (ans[i][j]) {
cout << "P ";
} else {
cout << "A ";
}
}
cout << endl;
}
}
}
F - Icebergs
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005
#define int long long
using namespace std;
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend bool operator<(const Point &a, const Point &b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
friend int sqr(const Point &p) {
return p.x * p.x + p.y * p.y;
}
friend int dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
friend int cross(const Point &a, const Point &b) {
return a.x * b.y - b.x * a.y;
}
};
int T, n, ans = 0;
Point p[MAX_N];
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y;
}
int res = 0;
for (int i = 2; i < n; i++) {
res += cross(p[i] - p[1], p[i + 1] - p[1]);
}
ans += abs(res);
}
cout << ans / 2 << endl;
}
G - Swapping Places
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define MAX_S 205
#define MAX_N 100005
#define pii pair<int, int>
using namespace std;
int S, L, n;
int a[MAX_N];
int deg[MAX_N];
bool tag[MAX_S][MAX_S];
string s[MAX_S];
map<string, int> mp;
queue<int> q[MAX_S];
vector<int> e[MAX_N];
int main() {
ios::sync_with_stdio(false);
cin >> S >> L >> n;
for (int i = 1; i <= S; i++) {
cin >> s[i];
}
sort(s + 1, s + 1 + S);
for (int i = 1; i <= S; i++) {
mp[s[i]] = i;
}
string sx, sy;
for (int i = 1; i <= L; i++) {
cin >> sx >> sy;
int x = mp[sx], y = mp[sy];
tag[x][y] = tag[y][x] = true;
}
for (int i = 1; i <= n; i++) {
cin >> sx;
a[i] = mp[sx];
}
for (int i = 1; i <= n; i++) {
q[a[i]].push(i);
}
for (int i = 1; i <= n; i++) {
q[a[i]].pop();
for (int j = 1; j <= S; j++) {
if (!tag[a[i]][j] && !q[j].empty()) {
e[i].push_back(q[j].front());
deg[q[j].front()]++;
}
}
}
priority_queue<pii, vector<pii>, greater<pii> > pq;
for (int i = 1; i <= n; i++) {
if (!deg[i]) {
pq.push(pii(a[i], i));
}
}
vector<string> vs;
while (!pq.empty()) {
pii p = pq.top();
pq.pop();
vs.push_back(s[p.first]);
for (int t : e[p.second]) {
deg[t]--;
if (!deg[t]) {
pq.push(pii(a[t], t));
}
}
}
for (string ts : vs) {
cout << ts << " ";
}
cout << endl;
}
H - Pseudo-Random Number Generator
找循环节程序：
#include <iostream>
#include <stdio.h>
#include <string.h>
#define S0 0x600dcafeLL
#define M (1LL << 40)
#define mov(x) ((x) + ((x) >> 20) + 12345) % M
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);
int pt = 0, st = S0;
int ph = 0, sh = S0;
do {
pt++, st = mov(st);
ph++, sh = mov(sh);
ph++, sh = mov(sh);
} while (st != sh);
ph = 0, sh = S0;
do {
pt++, st = mov(st);
ph++, sh = mov(sh);
} while (st != sh);
int L = ph;
do {
ph++, sh = mov(sh);
} while (st != sh);
int R = ph - 1;
cout << L << " " << R << endl;
}
打表程序：
#include <iostream>
#include <stdio.h>
#include <string.h>
#define L 350125310LL
#define R 532254518LL
#define T 5000000LL
#define S0 0x600dcafeLL
#define M (1LL << 40)
#define mov(x) ((x) + ((x) >> 20) + 12345) % M
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);
int sum = 0;
for (int i = 0, s = S0, cnt = !(s & 1); i <= R; i++, s = mov(s), cnt += !(s & 1)) {
if (i % T == 0) {
cout << "{" << s << ", " << cnt << "}, ";
}
if (i == L - 1) {
sum -= cnt;
} else if (i == R) {
sum += cnt;
}
}
cout << endl;
cout << sum << endl;
}
最终程序：
#include <iostream>
#include <stdio.h>
#include <string.h>
#define L 350125310LL
#define R 532254518LL
#define T 5000000LL
#define CNT 91029304LL
#define S0 0x600dcafeLL
#define M (1LL << 40)
#define mov(x) ((x) + ((x) >> 20) + 12345) % M
#define int long long
using namespace std;
const int TABLE[][2] = {{1611516670, 1}, {6995323118, 2500401}, {14370630249, 5004364}, {24473902285, 7500029}, {38312556854, 10006017}, {57274551969, 12506329}, {83248007737, 15011683}, {118826730177, 17517443}, {167560289742, 20012408}, {234323188514, 22530434}, {325792323073, 25031296}, {451094609069, 27539195}, {622741727028, 30040232}, {857898708083, 32538480}, {937685173, 35042602}, {6072677726, 37541450}, {13107744445, 40042828}, {22744003927, 42546233}, {35943646365, 45056959}, {54027907086, 47548216}, {78802032994, 50056831}, {112739509636, 52565704}, {159235062884, 55056278}, {222913708970, 57559660}, {310147760736, 60057168}, {429642460847, 62554179}, {593348380684, 65062411}, {817588294774, 67574933}, {295498034, 70077204}, {5192879414, 72572034}, {11901289737, 75074286}, {21092425584, 77586589}, {33681877906, 80089334}, {50930014590, 82577797}, {74557367833, 85076566}, {106926639410, 87569837}, {151258698876, 90060817}, {211997026857, 92557144}, {295206930517, 95067617}, {409189858068, 97582000}, {565345893787, 100089173}, {779223572048, 102578453}, {1072246754882, 105080524}, {4354683110, 107578420}, {10752858133, 110081437}, {19518274761, 112579315}, {31526697331, 115071718}, {47977804257, 117584728}, {70512631458, 120091493}, {101383583168, 122603663}, {143677078963, 125100277}, {201601781662, 127598938}, {280954761586, 130104566}, {389678281232, 132606644}, {538598461112, 135114812}, {742592321221, 137604957}, {1022070324749, 140110603}, {3554026557, 142613775}, {9655697881, 145118771}, {18014204912, 147616701}, {29466792348, 150119937}, {45154383935, 152614526}, {66642984633, 155117508}, {96085200428, 157608613}, {136417233148, 160106698}, {191671943332, 162605678}, {267368060404, 165108248}, {371063286307, 167605345}, {513107125545, 170101751}, {707668644954, 172599641}, {974225187667, 175085228}, {2790547793, 177572982}, {8611289031, 180074324}, {16584933110, 182564868}, {27507640334, 185067560}, {42470755600, 187569610}, {62966213954, 190070901}, {91040988045, 192573754}, {129505250351, 195073010}, {182194153727, 197571938}, {254367017868, 200067363}, {353236621546, 202571441}, {488691710416, 205056578}, {674235835123, 207563824}, {928397275086, 210056612}, {2061291639, 212555608}, {7611195984, 215046440}, {15215211602, 217558986}, {25631359205, 220055532}, {39898870311, 222551803}, {59446145748, 225059431}, {86223613511, 227563092}, {122903535528, 230050444}, {173156136173, 232565955}, {241996682198, 235069888}, {336303276921, 237573994}, {465478252203, 240074925}, {642434794044, 242579118}, {884883721897, 245073898}, {1367467361, 247575267}, {6660774750, 250065868}, {13913445317, 252566347}, {23846914106, 255061631}, {37457188797, 257561860}, {56101519545, 260064780}, {81642081850, 262557086}, {116629560400, 265048248}};
int n;
signed main() {
ios::sync_with_stdio(false);
cin >> n;
if (!n) {
cout << 0 << endl;
return 0;
}
n--;
int cnt = 0;
if (n >= R) {
cnt += (n - L + 1) / (R - L + 1) * CNT;
n = L - 1 + (n - L + 1) % (R - L + 1);
}
int p = n / T * T, s = TABLE[n / T][0];
cnt += TABLE[n / T][1];
while (p < n) {
p++, s = mov(s), cnt += !(s & 1);
}
cout << cnt << endl;
}
I - Rats
#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long
using namespace std;
int n1, n2, n12;
signed main() {
ios::sync_with_stdio(false);
cin >> n1 >> n2 >> n12;
cout << (n1 + 1) * (n2 + 1) / (n12 + 1) - 1 << endl;
}
J - Counting Trees
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define MAX_N 1000005
#define MOD 1000000007
#define inv(x) (fpow((x), MOD - 2))
#define int long long
using namespace std;
int n;
int a[MAX_N];
int cat[MAX_N];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = ans * x % MOD;
}
x = x * x % MOD, k >>= 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cat[0] = cat[1] = 1;
for (int i = 2; i <= n; i++) {
cat[i] = cat[i - 1] * (4 * i - 2) % MOD * inv(i + 1) % MOD;
}
int ans = 1;
stack<int> s;
a[n + 1] = -1;
for (int i = 1; i <= n + 1; i++) {
int cur = -1, cnt = 0;
while (!s.empty() && s.top() > a[i]) {
if (s.top() != cur) {
ans = (ans * cat[cnt]) % MOD;
cur = s.top(), cnt = 1;
} else {
cnt++;
}
s.pop();
}
if (cnt) {
ans = (ans * cat[cnt]) % MOD;
}
s.push(a[i]);
}
cout << ans << endl;
}
K - Birdwatching
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#define MAX_N 100005
using namespace std;
int n, m, K;
vector<int> e[MAX_N];
set<int> st[MAX_N];
void dfs(int x, int r) {
if (st[x].count(r) || st[x].size() >= 2) {
return;
}
st[x].insert(r);
for (int t : e[x]) {
if (t != K) {
dfs(t, r);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> K;
int x, y;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
e[y].push_back(x);
}
for (int t : e[K]) {
dfs(t, t);
}
vector<int> v;
for (int t : e[K]) {
if (st[t].size() == 1) {
v.push_back(t);
}
}
sort(v.begin(), v.end());
cout << v.size() << endl;
for (int t : v) {
cout << t << endl;
}
}
L - River Game
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 15
#define MAX_B 105
#define MAX_S 2000005
#define pii pair<int, int>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int n, cntz = 0, cnts = 0;
int sg[MAX_S];
int id[MAX_N][MAX_N];
bool flag[MAX_S];
bool vis[MAX_N][MAX_N];
char s[MAX_N][MAX_N];
vector<pii> vz[MAX_B];
vector<pii> vs[MAX_B];
bool ok(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= n;
}
void dfs1(int x, int y) {
vis[x][y] = true;
vz[cntz].push_back(pii(x, y));
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (ok(nx, ny) && !vis[nx][ny] && s[nx][ny] == '*') {
dfs1(nx, ny);
}
}
}
void extend(vector<pii> &v, int x) {
for (pii p : v) {
for (int i = 0; i < 4; i++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if (ok(nx, ny) && s[nx][ny] == '.') {
id[nx][ny] = x;
}
}
}
}
void dfs2(int x, int y) {
vis[x][y] = true;
vs[cnts].push_back(pii(x, y));
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (ok(nx, ny) && !vis[nx][ny] && id[nx][ny] == id[x][y]) {
dfs2(nx, ny);
}
}
}
bool check(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (ok(nx, ny) && vis[nx][ny]) {
return false;
}
}
return true;
}
int solve(vector<pii> &v) {
memset(vis, false, sizeof(vis));
int N = v.size();
for (int s = (1 << N) - 1; s >= 0; s--) {
for (pii p : v) {
vis[p.first][p.second] = false;
}
for (int i = 0; i < N; i++) {
if ((s >> i) & 1) {
vis[v[i].first][v[i].second] = true;
}
}
vector<int> vn;
for (int i = 0; i < N; i++) {
if (!((s >> i) & 1) && check(v[i].first, v[i].second)) {
int nxt = s | (1 << i);
flag[sg[nxt]] = true;
vn.push_back(nxt);
}
}
for (int i = 0;; i++) {
if (!flag[i]) {
sg[s] = i;
break;
}
}
for (int nxt : vn) {
flag[sg[nxt]] = false;
}
}
return sg[0];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!vis[i][j] && s[i][j] == '*') {
cntz++;
dfs1(i, j);
}
}
}
for (int i = 1; i <= cntz; i++) {
extend(vz[i], i);
}
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!vis[i][j] && id[i][j]) {
cnts++;
dfs2(i, j);
}
}
}
int sum = 0;
for (int i = 1; i <= cnts; i++) {
sum ^= solve(vs[i]);
}
if (sum) {
cout << "First player will win" << endl;
} else {
cout << "Second player will win" << endl;
}
}