2016 ACMICPC Asia Regional Dalian Online

太懒，强迫自己一波。MDZZ A 题意：有 N 个人，可以选择任意数目的人来参与游戏。 游戏规则要求选出来的人围成一个圆且任意两个人到圆心的连线夹角必须是 2∗πN的倍数且不能是 2∗πN ，而且通过旋转得到的方案认为是相同的。

我们把 N 个人当做N个点，这样第 i 个点坐人的话记为黑点，反之记为白点。 问题就变成−>给定环上 N 个点，黑白染色，要求黑点不能相邻，问你旋转同构的方案数。

记f[i]： i 个点黑白染色，不考虑旋转同构的方案数。 这样poyla定理： N 个点旋转同构的方案数ans=∑Ni=1f[gcd(i,N)]，用欧拉函数处理一下就 OK 了。

一开始推出公式 f[i]=f[i−1]+f[i−3] ，然后莫名 GG ？后来发现公式 f[i]=f[i−1]+f[i−2] 可以对上数据， why ？ 不管了，过了再说。。。但是 1 的时候输出2？不懂出题人

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<int, int> pii; const int MAXN = 2e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } LL euler(int n) { LL ans = n; for(int i = 2; i * i <= n; i++) { if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } } if(n > 1) ans = ans / n * (n - 1); return ans; } struct Matrix { LL a[2][2]; }; Matrix multi(Matrix x, Matrix y) { Matrix z; CLR(z.a, 0); for(int i = 0; i < 2; i++) { for(int k = 0; k < 2; k++) { if(x.a[i][k] == 0) continue; for(int j = 0; j < 2; j++) { z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % MOD) % MOD; } } } return z; } Matrix Pow(Matrix x, int n) { Matrix ans; for(int i = 0; i < 2; i++) { for(int j = 0; j < 2; j++) { if(i == j) { ans.a[i][j] = 1; } else { ans.a[i][j] = 0; } } } while(n) { if(n & 1) { ans = multi(ans, x); } x = multi(x, x); n >>= 1; } return ans; } LL Work(int n) { if(n == 1) return 1; if(n == 2) return 3; Matrix x; x.a[0][0] = 1; x.a[0][1] = 1; x.a[1][0] = 1; x.a[1][1] = 0; Matrix y = Pow(x, n - 2); return (1LL * 3 * y.a[0][0] % MOD + 1LL * 1 * y.a[1][0] % MOD) % MOD; } LL pow_mod(LL a, int n) { LL ans = 1; while(n) { if(n & 1) { ans = ans * a % MOD; } n >>= 1; a = a * a % MOD; } return ans; } int main() { // for(int i = 1; i <= 8; i++) { // cout << Work(i) << endl; // } int n; while(scanf("%d", &n) != EOF) { if(n == 1) { printf("2\n"); continue; } LL ans = 0; for(int i = 1; i * i <= n; i++) { if(n % i == 0) { add(ans, Work(i) * euler(n / i) % MOD); if(i * i != n) { add(ans, Work(n / i) * euler(i) % MOD); } } } printf("%lld\n", ans * pow_mod(n, MOD - 2) % MOD); } return 0; }

B 题意：求解区间不同 GCD 数目。 思路：枚举右端点，二分找到连续区间 GCD 的最右区间端点。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<int, int> pii; const int MAXN = 1e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } int g[MAXN][21], a[MAXN]; map<int, int> lp; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } void RMQ_init(int N) { for(int i = 1; i <= N; i++) { g[i][0] = a[i]; } for(int j = 1; (1 << j) <= N; j++) { for(int i = 1; i + (1 << j) - 1 <= N; i++) { g[i][j] = gcd(g[i][j-1], g[i + (1 << (j-1))][j-1]); } } } int Query(int L, int R) { int k = 0; while((1 << (k + 1)) <= R - L + 1) k++; return gcd(g[L][k], g[R - (1 << k) + 1][k]); } struct Node { int l, r, id; }; Node num[MAXN]; bool cmp1(Node a, Node b) { return a.r < b.r; } LL ans[MAXN]; LL C[MAXN]; int lowbit(int x) { return x & (-x); } int n; void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } LL Sum(int x) { LL s = 0; while(x > 0) { s += C[x]; x -= lowbit(x); } return s; } struct GCD { int l, r, val; }; GCD gnum[MAXN * 30]; bool cmp2(GCD a, GCD b) { return a.r < b.r; } int main() { int m; while(scanf("%d%d", &n, &m) != EOF) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } RMQ_init(n); int top = 0; for(int i = 1; i <= n; i++) { int j = i; while(j >= 1) { int v = Query(j, i); int l = 1, r = j, next; gnum[top].l = j; gnum[top].r = i; gnum[top].val = v; //cout << gnum[top].l << ' ' << gnum[top].r << ' ' << gnum[top].val << endl; top++; while(r >= l) { int mid = (l + r) >> 1; if(Query(mid, i) == v) { next = mid; r = mid - 1; } else { l = mid + 1; } } j = next - 1; } } for(int i = 1; i <= m; i++) { scanf("%d%d", &num[i].l, &num[i].r); num[i].id = i; } sort(num + 1, num + m + 1, cmp1); sort(gnum, gnum + top, cmp2); int j = 0; CLR(C, 0); lp.clear(); for(int i = 1; i <= m; i++) { while(j < top && gnum[j].r <= num[i].r) { int v = gnum[j].val; if(lp[v]) { add(lp[v], -1); } lp[v] = gnum[j].l; add(lp[v], 1); j++; } ans[num[i].id] = Sum(num[i].r) - Sum(num[i].l - 1); } for(int i = 1; i <= m; i++) { printf("%lld\n", ans[i]); } } return 0; }

F

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<int, int> pii; const int MAXN = 1e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } int a[20000 + 10]; int main() { int t; while(scanf("%d", &t) != EOF) { while(t--) { int n; scanf("%d", &n); int sum = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum += a[i]; } if(sum != n * (n - 1)) { printf("F\n"); continue; } sort(a + 1, a + n + 1); sum = 0; int s = 0; bool flag = true; for(int i = n; i >= 1; i--) { s += a[i]; sum += 2 * (i - 1); if(s > sum) { flag = false; break; } } printf(flag ? "T\n" : "F\n"); } } return 0; }

G

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef unsigned long long LL; typedef pair<int, int> pii; const int MAXN = 2e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } int main() { LL n, m; while(scanf("%llu%llu", &m, &n) != EOF) { LL sum = floor(m * m * 1.0 / 4); printf(n >= sum ? "T\n" : "F\n"); } return 0; }

H 思路：二分套个 RMQ 找到最小的 j 满足a[j]<a[i]。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<int, int> pii; const int MAXN = 1e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } int a[MAXN]; int Amin[MAXN][20]; void RMQ_init(int N) { for(int i = 1; i <= N; i++) Amin[i][0] = a[i]; for(int j = 1; (1<<j) <= N; j++) { for(int i = 1; i + (1<<j)-1 <= N; i++) Amin[i][j] = min(Amin[i][j-1], Amin[i+(1<<(j-1))][j-1]); } } int Query(int L, int R) { int k = 0; while((1<<(k+1)) <= R-L+1) k++; return min(Amin[L][k], Amin[R-(1<<k)+1][k]); } int Next[MAXN]; int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } RMQ_init(n); for(int i = 1; i <= n; i++) { int l = i + 1, r = n, pos = -1; while(r >= l) { int mid = l + r >> 1; if(Query(l, mid) < a[i]) { pos = mid; r = mid - 1; } else { l = mid + 1; } } Next[i] = pos; } int m; scanf("%d", &m); while(m--) { int l, r; scanf("%d%d", &l, &r); int ans = a[l]; int pos = l; for(;;) { pos = Next[pos]; if(pos > r || pos == -1) break; ans %= a[pos]; } printf("%d\n", ans); } } return 0; }

I 题意：求解补图最短路。 前面到达的点后面就没有用了，那就维护两个集合，一个当前点可以到达且没有被用过，一个当前点不可以到达且没有被用过。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<int, int> pii; const int MAXN = 2e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } vector<int> G[MAXN]; int d[MAXN]; set<int> use, have; set<int> :: iterator it; int n; int ans[MAXN]; void Solve(int s) { queue<int> Q; Q.push(s); CLR(d, INF); d[s] = 0; have.clear(); use.clear(); for(int i = 1; i <= n; i++) { if(i != s) { have.insert(i); } } while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!have.count(v)) continue; have.erase(v); use.insert(v); } for(it = have.begin(); it != have.end(); ++it) { Q.push(*it); d[*it] = d[u] + 1; } have.swap(use); use.clear(); } } int main() { int t; scanf("%d", &t); while(t--) { int m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) G[i].clear(); while(m--) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } int s; scanf("%d", &s); Solve(s); int top = 0; for(int i = 1; i <= n; i++) { if(i == s) continue; ans[top++] = (d[i] != INF ? d[i] : -1); } for(int i = 0; i < top; i++) { if(i > 0) printf(" "); printf("%d", ans[i]); } printf("\n"); } return 0; }

J 思路：我们处理出 DFS 序，然后对于第 i 个点找到孩子区间有多少个合法a[j]即 a[j]<=h=k/a[i] 。 N 次查询，我们离线做，在对应的h值限制下插入合法的解，然后用树状数组去统计，是可以做到 O(nlog(n)) 的。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #include <set> #include <cstdlib> #define ll o<<1 #define rr o<<1|1 #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair<LL, LL> pii; const int MAXN = 1e5 + 10; const int INF = 1e9 + 10; const double PI = acos(-1.0); const double eps = 1e-6; const int MOD = 1e9 + 7; void add(LL &x, LL y) { x += y; x %= MOD; } struct Edge { int from, to, next; }; Edge edge[MAXN * 2]; int head[MAXN], edgenum; void init() {CLR(head, -1); edgenum = 0;} void addEdge(int u, int v) { Edge E = {u, v, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } LL vs[MAXN]; int top; int son[MAXN]; LL a[MAXN]; int id[MAXN]; void DFS(int u, int fa) { son[u] = 1; id[u] = ++top; vs[top] = a[u]; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == fa) continue; DFS(v, u); son[u] += son[v]; } } int C[MAXN], n; int lowbit(int x) { return x & (-x); } void Update(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } int Sum(int x) { int s = 0; while(x > 0) { s += C[x]; x -= lowbit(x); } return s; } struct Node{ int l, r; LL h; }; Node num[MAXN]; bool cmp2(Node a, Node b){ return a.h < b.h; } int in[MAXN]; vector<pii> G; vector<pii> :: iterator it; bool cmp1(pii a, pii b){ return a.first < b.first; } int main() { int t, kcase = 1; scanf("%d", &t); while(t--) { LL k; scanf("%d%lld", &n, &k); init(); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); in[i] = 0; } for(int i = 0; i < n - 1; i++) { int u, v; scanf("%d%d", &u, &v); addEdge(u, v); in[v]++; } int root; for(int i = 1; i <= n; i++) { if(in[i] == 0) { root = i; break; } } top = 0; DFS(root, -1); G.clear(); for(int i = 1; i <= top; i++) { G.push_back(pii(vs[i], i)); } sort(G.begin(), G.end(), cmp1); for(int i = 1; i <= n; i++) { num[i].l = id[i]; num[i].r = id[i] + son[i] - 1; num[i].h = k / a[i]; } sort(num + 1, num + n + 1, cmp2); LL ans = 0; CLR(C, 0); it = G.begin(); for(int i = 1; i <= n; i++) { while(it != G.end() && it->first <= num[i].h) { Update(it->second, 1); it++; } ans += Sum(num[i].r) - Sum(num[i].l - 1); } for(int i = 1; i <= n; i++) { if(a[i] * a[i] <= k) { ans--; } } printf("%lld\n", ans); } return 0; }