[关闭]
@Falsyta 2015-10-24T12:39:31.000000Z 字数 8622 阅读 1672

AMPPZ 2014

OI AMPPZ

虽然暂时没写完但是为了增加填坑动力还是单挂出来好了。

AMPPZ2014 ben

由于起点终点都是加油站可以只考虑加油站。
建超级源点跑最短路，考虑离每个点最近的加油站。
容易发现一个加油站a要走到其他加油站必经若干加油站，而必经的加油站b满足一定存在一条边(u,v)使得a离x最近，b离v最近。
然后建出只含加油站的新图以后就转化成每次询问路径边权最小值。

  1. # include <cstdio>
  2. # include <algorithm>
  3. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  4. # define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
  5. using namespace std;
  6. const int inf = 1 << 30;
  7. # define NR 201000
  8. struct Edge {int y, frt, val; void set (int _y, int _frt, int _val) {y = _y, frt = _frt, val = _val;}} g[NR << 1];
  9. struct Arr {int x, y, w, id; Arr () {x = y = w = id = 0;} Arr (int _x, int _y, int _w, int _id): x(_x), y(_y), w(_w), id(_id) {}} e[NR << 1], qy[NR];
  10. int n, s, m, gsz, id[NR], q[5001000], fa[NR], pos[NR], dt[NR], esz, q0, ans[NR];
  11. bool inq[NR];
  12. # define v g[i].y
  13. inline bool cmpE (Arr a, Arr b) {return a.w < b.w;}
  14. inline void AE (int x, int y, int z) {g[++ gsz].set (y, pos[x], z), pos[x] = gsz;}
  15. inline int gf (int x) {return fa[x] == x ? x : (fa[x] = gf (fa[x]));}
  16. void spfa ()
  17. {
  18.     int head = 1, tail = 0, x;
  19.     REP (i, n) id[i] ? inq[q[++ tail] = i] = true : dt[i] = inf;
  20.     while (head <= tail)
  21.     {
  22.         x = q[head ++];
  23.         REP_G (i, x)
  24.             if (dt[x] + g[i].val < dt[v])
  25.             {
  26.                 dt[v] = dt[x] + g[i].val, id[v] = id[x];
  27.                 if (!inq[v]) inq[q[++ tail] = v] = true;
  28.             }
  29.         inq[x] = false;
  30.     }
  31. }
  32. int main ()
  33. {
  34.     scanf ("%d%d%d", &n, &s, &m); int t1, t2, t3;
  35.     REP (i, s) scanf ("%d", &t1), id[t1] = t1;
  36.     REP (i, m) scanf ("%d%d%d", &t1, &t2, &t3), AE (t1, t2, t3), AE (t2, t1, t3);
  37.     spfa ();
  38.     REP (x, n) {REP_G (i, x) if (id[x] < id[v]) e[++ esz] = Arr (id[x], id[v], dt[x] + dt[v] + g[i].val, 0); fa[x] = x;}
  39.     sort (e + 1, e + esz + 1, cmpE), scanf ("%d", &q0);
  40.     REP (i, q0) scanf ("%d%d%d", &qy[i].x, &qy[i].y, &qy[i].w), qy[i].id = i;
  41.     sort (qy + 1, qy + q0 + 1, cmpE);
  42.     int j = 1;
  43.     REP (i, q0)
  44.     {
  45.         for (; j <= esz && e[j].w <= qy[i].w; ++ j) {int fx = gf (e[j].x), fy = gf (e[j].y); if (fx != fy) fa[fx] = fy;}
  46.         ans[qy[i].id] = gf (qy[i].x) == gf (qy[i].y);
  47.     }
  48.     REP (i, q0) puts (ans[i] ? "TAK" : "NIE");
  49.     return 0;
  50. }

AMPPZ2014 cen

感觉自己简直在凑数……
本来想用FWT发现没有暴力快……

复杂度O(n2m+3m)。

  1. # include <cstdio>
  2. # include <algorithm>
  3. using namespace std;
  4. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  5. # define REP_0(i, n) for (int i = 0; i < n; ++ i)
  6. # define SR (1 << 16)
  7. # define NR 20
  8. const int inf = 1 << 30;
  9. int n, m, fi[SR], ts[SR], ans[SR], bid[SR], a[NR];
  10. int main ()
  11. {
  12.     scanf ("%d%d", &n, &m);
  13.     int M = 1 << m;
  14.     REP_0 (i, m) bid[1 << i] = i;
  15.     REP_0 (i, M) fi[i] = inf;
  16.     REP (i, n)
  17.     {
  18.         scanf ("%d", &ts[0]);
  19.         REP_0 (j, m) scanf ("%d", &a[j]);
  20.         REP (s, M - 1) ts[s] = ts[s ^ (s & -s)] + a[bid[s & -s]], fi[s] = min (fi[s], ts[s]);
  21.     }
  22.     REP (i, M - 1)
  23.     {
  24.         ans[i] = fi[i];
  25.         for (int j = (i - 1) & i; j; j = (j - 1) & i) ans[i] = min (ans[i], ans[j] + ans[i - j]);
  26.     }
  27.     printf ("%d\n", ans[M - 1]);
  28.     return 0;
  29. }

AMPPZ2014 fil

之前没看见限制……那个破翻译什么玩意啊T_T
有了限制就见了障碍就绕行就行了……

  1. # include <cstdio>
  2. # include <algorithm>
  3. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  4. # define pc putchar
  5. using namespace std;
  6. # define NR 1010
  7. int p[NR], n, m, K;
  8. bool a[NR][NR], fil[NR];
  9. void ret (int x, int y)
  10. {
  11.     a[x][y] = true;
  12.     if (x == 2 && y == 1) {pc ('D'); return ;}
  13.     if (!fil[x]) {pc ('D'), ret (x - 1, y); return ;}
  14.     if (y == 1) pc ('P'), fil[x] = false, ret (x, y + 1);
  15.     else pc ('L'), fil[x] = false, ret (x, y - 1);
  16. }
  17. void dfs (int x, int y)
  18. {
  19.     a[x][y] = true;
  20.     if (x == 2 && y == 1) {pc ('D'); return ;}
  21.     if (x > 1 && !a[x - 1][y])
  22.     {
  23.         if (y == 2) for (int i = x - 1; i >= 1 && !a[i][y]; -- i) a[i][y] = fil[i] = true;
  24.         else {pc ('D'), dfs (x - 1, y); return ;}
  25.     }
  26.     int _x = x, _y = x % 2 ? y + 1 : y - 1;
  27.     if (_y == 1)
  28.     {
  29.         if (x == n) {pc ('L'); ret (_x, _y); return ;}
  30.         pc ('G'), dfs (x + 1, y); return ;
  31.     }
  32.     if (_y == m + 1) {pc ('G'), dfs (x + 1, y); return ;}
  33.     if (a[_x][_y]) {pc ('G'), dfs (x + 1, y); return ;}
  34.     x % 2 ? pc ('P') : pc ('L');
  35.     dfs (_x, _y);
  36. }
  38. int main ()
  39. {
  40.     scanf ("%d%d%d", &n, &m, &K); int t1, t2;
  41.     swap (n, m);
  42.     REP (i, K) scanf ("%d%d", &t1, &t2), swap (t1, t2), a[t1][t2] = a[t1 + 1][t2] = a[t1][t2 + 1] = a[t1 + 1][t2 + 1] = true;
  43.     puts ("TAK");
  44.     dfs (1, 1);
  45.     return 0;
  46. }

AMMPPZ2014 glo

『我说啊，弱智是天生的么？』

枚举最小值Ai，预处理出其可行的区间，以及此区间中的最靠近i的两个最大值。

  1. # include <cstdio>
  2. # include <algorithm>
  3. using namespace std;
  4. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  5. # define REP_D(i, n) for (int i = n; i >= 1; -- i)
  6. # define NR 501000
  7. int n, a[NR], pl[NR], pr[NR], ml[NR], mr[NR], il[NR], ir[NR], ql[NR], qr[NR];
  8. const int inf = 1 << 30;
  9. pair <int, int> ans;
  10. template <class T0, class T1> bool RlxN (T0 &x, T1 y) {if (x > y) return x = y, true; return false;}
  11. template <class T0, class T1> bool RlxX (T0 &x, T1 y) {if (x < y) return x = y, true; return false;}
  12. int main ()
  13. {
  14.     scanf ("%d", &n);
  15.     pl[1] = ql[1] = 0, pr[n] = qr[n] = n + 1, ans = make_pair (-1, 1);
  16.     REP (i, n) ml[i] = mr[i] = -inf;
  17.     REP (i, n)
  18.     {
  19.         scanf ("%d", &a[i]);
  20.         if (i == 1) continue;
  21.         int j;
  22.         for (j = i - 1; j > 0 && a[j] > a[i]; j = pl[j])
  23.         {
  24.             if (a[j] > ml[i]) ml[i] = a[j], il[i] = j;
  25.             if (ml[j] > ml[i]) ml[i] = ml[j], il[i] = il[j];
  26.         }
  27.         pl[i] = j;
  28.         for (j = i - 1; j > 0 && a[j] < a[i]; j = ql[j]) ; 
  29.         ql[i] = j;
  30.     }
  31.     REP_D (i, n - 1)
  32.     {
  33.         int j;
  34.         for (j = i + 1; j <= n && a[j] > a[i]; j = pr[j])
  35.         {
  36.             if (a[j] > mr[i]) mr[i] = a[j], ir[i] = j;
  37.             if (mr[j] > mr[i]) mr[i] = mr[j], ir[i] = ir[j];
  38.         }
  39.         pr[i] = j;
  40.         for (j = i + 1; j <= n && a[j] < a[i]; j = qr[j]) ;
  41.         qr[i] = j;
  42.     }
  43.     REP (i, n)
  44.     {
  45.         int l0, l1, r0, r1;
  46.         if (ml[i] != mr[i]) ml[i] < mr[i] ? ml[i] = -inf : mr[i] = -inf;
  47.         l0 = l1 = pl[i] + 1, r0 = r1 = pr[i] - 1;
  48.         if (ml[i] != -inf) RlxX (l0, il[i] + 1), RlxX (l1, ql[il[i]] + 1);
  49.         if (mr[i] != -inf) RlxN (r0, ir[i] - 1), RlxN (r1, qr[ir[i]] - 1);
  50.         RlxN (ans, make_pair (-(r1 - l0 + 1), l0));
  51.         RlxN (ans, make_pair (-(r0 - l1 + 1), l1));
  52.     }
  53.     printf ("%d %d\n", -ans.first, ans.second);
  54.     return 0;
  55. }

AMPPZ2014 hit

题目愣是看错了两次想了三天T_T
直接导致自己毫无输出……（明明是自己的错啦……

去掉怨念以后题目还凑活吧。
枚举答案，显然只剩下⌊K2⌋个星号没填。

然后我们暴力枚举每个星号的状态，然后通过看出现位置之间的间隔是否超过答案来判定。
每个出现位置能匹配的状态数应该是O(1)的。
于是做一次的复杂度感觉是O(310+n)的。

应该就能过了……

  1. # include <cstdio>
  2. # include <cstring>
  3. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  4. # define NR 3010
  5. int q0, n, li[NR], lu[NR], lt[NR], len, m, lcp[NR], z, unk[NR][30];
  6. char s[NR], tmp[NR][30], a[NR], d[30];
  7. inline bool ec (char a, char b) {return a == b || a == '*' || b == '*';}
  8. bool check ()
  9. {
  10.     int last = 0;
  11.     REP (i, len)
  12.     {
  13.         if (li[i] - last > z) return false;
  14.         bool eql = true; REP (j, m) if (!ec (tmp[i][j], d[j])) {eql = false; break;}
  15.         if (eql) last = li[i];
  16.     }
  17.     return true;
  18. }
  19. bool dfs (int lv)
  20. {
  21.     if (lv > m) return check ();
  22.     d[lv] = 'R'; if (dfs (lv + 1)) return true;
  23.     d[lv] = 'G'; if (dfs (lv + 1)) return true;
  24.     d[lv] = 'B'; return dfs (lv + 1);
  25. }
  26. int main ()
  27. {
  28.     for (scanf ("%d", &q0); q0; -- q0)
  29.     {
  30.         scanf ("%s", s + 1), n = strlen (s + 1);
  31.         REP (i, n)
  32.         {
  33.             int j = 0; lu[i] = 0;
  34.             for (; i + j <= n && ec (s[1 + j], s[i + j]); ++ j) 
  35.                 if (s[1 + j] == '*') unk[i][++ lu[i]] = i + j;
  36.             lcp[i] = j;
  37.         }
  38.         bool succ = false;
  39.         for (z = 1; z < n; ++ z)
  40.         {
  41.             int last = 0, t = n - z + 1; bool fail = false;
  42.             if (lcp[t] < z) continue;
  43.             m = len = 0;
  44.             REP (i, z) {a[i] = s[i]; if (a[i] == '*') a[i] = s[n - z + i], m += s[n - z + i] == '*';}
  45.             REP (i, n - z + 1)
  46.             {
  47.                 if (i - last > z) {fail = true; break;}
  48.                 if (lcp[i] < z) continue;
  49.                 bool eql = true;
  50.                 REP (j, lu[t]) if (!ec (s[unk[i][j]], s[unk[t][j]])) {eql = false; break;}
  51.                 if (eql) 
  52.                 {
  53.                     li[++ len] = last = i; lt[len] = 0;
  54.                     REP (j, lu[t]) if (s[unk[t][j]] == '*') tmp[len][++ lt[len]] = s[unk[i][j]];
  55.                 }
  56.             }
  57.             if (fail) continue;
  58.             if (dfs (1))
  59.             {
  60.                 int j = 0;
  61.                 REP (i, z) putchar (a[i] == '*' ? d[++ j] : a[i]);
  62.                 succ = true; break;
  63.             }
  64.         }
  65.         if (!succ) REP (i, n) putchar (s[i] == '*' ? 'R' : s[i]);
  66.         putchar ('\n');
  67.     }
  68.     return 0;
  69. }

AMPPZ2014 ins

考虑拆环后用线段树维护。
对于一个区间考虑头的状态对整个区间的影响。
注意到最先开枪的后一个人的状态是确定的。

  1. # include <cstdio>
  2. # include <cstdlib>
  3. # include <algorithm>
  4. # include <vector>
  5. using namespace std;
  6. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  7. # define REP_0(i, n) for (int i = 0; i < n; ++ i)
  8. # define REP_V(it, s) for (vector <int>::iterator it = s.begin (); it != s.end (); ++ it)
  9. # define NR 201000
  10. typedef pair <int, int> Pii;
  11. typedef int Arr[3];
  12. Pii ap[NR];
  13. int ti[NR], tp[NR], ans[NR], n, q0, csz;
  14. struct Info
  15. {
  16.     Pii min; int s[3], c[3];
  17.     Info () {min = make_pair (0, 0), s[0] = s[1] = s[2] = c[0] = c[1] = c[2] = 0;}
  18.     Info (Pii _min, int _s0, int _s1, int _s2, int _c0, int _c1, int _c2)
  19.     {min = _min, s[0] = _s0, s[1] = _s1, s[2] = _s2, c[0] = _c0, c[1] = _c1, c[2] = _c2;}
  20. };
  21. # define NEXT_S(t) next[p][a.s[t]]
  22. # define u t[x]
  23. # define lc ch[0]
  24. # define rc ch[1]
  25. # define ulfc t[u.lc]
  26. # define urtc t[u.rc]
  27. # define w0 first
  28. # define w1 second
  29. struct Seg 
  30. {
  31.     int ch[2]; Info w;
  32.     inline void init (Pii min) {w.min = min, w.s[0] = 0, w.s[1] = 1, w.s[2] = 2, w.c[0] = 0, w.c[1] = 0, w.c[2] = 1;}
  33. };
  34. struct SegTree
  35. {
  36.     Seg *t;
  37.     Arr *next;
  38.     vector <int> id;
  39.     int root, sz, n, N;
  40.     Info merge (const Info &a, const Info &b, int p)
  41.     {
  42.         return p %= n, Info (min (a.min, b.min),
  43.             b.s[NEXT_S (0)], b.s[NEXT_S (1)], b.s[NEXT_S (2)],
  44.             a.c[0] + b.c[NEXT_S (0)], a.c[1] + b.c[NEXT_S (1)], a.c[2] + b.c[NEXT_S (2)]);
  45.     }
  46.     int build (int l, int r)
  47.     {
  48.         int x = ++ sz, mid = (l + r) >> 1;
  49.         if (l == r) return u.init (make_pair (ti[id[l % n]], l)), x;
  50.         return u.lc = build (l, mid), u.rc = build (mid + 1, r), u.w = merge (ulfc.w, urtc.w, mid), x;
  51.     }
  52.     void segUpd (int x, int l, int r, int p)
  53.     {
  54.         if (l == r) {u.w.min = make_pair (ti[id[l % n]], l); return ;}
  55.         int mid = (l + r) >> 1;
  56.         if (p <= mid) segUpd (u.lc, l, mid, p);
  57.         else segUpd (u.rc, mid + 1, r, p);
  58.         u.w = merge (ulfc.w, urtc.w, mid);
  59.     }
  60.     Info segQry (int x, int l, int r, int ql, int qr)
  61.     {
  62.         if (ql <= l && r <= qr) return u.w;
  63.         int mid = (l + r) >> 1;
  64.         if (qr <= mid) return segQry (u.lc, l, mid, ql, qr);
  65.         if (ql > mid) return segQry (u.rc, mid + 1, r, ql, qr);
  66.         return merge (segQry (u.lc, l, mid, ql, qr), segQry (u.rc, mid + 1, r, ql, qr), mid);
  67.     }
  68.     inline int getAns () {int p = t[root].w.min.w1; return segQry (root, 0, N, (p + 1) % n, (p + 1) % n + n - 1).c[0];}
  69.     inline int update (int r)
  70.     {
  71.         next[r][1] = next[r][2] = (ti[id[r % n]] > ti[id[(r + 1) % n]]);
  72.         int l = (r + n - 1) % n;
  73.         next[l][1] = next[l][2] = (ti[id[l % n]] > ti[id[(l + 1) % n]]);
  74.         return segUpd (root, 0, N, l), segUpd (root, 0, N, r), segUpd (root, 0, N, l + n), segUpd (root, 0, N, r + n), getAns ();
  75.     }
  76.     inline int init ()
  77.     {
  78.         n = id.size (), N = 2 * n - 1;
  79.         t = (Seg*) malloc ((4 * n + 10) * sizeof (Seg));
  80.         next = (Arr*) malloc ((n + 10) * sizeof (Arr));
  81.         REP_0 (i, n) ap[id[i % n]].w1 = i % n, next[i][0] = 2, next[i][1] = next[i][2] = (ti[id[i % n]] > ti[id[(i + 1) % n]]);
  82.         return root = build (0, N), getAns ();
  83.     }
  84. } sol[NR];
  86. int main ()
  87. {
  88.     scanf ("%d", &n); int sum = 0, t1, t2;
  89.     REP (i, n) scanf ("%d", &tp[i]);
  90.     REP (i, n) scanf ("%d", &ti[i]);
  91.     REP (i, n)
  92.     {
  93.         if (ap[i].w0) continue;
  94.         ap[i].w0 = ++ csz, sol[csz].id.clear (), sol[csz].id.push_back (i);
  95.         for (int j = tp[i]; j != i; j = tp[j]) sol[csz].id.push_back (j), ap[j].w0 = csz;
  96.         sum += (ans[csz] = sol[csz].init ());
  97.     }
  98.     printf ("%d\n", sum);
  99.     scanf ("%d", &q0);
  100.     REP (i, q0)
  101.     {
  102.         scanf ("%d%d", &t1, &t2), ti[t1] = t2;
  103.         int ts = ans[ap[t1].w0];
  104.         printf ("%d\n", sum += (ans[ap[t1].w0] = sol[ap[t1].w0].update (ap[t1].w1)) - ts);
  105.     }
  106.     return 0;
  107. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注