(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 '
'
 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 '
'
 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 '
'
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 '
'
 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 '
'
 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 '
'
 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

F. Four operations

方法：暴力

注意，符号的顺序是固定的。设最后结果为result = a+b-c*d/e, 为了使result最小，c 和 d 都应只取一位，而e最多取2位，因为c*d<100, 与其让c*d/e 从一个1位数变成0，不如让前面的数增加一位。然后a+b 一定有一个是一位数，另个一用尽所有剩下的数字（这样做结果位数最高）。枚举除号，再枚举加号即可。

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 '
'
 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 
 74 string str;
 75 ll a, b, c, d, e;
 76 
 77 ll solve()
 78 {
 79     return a+b-c*d/e;
 80 }
 81 int main()
 82 {
 83     ios::sync_with_stdio(false);
 84     cin.tie(0);
 85     int T;  cin >> T;
 86     for (int kase = 1; kase <= T; ++kase)
 87     {
 88         cin >>     str;
 89         int len = str.length();
 90         e = str.back()-'0';
 91         d = str[len-2]-'0';
 92         c = str[len-3]-'0';
 93         a = str.front()-'0';
 94         b = stoll(str.substr(1, len-4));
 95         ll ans = solve();
 96         a = stoll(str.substr(0, len-4));
 97         b = str[len-4]-'0';
 98         ans = max(ans, solve());
 99         if (len > 5)
100         {
101             e += 10*d;
102             d = c;
103             c = str[len-4]-'0';
104             b = str[len-5]-'0';
105             a = stoll(str.substr(0, len-5));
106             ans = max(ans, solve());
107             a = str.front()-'0';
108             b = stoll(str.substr(1, len-5));
109             ans = max(ans, solve());
110         }
111 
112         cout << "Case #" << kase << ": " << ans << newline;
113         
114     }
115 }
View Code

J. Just a math problem

方法：容斥定理，（mobius inversion？）

（搬运题解），g(k) 可以看作 m*n=k，gcd(m,n) == 1的有序对(m,n)的数量，那么 sum(g(k)) k=1,2,3,..,n就是 x*y <= n， gcd(x, y) = 1 的有序对(x,y)的数量。除了(1,1)之外，(x,y) x一定不等于y，那我们可以假设x < y， 只需枚举x，然后用容斥定理计算出可行的y的数量。可行的y的数量等于 [1, n/x] 中与x互质的数的数量-phi(x)。最后答案乘2 ，再上(1,1)这个情况。

code: (solve(), solve2()为两种容斥定理的解决方法，还有其他方法，如dfs）。

  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 '
'
 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 const int mod = 1e9+7;
 74 ll n;
 75 const int maxn = 1e6;
 76 ll p[maxn+1][8];
 77 ll phi[maxn+1] = {0};
 78 int ptr[maxn+1] = {0};
 79 
 80 void init()
 81 {
 82     phi[1] = 1;
 83     for (int i = 2; i <= maxn; ++i)
 84     {
 85         if (!ptr[i])
 86         {
 87             phi[i] = i-1;
 88             ptr[i] = 1;
 89             p[i][0] = i;
 90             for (ll j = i*2; j <= maxn; j += i)
 91             {
 92                 p[j][ptr[j]++] = i;
 93                 if (!phi[j]) phi[j] = j;
 94                 phi[j] -= phi[j]/i;
 95             }
 96         }
 97     }
 98 }
 99 
100 
101 
102 //bit operation
103 int cal (ll x, int num, ll &mul)
104 {
105     mul = 1;
106     int ans = 0, sz = ptr[x];
107     for (int i = 0; i < sz; ++i)
108         if (num & (1<<i))
109         {
110             ans += 1;
111             mul *= p[x][i];
112         }
113     return ans;
114 }
115 ll solve2(ll x)
116 {
117     ll r = n/x;
118     int sz = ptr[x];
119     ll ans = 0;
120     for (int i = 1; i < (1<<sz); ++i)
121     {
122         ll mul;
123         int ones = cal(x, i, mul);
124         if (ones&1)
125         {
126             ans = (ans + r/mul) % mod;
127         }
128         else
129             ans = ((ans -r/mul)%mod+mod)%mod;
130     }
131     ans = ((r-ans)%mod+mod)%mod;
132     ans = ((ans-phi[x])%mod+mod)%mod;
133 
134     return ans;
135 }
136 
137 //recursion
138 ll q[300];
139 int nq;
140 ll solve(ll m)
141 {
142     nq = 0;
143     ll ret = 0;
144     q[nq++] = -1;
145     for (ll i = 0; i < ptr[m]; ++i)
146     {
147         ll k = nq;
148         for (int j = 0; j < k; ++j)
149         {
150             q[nq++] = -1*q[j]*p[m][i];
151         }
152     }
153     ll nn = n/m;
154     for (ll i = 1; i < nq; ++i)
155         ret = (ret+nn/q[i])%mod;
156     return (nn-ret-phi[m])%mod;;
157 }
158 
159 
160 int main()
161 {
162     init();
163     ios::sync_with_stdio(false);
164     cin.tie(0);
165     int T;  cin >> T;
166     for (int kase = 1; kase <= T; ++kase)
167     {
168         cin >> n;
169 
170         ll ans = 0;
171         for (ll i = 1; i * i <= n; ++i)
172         {
173             ans += solve2(i);
174             ans %= mod;
175         }
176         cout << "Case #" << kase << ": " << ((2*ans%mod+1)%mod+mod)%mod << newline;
177     }
178 }
View Code

看了别人的code，好像也可以用mobius inversion 来作，可惜数论太差，需要补一补。

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 '
'
 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
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/skyette/p/6366925.html