第二周 3.6-3.12

3.6

a + b = a ^ b + (a & b << 1)

注意非法情况和0。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int main(void)
 7 {
 8     LL s, x, t, ans = 1LL;
 9     cin >> s >> x;
10     t = s == x ? 2LL : 0LL;
11     s -= x;
12     if(s < 0LL || s % 2LL) {puts("0"); return 0;}
13     s /= 2LL;
14     while(x || s)
15     {
16         if((x % 2LL) && (s % 2LL)) {puts("0"); return 0;}
17         if((x % 2LL) && !(s % 2LL)) ans <<= 1LL;
18         x /= 2LL, s /= 2LL;
19     }
20     cout << ans - t << endl;
21     return 0;
22 }

Aguin

CF 627 B Factory Repairs

两个bit随意搞。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 2e5 + 10;
 6 typedef long long LL;
 7 LL c[2][maxn];
 8 
 9 int lowbit(int s)
10 {
11     return s & (-s);
12 }
13 
14 void modify(int op, int i, LL x)
15 {
16     while(i < maxn) c[op][i] += x, i += lowbit(i);
17     return;
18 }
19 
20 LL query(int op, int i)
21 {
22     LL ret = 0LL;
23     while(i > 0) ret += c[op][i], i -= lowbit(i);
24     return ret;
25 }
26 
27 int main(void)
28 {
29     int n, k, a, b, q;
30     scanf("%d %d %d %d %d", &n, &k, &a, &b, &q);
31     while(q--)
32     {
33         int op, x, y;
34         scanf("%d", &op);
35         if(op == 1)
36         {
37             scanf("%d %d", &x, &y);
38             modify(0, x, min(a - query(0, x) + query(0, x - 1), (LL)y));
39             modify(1, x, min(b - query(1, x) + query(1, x - 1), (LL)y));
40         }
41         else
42         {
43             scanf("%d", &x);
44             printf("%I64d
", query(1, x - 1) + query(0, n) - query(0, x + k - 1));
45         }
46     }
47     return 0;
48 }

Aguin

CF 627 C Package Delivery

不是很懂贪心。

想起多校某题还不会QAQ。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 2e5 + 10;
 8 
 9 struct gas
10 {
11     int id, x, p;
12     friend bool operator < (gas A, gas B)
13     {
14         return A.p > B.p;
15     }
16 }g[maxn];
17 
18 bool cmp (gas A, gas B)
19 {
20     return A.x < B.x;
21 }
22 
23 int main(void)
24 {
25     int n, d, m;
26     scanf("%d %d %d", &d, &n, &m);
27     for(int i = 0; i < m; i++) scanf("%d %d", &g[i].x, &g[i].p);
28     sort(g, g + m, cmp);
29     LL ans = 0LL;
30     priority_queue<gas> pq;
31     int t = 0, now = n;
32     while(now < d)
33     {
34         while(t < m && g[t].x <= now) pq.push(g[t++]);
35         while(!pq.empty() && pq.top().x <= now - n) pq.pop();
36         if(pq.empty()) return puts("-1");
37         int x = pq.top().x, p = pq.top().p;
38         int nxt = min(d, x + n);
39         if(t < m && nxt >= g[t].x) nxt = g[t].x;
40         ans += (LL) p * (nxt - now);
41         now = nxt;
42     }
43     printf("%I64d
", ans);
44     return 0;
45 }

Aguin

3.7

CF 627 D Preorder Test

卡题了……崩溃。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 2e5 + 10;
 7 int n, k, a[maxn];
 8 
 9 //tree
10 int cnt, h[maxn];
11 struct edge
12 {
13     int fm, to, pre;
14 } e[maxn<<1];
15 
16 void add(int from, int to)
17 {
18     cnt++;
19     e[cnt].pre = h[from];
20     e[cnt].fm = from;
21     e[cnt].to = to;
22     h[from] = cnt;
23 }
24 
25 //dp
26 int sz[maxn], num[maxn];
27 void dfs1(int mid, int v, int f)
28 {
29     sz[v] = 1;
30     num[v] = a[v] >= mid ? 1 : 0;
31     for(int i = h[v]; i; i = e[i].pre)
32     {
33         int to = e[i].to;
34         if(to == f) continue;
35         dfs1(mid, to, v);
36         sz[v] += sz[to];
37         num[v] += num[to];
38     }
39 }
40 
41 int ff[maxn], m[2][maxn], pre[maxn];
42 void dfs2(int mid, int v, int f)
43 {
44     if(!f) ff[v] = a[v] >= mid ? 1 : 0;
45     pre[v] = m[0][v] = m[1][v] = 0;
46     for(int i = h[v]; i; i = e[i].pre)
47     {
48         int to = e[i].to;
49         if(to == f) continue;
50         if(num[v] - num[to] == sz[v] - sz[to] && ff[v]) ff[to] = 1;
51         else ff[to] = 0;
52         dfs2(mid, to, v);
53         if(a[to] < mid) continue;
54         if(sz[to] == num[to]) pre[v] += sz[to];
55         else
56         {
57             if(pre[to] > m[0][v]) m[1][v] = m[0][v], m[0][v] = pre[to];
58             else if(pre[to] > m[1][v]) m[1][v] = pre[to];
59         }
60     }
61     if(a[v] < mid) pre[v] = 0;
62     else pre[v] += m[0][v] + 1;
63 }
64 
65 bool ok(int mid)
66 {
67     dfs1(mid, 1, 0);
68     dfs2(mid, 1, 0);
69     for(int i = 1; i <= n; i++)
70     {
71         if(a[i] < mid) continue;
72         int tmp = pre[i] + m[1][i];
73         if(ff[i]) tmp += n - sz[i];
74         if(tmp >= k) return true;
75     }
76     return false;
77 }
78 
79 int main(void)
80 {
81     scanf("%d %d", &n, &k);
82     for(int i = 1; i <= n; i++) scanf("%d", a + i);
83     for(int i = 1; i < n; i++)
84     {
85         int u, v;
86         scanf("%d %d", &u, &v);
87         add(u, v), add(v, u);
88     }
89     int l = 1, r = 1e6, mid;
90     while(l < r)
91     {
92         mid = r - (r - l) / 2;
93         if(ok(mid)) l = mid;
94         else r = mid - 1;
95     }
96     printf("%d
", l);
97     return 0;
98 }

Aguin

3.8

什么都没干。

3.9

CF 627 E Orchestra

感觉很少写链表。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 int r, c, n, k, id[3333];
 8 
 9 struct vio
10 {
11     int id, x, y;
12 }v[3333], cpy[3333];
13 
14 bool cmp1(vio A, vio B)
15 {
16     return A.x < B.x;
17 }
18 
19 bool cmp2(vio A, vio B)
20 {
21     return A.y < B.y;
22 }
23 
24 struct node
25 {
26     int y;
27     int pre, nxt;
28 }l[3333];
29 
30 LL cal(int i, int k)
31 {
32     LL ret = 0LL;
33     int p1 = i, p2 = i, t = 0;
34     while(l[p1].pre && t < k - 1) p1 = l[p1].pre, t++;
35     while(l[p2].nxt && t < k - 1) p2 = l[p2].nxt, t++;
36     if(t < k - 1) return ret;
37     while(1)
38     {
39         if(l[p2].nxt) ret += (LL) (l[p1].y - l[l[p1].pre].y) * (l[l[p2].nxt].y - l[p2].y);
40         else ret += (LL) (l[p1].y - l[l[p1].pre].y) * (c + 1 - l[p2].y);
41         if(p1 == i || !l[p2].nxt) break;
42         p1 = l[p1].nxt;
43         p2 = l[p2].nxt;
44     }
45     return ret;
46 }
47 
48 void del(int i)
49 {
50     if(l[i].pre) l[l[i].pre].nxt = l[i].nxt;
51     if(l[i].nxt) l[l[i].nxt].pre = l[i].pre;
52 }
53 
54 int main(void)
55 {
56     scanf("%d %d %d %d", &r, &c, &n, &k);
57     for(int i = 0; i < n; i++) scanf("%d %d", &v[i].x, &v[i].y);
58     sort(v, v + n, cmp1);
59     for(int i = 0; i < n; i++) v[i].id = i;
60     memcpy(cpy, v, sizeof(cpy));
61     LL ans = 0LL;
62     for(int x1 = r; x1; x1--)
63     {
64         int cnt = 0;
65         LL cur = 0LL;
66         for(int i = 0; i < n; i++)
67         {
68             if(v[i].x < x1) continue;
69             sort(cpy + i, cpy + n, cmp2);
70             for(int j = i; j < n; j++)
71             {
72                 cnt++;
73                 l[cnt].y = cpy[j].y;
74                 l[cnt].pre = cnt - 1;
75                 if(cnt - 1) l[cnt-1].nxt = cnt;
76                 l[cnt].nxt = 0;
77                 id[cpy[j].id] = cnt;
78             }
79             break;
80         }
81         for(int i = 1; i + k - 1 <= cnt; i++)
82             cur += (LL) (l[i].y - l[i-1].y) * (c - l[i+k-1].y + 1);
83         int p = n - 1;
84         for(int x2 = r; x2 >= x1; x2--)
85         {
86             ans += cur;
87             while(p >= 0 && v[p].x == x2)
88             {
89                 cur -= cal(id[p],k);
90                 del(id[p]);
91                 p--;
92             }
93         }
94     }
95     printf("%I64d
", ans);
96     return 0;
97 }

Aguin

3.10-3.12

什么都没干。