首页 > 代码库 > (Incomplete) 2016年中国大学生程序设计竞赛（杭州）
(Incomplete) 2016年中国大学生程序设计竞赛（杭州）
反思：好好读题，一开始卡了好几道水题。多和队友交流思路。不要轻言放弃，珍惜上机机会。
A. Arcsoft‘s Office Rearrangement
方法： 贪心
注意到房子是连成一条线的，所以操作都都是对相邻的block进行或者产生相邻的block。贪心地从第一个block 开始处理。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 const int maxn = 1e5+1; 73 ll a[maxn]; 74 ll n, k; 75 76 int main() 77 { 78 ios::sync_with_stdio(false); 79 cin.tie(0); 80 int T; cin >> T; 81 for (int kase = 1; kase <= T; ++kase) 82 { 83 cin >> n >> k; 84 for (int i = 1; i <= n; ++i) 85 cin >> a[i]; 86 a[0] = 0; 87 for (int i = 1; i <= n; ++i) 88 a[i] += a[i-1]; 89 ll ans = 0; 90 if (a[n] % k != 0) 91 { 92 ans = -1; 93 } 94 else 95 { 96 ll block = a[n] / k; 97 int last = 0; 98 for (int i = 1; i <= n; ++i) 99 { 100 if (a[i] % block == 0) 101 { 102 ans += (a[i]-a[last])/block - 1; 103 last = i; 104 } 105 else 106 { 107 ans += 1; 108 } 109 } 110 } 111 cout << "Case #" << kase << ": " << ans << newline; 112 } 113 }
B. Bomb
方法：强联通分量
求出图的强联通分量，对于入度为0的强联通分量，选择最小的cost。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 const int maxn = 1e3+1; 73 int n; 74 ll r[maxn], x[maxn], y[maxn], c[maxn]; 75 ll mincost[maxn], indegree[maxn]; 76 bool adj[maxn][maxn]; 77 vector<int> g[maxn]; 78 bool connected(int u, int v) 79 { 80 ll dx = x[u]-x[v]; 81 ll dy = y[u]-y[v]; 82 return dx*dx+dy*dy <= r[u]*r[u]; 83 } 84 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt; 85 stack<int> Stack; 86 void dfs(int u) 87 { 88 pre[u] = lowlink[u] = ++dfs_clock; 89 Stack.push(u); 90 for (int i = 0; i < g[u].size(); ++i) 91 { 92 int v = g[u][i]; 93 if (!pre[v]) 94 { 95 dfs(v); 96 lowlink[u] = min(lowlink[u], lowlink[v]); 97 } else if (!sccno[v]) 98 { 99 lowlink[u] = min(lowlink[u], pre[v]); 100 } 101 } 102 if (lowlink[u] == pre[u]) 103 { 104 scc_cnt++; 105 for(;;) 106 { 107 int x = Stack.top(); Stack.pop(); 108 sccno[x] = scc_cnt; 109 if (x == u) break; 110 } 111 } 112 } 113 void find_scc(int n) 114 { 115 dfs_clock = scc_cnt = 0; 116 memset(sccno, 0, sizeof(sccno)); 117 memset(pre, 0, sizeof(pre)); 118 for (int i = 0; i < n; ++i) 119 if (!pre[i]) dfs(i); 120 } 121 int main() 122 { 123 ios::sync_with_stdio(false); 124 cin.tie(0); 125 int T; cin >> T; 126 for (int kase = 1; kase <= T; ++kase) 127 { 128 cin >> n; 129 for (int i = 0; i < n; ++i) g[i].clear(); 130 for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> r[i] >> c[i]; 131 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j && connected(i, j)) g[i].push_back(j); 132 find_scc(n); 133 memset(mincost, -1, sizeof(mincost)); 134 for (int i = 0; i < n; ++i) if (mincost[sccno[i]] == -1 || mincost[sccno[i]] > c[i]) mincost[sccno[i]] = c[i]; 135 memset(indegree, 0, sizeof(indegree)); 136 memset(adj, false, sizeof(adj)); 137 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (sccno[i] != sccno[j] && !adj[sccno[i]][sccno[j]] && connected(i, j)) adj[sccno[i]][sccno[j]] = true, indegree[sccno[j]] += 1; 138 ll ans = 0; 139 for (int i = 1; i <= scc_cnt; ++i) 140 if (!indegree[i]) ans += mincost[i]; 141 cout << "Case #" << kase << ": " << ans << newline; 142 } 143 144 }
C. Car
方法：贪心
最后一段的通过时间一定是1s，根据速度的关系，可以得出 di-1/ti-1 <= di/ti， 然后可以根据ti 求出 ti-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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 const int maxn = 1e5+1; 73 int a[maxn]; 74 int n; 75 76 int main() 77 { 78 ios::sync_with_stdio(false); 79 cin.tie(0); 80 int T; cin >> T; 81 for (int kase = 1; kase <= T; ++kase) 82 { 83 cin >> n; 84 a[0] = 0; 85 for (int i = 1; i <= n; ++i) cin >> a[i]; 86 int ans = 1; 87 int last = 1; 88 for (int i = n-1; i >= 1; --i) 89 { 90 int t = ceil(1.0*last*(a[i]-a[i-1])/(a[i+1]-a[i])); 91 ans += t; 92 last = t; 93 } 94 cout << "Case #" << kase << ": " << ans << newline; 95 } 96 }
D. Difference
方法：Meet in the Middle， 搜索
推导可知，y < 1e10，可以将y分成前半部分和后半部分。对于每一个k，预处理0-99999 的f[k][i]。对于一组input（x，k），枚举前半部分a*1e5（或者后半部分），将f(a*1e5, k) - a*1e5 储存到一个hashtable里（f(a*1e5, k) = f(a, k) = f[k][a]），再枚举另一半，f(b, k) - b, 观察 x-(f(b,k)-b) 是否在hashtable 中，更新答案。注意，如果x为0，最终答案要减1，因为要排除y ＝ 0*1e5 + 0的情况。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 const int maxb = 1e5; 73 ll powers[10][10]; 74 ll f[10][maxb+1]; 75 ll x, k; 76 unordered_map<ll, int> hashint; 77 int main() 78 { 79 ios::sync_with_stdio(false); 80 cin.tie(0); 81 for (int i = 0; i < 10; ++i) powers[1][i] = i; 82 for (int j = 2; j < 10; ++j) for (ll i = 0; i < 10; ++i) powers[j][i] = i*powers[j-1][i]; 83 for (int k = 1; k < 10; ++k) 84 for (int i = 0; i < maxb; ++i) 85 { 86 int cur = i; 87 f[k][i] = 0; 88 while (cur) 89 { 90 f[k][i] += powers[k][cur%10]; 91 cur /= 10; 92 } 93 } 94 95 int T; cin >> T; 96 for (int kase = 1; kase <= T; ++kase) 97 { 98 cin >> x >> k; 99 100 hashint.clear(); 101 for (ll i = 0; i < maxb; ++i) hashint[f[k][i]-i]+= 1; 102 ll ans = 0; 103 for (ll i = 0; i < maxb; ++i) 104 { 105 ll q = x-f[k][i]+i*1e5; 106 if (q >= 0 && hashint.count(q)) ans += hashint[q]; 107 } 108 if (x == 0) ans -= 1; 109 cout << "Case #" << kase << ": " << ans << newline; 110 } 111 }
还有一种方法，因为y的位数不会超过10个，所以可以暴力枚举各个数位i出现的数目d[i]， sumof(d[i]) = 10, （或者枚举各个非0数位i出现的数目d[i], 1 <= sumof(d[i]) <= 10) ，对于每一个d，我们可以求出f(y, k), 然后 y = f(y, k)-x, 得到y，再检查y的个数位是否满足d的要求。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 ll cnt[10]; 73 ll tmp[10]; 74 ll power[10][10]; 75 ll x, k; 76 ll cal_f() 77 { 78 ll ret = 0; 79 for (int i = 1; i < 10; ++i) ret += cnt[i] * power[k][i]; 80 return ret; 81 } 82 unordered_set<ll> ans; 83 void work(ll y) 84 { 85 if (y <= 0 || ans.count(y)) return; 86 memset(tmp, 0, sizeof(tmp)); 87 ll oy = y; 88 while (y) 89 { 90 tmp[y%10] += 1; 91 y /= 10; 92 } 93 94 for (int i = 1; i < 10; ++i) if (tmp[i] != cnt[i]) 95 { 96 97 return; 98 } 99 ans.insert(oy); 100 } 101 void dfs(int pos, int left) 102 { 103 if (pos == 10) 104 { 105 ll y = cal_f()-x; 106 work(y); 107 return; 108 } 109 for (cnt[pos] = 0; cnt[pos] <= left; ++cnt[pos]) 110 { 111 dfs(pos+1, left-cnt[pos]); 112 } 113 } 114 int main() 115 { 116 for (int k = 0; k < 10; ++k) power[1][k] = k; 117 for (int p = 2; p < 10; ++p) for (ll k = 0; k < 10; ++k) power[p][k] = power[p-1][k] * k; 118 ios::sync_with_stdio(false); 119 cin.tie(0); 120 int T; cin >> T; 121 for (int kase = 1; kase <= T; ++kase) 122 { 123 ans.clear(); 124 cin >> x >> k; 125 dfs(0, 10); 126 cout << "Case #" << kase << ": " << ans.size() << newline; 127 } 128 }
E. Equation
方法：状态压缩，搜索
（搬运题解）可以发现一共有36种不同的equation，如果对每种直接搜索的话，一共有2^36种可能。注意，其实可以将equation 分为三类：
1. 形如 x+x = (2*x)， 一共有 4 种
2. 除去第一类，形如 1+x = (x+1) ，有7种，每一种有两个表现形式，1 + x = (1+x) 或者 x + 1 = (1+x)。
3. 除去以上两类，形如 x + y = z, (x<y)， 有9种，每一种有两个表现形式，x+y=z 或者 y+x=z。
对于第一类的4种equation，我们可以选择取或者不取，2^4；对于第三类的9种equation, 我们可以选择不取，或者只取一个表现形式，或者取两个表现形式，3^9。在对前两类euqation选择完之后，对于第三类我们可以贪心求解。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 int cnt[10]; 73 int tmp[10]; 74 const int maxs = 314928; 75 int d[maxs][10]; 76 int ddd[maxs]; 77 int c[2][9] = {{2,2,2,2,2,3,3,3,4},{3,4,5,6,7,4,5,6,5}}; 78 bool fit(int state, bool res=true) 79 { 80 if (res) memcpy(tmp, cnt, sizeof(tmp)); 81 for (int i = 1; i < 10; ++i) 82 { 83 tmp[i] -= d[state][i]; 84 if (tmp[i] < 0) return false; 85 } 86 return true; 87 } 88 int main() 89 { 90 ios::sync_with_stdio(false); 91 cin.tie(0); 92 memset(d[0], 0, sizeof(d[0])); 93 ddd[0] = 0; 94 95 for (int i = 1; i < maxs; ++i) 96 { 97 int low = i%16; 98 int up = i/16; 99 bool done = false; 100 for (int j = 0; !done && low && j < 4; ++j) 101 if ((1<<j) & low) 102 { 103 done = true; 104 memcpy(d[i], d[i-(1<<j)], sizeof(d[i])); 105 ddd[i] = ddd[i-(1<<j)] + 1; 106 d[i][j+1] += 2; 107 d[i][2*j+2] += 1; 108 } 109 int base = 16; 110 for (int j = 0; !done && up && j < 9; ++j) 111 { 112 if (up % 3 != 0) 113 { 114 done = true; 115 memcpy(d[i], d[i-base], sizeof(d[i])); 116 rep(k, 2) d[i][c[k][j]] += 1; 117 d[i][c[0][j]+c[1][j]] += 1; 118 ddd[i] = ddd[i-base] + 1; 119 } 120 base *= 3; 121 up /= 3; 122 } 123 } 124 // brute force get value 125 /* 126 for (int i = 1; i < maxs; ++i) 127 { 128 int state = i; 129 int scnt = 0; 130 memset(tmp, 0, sizeof(tmp)); 131 for (int j = 0; j < 4; ++j) 132 { 133 if ((1<<j)&state) 134 { 135 scnt += 1; 136 tmp[j+1] += 2; 137 tmp[2*j+2] += 1; 138 } 139 } 140 int up = state/16; 141 for (int j = 0; j < 9; ++j) 142 { 143 scnt += up%3; 144 tmp[c[0][j]] += up%3; 145 tmp[c[1][j]] += up%3; 146 tmp[c[0][j]+c[1][j]] += up%3; 147 up /= 3; 148 } 149 ddd[state] = scnt; 150 memcpy(d[state], tmp, sizeof(d[state])); 151 //if (!fit(state, false)) {cerr << state << newline; break;} //test difference between 2 method 152 }*/ 153 int T; cin >> T; 154 for (int kase = 1; kase <= T; ++kase) 155 { 156 for (int i = 1; i <= 9; ++i) cin >> cnt[i]; 157 int ans = 0; 158 for (int state = 0; state < maxs; ++state) 159 { 160 if (fit(state)) 161 { 162 int tcnt = ddd[state]; 163 for (int i = 2; i <= 8 && tmp[1]; ++i) 164 { 165 for (int tt = 0; tt < 2 && tmp[1]; ++tt) 166 if (tmp[i] && tmp[i+1]) 167 { 168 tmp[1] -= 1; 169 tmp[i] -= 1; 170 tmp[i+1] -=1; 171 tcnt += 1; 172 } 173 174 } 175 ans = max(ans, tcnt); 176 } 177 } 178 179 cout << "Case #" << kase << ": " << ans << newline; 180 } 181 }
K. Kindom of obsession
方法：数论，二分图匹配
不难想到，设bi = s+i, （1<=i<=n)， 如果 1<= bi <= n, 那把bi放到bi上即可（反证即可，假设在合法的安排中，如果bi在Bi, bj在bi, 那么bi | bj, Bi | bi（ | 表示能整除），所以 Bi | bj, 所以可以交换bi 和 bj 的位置）。那么剩下的bi (bi > n)，只能至多有1个质数，并且将其放在位置1上；如果超过一个质数则没有答案。如果不超过一个质数，那么剩下的bi（bi > n) 不会超过 336 个（预计算，通过bitset 进行 素数筛选，发现1e9之内两个相间素数的间隔不超过336，实际情况比这个小得多），那么就将剩下的bi 与 ［1，min(s, n)]的数做一下二分图匹配，看是否能得到完美匹配。
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 #define Max(a,b) ((a)>(b)?(a):(b)) 26 #define Min(a,b) ((a)<(b)?(a):(b)) 27 #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) 28 #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) 29 #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) 30 #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) 31 #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) 32 #define FOREACH(a,b) for (auto &(a) : (b)) 33 #define rep(i,n) FOR(i,0,n) 34 #define repn(i,n) FORN(i,1,n) 35 #define drep(i,n) DFOR(i,n-1,0) 36 #define drepn(i,n) DFOR(i,n,1) 37 #define MAX(a,b) a = Max(a,b) 38 #define MIN(a,b) a = Min(a,b) 39 #define SQR(x) ((LL)(x) * (x)) 40 #define Reset(a,b) memset(a,b,sizeof(a)) 41 #define fi first 42 #define se second 43 #define mp make_pair 44 #define pb push_back 45 #define all(v) v.begin(),v.end() 46 #define ALLA(arr,sz) arr,arr+sz 47 #define SIZE(v) (int)v.size() 48 #define SORT(v) sort(all(v)) 49 #define REVERSE(v) reverse(ALL(v)) 50 #define SORTA(arr,sz) sort(ALLA(arr,sz)) 51 #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) 52 #define PERMUTE next_permutation 53 #define TC(t) while(t--) 54 #define forever for(;;) 55 #define PINF 1000000000000 56 #define newline ‘\n‘ 57 58 #define test if(1)if(0)cerr 59 using namespace std; 60 using namespace std; 61 typedef vector<int> vi; 62 typedef vector<vi> vvi; 63 typedef pair<int,int> ii; 64 typedef pair<double,double> dd; 65 typedef pair<char,char> cc; 66 typedef vector<ii> vii; 67 typedef long long ll; 68 typedef unsigned long long ull; 69 typedef pair<ll, ll> l4; 70 const double pi = acos(-1.0); 71 72 73 int n, s; 74 const int maxn = 282; 75 vector<int> g[maxn]; 76 bitset<maxn> cross; 77 int match[maxn]; 78 bool isprime(int n) 79 { 80 int root = sqrt(n+0.5); 81 for (int i = 2; i <= root; ++i) 82 if (n % i == 0) return false; 83 return true; 84 } 85 bool dfs(int cur) 86 { 87 for (auto nxt : g[cur]) 88 { 89 if (!cross[nxt]) 90 { 91 cross[nxt] = true; 92 if (match[nxt] == -1 || dfs(match[nxt])) 93 { 94 match[nxt] = cur; 95 return true; 96 } 97 } 98 } 99 return false; 100 } 101 int mxmatch() 102 { 103 memset(match, -1, sizeof(match)); 104 int ret = 0; 105 for (int i = 0; i < min(n, s); ++i) 106 { 107 cross.reset(); 108 ret += dfs(i); 109 } 110 return ret; 111 } 112 int main() 113 { 114 ios::sync_with_stdio(false); 115 cin.tie(0); 116 int T; cin >> T; 117 for (int kase = 1; kase <= T; ++kase) 118 { 119 cin >> n >> s; 120 bool ans = true; 121 int cnt = 0; 122 for (int i = max(n+1, s+1); i <= s+n; ++i) 123 { 124 if (isprime(i)) 125 { 126 cnt += 1; 127 if (cnt > 1) 128 { 129 ans = false; 130 break; 131 } 132 } 133 } 134 //cerr << ans << newline; 135 if (ans) 136 { 137 for (int i = 0; i < min(n, s); ++i) g[i].clear(); 138 for (int i = max(s, n)+1; i <= s+n; ++i) 139 for (int j = 1; j <= min(n, s); ++j) if (i % j == 0) 140 { 141 g[i-max(s,n)-1].push_back(j-1); 142 } 143 int ret = mxmatch(); 144 //cerr << ret << newline; 145 if (ret != s+n-max(n,s)) ans = false; 146 } 147 cout << "Case #" << kase << ": " << (ans?"Yes":"No") << newline; 148 } 149 }
(Incomplete) 2016年中国大学生程序设计竞赛（杭州）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。