A - Azshara's deep sea
咕
B - Blow up the city
DAG上的支配树板题。建立超级点 S，将所有指挥城市向 S 连一条边，则原题转化成了：从 S 出发，有多少个点为到达 a 或 b 的必经点（除 S 之外）。以 S 为根并根据反向图建立支配树，对于询问 a,b，答案即为 \mathrm{dep}[a]+\mathrm{dep}[b]-\mathrm{dep}[\mathrm{lca}(a,b)]。总复杂度 O(n\log n)。
C - Yukikaze and Demons
咕
D - Distribution of books
咕
E - Easy Math Problem
咕
F - Fansblog
签到题。首先由于素数密度为 \frac{1}{\log n}，所以暴力找小于 p 的第一个素数 q，复杂度 O(\log n\cdot\sqrt{n})。然后由威尔逊定理（当且仅当 p 为素数时，有 (p-1)!\equiv -1\pmod{p}），可得答案为 (p-q-1)!^{-1}，由于差值为 \log n 级别，暴力计算即可。
G - Find the answer
对于前 i 个元素，显然要选最大的若干个置0，所以离散化后建权值线段树，同时维护 \mathrm{sum} 和 \mathrm{cnt}，在线段树上二分即可。
H - Game
咕
I - K Subsequence
咕
J - Sindar's Art Exhibition
咕
K - Squrirrel
咕
Code
A - Azshara's deep sea
B - Blow up the city
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 100005
#define MAX_L 25
using namespace std;
int T, n, m, Q;
int deg[MAX_N];
int dep[MAX_N];
int par[MAX_N][MAX_L];
vector<int> e[MAX_N];
vector<int> re[MAX_N];
void ins(int x, int p) {
par[x][0] = p, dep[x] = dep[p] + 1;
for (int i = 1; i < MAX_L; i++) {
par[x][i] = par[par[x][i - 1]][i - 1];
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) {
swap(a, b);
}
for (int d = dep[a] - dep[b], i = 0; d; d >>= 1, i++) {
if (d & 1) {
a = par[a][i];
}
}
if (a == b) {
return a;
}
for (int i = MAX_L - 1; i >= 0; i--) {
if (par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n + 1; i++) {
deg[i] = dep[i] = 0;
e[i].clear(), re[i].clear();
for (int j = 0; j < MAX_L; j++) {
par[i][j] = 0;
}
}
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
e[x].push_back(y);
re[y].push_back(x);
deg[x]++;
}
for (int i = 1; i <= n; i++) {
if (!e[i].size()) {
e[i].push_back(n + 1);
re[n + 1].push_back(i);
deg[i]++;
}
}
queue<int> q;
q.push(n + 1);
while (!q.empty()) {
x = q.front(), q.pop();
if (e[x].size()) {
int anc = e[x][0];
for (int i = 1; i < e[x].size(); i++) {
anc = lca(anc, e[x][i]);
}
ins(x, anc);
}
for (int i = 0; i < re[x].size(); i++) {
int t = re[x][i];
deg[t]--;
if (!deg[t]) {
q.push(t);
}
}
}
scanf("%d", &Q);
int a, b;
while (Q--) {
scanf("%d%d", &a, &b);
int t = lca(a, b);
printf("%d\n", dep[a] + dep[b] - dep[t]);
}
}
}
C - Yukikaze and Demons
D - Distribution of books
E - Easy Math Problem
F - Fansblog
#include <iostream>
#include <stdio.h>
#include <string.h>
#define int __int128_t
#define LL long long
using namespace std;
int T, p;
bool check(int x) {
for (int i = 2; i * i <= x; i++) {
if (!(x % i)) {
return false;
}
}
return true;
}
int fpow(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1) {
ans = ans * x % p;
}
x = x * x % p, k >>= 1;
}
return ans;
}
LL read() {
LL x;
scanf("%lld", &x);
return x;
}
signed main() {
T = read();
while (T--) {
p = read();
int q = p - 2;
while (!check(q)) {
q -= 2;
}
int ans = 1;
for (int i = 2; i <= p - q - 1; i++) {
ans = ans * i % p;
}
printf("%lld\n", (long long)fpow(ans, p - 2, p));
}
}
G - Find the answer
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#define MAX_N 200005
#define MAX_T 1600005
#define int long long
using namespace std;
int T, n, m, rt, tot;
int a[MAX_N];
int L[MAX_T];
int R[MAX_T];
int sum[MAX_T];
int cnt[MAX_T];
vector<int> v;
int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void pushup(int k) {
sum[k] = sum[L[k]] + sum[R[k]];
cnt[k] = cnt[L[k]] + cnt[R[k]];
}
void upd(int pos, int &k, int l, int r, int x) {
if (!k) {
k = ++tot;
}
if (l == r) {
sum[k] += x, cnt[k]++;
return;
}
int md = (l + r) >> 1;
if (pos <= md) {
upd(pos, L[k], l, md, x);
} else {
upd(pos, R[k], md + 1, r, x);
}
pushup(k);
}
int ask(int k, int l, int r, int s) {
if (l == r) {
return l;
}
int md = (l + r) >> 1;
int ls = sum[L[k]];
if (ls >= s) {
return ask(L[k], l, md, s);
} else {
return ask(R[k], md + 1, r, s - ls);
}
}
int getcnt(int a, int b, int k, int l, int r) {
if (a <= l && r <= b) {
return cnt[k];
}
int md = (l + r) >> 1, ans = 0;
if (a <= md) {
ans += getcnt(a, b, L[k], l, md);
}
if (b > md) {
ans += getcnt(a, b, R[k], md + 1, r);
}
return ans;
}
int getsum(int a, int b, int k, int l, int r) {
if (a <= l && r <= b) {
return sum[k];
}
int md = (l + r) >> 1, ans = 0;
if (a <= md) {
ans += getsum(a, b, L[k], l, md);
}
if (b > md) {
ans += getsum(a, b, R[k], md + 1, r);
}
return ans;
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld", &n, &m);
v.clear();
for (int i = 1; i <= n; i++) {
scanf("%lld", a + i);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int N = v.size();
for (int i = 0; i <= tot; i++) {
L[i] = R[i] = sum[i] = cnt[i] = 0;
}
tot = rt = 0;
map<int, int> mp;
for (int i = 1; i <= n; i++) {
int x = ask(rt, 1, N, m - a[i]);
int s = getsum(1, x, rt, 1, N);
int c = getcnt(1, x, rt, 1, N);
int ts = getsum(x, x, rt, 1, N);
int tc = getcnt(x, x, rt, 1, N);
s -= ts, c -= tc;
int dc, dt = m - a[i] - s;
if (dt > 0) {
dc = min(tc, dt / v[x - 1]);
c += dc, s += dc * v[x - 1];
}
auto it = mp.upper_bound(v[x - 1]);
if (it != mp.end()) {
dt = m - a[i] - s;
if (dt > 0) {
dc = min(it->second, dt / it->first);
c += dc;
}
}
printf("%lld ", i - 1 - c);
upd(getid(a[i]), rt, 1, N, a[i]);
}
printf("\n");
}
}
H - Game
I - K Subsequence
J - Sindar's Art Exhibition
K - Squrirrel
你好，请问一下你有2019-2020 XX Opencup GP of Tokyo 这个练习题的答案么？