GCJ Practice Contest

https://codejam.withgoogle.com/codejam/contest/32004/dashboard

A. Old Magician

方法：

打表找规律，发现结果只和black个数的奇偶性有关。

code:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 #include <stack>
 8 #include <bitset>
 9 #include <cstdlib>
10 #include <cmath>
11 #include <set>
12 #include <list>
13 #include <deque>
14 #include <map>
15 #include <queue>
16 #include <fstream>
17 #include <cassert>
18 #include <unordered_map>
19 #include <unordered_set>
20 #include <cmath>
21 #include <sstream>
22 #include <time.h>
23 #include <complex>
24 #include <iomanip>
25 #include <tuple>
26 
27 #define Max(a,b) ((a)>(b)?(a):(b))
28 #define Min(a,b) ((a)<(b)?(a):(b))
29 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a))
30 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a))
31 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a))
32 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a))
33 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
34 #define FOREACH(a,b) for (auto &(a) : (b))
35 #define rep(i,n) FOR(i,0,n)
36 #define repn(i,n) FORN(i,1,n)
37 #define drep(i,n) DFOR(i,n-1,0)
38 #define drepn(i,n) DFOR(i,n,1)
39 #define MAX(a,b) a = Max(a,b)
40 #define MIN(a,b) a = Min(a,b)
41 #define SQR(x) ((LL)(x) * (x))
42 #define Reset(a,b) memset(a,b,sizeof(a))
43 #define fi first
44 #define se second
45 #define mp make_pair
46 #define pb push_back
47 #define all(v) v.begin(),v.end()
48 #define ALLA(arr,sz) arr,arr+sz
49 #define SIZE(v) (int)v.size()
50 #define SORT(v) sort(all(v))
51 #define REVERSE(v) reverse(ALL(v))
52 #define SORTA(arr,sz) sort(ALLA(arr,sz))
53 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
54 #define PERMUTE next_permutation
55 #define TC(t) while(t--)
56 #define forever for(;;)
57 #define PINF 1000000000000
58 #define newline '
'
59 
60 #define test if(1)if(0)cerr
61 using namespace std;
62 using namespace std;
63 typedef vector<int> vi;
64 typedef vector<vi> vvi;
65 typedef pair<int,int> ii;
66 typedef pair<double,double> dd;
67 typedef pair<char,char> cc;
68 typedef vector<ii> vii;
69 typedef long long ll;
70 typedef unsigned long long ull;
71 typedef pair<ll, ll> l4;
72 
73 
74 
75 
76 
77 int main()
78 {
79     ios::sync_with_stdio(false);
80     cin.tie(0);
81     int n;
82     cin >> n;
83     repn(i, n)
84     {
85         int x, y;   cin >> x >> y;
86         cout << "Case #" << i << ": ";
87         if (y%2) cout << "BLACK
";
88         else cout << "WHITE
";
89     }
90 }

View Code

B. Square Fields

方法：

最优解一定可以把所有的正方形移动，使得每个正方形至少有两条边上有点。首先二分长度，根据所有可能的横纵坐标建立n^2个正方形，对于每个正方形，可以用一个不超过2^15的整数表示哪些点可以被其覆盖，然后只需对这n^2个正方形进行一次背包，即可求出cover所有点所需的正方形的最小数目m。如果m <＝ k，则可行。

code：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <string>
  6 #include <vector>
  7 #include <stack>
  8 #include <bitset>
  9 #include <cstdlib>
 10 #include <cmath>
 11 #include <set>
 12 #include <list>
 13 #include <deque>
 14 #include <map>
 15 #include <queue>
 16 #include <fstream>
 17 #include <cassert>
 18 #include <unordered_map>
 19 #include <unordered_set>
 20 #include <cmath>
 21 #include <sstream>
 22 #include <time.h>
 23 #include <complex>
 24 #include <iomanip>
 25 #include <tuple>
 26 
 27 #define Max(a,b) ((a)>(b)?(a):(b))
 28 #define Min(a,b) ((a)<(b)?(a):(b))
 29 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a))
 30 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a))
 31 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a))
 32 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a))
 33 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
 34 #define FOREACH(a,b) for (auto &(a) : (b))
 35 #define rep(i,n) FOR(i,0,n)
 36 #define repn(i,n) FORN(i,1,n)
 37 #define drep(i,n) DFOR(i,n-1,0)
 38 #define drepn(i,n) DFOR(i,n,1)
 39 #define MAX(a,b) a = Max(a,b)
 40 #define MIN(a,b) a = Min(a,b)
 41 #define SQR(x) ((LL)(x) * (x))
 42 #define Reset(a,b) memset(a,b,sizeof(a))
 43 #define fi first
 44 #define se second
 45 #define mp make_pair
 46 #define pb push_back
 47 #define all(v) v.begin(),v.end()
 48 #define ALLA(arr,sz) arr,arr+sz
 49 #define SIZE(v) (int)v.size()
 50 #define SORT(v) sort(all(v))
 51 #define REVERSE(v) reverse(ALL(v))
 52 #define SORTA(arr,sz) sort(ALLA(arr,sz))
 53 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
 54 #define PERMUTE next_permutation
 55 #define TC(t) while(t--)
 56 #define forever for(;;)
 57 #define PINF 1000000000000
 58 #define newline '
'
 59 
 60 #define test if(1)if(0)cerr
 61 using namespace std;
 62 using namespace std;
 63 typedef vector<int> vi;
 64 typedef vector<vi> vvi;
 65 typedef pair<int,int> ii;
 66 typedef pair<double,double> dd;
 67 typedef pair<char,char> cc;
 68 typedef vector<ii> vii;
 69 typedef long long ll;
 70 typedef unsigned long long ull;
 71 typedef pair<ll, ll> l4;
 72 
 73 
 74 int n, k;
 75 int x[20], y[20];
 76 vector<int> bits;
 77 int dp[(1<<15)];
 78 
 79 inline bool valid(int mid)
 80 {
 81     bits.clear();
 82     rep(i, n) rep(j, n)
 83     {
 84         int x1 = x[i], y1 = y[j];
 85         int x2 = x1+mid, y2 = y1+mid;
 86         int ret = 0;
 87         rep(k, n) if (x1 <= x[k] && x[k] <= x2 && y1 <= y[k] && y[k] <= y2) ret |= (1<<k);
 88         bits.pb(ret);
 89     }
 90     Reset(dp, -1);
 91     dp[0] = 0;
 92     for (auto e : bits)
 93     {
 94         for (int cur = (1<<n)-1; cur >= 0; --cur) if (dp[cur] != -1)
 95         {
 96             int nxt = cur|e;
 97             int nxtv = dp[cur]+1;
 98             if (dp[nxt] == -1 || dp[nxt] > nxtv) dp[nxt] = nxtv;
 99         }
100     }
101     return dp[(1<<n)-1] <= k;
102 }
103 int main()
104 {
105     ios::sync_with_stdio(false);
106     cin.tie(0);
107     int T;  cin >> T;
108     repn(kase, T)
109     {
110         cin >> n >> k;
111         rep(i, n) cin >> x[i] >> y[i];
112         int left = 0, right = 1e9, mid, ans;
113         while (left <= right)
114         {
115             mid = (left+right)>>1;
116             if (valid(mid))
117             {
118                 ans = mid;
119                 right = mid-1;
120             }
121             else
122                 left = mid+1;
123         }
124         cout << "Case #" << kase << ": " << ans << newline;
125     }
126 }

View Code

C. Cycles

方法：

设禁止边集为K，则对K的每一个subset S，我们求出使用S中所有边构成的hamilton cycle有多少个，然后再利用容斥原理求解即可。

对于一个S，求出包含S中所有边的hamilton cycle的个数，可以这样做：首先，对于S产生的诱导子图，如果有一个点度数超过2，那么肯定不存在合理的hamilton 路，返回0个；同时，如果存在环，只有当只存在一个环而且该环本身就是hamilton路的时候，返回1，否则返回0。对于其他的情况，假设我们的到了path条路径，那么我们要先对这些路径定向，有2^path种方式，然后把这些路径看成点，再在所有的点中找出一条hamilton路；如果剩下有total个点（包含了path条路径），那么hamilton路有(total-1)!／2条。所以返回 2^path * (total-1)!/2。（cyclic permutation 的个数为(total-1)!，同时要考虑方向去重）。

code:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <string>
  6 #include <vector>
  7 #include <stack>
  8 #include <bitset>
  9 #include <cstdlib>
 10 #include <cmath>
 11 #include <set>
 12 #include <list>
 13 #include <deque>
 14 #include <map>
 15 #include <queue>
 16 #include <fstream>
 17 #include <cassert>
 18 #include <unordered_map>
 19 #include <unordered_set>
 20 #include <cmath>
 21 #include <sstream>
 22 #include <time.h>
 23 #include <complex>
 24 #include <iomanip>
 25 #include <tuple>
 26 
 27 #define Max(a,b) ((a)>(b)?(a):(b))
 28 #define Min(a,b) ((a)<(b)?(a):(b))
 29 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a))
 30 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a))
 31 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a))
 32 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a))
 33 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
 34 #define FOREACH(a,b) for (auto &(a) : (b))
 35 #define rep(i,n) FOR(i,0,n)
 36 #define repn(i,n) FORN(i,1,n)
 37 #define drep(i,n) DFOR(i,n-1,0)
 38 #define drepn(i,n) DFOR(i,n,1)
 39 #define MAX(a,b) a = Max(a,b)
 40 #define MIN(a,b) a = Min(a,b)
 41 #define SQR(x) ((LL)(x) * (x))
 42 #define Reset(a,b) memset(a,b,sizeof(a))
 43 #define fi first
 44 #define se second
 45 #define mp make_pair
 46 #define pb push_back
 47 #define all(v) v.begin(),v.end()
 48 #define ALLA(arr,sz) arr,arr+sz
 49 #define SIZE(v) (int)v.size()
 50 #define SORT(v) sort(all(v))
 51 #define REVERSE(v) reverse(ALL(v))
 52 #define SORTA(arr,sz) sort(ALLA(arr,sz))
 53 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
 54 #define PERMUTE next_permutation
 55 #define TC(t) while(t--)
 56 #define forever for(;;)
 57 #define PINF 1000000000000
 58 #define newline '
'
 59 
 60 #define test if(1)if(0)cerr
 61 using namespace std;
 62 using namespace std;
 63 typedef vector<int> vi;
 64 typedef vector<vi> vvi;
 65 typedef pair<int,int> ii;
 66 typedef pair<double,double> dd;
 67 typedef pair<char,char> cc;
 68 typedef vector<ii> vii;
 69 typedef long long ll;
 70 typedef unsigned long long ull;
 71 typedef pair<ll, ll> l4;
 72 
 73 const int mod = 9901;
 74 int n, k;
 75 vector<ii> E;
 76 int pa[301];
 77 
 78 ll fact[301];
 79 int bcnt[(1<<15)];
 80 int total = 0;
 81 int sz[301];
 82 int findpa(int id)
 83 {
 84     return id==pa[id]?id:pa[id]=findpa(pa[id]);
 85 }
 86 bool merge(int x, int y)
 87 {
 88     x = findpa(x), y = findpa(y);
 89     if (x != y)
 90     {
 91         pa[x] = y;
 92         sz[y] += sz[x];
 93         sz[x] = 0;
 94         --total;
 95         return true;
 96     }
 97     return false;
 98 }
 99 int deg[301];
100 void init(int n)
101 {
102     repn(i, n) pa[i] = i;
103     repn(i, n) sz[i] = 1;
104     total = n;
105     Reset(deg, 0);
106 }
107 
108 ll power(ll base, ll p)
109 {
110     if (!base) return 0;
111     ll ret = 1;
112     while (p)
113     {
114         if (p&1) ret = ret * base % mod;
115         base = base * base % mod;
116         p >>= 1;
117     }
118     return ret;
119 }
120 ll solve(int bit)
121 {
122     int error = 0;
123     init(n);
124     rep(i, k) if ((1<<i)&bit)
125     {
126         deg[E[i].first] += 1;
127         deg[E[i].second] += 1;
128         if (deg[E[i].first] > 2 || deg[E[i].second] > 2) return 0;
129         if (!merge(E[i].first, E[i].second))
130         {
131             ++error;
132         }
133     }
134     if (error == 1 && total == 1) return 2;
135     if (error) return 0;
136     int path = 0;
137     repn(i, n) if (sz[i] > 1) path += 1;
138     return power(2, path) % mod * fact[total-1] % mod;
139 }
140 int main()
141 {
142     fact[0] = 1;
143     repn(i, 300)
144     fact[i] = fact[i-1] * i % mod;
145     bcnt[0] = 0;
146     repn(i, (1<<15)-1)
147     bcnt[i] = bcnt[i>>1] + (i&1);
148     ios::sync_with_stdio(false);
149     cin.tie(0);
150     int T;  cin >> T;
151     repn(kase, T)
152     {
153         cin >> n >> k;
154         E.resize(k);
155         rep(i, k)
156         cin >> E[i].first >> E[i].second;
157         ll ret = 0;
158         rep(bit, (1<<k))
159         {
160             int sign = 1;
161             if (bcnt[bit] % 2) sign = -1;
162             ll tmp = solve(bit);
163             ret = (ret + sign * tmp) % mod;
164         }
165         cout << "Case #" << kase << ": " << (ret*9902/2%mod+mod)%mod << newline;
166         
167     }
168 }

View Code