[关闭]
@ljt12138 2017-04-09T23:43:31.000000Z 字数 16496 阅读 866

bzoj刷题记录：4.5-4.9

bzoj1027: [JSOI2007]合金

神题...

首先第三维可以忽略。

  1. 若干个原材料能合成一种合金，当且仅当其(x,y)在这几种原材料的多边形内。因此变成一个问题就是包住目标节点的最小节点数多边形。
  2. 然后居然可以floyd...(i,j)有边，如果所有目标节点都在(i,j)连线的右侧。然后多边形就变成一个环了。最小环就是答案。
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct p {
  5.     double x, y;
  6.     p operator - (const p &a)
  7.     { return (p) {x-a.x, y-a.y}; }
  8.     double operator * (const p &a)
  9.     { return x*a.y-y*a.x; }
  10. } mat[505], tar[505];
  11. int m, n;
  12. double tmp, eps = 1e-10;
  14. double dot(const p &a, const p &b)
  15. {
  16.     return a.x*b.x + a.y*b.y;
  17. }
  19. int sgn(double x)
  20. {
  21.     if (abs(x) <= eps) return 0;
  22.     return x > 0 ? 1 : -1;
  23. }
  25. bool on_side(int i, int j)
  26. {
  27.     for (int k = 1; k <= n; k++)
  28.         if ((tar[k]-mat[i])*(mat[j]-mat[i]) > eps ||
  29.             (abs((tar[k]-mat[i])*(mat[j]-mat[i])) <= eps && dot(mat[i]-tar[k], mat[j]-tar[k]) > eps)) return 0;
  30.     // cout << i << " " << j << " " << gt << " " << ls << " " << endl;
  31.     return 1;
  32. }
  34. int g[505][505];
  36. int main()
  37. {
  38.     scanf("%d%d", &m, &n);
  39.     for (int i = 1; i <= m; i++)
  40.         scanf("%lf%lf%lf", &mat[i].x, &mat[i].y, &tmp);
  41.     for (int i = 1; i <= n; i++)
  42.         scanf("%lf%lf%lf", &tar[i].x, &tar[i].y, &tmp);
  43.     memset(g, 127/3, sizeof g);
  44.     for (int i = 1; i <= m; i++)
  45.         for (int j = 1; j <= m; j++)
  46.             if (on_side(i, j))
  47.                 g[i][j] = 1;
  48.     for (int k = 1; k <= m; k++)
  49.         for (int i = 1; i <= m; i++)
  50.             for (int j = 1; j <= m; j++)
  51.                 g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
  52.     int ans = 233333333;
  53.     for (int i = 1; i <= m; i++) ans = min(ans, g[i][i]);
  54.     if (ans >= 23333333) cout << -1 << endl;
  55.     else cout << ans << endl;
  56.     return 0;
  57. }

bzoj1026: [SCOI2009]windy数

第一道数位dp233...果然神烦，调了一个小时左右吧（主要还是递推关系找错）
就是用dp[i][j][k]表示前i位中，最后一位填j，能否随便填/为前导零，然后一堆判断即可。
small trick：用把逻辑判断深入∑中，防止逻辑出错。
偷了个懒用了ctrl+c ctrl+v
另外吐槽黄学长代码随手hack...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. long long dp[20][10][4]; // 前i位，最后一位是j，能不能随便填/前导0
  5. long long A, B;
  6. int SA[20], SB[20];
  7. int lA = 0, lB = 0;
  9. int main()
  10. {
  11.     scanf("%lld%lld", &A, &B); A--;
  12.     for (long long i = A; i; i /= 10) SA[++lA] = i%10;
  13.     for (long long i = B; i; i /= 10) SB[++lB] = i%10;
  14.     /* calc ans ls B*/
  15.     for (int i = 1; i < SB[lB]; i++) dp[lB][i][1] = 1;
  16.     dp[lB][SB[lB]][0] = 1, dp[lB][0][2] = 1;
  17.     for (int i = lB-1; i >= 1; i--) {
  18.         for (int j = 0; j < 10; j++) {
  19.             for (int k = 0; k <= 2; k++)
  20.                 for (int l = 0; l < 10; l++)
  21.                     for (int p = 0; p <= 2; p++)
  22.                         dp[i][j][k] += dp[i+1][l][p]*(p==2||abs(j-l) >= 2)*
  23.                         ((k==0&&p==0&&j==SB[i])||(k==1&&(p==1||(p==2&&j)||(p==0&&j<SB[i])))||(k==2&&j==0&&p==2));
  24.         }
  25.     }
  26.     long long ans1 = 0, ans2 = 0;
  27.     for (int i = 0; i < 10; i++) ans1 += dp[1][i][0]+dp[1][i][1];//+dp[1][i][2];
  28.     memset(dp, 0, sizeof dp);
  29.     /* now ls A*/
  30.     for (int i = 1; i < SA[lA]; i++) dp[lA][i][1] = 1;
  31.     dp[lA][SA[lA]][0] = 1, dp[lA][0][2] = 1;
  32.     for (int i = lA-1; i >= 1; i--) {
  33.         for (int j = 0; j < 10; j++) {
  34.             for (int k = 0; k <= 2; k++)
  35.                 for (int l = 0; l < 10; l++)
  36.                     for (int p = 0; p <= 2; p++)
  37.                         dp[i][j][k] += dp[i+1][l][p]*(p==2||abs(j-l) >= 2)*
  38.                         ((k==0&&p==0&&j==SA[i])||(k==1&&(p==1||(p==2&&j)||(p==0&&j<SA[i])))||(k==2&&j==0&&p==2));
  39.         }
  40.     }
  41.     for (int i = 0; i < 10; i++) ans2 += dp[1][i][0]+dp[1][i][1];
  42.     cout << ans1-ans2 << endl;
  43.     return 0;
  44. }

bzoj1069: [SCOI2007]最大土地面积

显然(表示蒟蒻看不出哪里显然)四边形的两个点是凸包上一对对踵点，所以旋转卡壳找对踵点然后枚举另外左右两个点就好了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct vec {
  5.     double x, y;
  6.     double len_pow() const
  7.     { return x*x+y*y; }
  8.     friend vec operator - (const vec &a, const vec &b)
  9.     { return (vec) {a.x-b.x, a.y-b.y}; }
  10.     friend double operator * (const vec &a, const vec &b)
  11.     { return a.x*b.y-a.y*b.x; }
  12.     friend bool operator == (const vec &a, const vec &b)
  13.     { return b.x == a.x && b.y == a.y; }
  14. } pts[2005];
  15. int n;
  17. vec lft;
  18. double eps = 1e-7;
  19. int sgn(double a)
  20. { return abs(a) <= eps ? 0 : (a>eps?1:-1); }
  22. bool cmp(const vec &a, const vec &b)
  23. {
  24.     if (a == lft || b == lft) return a == lft;
  25.     return sgn((b-lft)*(a-lft)) == 0 ? a.len_pow() < b.len_pow() : sgn((b-lft)*(a-lft)) > 0;
  26. }
  28. stack<vec> stk;
  29. vec pl[2005];
  30. int tp = 0;
  31. void graham()
  32. {
  33.     lft.x = 1234567;
  34.     for (int i = 1; i <= n; i++)
  35.         if (pts[i].x < lft.x) lft = pts[i];
  36.     sort(pts+1, pts+n+1, cmp);
  37.     for (int i = 1; i <= n; i++) {
  38.         if (stk.empty()) stk.push(pts[i]);
  39.         else {
  40.             while (stk.size() >= 2) {
  41.                 vec tp = stk.top(); stk.pop();
  42.                 vec t2 = stk.top(); stk.pop();
  43.                 if ((t2-tp)*(pts[i]-tp) > 0) {stk.push(t2), stk.push(tp); break;}
  44.                 else stk.push(t2);
  45.             }
  46.             stk.push(pts[i]);
  47.         }
  48.     }
  49.     stk.push(lft);
  50.     tp = stk.size();
  51.     for (int i = tp-1; i >= 0; i--)
  52.         pl[i] = stk.top(), stk.pop();
  53.     double ans = 0;
  54.     for (int i = 0, j = 1; i < tp; i++) {
  55.         double l = 0, r = 0;
  56.         if (j == i) j = (j+1)%tp;
  57.         while((pl[(j+1)%tp]-pl[i]).len_pow() >= (pl[j]-pl[i]).len_pow())
  58.             j = (j+1)%tp;
  59.         for (int k = 0; k < tp; k++)
  60.             if (sgn((pl[k]-pl[i])*(pl[j]-pl[i])) <= 0) l = max(l, abs((pl[k]-pl[i])*(pl[j]-pl[i]))/2);
  61.             else r = max(r, abs((pl[k]-pl[i])*(pl[j]-pl[i]))/2);
  62.         ans = max(ans, l+r);
  63.     }
  64.     printf("%.3f", ans);
  65. }
  67. int main()
  68. {
  69.     scanf("%d", &n);
  70.     for (int i = 1; i <= n; i++)
  71.         scanf("%lf %lf", &pts[i].x, &pts[i].y);
  72.     graham();
  73.     return 0;
  74. }

bzoj1031: [JSOI2007]字符加密Cipher

输入S，把SS丢进后缀数组排序，然后扫一遍就可以了。
然而后缀数组写一遍就要看一遍模板...
一会再练习一下二分+hash大法...感觉做这个题应该很轻松

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005;
  5. struct SA {
  6.     struct p {
  7.         int k[2], id;
  8.         p(){}
  9.         p(int i, int a, int b) { id = i, k[0] = a, k[1] = b; }
  10.     } RE[MAXN], RT[MAXN];
  11.     int C[MAXN], SA[MAXN], height[MAXN], rank[MAXN], str[MAXN], n;
  12.     void radix_sort()
  13.     {
  14.         for (int y = 1; y >= 0; y--) {
  15.             memset(C, 0, sizeof C);
  16.             for (int i = 1; i <= n; i++) C[RE[i].k[y]]++;
  17.             for (int i = 1; i <= 200000; i++) C[i] += C[i-1];
  18.             for (int i = n; i >= 1; i--) RT[C[RE[i].k[y]]--] = RE[i];
  19.             for (int i = 1; i <= n; i++) RE[i] = RT[i];
  20.         }
  21.         for (int i = 1; i <= n; i++) {
  22.             rank[RE[i].id] = rank[RE[i-1].id];
  23.             if (RE[i].k[0] != RE[i-1].k[0] || RE[i].k[1] != RE[i-1].k[1])
  24.                 rank[RE[i].id]++;
  25.         }
  26.     }
  27.     void calc_sa()
  28.     {
  29.         for (int i = 1; i <= n; i++) RE[i] = p(i, str[i], 0);
  30.         radix_sort();
  31.         for (int k = 1; k < n; k <<= 1) {
  32.             for (int i = 1; i <= n; i++) RE[i] = p(i, rank[i], i+k<=n?rank[i+k]:0);
  33.             radix_sort();
  34.         }
  35.         for (int i = 1; i <= n; i++)
  36.             SA[rank[i]] = i;
  37.     }
  38. } SA;
  40. char str[MAXN];
  41. int main()
  42. {
  43.     scanf("%s", str+1);
  44.     int n = strlen(str+1); SA.n = n*2;
  45.     for (int i = 1; i <= n; i++) SA.str[i] = SA.str[i+n] = str[i];
  46.     SA.calc_sa();
  47.     for (int i = 1; i <= n*2; i++) {
  48.         if (SA.SA[i] <= n) {
  49.             printf("%c", SA.str[SA.SA[i]+n-1]);
  50.         }
  51.     }
  52.     return 0;
  53. }

bzoj1040: [ZJOI2008]骑士

这就是所谓环套树上dp吗？
求环套树上最大独立集。
由于每棵树至多一个环，只需要从(u,v)拆开这个环，做两次dp。一次不选u，一次不选v，然后取最大值。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005;
  5. int x[MAXN];
  6. int n;
  7. struct node {
  8.     int to, next;
  9. } edge[MAXN*2];
  10. int head[MAXN], top = 0;
  11. void push(int i, int j)
  12. { ++top, edge[top] = (node) { j, head[i]}, head[i] = top; }
  14. struct tree {
  15.     struct node {
  16.         int to, next;
  17.     } edge[MAXN];
  18.     int head[MAXN], top, vis[MAXN], rd[MAXN], v[MAXN], vt;
  19.     long long dp[MAXN], dpban[MAXN];
  20.     void clear()
  21.     { top = vt = 0; memset(head, 0, sizeof head); memset(vis, -1, sizeof vis); 
  22.      memset(rd, 0, sizeof rd); memset(v, 0, sizeof v); } 
  23.     void push(int i, int j)
  24.     { 
  25.       //cout << i<<"-->" << j << endl;
  26.       ++top, edge[top] = (node) { j, head[i]}, head[i] = top, rd[j]++;
  27.       if (vis[i] == -1) v[++vt] = i, vis[i] = 0;
  28.       if (vis[j] == -1) v[++vt] = j, vis[j] = 0;
  29.     }
  30.     long long dfs(int nd)
  31.     {
  32.         // cout << "dfs " << nd << endl;
  33.         if (dp[nd] != -1) return dp[nd];
  34.         if (vis[nd]) return dfs_ban(nd);
  35.         // --- choose nd ---
  36.         dp[nd] = x[nd];
  37.         for (int i = head[nd]; i; i = edge[i].next)
  38.             dp[nd] += dfs_ban(edge[i].to);
  39.         // --- not choose nd ---
  40.         long long ans = 0;
  41.         for (int i = head[nd]; i; i = edge[i].next)
  42.             ans += dfs(edge[i].to);
  43.         return dp[nd] = max(dp[nd], ans);
  44.     }
  45.     long long dfs_ban(int nd)
  46.     {
  47.         //cout << "dfs_ban " << nd << endl;
  48.         if (dpban[nd] != -1) return dpban[nd];
  49.         dpban[nd] = 0;
  50.         for (int i = head[nd]; i; i = edge[i].next)
  51.             dpban[nd] += dfs(edge[i].to);
  52.         return dpban[nd];
  53.     }
  54.     long long result()
  55.     {
  56.         memset(dp, -1, sizeof dp), memset(dpban, -1, sizeof dpban);
  57.         int rt = 0;
  58.         for (int i = 1; i <= vt; i++) 
  59.             if (rd[v[i]] == 0) {
  60.                 rt = v[i];
  61.                 break;
  62.             }
  63.         return dfs(rt);
  64.     }
  65. } T;
  67. int vis[MAXN];
  68. int u, v; // 拆环点 
  69. void dfs(int i, int f = 0)
  70. {
  71.     vis[i] = 1;
  72.     for (int k = head[i]; k; k = edge[k].next) {
  73.         int to = edge[k].to;
  74.         if (f == to);
  75.         else if (!vis[to]) T.push(i, to), dfs(to, i);
  76.         else u = i, v = to;
  77.     }
  78. }
  79. long long work(int i)
  80. {
  81.     T.clear();
  82.     dfs(i);
  83.     // cout << u << " " << v << endl; 
  84.     long long ans = 0;
  85.     T.vis[u] = 0, T.vis[v] = 1;
  86.     ans = max(ans, T.result());
  87.     T.vis[v] = 0, T.vis[u] = 1;
  88.     ans = max(ans, T.result());
  89.     return ans;
  90. }
  92. int main()
  93. {
  94.     scanf("%d", &n);
  95.     for (int i = 1; i <= n; i++) {
  96.         int tar;
  97.         scanf("%d%d", &x[i], &tar);
  98.         push(i, tar), push(tar, i);
  99.     }
  100.     memset(vis, 0, sizeof vis);
  101.     long long ans = 0;
  102.     for (int i = 1; i <= n; i++) 
  103.         if (!vis[i]) 
  104.             ans += work(i);
  105.     cout << ans << endl;
  106.     return 0;
  107. }

bzoj2234: 营业额统计

set水过...
鉴于那个年代不能stl，再写一个splay..
其实那个年代也没有splay

set:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. set<int> table;
  5. int n;
  6. int main()
  7. {
  8.     scanf("%d", &n);
  9.     int cnt = 0;
  10.     for (int i = 1; i <= n; i++) {
  11.         int a; if (scanf("%d", &a)==EOF) a = 0;
  12.         set<int>::iterator k = table.lower_bound(a), t = k;
  13.         if (k != table.begin()) k--;
  14.         int ans = INT_MAX;
  15.         if (i == 1) ans = a;
  16.         else {
  17.             if (t != table.end()) ans = min(ans, abs(*t-a));//, printf("--%d--\n", *t);
  18.             if (k != table.end()) ans = min(ans, abs(*k-a));//, printf("--%d--\n", *k);
  19.         }
  20.         cnt += ans;
  21.         table.insert(a);
  22.     }
  23.     cout << cnt << endl;
  24.     return 0;
  25. }

splay:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 40005;
  5. int dat[MAXN], chl[MAXN][2], fa[MAXN], top = 0, root = 0;
  6. int new_node(int ke, int f)
  7. { return dat[++top] = ke, fa[top] = f, top; }
  8. void zig(int nd)
  9. {
  10.     int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  11.     int son = chl[nd][tp^1];
  12.     if (son) fa[son] = p; fa[p] = nd, fa[nd] = g;
  13.     if (g) chl[g][tg] = nd; else root = nd;
  14.     chl[nd][tp^1] = p, chl[p][tp] = son;
  15. }
  16. void splay(int nd)
  17. {
  18.     while (fa[nd]) {
  19.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  20.         if (!g) {zig(nd); break; }
  21.         if (tp == tg) zig(p), zig(nd);
  22.         else zig(nd), zig(nd);
  23.     }
  24. }
  25. void push_ele(int ke)
  26. {
  27.     if (!root) { root = new_node(ke, 0); return; }
  28.     int nd = root, p = fa[nd];
  29.     while (nd) p = nd, nd = chl[nd][dat[nd]<=ke];
  30.     chl[p][dat[p] <= ke] = new_node(ke, p);
  31.     splay(chl[p][dat[p]<=ke]);
  32. }
  33. int ans_of(int num)
  34. {
  35.     if (!root) return num;
  36.     int ans = INT_MAX;
  37.     int nd = root;
  38.     while (nd) {
  39.         ans = min(ans, abs(dat[nd]-num));
  40.         nd = chl[nd][dat[nd]<=num];
  41.     }
  42.     return ans;
  43. }
  45. int main()
  46. {
  47.     int n, a;
  48.     memset(chl, 0, sizeof chl);
  49.     memset(fa, 0, sizeof fa);
  50.     scanf("%d", &n);
  51.     int sum = 0;
  52.     for (int i = 1; i <= n; i++) {
  53.         if (scanf("%d", &a) == EOF) a = 0;
  54.         sum += ans_of(a), push_ele(a);
  55.     }
  56.     cout << sum << endl;
  57.     return 0;
  58. }

bzoj1019: [SHOI2008]汉诺塔

手玩一会发现方法是唯一的。
凡汉诺塔就考虑最大盘，枚举最大盘两种行进模式，然后递归判断是否可行。那个优先级限制事实上只作用在一个盘子的时候。
最后带个记忆化即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. long long dp[35][4][4];
  5. pair<int,int> pr[7];
  6. int n;
  8. long long dfs(int n, int s, int t)
  9. {
  10.     if (dp[n][s][t] != -1) return dp[n][s][t];
  11.     if (n == 1) {
  12.         for (int i = 1; i <= 6; i++) {
  13.             if (pr[i].first == s && pr[i].second != t) {dp[n][s][t] = -1234567; break;}
  14.             if (pr[i].first == s && pr[i].second == t) {dp[n][s][t] = 1; break;}
  15.         }
  16.     } else {
  17.         if (dfs(n-1, s, t) > 0 && dfs(n-1, t, s) > 0) dp[n][s][t] = 2+dfs(n-1, s, t)*2+dfs(n-1, t, s);
  18.         else if (dfs(n-1, s, 6-s-t) > 0 && dfs(n-1, 6-s-t, t) > 0) dp[n][s][t] = dfs(n-1, s, 6-s-t) + dfs(n-1, 6-s-t, t) + 1;
  19.         else dp[n][s][t] = -1234567;
  20.     }
  21.     // printf("%d,%d,%d ==> %lld\n", n, s, t, dp[n][s][t]);
  22.     return dp[n][s][t];
  23. }
  25. int main()
  26. {
  27.     memset(dp, -1, sizeof dp);
  28.     scanf("%d", &n);
  29.     for (int i = 1; i <= 6; i++) {
  30.         char s[2];
  31.         scanf("%s", s);
  32.         pr[i] = make_pair(s[0]-'A'+1, s[1]-'A'+1);
  33.     }
  34.     if (dfs(n, 1, 3)>0) cout << dfs(n, 1, 3) << endl;
  35.     else cout << dfs(n, 1, 2) << endl;
  36.     return 0;
  37. }

bzoj1022: [SHOI2008]小约翰的游戏John

和NIM很像啊，然而找不到太多思路，然后就用通用策略打表找规律，可以发现很强的结论：只需要特判非0即1的局面，剩下的和普通NIM一样（SG&XOR）。

  1. #include <cstdio>
  2. using namespace std;
  4. int main()
  5. {
  6.     int T;
  7.     scanf("%d", &T);
  8.     while (T--) {
  9.         int n; scanf("%d", &n);
  10.         int ans = 0, cnt = 0, c2 = 0;
  11.         for (int i = 1; i <= n; i++) {
  12.             int a; scanf("%d", &a);
  13.             ans ^= a;
  14.             if (a == 1) cnt++;
  15.             if (a == 0) c2++;
  16.         }
  17.         if (cnt+c2 == n) {
  18.             if (cnt&1) puts("Brother");
  19.             else puts("John");
  20.         } else {
  21.             if (ans == 0) puts("Brother");
  22.             else puts("John");
  23.         }
  24.     }
  25.     return 0;
  26. }

bzoj1188: [HNOI2007]分裂游戏

题不是今天写的，但还是mark一下。
分裂之后两个石子就独立了，所以：

sg(n)=mex{sg(i)⊕sg(j) | i>n,j≥i}

n很小，暴力算就可以了。
至于计数题，仍然大暴力，枚举分裂位置求新局面的sg异或和即可。
设原局面异或和为ans，新位置i→(j,k)，相当于去掉i，加上j，k，由于任何一个元素都是异或的幂等元，去掉等同于加上，新的异或和为

ans⊕sg(i)⊕sg(j)⊕sg(k)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int a[30], sg[30];
  5. int n;
  6. int basket[100];
  8. int main()
  9. {
  10.     int t; scanf("%d", &t);
  11.     while (t--) {
  12.         scanf("%d", &n);
  13.         for (int i = 1; i <= n; i++)
  14.             scanf("%d", &a[i]);
  15.         sg[n] = 0;
  16.         for (int i = n-1; i >= 1; i--) {
  17.             memset(basket, 0, sizeof basket);
  18.             for (int j = i+1; j <= n; j++)
  19.                 for (int k = j; k <= n; k++)
  20.                     basket[sg[j]^sg[k]] = 1;
  21.             for (int j = 0; ; j++) if (basket[j] == 0) { sg[i] = j; break; }
  22.         }
  23.         int ans = 0;
  24.         for (int i = 1; i <= n; i++)
  25.             if (a[i]&1)
  26.                 ans ^= sg[i];
  27.         if (ans == 0) {
  28.             printf("-1 -1 -1\n0\n");
  29.         } else {
  30.             int a1, b, c, cnt = 0; a1 = b = c = -1;
  31.             for (int i = 1; i <= n; i++)
  32.                 for (int j = i+1; j <= n; j++)
  33.                     for (int k = j; k <= n; k++)
  34.                         if (((ans^sg[i]^sg[j]^sg[k]) == 0) ){
  35.                             if (a1+b+c < 0) a1 = i, b = j, c = k;
  36.                             cnt++;
  37.                         } 
  38.             printf("%d %d %d\n%d\n", a1-1, b-1, c-1, cnt);
  39.         }
  40.     }
  41.     return 0;
  42. }

bzoj2728: [HNOI2012]与非

神题......磕了一上午无果，后来看了大爷题解。
首先发现{∘=nand}构成一个联结词完备集，因为：

  1. ¬a=a∘a
  2. a∧b=¬(a∘b)
  3. a∨b=¬(¬a∧¬b)
  4. …

然后就用奇奇怪怪的方法搞了一个每个位置都仅出现在一个数的线性基出来，然后贪心...

大爷题解传送门

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. long long bas[70];
  5. int n, kp, k; long long L, R;
  6. long long a[1010], upp;
  7. int v[70];
  9. long long query(long long up)
  10. {
  11.     if (up == -1) return -1;
  12.     long long now = 0, ans = 0;
  13.     for (int i = 1; i <= k; i++) {
  14.         if ((now|bas[i]) <= up)
  15.             now |= bas[i], ans += (1ll<<(k-i));
  16.     }
  17.     return ans;
  18. }
  20. int main()
  21. {
  22.     memset(v, 0, sizeof v);
  23.     scanf("%d%d%lld%lld", &n, &kp, &L, &R);
  24.     for (int i = 1; i <= n; i++)
  25.         scanf("%lld", &a[i]);
  26.     upp = (1ll<<kp)-1;
  27.     for (int j = kp-1; j >= 0; j--)
  28.         if (!v[j]) {
  29.             long long now = upp;
  30.             for (int i = 1; i <= n; i++)
  31.                 if (!(a[i]&(1ll<<j)))
  32.                     now &= ~a[i]&upp;
  33.                 else
  34.                     now &= a[i];
  35.             bas[++k] = now;
  36.             for (int i = 0; i <= j; i++)
  37.                 if (now&(1ll<<i))
  38.                     v[i] = 1;
  39.         }
  40.     cout << query(R)-query(L-1) << endl;
  41.     return 0;
  42. }

上午那个线性基太伤人...于是下午打算复习tarjan。
其实是重新学...
以前很喜欢做缩点不过只会ko..算法，学了tarjan感觉打开了新世界大门。才知道那个stack存的是根到这个点的路径...

bzoj2730: [HNOI2012]矿场搭建

貌似有大爷用点双做？
首先用tarjan算出割点集S，然后判断G−G(S)的每个联通块。如果和两个割点相连则不用管，如果仅和一个割点连着要建一个。最后乘一乘就好。
特判没有割点要建两个。
初始化坑人...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1050;
  5. int m;
  7. int arr[MAXN], tp = 0;
  8. struct graph {
  9.     struct node {
  10.         int to, next;
  11.     } edge[MAXN];
  12.     int head[MAXN], n, top, low[MAXN], dfn[MAXN], vis[MAXN], deg[MAXN], dft;
  13.     int cut[MAXN], gp[MAXN], gp_top, lk[MAXN][MAXN], cut_cnt;
  14.     void clear()
  15.     { memset(arr, 0, sizeof arr); memset(head,0,sizeof head); memset(vis, 0, sizeof vis);
  16.       memset(cut, 0, sizeof cut); n = top = dft = gp_top = cut_cnt = 0;
  17.       memset(deg, 0, sizeof deg); memset(gp, 0, sizeof gp);
  18.       memset(dfn, 0, sizeof dfn); memset(lk, 0, sizeof lk); }
  19.     void push(int i, int j)
  20.     { ++top, edge[top] = (node) {j, head[i]}, head[i] = top; n = max(n, max(i,j)); }
  21.     void tarjan(int nd, int f);
  22.     void work(int);
  23.     void dfs(int nd, int &siz, int &lkt);
  24. } g;
  25. void graph::tarjan(int nd, int f)
  26. {
  27.     vis[nd] = 1, low[nd] = dfn[nd] = ++dft;
  28.     for (int i = head[nd]; i; i = edge[i].next) {
  29.         int to = edge[i].to;
  30.         if (!vis[to]) tarjan(to, nd), low[nd] = min(low[nd], low[to]), deg[nd]++;
  31.         else if (to != f) low[nd] = min(low[nd], dfn[to]);
  32.         if (dfn[nd] <= low[to]) {if (!f) cut[nd] = deg[nd]>=2; else cut[nd] = 1; cut_cnt += cut[nd];}
  33.     }
  34. }
  35. void graph::dfs(int nd, int &siz, int &lkt)
  36. {
  37.     gp[nd] = gp_top, siz++;
  38.     // cerr << "Group " << gp_top << " ---> " << nd << endl;
  39.     for (int i = head[nd]; i; i = edge[i].next) {
  40.         int to = edge[i].to;
  41.         if (!gp[to] && !cut[to]) dfs(to, siz, lkt);
  42.         else if (cut[to] && lk[gp_top][to] == 0) lk[gp_top][to] = 1, lkt++;
  43.     }
  44. }
  45. void graph::work(int c)
  46. {
  47.     for (int i = 1; i <= n; i++)
  48.         if (!dfn[i])
  49.             tarjan(i, 0);
  50.     if (cut_cnt == 0) {
  51.         printf("Case %d: %d %lld\n", c, 2, (long long)n*(n-1)/2);
  52.         return;
  53.     }
  54.     for (int i = 1; i <= n; i++) {
  55.         if (!cut[i] && !gp[i]) {
  56.             int siz = 0, lkt = 0;
  57.             gp_top++, dfs(i, siz, lkt);
  58.             if (lkt == 1) arr[++tp] = siz;
  59.         }
  60.     }
  61.     long long ans = 1;
  62.     for (int i = 1; i <= tp; i++) ans *= arr[i];
  63.     printf("Case %d: %d %lld\n", c, tp, ans);
  64. }
  66. int main()
  67. {
  68.     int cas = 0;
  69.     while (scanf("%d", &m)) {
  70.         g.clear(); tp = 0;
  71.         if (m == 0) break;
  72.         ++cas;
  73.         for (int i = 1; i <= m; i++) {
  74.             int u, v; scanf("%d %d", &u, &v);
  75.             g.push(u, v), g.push(v, u);
  76.         }
  77.         g.work(cas);
  78.     }
  79.     return 0;
  80. }

bzoj1051: [HAOI2006]受欢迎的牛

做过好几遍了...
练模板首选2333

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 10005, MAXM = 100005;
  5. int n, m;
  6. struct graph {
  7.     struct node {
  8.         int to, next;
  9.     } edge[MAXM];
  10.     int head[MAXN], top, d[MAXN];
  11.     graph(){top = 0; memset(head, 0, sizeof head),memset(d, 0, sizeof d); }
  12.     void push(int i, int j)
  13.     { d[i]++, ++top, edge[top] = (node) {j, head[i]}, head[i] = top; }
  14. } g, g1;
  16. int dfn[MAXN], low[MAXN], stk[MAXN], top = 0, vis[MAXN], dft = 0;
  17. int gp[MAXN], gtop = 0, gsiz[MAXN];
  18. set<pair<int,int> > hst;
  20. void tarjan(int nd)
  21. {
  22.     dfn[nd] = low[nd] = ++dft, vis[nd] = 1, stk[++top] = nd;
  23.     for (int i = g.head[nd]; i; i = g.edge[i].next) {
  24.         int to = g.edge[i].to;
  25.         if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
  26.         else if (vis[to]) low[nd] = min(low[nd], dfn[to]);
  27.     }
  28.     if (low[nd] == dfn[nd]) {
  29.         gtop++;
  30.         int now;
  31.         do {
  32.             now = stk[top--];
  33.             // printf("%d ", now);
  34.             gp[now] = gtop, gsiz[gtop]++;
  35.             vis[now] = 0;
  36.         } while(now != nd); //puts("");
  37.     }
  38. }
  40. void work()
  41. {
  42.     int cnt = 0, ans = 0;
  43.     for (int i = 1; i <= gtop; i++) if (g1.d[i] == 0) cnt++, ans += gsiz[i];
  44.     if (cnt != 1) puts("0");
  45.     else printf("%d\n", ans);
  46. }
  48. int main()
  49. {
  50.     scanf("%d%d", &n, &m);
  51.     for (int i = 1; i <= m; i++) {
  52.         int u, v; scanf("%d%d", &u, &v);
  53.         g.push(u, v);
  54.     }
  55.     for (int i = 1; i <= n; i++)
  56.         if (!dfn[i])
  57.             tarjan(i);
  58.     for (int i = 1; i <= n; i++) {
  59.         for (int j = g.head[i]; j; j = g.edge[j].next) {
  60.             int to = g.edge[j].to;
  61.             if (gp[to] != gp[i] && !hst.count(make_pair(gp[i],gp[to]))) {
  62.                 hst.insert(make_pair(gp[i], gp[to]));
  63.                 g1.push(gp[i], gp[to]);
  64.             }
  65.         }
  66.     }
  67.     work();
  68.     return 0;
  69. }

bzoj2330: [SCOI2011]糖果

缩点建图，取等号的边长为0，不取的边长为1。不能满足当且仅当存在长度大于1的环。
然后缩完点就变成dag上最长链了。dp做就可以。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005, MAXM = 200005;
  5. struct graph {
  6.     struct node {
  7.         int to, next, dis;
  8.     } edge[MAXM];
  9.     int head[MAXN], top;
  10.     graph(){top = 0; memset(head, 0, sizeof head);}
  11.     void push(int i, int j, int d)
  12.     { //printf("%d--%d-->%d\n", i, d, j); 
  13.     ++top, edge[top] = (node) {j, head[i], d}, head[i] = top; }
  14. }g, g1;
  15. int n, m;
  17. int dfn[MAXN], low[MAXN], prelen[MAXN], stk[MAXN], vis[MAXN], top = 0, dft = 0;
  18. int gp[MAXN], gsiz[MAXN], gtop = 0, len_end[MAXN];
  19. int fail = 0;
  21. void tarjan(int nd)
  22. {
  23.     dfn[nd] = low[nd] = ++dft, stk[++top] = nd, vis[nd] = 1;
  24.     for (int i = g.head[nd]; i; i = g.edge[i].next) {
  25.         int to = g.edge[i].to, d = g.edge[i].dis;
  26.         if (!dfn[to]) prelen[to] = d, tarjan(to), low[nd] = min(low[nd], low[to]);
  27.         else if (vis[to]) low[nd] = min(low[nd], dfn[to]), len_end[MAXN] += d;
  28.     }
  29.     if (dfn[nd] == low[nd]) {
  30.         ++gtop; int now, len = len_end[MAXN];
  31.         // printf("--- Group %d ---\n", gtop);
  32.         do {
  33.             now = stk[top--], vis[now] = 0;
  34.             // printf("%d ", now);
  35.             gp[now] = gtop, gsiz[gtop]++, len += prelen[now]*(now!=nd);
  36.         } while (now != nd); //puts("");
  37.         if (len != 0) {fail = 1; return;}
  38.     }
  39. }
  41. int dp[MAXN];
  42. int dfs(int nd)
  43. {
  44.     if (dp[nd] != -1) return dp[nd];
  45.     dp[nd] = 0;
  46.     for (int i = g1.head[nd]; i; i = g1.edge[i].next) {
  47.         int to = g1.edge[i].to, d = g1.edge[i].dis;
  48.         dp[nd] = max(dp[nd], dfs(to)+d);
  49.     }
  50.     return dp[nd] == 0 ? dp[nd] = 1 : dp[nd];
  51. }
  53. void work()
  54. {
  55.     for (int i = 1; i <= n; i++)
  56.         for (int j = g.head[i]; j; j = g.edge[j].next) {
  57.             int to = g.edge[j].to, d = g.edge[j].dis;
  58.             if (gp[i] != gp[to])
  59.                 g1.push(gp[to], gp[i], d); // 反图
  60.         }
  61.     memset(dp, -1, sizeof dp);
  62.     long long ans = 0;
  63.     for (int i = 1; i <= gtop; i++)
  64.         ans += dfs(i)*(long long)gsiz[i];
  65.     printf("%lld\n", ans);
  66. }
  68. int main()
  69. {
  70.     scanf("%d%d", &n, &m);
  71.     for (int i = 1; i <= m; i++) {
  72.         int x, u, v; scanf("%d%d%d", &x, &u, &v);
  73.         switch (x) {
  74.             case 1: g.push(u, v, 0), g.push(v, u, 0); break;
  75.             case 2: g.push(u, v, 1); break;
  76.             case 3: g.push(v, u, 0); break;
  77.             case 4: g.push(v, u, 1); break;
  78.             case 5: g.push(u, v, 0); break;
  79.         }
  80.     }
  81.     for (int i = 1; i <= n; i++)
  82.         if (!dfn[i])
  83.             tarjan(i);
  84.     if (fail == 1) puts("-1");
  85.     else work();
  86.     return 0;
  87. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注