CodeForces Round #250 Div2

A. The Child and Homework

注意仔细读题，WA了好多次，=_=

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 110;
 7 
 8 char s[4][maxn];
 9 int l[4], r[4];
10 
11 bool cmp(int a, int b) { return l[a] < l[b]; }
12 
13 int main()
14 {
15     //freopen("in.txt", "r", stdin);
16 
17     for(int i = 0; i < 4; i++) r[i] = i;
18     for(int i = 0; i < 4; i++) scanf("%s", s[i]);
19     for(int i = 0; i < 4; i++) { l[i] = strlen(s[i]); l[i] -= 2; }
20     sort(r, r + 4, cmp);
21 
22     int ans = -1;
23     if(l[r[0]] * 2 <= l[r[1]]) ans = r[0];
24     if(l[r[3]] >= l[r[2]] * 2) { if(ans == -1) ans = r[3]; else ans = 2; }
25     if(ans == -1) ans = 2;
26 
27     printf("%c
", 'A' + ans);
28 
29     return 0;
30 }

代码君

B. The Child and Set (贪心)

把那些lowbit都算出来，然后从大到小排个序，依次往里面填就好了。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using std::sort;
 4 const int maxn = 100000 + 10;
 5 int lowbit[maxn], r[maxn], ans[maxn], cnt;
 6 
 7 bool cmp(int a, int b) { return lowbit[a] > lowbit[b]; }
 8 
 9 int main()
10 {
11     int s, n;
12     scanf("%d%d", &s, &n);
13 
14     for(int i = 1; i <= n; i++) { r[i] = i; lowbit[i] = i & (-i); }
15     sort(r + 1, r + 1 + n, cmp);
16     int t = 0;
17     for(int i = 1; i <= n; i++)
18     {
19         if(t == s) break;
20         if(lowbit[r[i]] + t <= s) { t += lowbit[r[i]]; ans[cnt++] = r[i]; }
21     }
22 
23     if(t != s) { puts("-1"); return 0; }
24     printf("%d
%d", cnt, ans[0]);
25     for(int i = 1; i < cnt; i++) printf(" %d", ans[i]);
26     puts("");
27 
28     return 0;
29 }

代码君

C. The Child and Toy (贪心)

最优的删点方式就是从最大的点开始删起。

不妨从边的角度考虑更为方便，最终没有任意两个点事连通的，所以每条边都会被删去。考虑边(u, v)，它被删去的时候贡献的一定是uv中较小的权值。

所以算法就是，读进每条边累加它权值较小的那个端点的权值即可。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using std::min;
 4 
 5 const int maxn = 1000 + 10;
 6 const int maxm = 2000 + 10;
 7 
 8 int a[maxn], u[maxm], v[maxm];
 9 
10 int main()
11 {
12     int n, m, ans = 0;
13     scanf("%d%d", &n, &m);
14     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
15     for(int i = 0; i < m; i++) { scanf("%d%d", &u[i], &v[i]); ans += min(a[u[i]], a[v[i]]); }
16     printf("%d
", ans);
17 
18     return 0;
19 }

代码君

D. The Child and Zoo (贪心含秩并查集最大生成树)

　　给每条边赋一个权值，为两端顶点权值较小的那个，然后将这些边从大到小排序。

　　一开始图是空的，每加进一条权值为w的边可能会将两个连通分量连通起来，那么对于分别位于这两个连通分量中的(u, v)，f(u, v) = w，而这样的f(u, v)一共有 p * q个，其中pq分别为这两个连通分量的秩。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 100000 + 10;
 6 int a[maxn], u[maxn], v[maxn], w[maxn], r[maxn], cnt[maxn];
 7 
 8 int pa[maxn];
 9 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }
10 
11 bool cmp(int a, int b) { return w[a] > w[b]; }
12 
13 int main()
14 {
15     //freopen("in.txt", "r", stdin);
16 
17     int n, m;
18     scanf("%d%d", &n, &m);
19     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
20     for(int i = 1; i <= m; i++) { scanf("%d%d", &u[i], &v[i]); w[i] = min(a[u[i]], a[v[i]]); }
21 
22     for(int i = 1; i <= n; i++) { pa[i] = i; cnt[i] = 1; }
23     for(int i = 1; i <= m; i++) r[i] = i;
24     sort(r + 1, r + 1 + m, cmp);
25 
26     double ans = 0.0;
27     int c = n;
28     for(int i = 1; i <= m && c > 1; i++)
29     {
30         int px = findset(u[r[i]]);
31         int py = findset(v[r[i]]);
32         if(px != py)
33         {
34             ans += (double) cnt[px] * cnt[py] * w[r[i]];
35             pa[px] = py; cnt[py] += cnt[px];
36             c--;
37         }
38     }
39 
40     printf("%.6f
", ans * 2 / (n * 1.0 * (n - 1)));
41 
42     return 0;
43 }

代码君

E. The Child and Polygon (区间DP 叉积)

不妨将这些点按照逆时针顺序编号0 ~ n-1。d(i, j)表示多边形 i, i+1 ,..., j, i 的三角剖分的方法数。

则有状态转移方程 d(i, j) = sum{ d(i, k) * d(k, j) | i < k < j 且线段ik在多边形内部 }

可以通过叉积来判断线段是否在多边形内部，具体就是判断 ji × jk 是否为正。

总时间复杂度为O(n³)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const LL MOD = 1000000007;
 8 
 9 const int maxn = 200 + 10;
10 int n;
11 
12 struct Point
13 {
14     LL x, y;
15     Point(LL x = 0, LL y = 0):x(x), y(y) {}
16 }p[maxn];
17 
18 Point operator - (const Point& A, const Point& B)
19 { return Point(A.x - B.x, A.y - B.y); }
20 
21 LL Cross(const Point& A, const Point& B)
22 { return A.x * B.y - A.y * B.x; }
23 
24 LL d[maxn][maxn];
25 
26 LL dp(int L, int R)
27 {
28     if(d[L][R] != -1) return d[L][R];
29     LL& ans = d[L][R];
30     if(R - L == 1) return ans = 1;
31     ans = 0;
32     for(int i = L + 1; i < R; i++)
33         if(Cross(p[L] - p[R], p[i] - p[R]) > 0)
34             ans = (ans + dp(L, i) * dp(i, R)) % MOD;
35     return ans;
36 }
37 
38 int main()
39 {
40     //freopen("in.txt", "r", stdin);
41 
42     scanf("%d", &n);
43     LL x, y;
44     for(int i = 0; i < n; i++)
45     {
46         scanf("%I64d%I64d", &x, &y);
47         p[i] = Point(x, y);
48     }
49 
50     LL area = 0;
51     for(int i = 1; i + 1 < n; i++)
52         area += Cross(p[i] - p[0], p[i+1] - p[0]);
53     if(area < 0) reverse(p, p + n);
54 
55     memset(d, -1, sizeof(d));
56     printf("%I64d
", dp(0, n - 1));
57 
58     return 0;
59 }

代码君

最后看了下Div1的两道题：

D. The Child and Sequence (线段树单点修改)

动态询问连续子序列的和。操作有 单点修改 和将 连续区间的每个数都模上x

重点说一下取模的操作，可以维护一个区间的最大值，当区间的最大值小于x的时候，那么便不用取模了。

而且每个数每次取模以后的值至少要减半，所以每个数取模的次数不会太多。

balabala...

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 const int maxn = 100000 + 10;
 9 int n, m, qL, qR, p, op;
10 LL v;
11 LL sumv[maxn << 2], maxv[maxn << 2];
12 
13 void pushup(int o)
14 {
15     sumv[o] = sumv[o<<1] + sumv[o<<1|1];
16     maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
17 }
18 
19 void build(int o, int L, int R)
20 {
21     if(L == R) { scanf("%I64d", &sumv[o]); maxv[o] = sumv[o]; return; }
22     int M = (L + R) / 2;
23     build(o<<1, L, M);
24     build(o<<1|1, M+1, R);
25     pushup(o);
26 }
27 
28 void update1(int o, int L, int R)
29 {
30     if(L == R) { sumv[o] = maxv[o] = v; return; }
31     int M = (L + R) / 2;
32     if(p <= M) update1(o<<1, L, M);
33     else update1(o<<1|1, M+1, R);
34     pushup(o);
35 }
36 
37 void update2(int o, int L, int R)
38 {
39     if(maxv[o] < v) return;
40     if(L == R) { sumv[o] %= v; maxv[o] %= v; return; }
41     int M = (L + R) / 2;
42     if(qL <= M) update2(o<<1, L, M);
43     if(qR > M) update2(o<<1|1, M+1, R);
44     pushup(o);
45 }
46 
47 LL query(int o, int L, int R)
48 {
49     if(qL <= L && qR >= R) return sumv[o];
50     int M = (L + R) / 2;
51     LL ans = 0;
52     if(qL <= M) ans += query(o<<1, L, M);
53     if(qR > M) ans += query(o<<1|1, M+1, R);
54     return ans;
55 }
56 
57 int main()
58 {
59     //freopen("in.txt", "r", stdin);
60 
61     cin >> n >> m;
62     build(1, 1, n);
63     while( m-- )
64     {
65         scanf("%d", &op);
66         if(op == 1)
67         {
68             scanf("%d%d", &qL, &qR);
69             printf("%I64d
", query(1, 1, n));
70         }
71         else if(op == 2)
72         {
73             scanf("%d%d%I64d", &qL, &qR, &v);
74             update2(1, 1, n);
75         }
76         else
77         {
78             scanf("%d%I64d", &p, &v);
79             update1(1, 1, n);
80         }
81     }
82 
83     return 0;
84 }

代码君

E题看到用什么母函数，多项式求根，FFT，就打算把这道题放一放了，毕竟太弱Q_Q