voidaddEdge(int u, int v){ N[u].e = new (_curr++) Edge(&N[u], &N[v]); N[v].e = new (_curr++) Edge(&N[v], &N[u]); }
intmin; Node *minV;
voiddfs(Node *u){ u->vis = true; if (!minV || u->w < min) { min = u->w; minV = u; }
for (Edge *e = u->e; e; e = e->next) if (!e->v->vis) dfs(e->v); }
voidclear(int n){ _curr = _pool; for (int i = 0; i < n; i++) { N[i].e = NULL; N[i].used = false; N[i].vis = false; } }
intmain(){ int n, m; while (scanf("%d %d", &n, &m) == 2) { clear(n);
for (int i = 0; i < n; i++) scanf("%d", &N[i].w);
for (int i = 0, u, v; i < m; i++) { scanf("%d %d", &u, &v); addEdge(u, v); }
int need = n - m - 1; if (n / 2 < need) { puts("Impossible"); continue; } elseif (need == 0) { puts("0"); continue; } else { longlong ans = 0; for (int i = 0; i < n; i++) if (!N[i].vis) { minV = NULL; dfs(&N[i]); ans += min; minV->used = true; }
--need; staticstd::vector<int> vec; vec.clear(); for (int i = 0; i < n; i++) if (!N[i].used) vec.push_back(N[i].w); std::sort(vec.begin(), vec.end());
voidaddEdge(int u, int v, int cap){ N[u].e = new (_curr++) Edge(&N[u], &N[v], cap); N[v].e = new (_curr++) Edge(&N[v], &N[u], 0); N[u].e->rev = N[v].e; N[v].e->rev = N[u].e; }
namespace Dinic { boollevel(Node *s, Node *t, int n){ for (int i = 0; i < n; i++) N[i].level = 0;
staticstd::queue<Node *> q; while (!q.empty()) q.pop(); q.push(s); s->level = 1;
while (!q.empty()) { Node *u = q.front(); q.pop();
for (Edge *e = u->e; e; e = e->next) if (e->cap > e->flow && !e->v->level) { e->v->level = u->level + 1; if (e->v == t) returntrue; q.push(e->v); } }
returnfalse; }
intfindPath(Node *u, Node *t, int limit = INT_MAX){ if (u == t) return limit;
for (Edge *&e = u->curr; e; e = e->next) if (e->cap > e->flow && e->v->level == u->level + 1) { int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow)); if (flow > 0) { e->flow += flow; e->rev->flow -= flow; return flow; } }
return0; }
intsolve(int s, int t, int n){ int res = 0; while (level(&N[s], &N[t], n)) { for (int i = 0; i < n; i++) N[i].curr = N[i].e; int flow; while ((flow = findPath(&N[s], &N[t])) > 0) res += flow; } return res; } } // namespace Dinic
voidbfs(int s, int t){ staticstd::queue<Node *> q;
int s = 0, t = odd + even + 1; n = odd + even + 2; clear(n);
for (int i = 1; i <= odd; i++) addEdge(s, i, 1); for (int i = 1; i <= even; i++) addEdge(i + odd, t, 1); for (int i = 1; i <= odd; i++) for (int j = 1; j <= even; j++) if (isPrime(w[1][i] + w[0][j])) addEdge(i, j + odd, 1);
Dinic::solve(s, t, n);
bfs(s, t);
bool flag = false; for (int i = 1; i <= odd; i++) if (N[i].canS && isPrime(w[1][i])) { flag = true; break; } for (int i = 1; i <= even; i++) if (N[i + odd].canT && isPrime(w[0][i])) { flag = true; break; }
int left = -1, right = -1; for (int i = 1; i <= n; i++) if (a[i] == 1) { left = i - 1; break; } if (left == -1) left = n; for (int i = n; i; i--) if (a[i] == 1) { right = i + 1; break; } if (right == -1) right = 1;
int lc = left, rc = n - right + 1, S; if (lc < rc) S = pre[left + 1]; else S = sum[right - 1]; int ans = sor[std::min(S, k)]; for (int i = 1; i <= std::min(lc, rc); i++) { if (S + 2 * i <= k) ans ^= (S + 2 * i); elsebreak; }
printf("%d\n", ans); } return0; }
Contest 9 - A - LYK and Heltion’s gifts
题目大意
用两种颜色染一个有 n 个珠子的首饰,要求不能有相邻的黑色珠子,求可能的染色方案数,旋转相同视为同一种,答案对 1,000,000,007 取模。
f[1] = 1; f[2] = 3; f[3] = 4; for (int i = 4; i < MAXN; i++) { f[i] = f[i - 1] + f[i - 2]; f[i] >= MOD ? f[i] -= MOD : 0; }
inv[1] = 1; for (int i = 2; i < MAXN; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; }
longlongcalc(int n){ int x = n; longlong res = f[n] + phi[n] * f[1] % MOD; res >= MOD ? res -= MOD : 0; for (int i = 2; i <= n / 2; i++) if (n % i == 0) { int t = phi[n / i]; res += f[i] * t % MOD; res >= MOD ? res -= MOD : 0; } res = res * inv[n] % MOD; return res; }
intmain(){ pre();
int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); longlong ans = calc(n); printf("%lld\n", ans); } return0; }
Contest 9 - H - LYK and Painting
题目大意
长为 N 的序列上,每次可以让一段长为 K 的子区间染成同一种颜色(可覆盖),一共有 M 种颜色。最终使得每个位置上都有颜色,求能得到的最终序列的种数,答案对 1,000,000,007 取模。
1≤N≤231−1
1≤M≤100,000
1≤K≤100
1≤T≤10,大测试点不超过 3 个。
时间限制:2s,内存限制:512MB。
题解
最终的序列中,必有一段长度至少为 K 的子区间上颜色相同。由于 N 太大,我们可以考虑用 MN 减去不存在这样子区间的种数。记 f(n) 为长为 n 的、不存在这样子区间的种数,则转移为:
Matrix(int n, int m, bool eye = false) : n(n), m(m) { for (int i = 0; i < n; i++) std::fill(a[i], a[i] + m, 0); if (eye) for (int i = 0; i < n; i++) a[i][i] = 1; }