首页 > 代码库 > (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 }
View Code

 

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 }
View Code

 

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 }
View Code

 

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 }
View Code

还有一种方法,因为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 }
View Code

 

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 }
View Code

 

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 }
View Code

 

(Incomplete) 2016年中国大学生程序设计竞赛(杭州)