[关闭]
@Falsyta 2015-09-25T07:56:29.000000Z 字数 19327 阅读 2570

TCO 2013

OI TCO Topcoder

Level 3

虽然好累但是总算是写完了……
感觉老是看题解也不是事……还是去写写Level 1,2去放松下吧……

TCO13 Round 1A DirectionBoard

……注意到合法解应该是每个点出入度都为1。
然后建二分图就是最小权匹配了。

  1. # include <cstdio>
  2. # include <cstring>
  3. # include <algorithm>
  5. # define REP(i, n) for (int i = 1; i <= n; i ++)
  6. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  7. # define RST(a) memset (a, 0, sizeof (a))
  8. # define CLR(a, x) memset (a, x, sizeof (a))
  10. using namespace std;
  12. int dx[] = {-1, 1, 0, 0};
  13. int dy[] = {0, 0, -1, 1};
  15. template <class T0, class T1> bool RlxN (T0 &a, T1 b) {if (a > b) return a = b, true; return false;}
  16. template <class T0, class T1> bool RlxX (T0 &a, T1 b) {if (a < b) return a = b, true; return false;}
  18. const int inf = 1 << 30;
  20. # define P(i, j) ((i) * m + (j) + 1)
  21. # define PR 400
  23. class DirectionBoard
  24. {
  25. private:
  26.     int ord[400];
  27.     int g[PR][PR], lx[PR], ly[PR], match[PR], lack, N;
  28.     bool visx[PR], visy[PR];
  30.     bool Find (int x)
  31.     {
  32.         visx[x] = true; int t;
  33.         REP (y, N)
  34.         {
  35.             if (visy[y]) continue;
  36.             t = lx[x] + ly[y] - g[x][y];
  37.             if (t == 0)
  38.             {
  39.                 visy[y] = true;
  40.                 if (match[y] == -1 || Find (match[y]))
  41.                     return match[y] = x, true;
  42.             }
  43.             else RlxN (lack, t);
  44.         }
  45.         return false;
  46.     }
  48.     int KM ()
  49.     {
  50.         RST (lx), RST (ly), CLR (match, -1);
  51.         REP (i, N) REP (j, N) RlxX (lx[i], g[i][j]);
  52.         REP (x, N)
  53.         {
  54.             while (true)
  55.             {
  56.                 RST (visx), RST (visy), lack = inf;
  57.                 if (Find (x)) break;
  58.                 REP (i, N) 
  59.                 {
  60.                     if (visx[i]) lx[i] -= lack; 
  61.                     if (visy[i]) ly[i] += lack;
  62.                 }
  63.             }
  64.         }
  65.         int ans = 0;
  66.         REP (i, N) ans += g[match[i]][i];
  67.         return ans;
  68.     }
  71. public:
  72.     int getMinimum (vector <string> board)
  73.     {
  74.         int n = board.size (), m = board[0].length ();
  75.         ord['U'] = 0, ord['D'] = 1, ord['L'] = 2, ord['R'] = 3;
  76.         N = n * m;
  77.         REP (i, N) REP (j, N) g[i][j] = - 10000; 
  78.         REP_0 (i, n)
  79.         {
  80.             REP_0 (j, m)
  81.             {
  82.                 int _d = ord[board[i][j]];
  83.                 REP_0 (d, 4)
  84.                 {
  85.                     int mx = (i + dx[d] + n) % n, my = (j + dy[d] + m) % m;
  86.                     RlxX (g[P (i, j)][P (mx, my)], - (d != _d));
  87.                 }
  88.             }
  89.         }
  90.         return - KM ();
  91.     }
  92. };

TCO13 Round 1B EllysReversals

如果没有翻转前缀长度为偶数的限制则显然可以将串s中的字母任意排列。
加上限制也只不过是2i+1位要和2i+2位相邻而已（最后一位特殊处理）。

  1. # include <cstdio>
  2. # include <algorithm>
  3. # include <iostream>
  4. # include <string>
  5. # include <cstring>
  6. # include <set>
  8. using namespace std;
  10. class EllysReversals
  11. {
  12. private:
  13.     set <string> strSet;
  15.     string transform (string word)
  16.     {
  17.         string result;
  18.         vector <pair <char, char> > temp;
  19.         for (int i = 0; i < word.length (); i ++)
  20.         {
  21.             if (i % 2 == 0) continue;
  22.             char a = word[i - 1], b = word[i];
  23.             if (a > b) swap (a, b);
  24.             temp.push_back (make_pair (a, b));
  25.         }
  26.         sort (temp.begin (), temp.end ());
  27.         for (int i = 0; i < temp.size (); i ++)
  28.             result.push_back (temp[i].first), result.push_back (temp[i].second);
  29.         if (word.length () % 2 == 1)
  30.             result.push_back (word[word.length () - 1]);
  31.         return result;
  32.     }
  33. public:
  34.     int getMin (vector <string> words)
  35.     {
  36.         for (int i = 0; i < words.size (); i ++)
  37.         {
  38.             string str = transform (words[i]);
  39.             if (strSet.find (str) != strSet.end ())
  40.                 strSet.erase (str);
  41.             else
  42.                 strSet.insert (str);
  43.         }
  44.         return (int) strSet.size ();
  45.     }
  46. };

TCO13 Round 1C TheKnights

似乎忘了贴上的样子……
计算每个点被攻击到的概率就好了，然后就是大暴力嘛……
似乎当时着急回去上课把代码写得乱七八糟的……

  1. # include <cstdio>
  2. # include <cassert>
  3. # include <iostream>
  4. # include <algorithm>
  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 FOR(i, a, b) for (int i = a; i <= b; i ++)
  9. typedef double dd;
  10. typedef long double ld;
  11. ld max (ld a, ld b, ld c) {return max (a, max (b, c));}
  12. ld min (ld a, ld b, ld c) {return min (a, min (b, c));}
  13. class TheKnights
  14. {
  15. private:
  16.     double solve0 (ld n, ld a)
  17.     {
  18.         ld dx[] = {-a, -a, 0,  a,  a};
  19.         ld dy[] = {-a,  a, 0, -a,  a};
  20.         ld N = n * n;
  21.         ld t0 = 0, t1 = 0;
  22.         REP_0 (d, 5)
  23.         {
  24.             ld _x = dx[d], _y = dy[d];
  25.             t0 += max ((ld) 0, min (n, n - _x) - max ((ld) 1, 1 - _x) + 1) * max ((ld) 0, min (n, n - _y) - max ((ld) 1, 1 - _y) + 1); 
  26.         }
  27.         REP_0 (d0, 5)
  28.             FOR (d1, d0 + 1, 4)
  29.             {
  30.                 ld _x = dx[d0], __x = dx[d1], _y = dy[d0], __y = dy[d1];
  31.                 t1 += max ((ld) 0, min (n, n - _x, n - __x) - max ((ld) 1, 1 - _x, 1 - __x) + 1) * max ((ld) 0, min (n, n - _y, n - __y) - max ((ld) 1, 1 - _y, 1 - __y) + 1); 
  32.             }
  33.         return (dd) (2 * t0 / N - t1 * 2 / N / (N - 1));
  34.     }
  36. public:
  37.     double find (int _n, int _a, int _b)
  38.     {
  39.         if (_a == _b) return solve0 ((ld) _n, (ld) _a);
  40.         ld n = _n;
  41.         ld a = _a, b = _b;
  42.         ld dx[] = {-b, -b, -a, -a,  0,  a,  a,  b,  b};
  43.         ld dy[] = {-a,  a, -b,  b,  0, -b,  b, -a,  a};
  44.         ld N = n * n;
  45.         ld t0 = 0, t1 = 0;
  46.         REP_0 (d, 9)
  47.         {
  48.             ld _x = dx[d], _y = dy[d];
  49.             t0 += max ((ld) 0, min (n, n - _x) - max ((ld) 1, 1 - _x) + 1) * max ((ld) 0, min (n, n - _y) - max ((ld) 1, 1 - _y) + 1); 
  50.         }
  51.         REP_0 (d0, 9)
  52.             FOR (d1, d0 + 1, 8)
  53.             {
  54.                 ld _x = dx[d0], __x = dx[d1], _y = dy[d0], __y = dy[d1];
  55.                 t1 += max ((ld) 0, min (n, n - _x, n - __x) - max ((ld) 1, 1 - _x, 1 - __x) + 1) * max ((ld) 0, min (n, n - _y, n - __y) - max ((ld) 1, 1 - _y, 1 - __y) + 1); 
  56.             }
  57.         return (dd) (2 * t0 / N - t1 * 2 / N / (N - 1));
  58.     }
  59. };

TCO13 Round 2A ThePowers

然而不对着题解估计还是写不出来…………
考虑将可能算重的X化为gk。
对于每个可能的g，考虑算不同的gkY的个数。
显然不同的g之间相互独立，则转化为k∈[1,loggA],Y∈[1,B]的不同的kY个数。
容斥计算，为了方便计算可以将kY的取值分成[1,loggA]段计算，每一段计算((i−1)B,iB]的个数。

  1. # include <cstdio>
  2. # include <cstring>
  3. # include <cassert>
  4. # include <algorithm>
  5. # include <iostream>
  6. using namespace std;
  7. typedef long long ll;
  8. # define REP(i, n) for (int i = 1; i <= n; i ++)
  9. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  10. # define FOR(i, a, b) for (int i = a; i <= b; i ++)
  11. # define CLR(a, x) memset (a, x, sizeof (a))
  12. class ThePowers
  13. {
  14. private:
  15.     int pl[100], psz;
  16.     int bitc[1 << 15], dn[1 << 15];
  17.     ll rec[50], lcm[1 << 15];
  18.     template <class T> T gcx (T a, T b) 
  19.     {
  20.         if (a < b) swap (a, b);
  21.         return !b ? a : gcx (b, a % b);
  22.     }
  23.     bool check (int n)
  24.     {
  25.         int d = -1;
  26.         for (int i = 2; i * i <= n; i ++)
  27.         {
  28.             if (n % i != 0) continue;
  29.             int q = 0;
  30.             while (n % i == 0) n /= i, q ++;
  31.             if (d == -1) d = q;
  32.             else d = gcx (d, q);
  33.         }
  34.         if (n > 1) return true;
  35.         else return d == 1;
  36.     }
  37.     ll calc (ll L, ll R)
  38.     {
  39.         int M = 1 << psz;
  40.         ll res = 0;
  41.         lcm[0] = 1;
  42.         REP (s, M - 1)
  43.         {
  44.             lcm[s] = lcm[s - (s & -s)] * pl[dn[s & -s]] / gcx (lcm[s - (s & -s)], (ll) pl[dn[s & -s]]);
  45.             if (bitc[s] & 1) res += R / lcm[s] - L / lcm[s];
  46.             else res -= R / lcm[s] - L / lcm[s];
  47.         }
  48.         return res;
  49.     }
  50.     ll solve (int n, int m)
  51.     {
  52.         if (rec[n] != -1) return rec[n];
  53.         ll &s = rec[n]; s = 0;
  54.         REP (i, n)
  55.         {
  56.             psz = 0;
  57.             FOR (j, i, n)
  58.             {
  59.                 bool succ = true;
  60.                 FOR (k, i, j - 1) if (j % k == 0) {succ = false; break;}
  61.                 if (succ) pl[++ psz] = j;
  62.             }
  63.             s += calc (1ll * (i - 1) * m, 1ll * i * m);
  64.         }
  65.         return s;
  66.     }
  67. public:
  68.     ll find (int n, int m)
  69.     {
  70.         int _s = sqrt (n), M = 1 << 15;
  71.         CLR (rec, -1);
  72.         ll ans = m - 1;
  73.         REP (i, M - 1) bitc[i] = bitc[i - (i & - i)] + 1;
  74.         REP_0 (i, 15) dn[1 << i] = i + 1;
  75.         FOR (i, 2, _s)
  76.         {
  77.             if (!check (i)) continue;
  78.             int q = 0, t = 1;
  79.             while (1ll * t * i <= n) t *= i, q ++;
  80.             ans += 1ll * q * m - solve (q, m);
  81.         }
  82.         return 1ll * n * m - ans;
  83.     }
  84. };

TCO 2013 Round 2B LitPanels

考虑枚举一个长方形卡住它。
剩下的就是分类讨论大暴力了。
虽然不知道题解为什么写的是容斥……
时间复杂度O(N2)。

  1. # include <cstdio>
  2. # include <cassert>
  3. # include <iostream>
  4. # include <algorithm>
  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. const int P = 1000000007;
  9. class LitPanels
  10. {
  11. private:
  12.     int n, m, a, b;
  13.     int pw2[2000];
  14.     int calc (int sq)
  15.     {
  16.         int res = 0;
  17.         REP_0 (s, 4)
  18.         {
  19.             int cnt = (s >> 1 & 1) + (s & 1), _q = sq, tmp = 1;
  20.             REP (t, 2 - cnt) _q -= a + b - 2, tmp = 1ll * tmp * (pw2[a - 1] + P - 1) % P * (pw2[b - 1] + P - 1) % P;
  21.             res = (res + 1ll * tmp * pw2[_q]) % P;
  22.         }
  23.         return res;
  24.     }
  26.     int calc0 (int sq, int x, int y)
  27.     {
  28.         int res = 0;
  29.         REP_0 (s, 16)
  30.         {
  31.             bool c0 = s & 1, c1 = s >> 1 & 1, c2 = s >> 2 & 1, c3 = s >> 3;
  32.             int tmp = 1, _q = sq;
  33.             if (!c0 && !c3) tmp = 1ll * tmp * (pw2[x - 2] + P - 1) % P, _q -= x - 2;
  34.             if (!c1 && !c2) tmp = 1ll * tmp * (pw2[x - 2] + P - 1) % P, _q -= x - 2;
  35.             if (!c0 && !c1) tmp = 1ll * tmp * (pw2[y - 2] + P - 1) % P, _q -= y - 2;
  36.             if (!c2 && !c3) tmp = 1ll * tmp * (pw2[y - 2] + P - 1) % P, _q -= y - 2;
  37.             res = (res + 1ll * tmp * pw2[_q]) % P;
  38.         }
  39.         return res;
  40.     }
  41. public:
  42.     int countPatterns (int _n, int _m, int _a, int _b)
  43.     {
  44.         n = _n, m = _m, a = _a, b = _b;
  45.         int ans = 1;
  46.         pw2[0] = 1;
  47.         REP (i, n * m) pw2[i] = (pw2[i - 1] << 1) % P;
  48.         REP (i, n)
  49.             REP (j, m)
  50.             {
  51.                 int res = 0;
  52.                 if (i == 1 && j == 1) res = 1;
  53.                 else if (i == 1) res = pw2[min (j, b * 2) - 2];
  54.                 else if (j == 1) res = pw2[min (i, a * 2) - 2];
  55.                 else if (i <= a || j <= b) res = calc0 (min (a * 2, i) * min (b * 2, j) - 4, min (a * 2, i), min (b * 2, j));
  56.                 else if (a < i && i < a * 2 && b < j && j < b * 2)
  57.                 {
  58.                     res = calc (i * j - 2 * (i - a) * (j - b) - 2) << 1;
  59.                     if (res >= P) res -= P;
  60.                     int _a = (a << 1) - i, _b = (b << 1) - j,
  61.                         ta = pw2[_a] + P - 1, 
  62.                         tb = pw2[_b] + P - 1, 
  63.                         tc = pw2[_a * j + _b * i - _a * _b - _a * 2 - _b * 2];
  64.                     if (ta >= P) ta -= P; if (tb >= P) tb -= P;
  65.                     res -= 1ll * ta * ta % P * tb % P * tb % P * tc % P;
  66.                     if (res >= P) res -= P;
  67.                     if (res < 0) res += P;
  68.                 }
  69.                 else if (i >= a * 2 || j >= b * 2) {res = calc (a * b * 2 - 2) << 1; if (res >= P) res -= P;}
  70.                 else assert (0);
  71.                 ans = (ans + 1ll * (n - i + 1) * (m - j + 1) * res) % P;
  72.             }
  74.         return ans;
  75.     }
  76. };

TCO13 Round 2C WellTimedSearch

…………显然枚举第i层节点就好了……

  1. # include <cstdio>
  2. # include <algorithm>
  3. # define REP(i, n) for (int i = 1; i <= n; i ++)
  4. # define REP_D(i, n) for (int i = n; i >= 1; i --)
  5. # define FOR(i, a, b) for (int i = a; i <= b; i ++)
  6. using namespace std;
  7. typedef double dd;
  8. class WellTimedSearch
  9. {
  10. public:
  11.     double getProbability (int n, int l, int r)
  12.     {
  13.         dd ans = 0;
  14.         REP (i, n)
  15.         {
  16.             int t = i, rem = n - i, wst = 0;
  17.             REP_D (j, l - 1) 
  18.             {
  19.                 t = (t + 1) >> 1; 
  20.                 if (t == 1) {rem -= j, wst += j; break;}
  21.                 rem -= t, wst += t;
  22.             }
  23.             if (t != 1 || rem < 0) return ans;
  24.             t = i;
  25.             FOR (j, l + 1, r)
  26.             {
  27.                 t <<= 1, rem -= min (rem, t);
  28.                 if (!rem) break;
  29.             }
  30.             wst += rem;
  31.             ans = max (ans, (dd) (n - wst) / n);
  32.         }
  33.         return ans;
  34.     }
  35. };

TCO 2013 Round 3A TrickyInequality

似乎这是TCO13最难的题了……

太可怕了…………
我们从头来。
为了方便在这里贴出用到的公式：

xn−=∑k=0n(−1)n−k[nk]xk(1)

xn=∑k{nk}xk−(2)

Δnf(x)=∑i=0dci(xi−n)其中f(x)=∑i=0dci(xi)(3)

考虑容斥， 显然答案为∑nk=0(−1)k(nk)(s−ktm)
(−1)k(nk)不好化简，我们考虑n阶差分，显然有

Δnf(x)=∑k=0n(−1)n−k(nk)f(x+k)

稍加处理就得到我们需要的形式，令f(x)=(s−xtm)，所求即Δnf(0)：
对差分的常用技巧是将其转化为牛顿级数，我们先试图将f(x)转化成一个多项式，然后再转化成牛顿级数。
下降幂可以用斯特林数很容易地转化成多项式（公式 (1)）：
(s−xtm)=1m!∑j=0mxj∑i=jm(−1)m−i+j(ij)[mi]tjsi−j

继续转化多项式（利用公式(2)），令多项式中xi的系数为ai。

∑i=0maixi=∑j=0m(xj)∑i=jmai{ij}j!

于是得到牛顿级数，令(xi)的系数为bi，则bn为所求（公式(3)）。
将ai代入，最终得到：

∑k=0n(−1)k(nk)(s−ktm)=n!(−1)n+mtnm!∑i=0m−n∑j=0m−n−i(−1)j(n+i+jj){n+in}[mn+i+j]tisj

最后只剩下计算快速斯特林数的问题了，注意到有n+i−n≤100,m−n−i−j≤100。
我们考虑斯特林数的组合意义。
第二类斯特林数表示将n个元素分为k个非空子集的方案数。
容易发现至多只有n−k个子集的大小大于1。
我们暴力枚举大于1的子集个数，则有：

{nk}=∑i=0n−k(nn−k+i)g(n−k+i,i)

其中g(n,k)为将n个元素分为k个大小大于1的子集的方案数。
考虑第n个元素要么与此前一个元素一起成为一个新集合，要么加入之前的集合，则有g(n,k)=kg(n−1,k)+(n−1)g(n−2,k−1)

第一类斯特林数表示将n个元素分为k个非空环排列的方案数。
类似第二类斯特林数，有

[nk]=∑i=0n−k(nn−k+i)f(n−k+i,i)

其中g(n,k)为将n个元素分为k个大小大于1的环排列的方案数。
我们用一个序列表示这些环排列，每个环排列我们令其中最小的元素排在第一个，排列之间用一个特殊元素分割，考虑第n个元素要么与此前一个元素一起成为一个新环排列，要么插入之前的环排列构成的序列，则有：f(n,k)=(n−1)f(n−1,k)+(n−1)f(n−2,k−1)

因此最终复杂度为O((m−n)2)。

太可怕了…………

  1. # include <cstdio>
  2. # include <cassert>
  3. # include <iostream>
  4. # include <algorithm>
  6. using namespace std;
  8. # define REP(i, n) for (int i = 1; i <= n; i ++)
  9. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  10. # define REP_0N(i, n) for (int i = 0; i <= n; i ++)
  11. # define FOR(i, a, b) for (int i = a; i <= b; i ++)
  13. typedef long long ll;
  15. # define P 1000000007
  16. # define NR 500
  18. class TrickyInequality
  19. {
  20. private:
  21.     int f[NR][NR], g[NR][NR], stir1[NR], stir2[NR], iv[NR];
  22.     int n, m;
  24.     inline int Pow (int a, int z)
  25.     {
  26.         int s = 1;
  27.         do {if (z & 1) s = 1ll * s * a % P; a = 1ll * a * a % P;} while (z >>= 1);
  28.         return s;
  29.     }
  30.     inline int inv (int x) {return x <= 4 * (n - m) + 10 ? iv[x] : Pow (x, P - 2);}
  31.     int calc (int n, int m, int a[NR][NR])
  32.     {
  33.         int res = 0, _bi = 1;
  34.         REP (i, n - m) _bi = 1ll * _bi * (n - i + 1) % P * inv (i) % P;
  35.         REP_0N (i, n - m)
  36.         {
  37.             res = (res + 1ll * a[n - m + i][i] * _bi) % P;
  38.             _bi = 1ll * _bi * (m - i) % P * inv (n - m + i + 1) % P;
  39.         }
  40.         return res;
  41.     }
  42.     void init (int n, int a, int b)
  43.     {
  44.         REP (i, n) iv[i] = Pow (i, P - 2);
  45.         f[0][0] = g[0][0] = 1;
  46.         REP (i, n)
  47.             REP (j, n)
  48.             {
  49.                 f[i][j] = 1ll * f[i - 1][j] * (i - 1) % P;
  50.                 g[i][j] = 1ll * g[i - 1][j] * j % P;
  51.                 if (i > 1)
  52.                     f[i][j] = (f[i][j] + 1ll * f[i - 2][j - 1] * (i - 1)) % P, 
  53.                     g[i][j] = (g[i][j] + 1ll * g[i - 2][j - 1] * (i - 1)) % P;
  54.             }
  56.         REP_0N (i, n) stir1[i] = calc (b, a + i, f);
  57.         REP_0N (i, n) stir2[i] = calc (a + i, a, g);
  58.     }
  60. public:
  61.     int countSolutions (ll s, int t, int _n, int _m)
  62.     {
  63.         n = _n, m = _m, s %= P;
  64.         init ((m - n) * 2 + 10, n, m);
  65.         int _a = Pow (t, n);
  66.         FOR (i, n + 1, m) _a = 1ll * _a * inv (i) % P;
  67.         if ((n + m) % 2 == 1) _a = P - _a;
  68.         int _tp = 1, res = 0;
  69.         REP_0N (i, m - n)
  70.         {
  71.             int _si = 1, _sp = 1, _bi = 1, tmp = 0;
  72.             REP_0N (j, m - n - i)
  73.             {
  74.                 tmp = (tmp + 1ll * _si * _bi % P * stir1[i + j] % P * _sp) % P;
  75.                 _bi = 1ll * _bi * (n + i + j + 1) % P * inv (j + 1) % P;
  76.                 _sp = 1ll * _sp * s % P;
  77.                 _si = P - _si;
  78.             }
  79.             res = (res + 1ll * tmp * stir2[i] % P * _tp) % P;
  80.             _tp = 1ll * _tp * t % P;
  81.         }
  82.         return 1ll * res * _a % P;
  83.     }
  84. };

TCO 2013 Round 3B ToastJumping

考虑一个向量的时候f(x)=⌊D−x2−−−−−−√⌋上的整点构成的凸壳。
可以证明N个向量的时候凸壳是与1个向量时相似的。
我的民科证法是
考虑对于一个凸壳上的点P，不存在凸壳上异于P的点A,B，使得OA−→−+OB−→−与OP共线且，|OA−→−+OB−→−|>2|OP−→−|，画一画似乎可以发现因为是凸的所以显然……

  1. # include <cstdio>
  2. # include <cmath>
  3. # include <iostream>
  4. # include <algorithm>
  5. # include <vector>
  6. # define REP(i, n) for (int i = 1; i <= n; i ++)
  7. # define REP_0N(i, n) for (int i = 0; i <= n; i ++)
  8. using namespace std;
  9. typedef long double ld;
  10. typedef long long ll;
  11. typedef pair <int, int> poi;
  12. const ll lnf = 1ll << 61;
  13. class ToastJumping
  14. {
  15. private:
  16.     poi po[1000000];
  17.     int pl;
  18. # define _x first
  19. # define _y second
  20.     ll proc (ll a, ld b) {if (a - b > 0.99999999) return a - 1; return a;}
  21.     inline bool check (poi a, poi b, poi c) {return 1ll * (b._x - a._x) * (c._y - a._y) >= 1ll * (c._x - a._x) * (b._y - a._y);}
  22.     int solve (int X, int Y, int D)
  23.     {
  24.         int s = sqrt (D + 0.000001);
  25.         pl = 0;     
  26.         REP_0N (x, s)
  27.         {
  28.             poi t = make_pair (x, (int) (sqrt (D - x * x) + 0.00001));
  29.             while (pl >= 2 && check (po[pl - 1], po[pl], t)) pl --;
  30.             po[++ pl] = t;
  31.         }
  32.         ll ans = lnf;
  33.         REP (i, pl - 1)
  34.         {
  35.             ld k = (ld) (po[i + 1].second - po[i].second) / (po[i + 1].first - po[i].first), b = po[i].second - po[i].first * k;
  36.             ll _l = max (1ll * (X + po[i + 1].first - 1) / po[i + 1].first, proc (ceil ((Y - k * X) / b), (Y - k * X) / b)), _r = lnf;
  37.             if (po[i].first > 0) _r = min (_r, 1ll * X / po[i].first);
  38.             if (_l <= _r) ans = min (ans, _l);
  39.         }
  40.         return (int) ans;
  41.     }
  42. public:
  43.     vector <int> minJumps (vector <int> x, vector <int> y, vector <int> d)
  44.     {
  45.         vector <int> answer;
  46.         for (int i = 0; i < x.size (); i ++) answer.push_back (solve (abs (x[i]), abs (y[i]), d[i]));
  47.         return answer;
  48.     }
  49. };

TCO 2013 Semifinal 1 GameWithTree

首先这个博弈状态形成DAG是显然的。
…………考虑全白的子树强制第一步选根的SG值为2d（d为子树最大深度）。
黑点显然是各儿子子树SG值的异或和。
考虑根为白点的子树。
结论：根为白点的子树的SG值为各儿子子树SG值的异或和再异或2d。

证明：
考虑利用SG函数的定义用数学归纳法证明。

假设我们正在证明某个“各儿子子树SG值的异或和再异或2d”的值为S的状态，且其后继状态都已被证明。

（对于根被选中的后继状态显然是对的）

令“各儿子子树SG值的异或和”为T。
考虑根未被选中的状态。
对于0≤X<2d的SG值X显然可以选根得到。
对于2d≤X<S的SG值X，我们可以将根忽略不计，只在儿子中进行操作。
因此对于0≤X<S的状态都可以被达到。

下面证明SG值S不能被达到。
假设可以达到某状态Z，其SG值为S。
由于状态Z可以被到达，所以对于状态Z结论是对的。
则状态Z中根必然未被选中，因为容易得到T<2d，
于是我们将状态Z中的根去掉得到状态Z′，可知Z′的SG值为T，显然违反了SG的定义。

证毕。（好民科啊T_T………………

算了应该是对的……

  1. # include <cstdio>
  2. # include <iostream>
  3. # include <algorithm>
  4. # include <vector>
  5. # include <string>
  6. using namespace std;
  7. struct Edge {int y, frt; void Set (int yr, int fr) {y = yr, frt = fr;}};
  8. typedef long long ll;
  9. # define v g[i].y
  10. # define NR 1000
  11. class GameWithTree
  12. {
  13. private:
  14.     Edge g[NR];
  15.     int pos[NR], dep[NR], gsz;
  16.     ll f[NR];
  17.     bool col[NR];
  18.     void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
  19.     void DFS (int x)
  20.     {
  21.         for (int i = pos[x]; i; i = g[i].frt)
  22.         {
  23.             DFS (v);
  24.             dep[x] = max (dep[x], dep[v]);
  25.             f[x] ^= f[v];
  26.         }
  27.         if (!col[x]) f[x] ^= 1ll << dep[x];
  28.         dep[x] ++;
  29.     }
  30. public:
  31.     string winner (vector <int> parent, string color)
  32.     {
  33.         for (int i = 0; i < parent.size (); i ++)
  34.             AE (parent[i] + 1, i + 2);
  35.         for (int i = 0; i < color.length (); i ++)
  36.             col[i + 1] = color[i] == 'B';
  37.         string answer;
  38.         DFS (1);
  39.         if (f[1] > 0) answer = "Masha";
  40.         else answer = "Petya";
  41.         return answer;
  42.     }
  43. };

TCO 2013 Semifinal 2 OneBlack

可以发现无障碍的话就是要求一个把左上和右下隔开的方案。
有障碍的话把障碍缩点，统计左下到右上的路径就好。
一手贱把O(N2)写成O(N4)了……

  1. # include <cstdio>
  2. # include <iostream>
  3. # include <algorithm>
  4. # include <cassert>
  5. # include <string>
  6. # include <vector>
  7. using namespace std;
  8. # define REP(i, n) for (int i = 1; i <= n; i ++)
  9. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  10. # define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
  11. int dx[] = {-1, -1, -1,  0,  0,  1,  1,  1};
  12. int dy[] = {-1,  0,  1, -1,  1, -1,  0,  1};
  13. # define NR 60
  14. # define PR 2000
  15. # define P 1000000007
  16. class OneBlack
  17. {
  18. private:
  19.     int f[PR], in[PR], q[PR], S, T;
  20.     int n, m, col[NR][NR], csz;
  21.     bool v1[NR][NR], v2[NR][NR], del[NR][NR], mp[NR][NR], g[PR][PR];
  22.     inline void AE (int x, int y) {if (!g[x][y]) in[y] ++, g[x][y] = true;}
  23.     inline int poi (int x, int y)
  24.     {
  25.         if (x < 1 || x > n || y < 1 || y > m) return -1;
  26.         return (x - 1) * m + y;
  27.     }
  28.     void dfs1 (int x, int y) {if (poi (x, y) == -1 || v1[x][y] || mp[x][y]) return ; v1[x][y] = 1, dfs1 (x + 1, y), dfs1 (x, y + 1);}
  29.     void dfs2 (int x, int y) {if (poi (x, y) == -1 || v2[x][y] || mp[x][y]) return ; v2[x][y] = 1, dfs2 (x - 1, y), dfs2 (x, y - 1);}
  30.     void dfs3 (int x, int y, int c)
  31.     {
  32.         if (poi (x, y) == -1 || col[x][y] || !del[x][y]) return ;
  33.         col[x][y] = c; REP_0 (d, 8) dfs3 (x + dx[d], y + dy[d], c);
  34.     }
  35.     int Topo ()
  36.     {
  37.         int h = 1, t = 0, N = 2 * n * m + 2;
  38.         q[++ t] = S, f[S] = 1;
  39.         while (h <= t)
  40.         {
  41.             int x = q[h ++];
  42.             REP (v, N)
  43.             {
  44.                 if (!g[x][v]) continue;
  45.                 f[v] += f[x]; if (f[v] >= P) f[v] -= P;
  46.                 if (!(-- in[v])) q[++ t] = v;
  47.             }
  48.         }
  49.         return f[T];
  50.     }
  51.     inline int gridId (int i, int j) {return del[i][j] ? col[i][j] : (csz + poi (i, j));}
  52. public:
  53.     int countColorings (vector <string> grid)
  54.     {
  55.         n = grid.size (), m = grid[0].length (), S = 2 * n * m + 1, T = 2 * n * m + 2;
  56.         int _a = 1;
  57.         REP (i, n) REP (j, m) mp[i][j] = grid[i - 1][j - 1] == '#';
  58.         dfs1 (1, 1), dfs2 (n, m);
  59.         REP (i, n) REP (j, m) del[i][j] = !v1[i][j] || !v2[i][j] || mp[i][j];
  60.         REP (i, n) REP (j, m) if (!col[i][j] && del[i][j]) dfs3 (i, j, ++ csz);
  61.         REP (i, n) 
  62.         {
  63.             if (del[i][1] || !del[i + 1][1]) AE (S, gridId (i, 1)); 
  64.             if (del[i][m] || !del[i - 1][m]) AE (gridId (i, m), T);
  65.         }
  66.         REP (i, m) 
  67.         {
  68.             if (del[1][i] || !del[1][i + 1]) AE (gridId (1, i), T); 
  69.             if (del[n][i] || !del[n][i - 1]) AE (S, gridId (n, i));
  70.         }
  71.         REP (i, n)
  72.             REP (j, m)
  73.             {
  74.                 int x = poi (i, j);
  75.                 if (del[i][j])
  76.                 {
  77.                     int y = poi (i - 1, j);
  78.                     if (y != -1 && !del[i - 1][j]) AE (col[i][j], csz + y);
  79.                     y = poi (i, j + 1);
  80.                     if (y != -1 && !del[i][j + 1]) AE (col[i][j], csz + y);
  81.                     y = poi (i - 1, j + 1);
  82.                     if (y != -1 && !del[i - 1][j + 1]) AE (col[i][j], csz + y);
  83.                     if (!mp[i][j]) {_a = _a << 1; if (_a >= P) _a -= P;}
  84.                 }
  85.                 else
  86.                 {
  87.                     int y = poi (i - 1, j + 1);
  88.                     if (y != -1) 
  89.                     {
  90.                         if (del[i - 1][j + 1]) AE (csz + x, col[i - 1][j + 1]);
  91.                         else if (!del[i - 1][j] && !del[i][j + 1]) AE (csz + x, csz + y);
  92.                     }
  93.                     y = poi (i - 1, j);
  94.                     if (y != -1 && del[i - 1][j]) AE (csz + x, col[i - 1][j]);
  95.                     y = poi (i, j + 1);
  96.                     if (y != -1 && del[i][j + 1]) AE (csz + x, col[i][j + 1]);
  97.                 }
  98.             }   
  99.         return 1ll * _a * Topo () % P;
  100.     }
  101. };

TCO 2013 Wildcard SemiMultiple

本来打算写强行DP搞的……写了三节课以后还是决定弃疗写“循环逆卷积（雾）？”……
反正就是想办法把可以改的位抠出来……
目前还不知道为什么这是对的…………
休息去想想……

  1. # include <cstdio>
  2. # include <cstring>
  3. # include <iostream>
  4. # include <cassert>
  6. using namespace std;
  8. # define REP(i, n) for (int i = 1; i <= n; i ++)
  9. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  10. # define REP_0N(i, n) for (int i = 0; i <= n; i ++)
  11. # define FOR(i, a, b) for (int i = a; i <= b; i ++)
  12. # define Mo(a) if ((a) >= 1000000007) a -= 1000000007;
  13. # define RST(a) memset (a, 0, sizeof (a))
  14. # define mod 1000000007
  16. # define NR 2010
  18. class SemiMultiple
  19. {
  20. private:
  21.     int bi[NR][NR], f[NR][NR], pw[NR], cnt[NR], g[NR], tv[NR];
  22.     int n, m;
  24.     void inv (int t)
  25.     {
  26.         int sum = 0;
  27.         REP_0 (i, m) {sum += g[i]; Mo (sum);}
  28.         if (sum % 2 == 1) sum = (sum + mod) / 2;
  29.         else sum >>= 1;
  30.         for (int i = 1; i < m; i += 2) {sum += mod - g[(i + 1) * t % m]; Mo (sum);}
  31.         tv[0] = sum;
  32.         REP_0 (i, m - 1) tv[(i + 1) * t % m] = (g[(i + 1) * t % m] - tv[i * t % m] + mod) % mod;
  33.         REP_0 (i, m) g[i] = tv[i];  
  34.     }
  36.     int solve ()
  37.     {
  38.         bi[0][0] = f[0][0] = pw[0] = 1;
  39.         REP (i, n) 
  40.         {
  41.             pw[i] = pw[i - 1] * 2 % m, cnt[pw[i - 1]] ++, bi[i][0] = 1;
  42.             REP (j, n) {bi[i][j] = bi[i - 1][j - 1] + bi[i - 1][j]; Mo (bi[i][j]);}
  43.         }
  44.         REP (i, n) REP_0 (j, m) {f[i][j] = f[i - 1][j] + f[i - 1][(j - pw[n - i] + m) % m]; Mo (f[i][j]);}
  45.         if (m == 1) return 0;
  46.         if (n <= 0) return 0;
  47.         if (n == 1) return 1;
  48.         int res = 0;
  49.         REP (i, m - 1)
  50.         {
  51.             if (!cnt[i] && !cnt[m - i]) continue;
  52.             REP_0 (j, m) g[j] = f[n][j];
  53.             REP (j, cnt[i]) inv (i);
  54.             REP (j, cnt[m - i]) inv (m - i);
  55.             REP_0N (c0, cnt[i])
  56.                 REP_0N (c1, cnt[m - i])
  57.                 {
  58.                     if (!c0 && c1 == cnt[m - i]) continue;
  59.                     res = (res + 1ll * bi[cnt[i]][c0] * bi[cnt[m - i]][c1] % mod * g[(i - c0 * i % m - c1 * (m - i) % m + m + m) % m]) % mod;
  60.                 }
  61.         }
  62.         return res;
  63.     }
  65. public:
  66.     int count (int _n, int _m)
  67.     {
  68.         int t = 0;
  69.         while (_m % 2 == 0) _m >>= 1, t ++;
  70.         m = _m, n = max (_n - t, 0);
  71.         return (solve () + 1ll * min (_n, t) * f[n][0]) % mod;
  72.     }
  73. };

TCO 2013 Finals TBlocks

似乎没有想象中恶心……
分类讨论距离不大于2的格子，可以发现，相邻的情况和在斜的情况都很简单，只有相距两格有问题。
按照相邻两格建图，对于一个点数为N的连通块，考虑贡献：
只有一个环：1
只有一个相邻情况：1
只有一个斜情况：2
无环无相邻情况无斜情况：3N+1
其他：0

  1. # include <cstdio>
  2. # include <cstring>
  3. # include <algorithm>
  4. # include <vector>
  5. # include <string>
  6. # include <iostream>
  7. # define REP(i, n) for (int i = 1; i <= n; i ++)
  8. # define REP_0(i, n) for (int i = 0; i < n; i ++)
  9. # define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
  10. using namespace std;
  11. # define v g[i].y
  12. # define P 1000000007
  13. int dx0[] = {-1, 0, 1, 0};
  14. int dy0[] = {0, -1, 0, 1};
  15. int dx1[] = {-1, -1,  1,  1};
  16. int dy1[] = {-1,  1, -1,  1};
  17. # define NR 60
  18. # define PR 2600
  19. struct Edge {int y, frt; void Set (int yr, int fr) {y = yr, frt = fr;}} g[PR * 50];
  20. class TBlocks
  21. {
  22. private:
  23.     bool mp[NR][NR], vis[PR];
  24.     int z[PR], pos[PR], gsz, n, m, __poc;
  25.     void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
  26.     inline bool vaild (int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m;}
  27.     inline int poi (int x, int y) {return (x - 1) * m + y;}
  28.     int dfs (int x, int pre)
  29.     {
  30.         __poc ++, vis[x] = true;
  31.         int res = z[x], rc = 0;
  32.         REP_G (i, x)
  33.         {
  34.             if (v == pre) continue;
  35.             if (vis[v]) rc ++;
  36.             else
  37.             {
  38.                 int ty = dfs (v, x);        
  39.                 if (!ty) continue;
  40.                 else if (ty < -1) rc += -ty - 1;
  41.                 else if (res != 0) res = -1;
  42.                 else res = ty;
  43.             }
  44.         }
  45.         if (rc > 2) return -1;
  46.         if (rc > 0) return res != 0 ? -1 : -1 - rc;
  47.         return res;
  48.     }
  49.     int solve ()
  50.     {
  51.         gsz = 0;
  52.         REP (i, n * m) z[i] = pos[i] = 0, vis[i] = false;
  53.         REP (i, n)
  54.             REP (j, m)
  55.             {
  56.                 if (!mp[i][j]) continue;
  57.                 int u = poi (i, j);     
  58.                 REP_0 (d, 4)
  59.                     if (!vaild (i + dx0[d], j + dy0[d]) || mp[i + dx0[d]][j + dy0[d]])
  60.                     {
  61.                         if (z[u]) return 0;
  62.                         z[u] = 1;
  63.                     }
  65.                 REP_0 (d, 4) 
  66.                     if (vaild (i + dx1[d], j + dy1[d]) && mp[i + dx1[d]][j + dy1[d]]) 
  67.                     {
  68.                         if (z[u]) return 0;
  69.                         z[u] = 2;
  70.                     }
  72.                 REP_0 (d, 4) 
  73.                     if (vaild (i + dx0[d] * 2, j + dy0[d] * 2) && mp[i + dx0[d] * 2][j + dy0[d] * 2]) 
  74.                         AE (u, poi (i + dx0[d] * 2, j + dy0[d] * 2));
  75.             }
  76.         int res = 1, cnt2 = 0;
  77.         REP (i, n)
  78.             REP (j, m)
  79.             {
  80.                 if (!mp[i][j] || vis[poi (i, j)]) continue;
  81.                 __poc = 0; int ty = dfs (poi (i, j), 0);
  82.                 if (ty == -1) return 0;
  83.                 if (ty == -2 || ty == -3) {res <<= 1; if (res >= P) res -= P;}
  84.                 if (ty == 2) cnt2 ++;
  85.                 if (!ty) res = 1ll * res * (3 * __poc + 1) % P;
  86.             }
  87.         REP (i, cnt2 / 2) {res <<= 1; if (res >= P) res -= P;}
  88.         return res;
  89.     }
  90. public:
  91.     int count (vector <string> board)
  92.     {
  93.         n = board.size (), m = board[0].size ();
  94.         int cnt = 0, px[20], py[20];
  95.         REP_0 (i, n) 
  96.             REP_0 (j, m)
  97.             {
  98.                 if (board[i][j] == '*') px[cnt] = i + 1, py[cnt] = j + 1, cnt ++;
  99.                 else mp[i + 1][j + 1] = board[i][j] == 'o';
  100.             }
  101.         int M = 1 << cnt, res = 0;
  102.         REP_0 (s, M)
  103.         {
  104.             REP_0 (i, cnt) if (s >> i & 1) mp[px[i]][py[i]] = true;
  105.             res += solve (); if (res >= P) res -= P;
  106.             REP_0 (i, cnt) if (s >> i & 1) mp[px[i]][py[i]] = false;
  107.         }
  108.         return res;
  109.     }
  110. };
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注