【 2013 Multi-University Training Contest 1 】

HDU 4602 Partition

f[i]表示和为i的方案数。已知f[i]=2^i-1。

dp[i]表示和为i，k有多少个。那么dp[i]=dp[1]+dp[2]+...+dp[i-1]+f[i-k]。

考虑与f有关的项：

f[n-k]是答案的一部分，即2^n-k-1是答案的一部分。

把与dp有关的项：

令s[i-1]=dp[1]+dp[2]+...+dp[i-1]，那么s[n-1]是答案的一部分。

s[i]=s[i-1]+dp[i]，又dp[i]=s[i-1]+f[i-k]。推出s[i]=2*s[i-1]+f[i-k]，dp[k]=s[k]=1。

可以推出s[n-1]=2^n-k-1+(n-k-1)*2^n-k-2。

 1 #include<iostream>
 2 typedef long long LL;
 3 LL MOD = 1000000007LL;
 4 using namespace std;
 5 LL powmod(LL a, LL b) {
 6     LL ans;
 7     a %= MOD;
 8     for (ans = 1; b; b >>= 1) {
 9         if (b & 1) {
10             ans *= a;
11             ans %= MOD;
12         }
13         a *= a;
14         a %= MOD;
15     }
16     return ans;
17 }
18 int main() {
19     int T;
20     LL n, k;
21     LL ans;
22     cin >> T;
23     while (T--) {
24         cin >> n >> k;
25         if (k > n) {
26             ans = 0;
27         } else if (k == n) {
28             ans = 1;
29         } else if (n - k == 1) {
30             ans = 2;
31         } else if (n - k == 2) {
32             ans = 5;
33         } else {
34             ans = powmod(2, n - k - 1)
35                     + (n - k - 1) * powmod(2, n - k - 2) % MOD;
36             ans += powmod(2, n - k - 1);
37             ans = (ans % MOD + MOD) % MOD;
38         }
39         cout << ans << endl;
40     }
41     return 0;
42 }

View Code

HDU 4604 Deque

枚举第i个数，假设它最早出现且在队列里，那么以i为起点的最长非降子序列一定在队列里（push_back），以i为起点的最长非升子序列也一定在队列里(push_front)。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define MAXN 100010
 4 #define oo 123456789
 5 using namespace std;
 6 int arr[MAXN];
 7 int up[MAXN], down[MAXN], cnt[MAXN];
 8 int st[MAXN], top;
 9 void LIS(int n, int dp[]) {
10     int i;
11     int pos;
12     top = -1;
13     for (i = 0; i < n; i++) {
14         if (top < 0 || st[top] <= arr[i]) {
15             st[++top] = arr[i];
16             dp[i] = top + 1;
17         } else {
18             pos = upper_bound(st, st + top + 1, arr[i]) - st;
19             st[pos] = arr[i];
20             dp[i] = pos + 1;
21         }
22         cnt[i] = min(cnt[i],
23                 upper_bound(st, st + top + 1, arr[i])
24                         - lower_bound(st, st + top + 1, arr[i]));
25     }
26 }
27 int main() {
28     int T;
29     int n;
30     int i;
31     int ans;
32     scanf("%d", &T);
33     while (T--) {
34         scanf("%d", &n);
35         for (i = 0; i < n; i++) {
36             scanf("%d", &arr[i]);
37             cnt[i] = oo;
38         }
39         reverse(arr, arr + n);
40         LIS(n, up);
41         for (i = 0; i < n; i++) {
42             arr[i] = -arr[i];
43         }
44         LIS(n, down);
45         ans = 0;
46         for (i = 0; i < n; i++) {
47             ans = max(ans, up[i] + down[i] - cnt[i]);
48         }
49         printf("%d
", ans);
50     }
51     return 0;
52 }

View Code

HDU 4605 Magic Ball Game

统计树上一个节点到根，权值大于/小于某个数的个数：数状数组/线段树。

离线处理询问，对所有w的值离散化。

从树根开始DFS，第一次到达一个节点时，回答所有询问。

向儿子DFS时，更新往左/右的数状数组。

最后一次离开一个节点时，还原现场。

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<vector>
  7 #include<set>
  8 #define MAXN 200010
  9 using namespace std;
 10 int w[MAXN], tmp[MAXN];
 11 struct node {
 12     int pre;
 13     int next[2];
 14     void init() {
 15         pre = -1;
 16         next[0] = next[1] = -1;
 17     }
 18 } tree[MAXN];
 19 struct Ask {
 20     int weight;
 21     int pos;
 22 };
 23 vector<Ask> q[MAXN];
 24 pair<int, int> res[MAXN];
 25 bool stop[MAXN];
 26 multiset<int> myset;
 27 inline int lowbit(int x) {
 28     return x & -x;
 29 }
 30 void update(int arr[], int i, int val) {
 31     for (; i < MAXN; i += lowbit(i)) {
 32         arr[i] += val;
 33     }
 34 }
 35 int sum(int arr[], int i) {
 36     int ans;
 37     for (ans = 0; i > 0; i -= lowbit(i)) {
 38         ans += arr[i];
 39     }
 40     return ans;
 41 }
 42 int left[MAXN], right[MAXN];
 43 void dfs(int x) {
 44     int i, j;
 45     for (i = 0; i < (int) q[x].size(); i++) {
 46         j = q[x][i].pos;
 47         if (myset.count(q[x][i].weight)) {
 48             res[j].first = -1;
 49         } else {
 50             res[j].first = sum(right, q[x][i].weight - 1);
 51             res[j].second = 3 * sum(left, q[x][i].weight - 1)
 52                     + 3 * sum(right, q[x][i].weight - 1);
 53 
 54             res[j].second += sum(left, MAXN - 1) - sum(left, q[x][i].weight);
 55             res[j].second += sum(right, MAXN - 1) - sum(right, q[x][i].weight);
 56         }
 57     }
 58 
 59     myset.insert(w[x]);
 60     if (tree[x].next[0] != -1) {
 61         update(left, w[x], 1);
 62         dfs(tree[x].next[0]);
 63         update(left, w[x], -1);
 64     }
 65     if (tree[x].next[1] != -1) {
 66         update(right, w[x], 1);
 67         dfs(tree[x].next[1]);
 68         update(right, w[x], -1);
 69     }
 70     myset.erase(myset.find(w[x]));
 71 }
 72 int main() {
 73     int T;
 74     int n, m;
 75     int i, j;
 76     int u, a, b;
 77     int size;
 78     Ask ask;
 79     scanf("%d", &T);
 80     while (T--) {
 81         scanf("%d", &n);
 82         size = 0;
 83         for (i = 1; i <= n; i++) {
 84             scanf("%d", &w[i]);
 85             tree[i].init();
 86             q[i].clear();
 87             tmp[size++] = w[i];
 88         }
 89         scanf("%d", &m);
 90         while (m--) {
 91             scanf("%d%d%d", &u, &a, &b);
 92             tree[u].next[0] = a;
 93             tree[u].next[1] = b;
 94             tree[a].pre = u;
 95             tree[b].pre = u;
 96         }
 97         scanf("%d", &m);
 98         for (i = 0; i < m; i++) {
 99             scanf("%d%d", &u, &ask.weight);
100             ask.pos = i;
101             q[u].push_back(ask);
102             tmp[size++] = ask.weight;
103         }
104         sort(tmp, tmp + size);
105         size = unique(tmp, tmp + size) - tmp;
106         for (i = 1; i <= n; i++) {
107             w[i] = lower_bound(tmp, tmp + size, w[i]) - tmp + 1;
108             for (j = 0; j < (int) q[i].size(); j++) {
109                 q[i][j].weight = lower_bound(tmp, tmp + size, q[i][j].weight)
110                         - tmp + 1;
111             }
112         }
113         myset.clear();
114         memset(left, 0, sizeof(left));
115         memset(right, 0, sizeof(right));
116         for (i = 1; i <= n; i++) {
117             if (tree[i].pre < 0) {
118                 dfs(i);
119                 break;
120             }
121         }
122         for (i = 0; i < m; i++) {
123             if (res[i].first < 0) {
124                 puts("0");
125             } else {
126                 printf("%d %d
", res[i].first, res[i].second);
127             }
128         }
129     }
130     return 0;
131 }

View Code

HDU 4606 Occupy Cities

预处理出任意两个城市的最短距离。

若士兵可以从一个城市i到达另一个城市j，且i比j先占领，才连i->j的边。

二分士兵背包的容量，可以得到一个有向图。二分条件是有向图的最小路径覆盖与士兵人数的关系。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 #define MAXN 310
  6 #define MAXM 10010
  7 #define oo 123456789
  8 #define eps 1e-6
  9 using namespace std;
 10 
 11 struct point {
 12     double x, y;
 13 };
 14 struct line {
 15     point a, b;
 16 };
 17 point city[MAXN];
 18 line barr[MAXN];
 19 
 20 double dis[MAXN][MAXN];
 21 int first[MAXM], next[MAXM], v[MAXM], e;
 22 int order[MAXN];
 23 int cx[MAXN], cy[MAXN];
 24 bool mk[MAXN];
 25 
 26 int dbcmp(double x, double y) {
 27     if (fabs(x - y) < eps) {
 28         return 0;
 29     } else {
 30         return x > y ? 1 : -1;
 31     }
 32 }
 33 bool zero(double x) {
 34     return fabs(x) < eps;
 35 }
 36 double dist(point p1, point p2) {
 37     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
 38 }
 39 double xmult(point p1, point p2, point p0) {
 40     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
 41 }
 42 int dots_inline(point p1, point p2, point p3) {
 43     return zero(xmult(p1, p2, p3));
 44 }
 45 int same_side(point p1, point p2, line l) {
 46     return xmult(l.a, p1, l.b) * xmult(l.a, p2, l.b) > eps;
 47 }
 48 int same_side(point p1, point p2, point l1, point l2) {
 49     return xmult(l1, p1, l2) * xmult(l1, p2, l2) > eps;
 50 }
 51 inline int dot_online_in(point p, point l1, point l2) {
 52     return zero(xmult(p, l1, l2)) && (l1.x - p.x) * (l2.x - p.x) < eps
 53             && (l1.y - p.y) * (l2.y - p.y) < eps;
 54 }
 55 int dot_online_in(point p, line l) {
 56     return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x) * (l.b.x - p.x) < eps
 57             && (l.a.y - p.y) * (l.b.y - p.y) < eps;
 58 }
 59 int intersect_in(point u1, point u2, point v1, point v2) {
 60     if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
 61         return !same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2);
 62     return dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2)
 63             || dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2);
 64 }
 65 
 66 void floyd(int n) {
 67     int i, j, k;
 68     for (k = 0; k < n; k++) {
 69         for (i = 0; i < n; i++) {
 70             for (j = 0; j < n; j++) {
 71                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
 72             }
 73         }
 74     }
 75 }
 76 inline void addEdge(int x, int y) {
 77     v[e] = y;
 78     next[e] = first[x];
 79     first[x] = e++;
 80 }
 81 int path(int x) {
 82     int y;
 83     for (int i = first[x]; i != -1; i = next[i]) {
 84         y = v[i];
 85         if (!mk[y]) {
 86             mk[y] = true;
 87             if (cy[y] == -1 || path(cy[y])) {
 88                 cx[x] = y;
 89                 cy[y] = x;
 90                 return 1;
 91             }
 92         }
 93     }
 94     return 0;
 95 }
 96 int match(int n) {
 97     int res, i;
 98     memset(cx, -1, sizeof(cx));
 99     memset(cy, -1, sizeof(cy));
100     for (res = i = 0; i < n; i++) {
101         if (cx[i] == -1) {
102             memset(mk, false, sizeof(mk));
103             res += path(i);
104         }
105     }
106     return res;
107 }
108 int main() {
109     int T;
110     int n, m, p;
111     int i, j, k;
112     double low, high, mid;
113     scanf("%d", &T);
114     while (T--) {
115         scanf("%d%d%d", &n, &m, &p);
116         for (i = 0; i < n; i++) {
117             scanf("%lf%lf", &city[i].x, &city[i].y);
118         }
119         for (i = 0; i < m; i++) {
120             scanf("%lf%lf%lf%lf", &barr[i].a.x, &barr[i].a.y, &barr[i].b.x,
121                     &barr[i].b.y);
122         }
123         for (i = 0; i < n; i++) {
124             scanf("%d", &order[i]);
125             order[i]--;
126         }
127 
128         for (i = 0; i < n + m + m; i++) {
129             for (j = 0; j <= i; j++) {
130                 dis[i][j] = dis[j][i] = oo;
131             }
132         }
133 
134         for (i = 0; i < n; i++) {
135             dis[i][i] = 0;
136             for (j = i + 1; j < n; j++) {
137                 for (k = 0; k < m; k++) {
138                     if (intersect_in(city[i], city[j], barr[k].a, barr[k].b)) {
139                         break;
140                     }
141                 }
142                 if (k >= m) {
143                     dis[i][j] = dis[j][i] = dist(city[i], city[j]);
144                 }
145             }
146         }
147 
148         for (i = 0; i < n; i++) {
149             for (j = 0; j < m; j++) {
150                 for (k = 0; k < m; k++) {
151                     if (j == k) {
152                         continue;
153                     }
154                     if (intersect_in(city[i], barr[j].a, barr[k].a,
155                             barr[k].b)) {
156                         break;
157                     }
158                 }
159                 if (k >= m) {
160                     dis[i][n + (j << 1)] = dis[n + (j << 1)][i] = dist(city[i],
161                             barr[j].a);
162                 }
163                 for (k = 0; k < m; k++) {
164                     if (j == k) {
165                         continue;
166                     }
167                     if (intersect_in(city[i], barr[j].b, barr[k].a,
168                             barr[k].b)) {
169                         break;
170                     }
171                 }
172                 if (k >= m) {
173                     dis[i][n + (j << 1 | 1)] = dis[n + (j << 1 | 1)][i] = dist(
174                             city[i], barr[j].b);
175                 }
176 
177             }
178         }
179 
180         for (i = 0; i < m; i++) {
181             for (j = 0; j < i; j++) {
182                 for (k = 0; k < m; k++) {
183                     if (k == i || k == j) {
184                         continue;
185                     }
186                     if (intersect_in(barr[i].a, barr[j].a, barr[k].a,
187                             barr[k].b)) {
188                         break;
189                     }
190                 }
191                 if (k >= m) {
192                     dis[n + (i << 1)][n + (j << 1)] = dis[n + (j << 1)][n
193                             + (i << 1)] = dist(barr[i].a, barr[j].a);
194                 }
195 
196                 for (k = 0; k < m; k++) {
197                     if (k == i || k == j) {
198                         continue;
199                     }
200                     if (intersect_in(barr[i].a, barr[j].b, barr[k].a,
201                             barr[k].b)) {
202                         break;
203                     }
204                 }
205                 if (k >= m) {
206                     dis[n + (i << 1)][n + (j << 1 | 1)] =
207                             dis[n + (j << 1 | 1)][n + (i << 1)] = dist(
208                                     barr[i].a, barr[j].b);
209                 }
210 
211                 for (k = 0; k < m; k++) {
212                     if (k == i || k == j) {
213                         continue;
214                     }
215                     if (intersect_in(barr[i].b, barr[j].a, barr[k].a,
216                             barr[k].b)) {
217                         break;
218                     }
219                 }
220                 if (k >= m) {
221                     dis[n + (i << 1 | 1)][n + (j << 1)] = dis[n + (j << 1)][n
222                             + (i << 1 | 1)] = dist(barr[i].b, barr[j].a);
223                 }
224 
225                 for (k = 0; k < m; k++) {
226                     if (k == i || k == j) {
227                         continue;
228                     }
229                     if (intersect_in(barr[i].b, barr[j].b, barr[k].a,
230                             barr[k].b)) {
231                         break;
232                     }
233                 }
234                 if (k >= m) {
235                     dis[n + (i << 1 | 1)][n + (j << 1 | 1)] = dis[n
236                             + (j << 1 | 1)][n + (i << 1 | 1)] = dist(barr[i].b,
237                             barr[j].b);
238                 }
239             }
240         }
241 
242         floyd(n + m + m);
243 
244         low = 0;
245         high = oo;
246         while (dbcmp(low, high) < 0) {
247             e = 0;
248             memset(first, -1, sizeof(first));
249             mid = (low + high) * 0.5;
250             for (i = 0; i < n; i++) {
251                 for (j = i + 1; j < n; j++) {
252                     if (dbcmp(dis[order[i]][order[j]], mid) <= 0) {
253                         addEdge(order[i], order[j]);
254                     }
255                 }
256             }
257             if (n - match(n) > p) {
258                 low = mid;
259             } else {
260                 high = mid;
261             }
262         }
263 
264         printf("%.2lf
", mid);
265 
266     }
267     return 0;
268 }

View Code

HDU 4607 Park Visit

最长链上的边走一次，其他边都必须走两次。

dp[i][0]表示以i为根的子树的最大深度，dp[i][1]表示以i为根的子树的次大深度。

答案就是max(dp[i][0]+dp[i][1])。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MAXN 200010
 5 using namespace std;
 6 int first[MAXN], next[MAXN], v[MAXN], e;
 7 int dp[MAXN][2];
 8 bool vis[MAXN];
 9 inline void addEdge(int x, int y) {
10     v[e] = y;
11     next[e] = first[x];
12     first[x] = e++;
13 }
14 void dfs(int x) {
15     vis[x] = true;
16     dp[x][0] = dp[x][1] = 0;
17     for (int i = first[x]; i != -1; i = next[i]) {
18         int y = v[i];
19         if (!vis[y]) {
20             dfs(y);
21             if (dp[y][0] + 1 >= dp[x][0]) {
22                 dp[x][1] = dp[x][0];
23                 dp[x][0] = dp[y][0] + 1;
24             } else if (dp[y][0] + 1 >= dp[x][1]) {
25                 dp[x][1] = dp[y][0] + 1;
26             }
27         }
28     }
29 }
30 int main() {
31     int T;
32     int n, m;
33     int i;
34     int x, y;
35     scanf("%d", &T);
36     while (T--) {
37         scanf("%d%d", &n, &m);
38         e = 0;
39         memset(first, -1, sizeof(first));
40         for (i = 1; i < n; i++) {
41             scanf("%d%d", &x, &y);
42             addEdge(x, y);
43             addEdge(y, x);
44         }
45         memset(vis, false, sizeof(vis));
46         dfs(1);
47         x = 0;
48         for (i = 1; i <= n; i++) {
49             x = max(x, dp[i][0] + dp[i][1]);
50         }
51         while (m--) {
52             scanf("%d", &y);
53             if (y <= x + 1) {
54                 printf("%d
", y - 1);
55             } else {
56                 printf("%d
", x + 2 * (y - x - 1));
57             }
58         }
59     }
60     return 0;
61 }

View Code

HDU 4608 I-number

因为y不会比x大多少，所以直接高精度加法暴力。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MAXN 200010
 5 using namespace std;
 6 int digit[MAXN];
 7 char str[MAXN];
 8 int main() {
 9     int T;
10     int i;
11     int len;
12     int sum;
13     scanf("%d", &T);
14     while (T--) {
15         scanf(" %s", str);
16         len = strlen(str);
17         memset(digit, 0, sizeof(digit));
18         for (i = 0; str[i]; i++) {
19             digit[i] = str[i] - '0';
20         }
21         reverse(digit, digit + len);
22         while (1) {
23             digit[0]++;
24             sum = 0;
25             for (i = 0; i < len; i++) {
26                 if (digit[i] > 9) {
27                     digit[i] -= 10;
28                     digit[i + 1]++;
29                     if (i == len - 1) {
30                         len++;
31                     }
32                 }
33                 sum += digit[i];
34             }
35             if (sum % 10 == 0) {
36                 break;
37             }
38         }
39         for (i = len - 1; i >= 0; i--) {
40             printf("%d", digit[i]);
41         }
42         putchar('
');
43     }
44     return 0;
45 }

View Code

HDU 4609 3-idiots

对于多项式乘法，普通做法需要O(n²)的时间复杂度。

而FFT仅需要O(nlogn)的时间复杂度。

把三角形边长作为多项式的指数，边长的出现次数作为多项式的系数。

把两个多项式相乘，即可得到任意两边长之和(i)出现的次数(num[i])。

由于一条边只能使用一次，所以num[arr[i]+arr[i]]--。

由于“先a后b”与“先b后a”属于同一种方案，所以num[i]>>=1。

不妨假设a<=b<=c，要构成三角形只要满足a+b>c。

由于a+b>c不容易统计，但是a+b<=c的方案数很容易统计，枚举c就可以做到。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #define MAXN 400010
  6 #define EPS 1e-8
  7 typedef long long LL;
  8 using namespace std;
  9 double PI = acos(-1.0);
 10 int arr[MAXN];
 11 LL num[MAXN], sum[MAXN];
 12 struct complex {
 13     double r, i;
 14     complex(double _r = 0, double _i = 0) {
 15         r = _r;
 16         i = _i;
 17     }
 18     complex operator+(const complex &b) {
 19         return complex(r + b.r, i + b.i);
 20     }
 21     complex operator-(const complex &b) {
 22         return complex(r - b.r, i - b.i);
 23     }
 24     complex operator*(const complex &b) {
 25         return complex(r * b.r - i * b.i, r * b.i + i * b.r);
 26     }
 27 };
 28 complex x[MAXN];
 29 void change(complex y[], int len) {
 30     for (int i = 1, j = len >> 1; i < len - 1; i++) {
 31         if (i < j) {
 32             swap(y[i], y[j]);
 33         }
 34         int k = len >> 1;
 35         for (; j >= k; k >>= 1) {
 36             j -= k;
 37         }
 38         if (j < k) {
 39             j += k;
 40         }
 41     }
 42 }
 43 void FFT(complex y[], int len, int on) {
 44     change(y, len);
 45     for (int h = 2; h <= len; h <<= 1) {
 46         complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
 47         for (int j = 0; j < len; j += h) {
 48             complex w(1, 0);
 49             for (int k = j; k < j + (h >> 1); k++) {
 50                 complex u = y[k];
 51                 complex t = w * y[k + (h >> 1)];
 52                 y[k] = u + t;
 53                 y[k + (h >> 1)] = u - t;
 54                 w = w * wn;
 55             }
 56         }
 57     }
 58     if (on == -1) {
 59         for (int i = 0; i < len; i++) {
 60             y[i].r /= len;
 61         }
 62     }
 63 }
 64 int main() {
 65     int T;
 66     int n;
 67     int len, len1;
 68     double ans;
 69     scanf("%d", &T);
 70     while (T--) {
 71         memset(num, 0, sizeof(num));
 72         scanf("%d", &n);
 73         for (int i = 0; i < n; i++) {
 74             scanf("%d", &arr[i]);
 75             num[arr[i]]++;
 76         }
 77         sort(arr, arr + n);
 78         len1 = arr[n - 1] + 1;
 79         for (len = 1; len <= (len1 << 1); len <<= 1)
 80             ;
 81         for (int i = 0; i < len1; i++) {
 82             x[i] = complex(num[i], 0);
 83         }
 84         for (int i = len1; i < len; i++) {
 85             x[i] = complex(0, 0);
 86         }
 87         FFT(x, len, 1);
 88         for (int i = 0; i < len; i++) {
 89             x[i] = x[i] * x[i];
 90         }
 91         FFT(x, len, -1);
 92         for (int i = 0; i < len; i++) {
 93             num[i] = (LL) (x[i].r + 0.5 + EPS);
 94         }
 95         for (int i = 0; i < n; i++) {
 96             num[arr[i] + arr[i]]--;
 97         }
 98         for (int i = 0; i < len; i++) {
 99             num[i] >>= 1;
100         }
101         sum[0] = 0;
102         for (int i = 1; i < len; i++) {
103             sum[i] = sum[i - 1] + num[i];
104         }
105         ans = 0;
106         for (int i = 0; i < n; i++) {
107             ans += sum[arr[i]];
108         }
109         printf("%.7lf
", 1 - ans * 6 / (n * (n - 1.0) * (n - 2.0)));
110     }
111     return 0;
112 }

View Code

4610 Cards

通过筛素数可以快速判定素数。

条件1，条件2可以快速解决；

条件3，一个数约数之和可能大于该数的好几倍；

条件4，一个数约束的乘积可能爆longlong，要通过分解素因子，判是否是平方数。

由于N的总数不超过20000，N个数的范围都在10⁶内，所以可以O(sqrt(n))的复杂度处理出约数。

由于条件只有4个，所以K个数中，只有2⁴=16个不同种类的数。因此可以枚举每种数是否出现2¹⁶，贪心的选择。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<algorithm>
  5 #include<map>
  6 #define oo 987654321
  7 #define MAXP 5000010
  8 #define MAXN 1000010
  9 #define MAXM 4
 10 typedef long long LL;
 11 using namespace std;
 12 bool p[MAXP];
 13 int num[1 << MAXM];
 14 int satisfy[MAXN];
 15 int add[MAXM];
 16 vector<int> prime;
 17 void init() {
 18     int i, j;
 19     memset(p, true, sizeof(p));
 20     p[0] = p[1] = false;
 21     for (i = 2; i * i < MAXP; i++) {
 22         if (p[i]) {
 23             for (j = i * i; j < MAXP; j += i) {
 24                 p[j] = false;
 25             }
 26         }
 27     }
 28     for (i = 2; i < MAXP; i++) {
 29         if (p[i]) {
 30             prime.push_back(i);
 31         }
 32     }
 33 }
 34 bool isSquare(int val, int cnt, int flag) {
 35     map<int, int> mymap;
 36     int i;
 37     for (i = 0; prime[i] * prime[i] <= val; i++) {
 38         while (val % prime[i] == 0) {
 39             mymap[prime[i]]++;
 40             val /= prime[i];
 41         }
 42     }
 43     if (val > 1) {
 44         mymap[val]++;
 45     }
 46     map<int, int>::iterator it;
 47     for (it = mymap.begin(); it != mymap.end(); it++) {
 48         (*it).second *= cnt;
 49     }
 50     for (i = 0; prime[i] * prime[i] <= flag; i++) {
 51         while (flag % prime[i] == 0) {
 52             mymap[prime[i]]++;
 53             flag /= prime[i];
 54         }
 55     }
 56     if (flag > 1) {
 57         mymap[flag]++;
 58     }
 59     for (it = mymap.begin(); it != mymap.end(); it++) {
 60         if ((*it).second & 1) {
 61             return false;
 62         }
 63     }
 64     return true;
 65 }
 66 void getSatisfy(int val) {
 67     if (satisfy[val] < 0) {
 68         int res = 0;
 69         int i;
 70         int amount = 0;
 71         int sum = 0;
 72         int product = 0;
 73         int flag = 1;
 74         for (i = 1; i * i < val; i++) {
 75             if (val % i == 0) {
 76                 amount += 2;
 77                 sum += i + val / i;
 78                 product++;
 79             }
 80         }
 81         if (i * i == val) {
 82             amount++;
 83             sum += i;
 84             flag = i;
 85         }
 86         if (p[val]) {
 87             res |= 1 << 0;
 88         }
 89         if (p[amount]) {
 90             res |= 1 << 1;
 91         }
 92         if (p[sum]) {
 93             res |= 1 << 2;
 94         }
 95         if (isSquare(val, product, flag)) {
 96             res |= 1 << 3;
 97         }
 98         satisfy[val] = res;
 99     }
100 }
101 int numOfOne(int val) {
102     int res;
103     for (res = 0; val; val >>= 1) {
104         res += val & 1;
105     }
106     return res;
107 }
108 bool cmp(int x, int y) {
109     return numOfOne(x) > numOfOne(y);
110 }
111 int main() {
112     int T;
113     int n, k;
114     int i, j;
115     int tmp, cnt;
116     int ans, res;
117     int sum;
118     bool flag;
119     vector<int> g;
120     init();
121     memset(satisfy, -1, sizeof(satisfy));
122     scanf("%d", &T);
123     while (T--) {
124         memset(num, 0, sizeof(num));
125         scanf("%d%d", &n, &k);
126         for (i = 0; i < n; i++) {
127             scanf("%d%d", &tmp, &cnt);
128             getSatisfy(tmp);
129             num[satisfy[tmp]] += cnt;
130 
131             printf("%d", numOfOne(satisfy[tmp]));
132             if (i < n - 1) {
133                 putchar(' ');
134             } else {
135                 putchar('
');
136             }
137         }
138         for (i = 0; i < MAXM; i++) {
139             scanf("%d", &add[i]);
140         }
141         ans = -oo;
142         for (i = 0; i < (1 << (1 << MAXM)); i++) {
143             g.clear();
144             for (tmp = i, j = 0; tmp; tmp >>= 1, j++) {
145                 if (tmp & 1) {
146                     g.push_back(j);
147                 }
148             }
149             if ((int) g.size() > k) {
150                 continue;
151             }
152             flag = true;
153             sum = 0;
154             tmp = 0;
155             for (j = 0; flag && j < (int) g.size(); j++) {
156                 if (num[g[j]] <= 0) {
157                     flag = false;
158                 }
159                 sum += num[g[j]];
160                 tmp |= g[j];
161             }
162             if (flag && sum >= k) {
163                 sort(g.begin(), g.end(), cmp);
164                 res = 0;
165                 for (j = 0; j < MAXM; j++, tmp >>= 1) {
166                     if (!(tmp & 1)) {
167                         res += add[j];
168                     }
169                 }
170                 for (j = 0; j < (int) g.size(); j++) {
171                     res += numOfOne(g[j]);
172                 }
173                 tmp = k - g.size();
174                 for (j = 0; tmp && j < (int) g.size(); j++) {
175                     cnt = min(tmp, num[g[j]] - 1);
176                     res += cnt * numOfOne(g[j]);
177                     tmp -= cnt;
178                 }
179                 ans = max(ans, res);
180             }
181         }
182         printf("%d
", ans);
183     }
184     return 0;
185 }

View Code