A
同联盟的朋友连一条权值为$0$的边，不同联盟的朋友连一条权值为$1$的边，即可以把每一次换联盟看成走一条权值为1的边。那么以每一个人为起点的话终点就是这个人到其他所有人中最短路的最大值。求这些最大值的最小值即可。
#include <bits/stdc++.h> using namespace std; const int N = 110; const int INF = 0x3f3f3f3f; int mp[N][N], col[N], n, m; void floyd() { int ans = INF; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]); for (int i = 1; i <= n; i++) { int temp = 0; for (int j = 1; j <= n; j++) temp = max(temp, mp[i][j]); ans = min(ans, temp); } printf("%d\n", ans); } int main() { while (~scanf("%d%d", &n, &m), n + m) { memset(mp, 0x3f, sizeof(mp)); for (int i = 1; i <= n; i++) { scanf("%d", &col[i]); mp[i][i] = 0; } while (m--) { int u, v; scanf("%d%d", &u, &v); if (col[u] == col[v]) mp[u][v] = 0; else mp[u][v] = 1; mp[v][u] = mp[u][v]; } floyd(); } return 0; }
C
思路应该很清晰，两个点即当前到串的位置作为状态，分别枚举两个点的后继形成的字符是否等于串的当前字符。但是很不幸，直接dfs T了。原因就是刚开始这两个点在shift位置，第一个点往下一个点走，下一个点又走回shift，无限递归。
所以把状态记录下来。bfs或dfs都行。
#include <bits/stdc++.h> using namespace std; const int N = 110; const char *str1 = " qwertyuiopasdfghjkl;zxcvbnm,./## ##"; const char *str2 = " QWERTYUIOPASDFGHJKL:ZXCVBNM<>?## ##"; const int dir[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; char s[N]; vector<int> mp[N]; int n; bool dp[N][42][42]; struct Node { int cur, pos1, pos2; }; int main() { for (int i = 1; i <= 40; i++) { int x = i / 10, y = i % 10; if (!y) y = 10; else x++; for (int j = 0; j < 8; j++) { int dx = x + dir[j][0], dy = y + dir[j][1]; if (dx <= 0 || dx > 4 || dy <= 0 || dy > 10) continue; int temp = (dx - 1) * 10 + dy; mp[i].push_back(temp); } } while (gets(s + 1), s[1] != ‘*‘) { n = strlen(s + 1); bool ans = 0; memset(dp, 0, sizeof dp); dp[0][31][40] = 1; queue<Node> que; que.push((Node){0, 31, 40}); while (!que.empty()) { Node p = que.front(); que.pop(); int pos1 = p.pos1, pos2 = p.pos2, cur = p.cur; if (cur == n) { ans = 1; break; } for (auto x: mp[pos1]) { if (x == pos2) continue; if (str1[pos2] == ‘#‘) { if (str2[x] == s[cur + 1]) { if (!dp[cur + 1][x][pos2]) que.push((Node){cur + 1, x, pos2}); dp[cur + 1][x][pos2] = 1; } else if (str2[x] == ‘#‘) { if (!dp[cur][x][pos2]) que.push((Node){cur, x, pos2}); dp[cur][x][pos2] = 1; } } else { if (str1[x] == s[cur + 1]) { if (!dp[cur + 1][x][pos2]) que.push((Node){cur + 1, x, pos2}); dp[cur + 1][x][pos2] = 1; } else if (str1[x] == ‘#‘) { if (!dp[cur][x][pos2]) que.push((Node){cur, x, pos2}); dp[cur][x][pos2] = 1; } } } for (auto x: mp[pos2]) { if (x == pos1) continue; if (str1[pos1] == ‘#‘) { if (str2[x] == s[cur + 1]) { if (!dp[cur + 1][pos1][x]) que.push((Node){cur + 1, pos1, x}); dp[cur + 1][pos1][x] = 1; } else if (str2[x] == ‘#‘) { if (!dp[cur][pos1][x]) que.push((Node){cur, pos1, x}); dp[cur][pos1][x] = 1; } } else { if (str1[x] == s[cur + 1]) { if (!dp[cur + 1][pos1][x]) que.push((Node){cur + 1, pos1, x}); dp[cur + 1][pos1][x] = 1; } else if (str1[x] == ‘#‘) { if (!dp[cur][pos1][x]) que.push((Node){cur, pos1, x}); dp[cur][pos1][x] = 1; } } } } if (ans) puts("1"); else puts("0"); } return 0; }
D
画一下函数图像，发现最大值最小值在凸壳上。那么最大值和最小值的差值必定是一个单峰函数，那么可以三分。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; double k[N], b[N]; int n; double check(double mid) { double mx = -1e30, mn = 1e30; for (int i = 1; i <= n; i++) { mx = max(mx, mid * k[i] + b[i]); mn = min(mn, mid * k[i] + b[i]); } return mx - mn; } int main() { while (~scanf("%d", &n), n) { for (int i = 1; i <= n; i++) scanf("%lf%lf", &b[i], &k[i]); double l = 0, r = 1e15; for (int cnt = 0; cnt < 200; cnt++) { double ll = l + (r - l) / 3.0, rr = r - (r - l) / 3.0; if (check(ll) > check(rr)) l = ll; else r = rr; } printf("%.3f\n", check(l)); } return 0; }
F
用一个节点表示一个长度为$K$的区间(向右延伸)。维护每一个数与其不互质的前趋和后继。如果两个数的间隔小于$K$则会使一定数量的区间不合法，再转化一下，求区间中所有满足条件的区间个数，假设为$cnt$，那么答案就是$n-k+1-cnt$。
假设$(x,y)$为两个下标不合法，那么对线段树上的区间$(y - k + 1, x)$加1，那么所有合法的区间就是线段树上对应节点值为$0$的个数，因为这个值不会小于$0$，那么线段树维护最小值和最小值的个数即可。
然后维护每个数的前趋后继就用set维护每一个质数出现的下标，因为值的范围也小于$10^5$,那么每次操作需遍历的质数不超过$O(logn)$个，所以时间复杂度为$O(nlognloglogn)$
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; struct Seg { #define lp p << 1 #define rp p << 1 | 1 int mn[N << 2], cnt[N << 2], lazy[N << 2]; inline void pushup(int p) { mn[p] = min(mn[lp], mn[rp]); cnt[p] = 0; if (mn[p] == mn[lp]) cnt[p] += cnt[lp]; if (mn[p] == mn[rp]) cnt[p] += cnt[rp]; } inline void tag(int p, int v) { lazy[p] += v; mn[p] += v; } inline void pushdown(int p) { if (lazy[p]) { tag(lp, lazy[p]); tag(rp, lazy[p]); lazy[p] = 0; } } void build(int p, int l, int r) { lazy[p] = mn[p] = 0; if (l == r) { cnt[p] = 1; return; } int mid = l + r >> 1; build(lp, l, mid); build(rp, mid + 1, r); pushup(p); } void update(int p, int l, int r, int x, int y, int val) { if (x > y) return; if (x <= l && y >= r) { tag(p, val); return; } int mid = l + r >> 1; pushdown(p); if (x <= mid) update(lp, l, mid, x, y, val); if (y > mid) update(rp, mid + 1, r, x, y, val); pushup(p); } } seg; set<int> st[N]; vector<int> has[N]; bool vis[N]; int n, k, m, a[N], all; void change(int x, int y, int p) { int l = y - k + 1, r = x; seg.update(1, 1, all, l, r, p); } void ins(int index, int pos) { st[index].insert(pos); auto p = st[index].find(pos); auto q = p; p--; q++; if (*p && *q < N) change(*p, *q, -1); if (*p) change(*p, pos, 1); if (*q < N) change(pos, *q, 1); } void add(int pos, int val) { for (auto x: has[val]) ins(x, pos); } void del(int index, int pos) { auto p = st[index].find(pos); auto q = p; p--; q++; if (*p && *q < N) change(*p, *q, 1); if (*p) change(*p, pos, -1); if (*q < N) change(pos, *q, -1); st[index].erase(pos); } void dec(int pos, int val) { for (auto x: has[val]) del(x, pos); } inline int query() { if (seg.mn[1] > 0) return all; return all - seg.cnt[1]; } int main() { for (int i = 2; i < N; i++) if (!vis[i]) for (int j = i; j < N; j += i) { vis[j] = 1; has[j].push_back(i); } while (~scanf("%d%d%d", &n, &k, &m), n + k + m) { all = n - k + 1; for (int i = 1; i < N; i++) { st[i].clear(); st[i].insert(0); st[i].insert(N); } seg.build(1, 1, all); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(i, a[i]); } printf("%d\n", query()); while (m--) { int u, v; scanf("%d%d", &u, &v); dec(u, a[u]); add(u, a[u] = v); printf("%d\n", query()); } long long ans = 0; for (int i = 1; i <= n; i++) ans += a[i]; printf("%lld\n", ans); } return 0; }
G
首先求出$1$到$2$的所有最短路，然后搜一下所有最短路的权值，然后再spfa求$2$回到$1$的经过这条最短路的某些城市最小花费更新答案。整个思路就是暴搜。
#include <bits/stdc++.h> using namespace std; const int N = 40; vector<int> G[N]; int n, m, ans; int temp[N], w[N], dp[N], level[N]; void bfs() { queue<int> que; memset(level, 0, sizeof(level)); level[1] = 1; que.push(1); while (!que.empty()) { int u = que.front(); que.pop(); for (auto v: G[u]) { if (level[v] == 0) { level[v] = level[u] + 1; que.push(v); } } } } bool inq[N]; int cal() { memset(dp, 0x3f, sizeof(dp)); dp[2] = 0; memset(inq, 0, sizeof(inq)); queue<int> que; que.push(2); inq[2] = 1; while (!que.empty()) { int u = que.front(); que.pop(); inq[u] = 0; for (auto v: G[u]) { if (dp[v] > dp[u] + temp[v]) { dp[v] = dp[u] + temp[v]; if (!inq[v]) { inq[v] = 1; que.push(v); } } } } return dp[1]; } void dfs(int u, int val) { if (u == 2) { ans = max(ans, val - cal()); return; } for (auto v: G[u]) if (level[v] == level[u] + 1) { temp[v] = w[v]; dfs(v, val + w[v]); temp[v] = 0; } } int main() { while (~scanf("%d%d", &n, &m), n + m) { for (int i = 1; i <= n; i++) G[i].clear(); for (int i = 3; i <= n; i++) scanf("%d", &w[i]); while (m--) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } bfs(); memset(temp, 0, sizeof(temp)); ans = 0; dfs(1, 0); printf("%d\n", ans); } return 0; }
H
固定一端，往一个方向延伸时，gcd种类数最多只有$O(logn)$种，因为新加入一个数要不让gcd减半，要么不变。
那么扫描线扫右端点，$v[j]$表示当前右端点为$i$，左端点为$j$时的区间gcd，并保存一下$l[j]$表示当前右端点为$j$，左端点为$l[j]$的区间gcd均相等。
待会做一下HDU5869加深一下印象。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int mp[N]; int a[N], l[N], v[N]; int gcd(int x, int y) { return y ? gcd(y, x % y) : x; } int main() { int n; while (~scanf("%d", &n), n) { memset(mp, 0, sizeof(mp)); memset(l, 0, sizeof(l)); memset(v, 0, sizeof(v)); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { v[i] = a[i]; for (int j = l[i] = i; j; j = l[j] - 1) { v[j] = gcd(v[j], a[i]); while (l[j] > 1 && gcd(a[i], v[l[j] - 1]) == gcd(a[i], v[j])) l[j] = l[l[j] - 1]; mp[v[j]] = 1; } } int ans = 0; for (int i = 1; i <= 100; i++) ans += mp[i]; printf("%d\n", ans); } return 0; }
I
直接预处理就行了。因为增长的很快，很快就爆$10^6$
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 7; int cnt[N]; int main() { for (int i = 2; i < N; i++) { int x = 0; for (int j = i; j < N; j++) { x += j; if (x > N) break; cnt[x]++; } } int n; while (~scanf("%d", &n), n) { printf("%d\n", cnt[n]); } return 0; }
J
很明显的状压DP。只不过需要状压套状压。
首先跟选择顺序有关，而每个开关打开后又跟其中走的顺序有关。
一个一个解决。
第一个要解决的是，以第$i$个开关为起点，以第$j$个位置为终点的$d[i][j]$，输入时可以$O(n^2)$求。
第二个，走了集合为$s$的开关，且当前在第$i$个开关的$dp_[s][i]$，即$s$集合中除了$i$其他都已经全部走完了。第三个，走了集合为$s$的开关，且当前在第$i$个开关的第$j$个位置，即$s$集合中所有开关都走了一遍。
两个互相转移。
$dp[s][i][j] = min(dp_[s][i] + d[i][j])$
$dp_[s|(1<<j)][j] = min(dp[s][i][k] + dis(p[i][k], sw[j])$
当限制条件增多就必须加维度了，可以大概从数据范围猜复杂度。
最后复杂度为$O(2^nn^3)$
#include <bits/stdc++.h> using namespace std; struct Point { int x, y, z; } ori, sw[13], p[13][13]; const double inf = 1e18; double f[1 << 13][13]; double d[13][13]; double dp_[1 << 13][13]; double dp[1 << 13][13][13]; int n; int K[13]; double sqr(double x) { return x * x; } double dis_(const Point &a, const Point &b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y) + sqr(a.z - b.z)); } inline Point read() { Point t; scanf("%d%d%d", &t.x, &t.y, &t.z); return t; } int main() { while (~scanf("%d", &n), n) { ori = read(); for (int i = 0; i < n; i++) { scanf("%d", &K[i]); sw[i] = read(); for (int j = 0; j < K[i]; j++) p[i][j] = read(); int S = 1 << K[i]; for (int j = 0; j < S; j++) for (int k = 0; k < K[i]; k++) f[j][k] = inf; for (int j = 0; j < K[i]; j++) f[1 << j][j] = dis_(sw[i], p[i][j]); for (int s = 0; s < S; s++) { for (int j = 0; j < K[i]; j++) if (f[s][j] != inf && (s >> j & 1)) for (int k = 0; k < K[i]; k++) if (~s >> k & 1) f[s | (1 << k)][k] = min(f[s | (1 << k)][k], f[s][j] + dis_(p[i][j], p[i][k])); } for (int j = 0; j < K[i]; j++) d[i][j] = f[S - 1][j]; } int S = 1 << n; for (int s = 0; s < S; s++) for (int i = 0; i < n; i++) { dp_[s][i] = inf; for (int j = 0; j < K[i]; j++) { dp[s][i][j] = inf; } } for (int i = 0; i < n; i++) dp_[1 << i][i] = dis_(ori, sw[i]); for (int s = 0; s < S; s++) { for (int i = 0; i < n; i++) if (dp_[s][i] != inf) for (int j = 0; j < K[i]; j++) dp[s][i][j] = min(dp[s][i][j], dp_[s][i] + d[i][j]); for (int i = 0; i < n; i++) if (s >> i & 1) for (int j = 0; j < n; j++) if (~s >> j & 1) for (int k = 0; k < K[i]; k++) if (dp[s][i][k] != inf) dp_[s | (1 << j)][j] = min(dp_[s | (1 <<j)][j], dp[s][i][k] + dis_(p[i][k], sw[j])); } double ans = inf; for (int i = 0; i < n; i++) for (int j = 0; j < K[i]; j++) ans = min(ans, dp[S - 1][i][j]); printf("%.10f\n", ans); } return 0; }
XIV Open Cup named after E.V. Pankratiev. GP of America
原文：https://www.cnblogs.com/Mrzdtz220/p/11673260.html
