# #11：假日将尽的挣扎——6

cf818A

``` 1 #include <bits/stdc++.h>
2 #define ll __int64
3 using namespace std;
4
5 ll n, k;
6
7 int main() {
8     cin >> n >> k;
9     ll a = n / 2 / (k+1);
10     ll b = k * a;
11     printf("%I64d %I64d %I64d\n", a, b, n-a-b);
12     return 0;
13 }```
View Code

818B，没有指示的数字随便赋值即可。

``` 1 #include <bits/stdc++.h>
2 #define ll __int64
3 using namespace std;
4
5 int n, m;
6 int l[105];
7 int a[105];
8 bool mark[105];
9 vector<int> v;
10
11 int main() {
12     cin >> n >> m;
13     for (int i = 0; i < m; i++) {
14         cin >> l[i];
15         int k = (l[i] - l[i-1] + n) % n;
16         if (!k)    k = n;
17         if (!a[l[i-1]]) {
18             a[l[i-1]] = k;
19         } else if (a[l[i-1]] != k) {
20             puts("-1");
21             return 0;
22         }
23     }
24
25     for (int i = 1; i <= n; i++) {
26         if (a[i]) {
27             if (!mark[a[i]])
28                 mark[a[i]] = true;
29             else {
30                 puts("-1");
31                 return 0;
32             }
33         } else {
34             v.push_back(i);
35         }
36     }
37     for (int i = 1; i <= n; i++) {
38         if (!mark[i]) {
39             a[v.back()] = i;
40             v.pop_back();
41         }
42     }
43
44     for_each(a+1, a+1+n, [](int x) {cout << x << " ";});
45     return 0;
46 }```
View Code

818C，sweep line，坐标点为下标差分计数。

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int maxcor = 1e5 + 5;
5 int d, n, m;
6 int cntl, cntr, cntt, cntb;
7 struct Point {
8     int x1, y1, x2, y2;
9 }sofa[maxcor];
10 int cnt_left[maxcor], cnt_right[maxcor], cnt_top[maxcor], cnt_bottom[maxcor];
11
12 inline bool l(int i) {
13     int k = cnt_left[max(sofa[i].x1, sofa[i].x2) - 1];
14     if (sofa[i].x1 != sofa[i].x2)    k--;
15     return k == cntl;
16 }
17
18 inline bool r(int i) {
19     int k = cnt_right[min(sofa[i].x1, sofa[i].x2) + 1];
20     if (sofa[i].x1 != sofa[i].x2)    k--;
21     return k == cntr;
22 }
23
24 inline bool t(int i) {
25     int k = cnt_top[max(sofa[i].y1, sofa[i].y2) - 1];
26     if (sofa[i].y1 != sofa[i].y2)    k--;
27     return k == cntt;
28 }
29
30 inline bool b(int i) {
31     int k = cnt_bottom[min(sofa[i].y1, sofa[i].y2) + 1];
32     if (sofa[i].y1 != sofa[i].y2)    k--;
33     return k == cntb;
34 }
35
36 int main() {
37     cin >> d >> n >> m;
38     for (int i = 1; i <= d; i++) {
39         int x1, y1, x2, y2;
40         cin >> x1 >> y1 >> x2 >> y2;
41         sofa[i] = {x1, y1, x2, y2};
42
43         cnt_left[min(x1, x2)]++;
44         cnt_right[max(x1, x2)]++;
45         cnt_top[min(y1, y2)]++;
46         cnt_bottom[max(y1, y2)]++;
47     }
48     cin >> cntl >> cntr >> cntt >> cntb;
49
50     for (int i = 1; i <= 1e5; i++) {
51         cnt_left[i] += cnt_left[i-1];
52         cnt_top[i] += cnt_top[i-1];
53     }
54     for (int i = 1e5; i; i--) {
55         cnt_right[i] += cnt_right[i+1];
56         cnt_bottom[i] += cnt_bottom[i+1];
57     }
58
59     for (int i = 1; i <= d; i++) {
60         if (l(i) && r(i) && t(i) && b(i)) {
61             cout << i << endl;
62             return 0;
63         }
64     }
65     puts("-1");
66     return 0;
67 }```
View Code

818D，gameover之时将此数打标记，否则继续计数。

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int maxcolor = 1e6 + 5;
5 bool mark[maxcolor];
6 int n, A, cntA;
7 int cnt[maxcolor];
8
9 int main() {
10     cin >> n >> A;
11     mark[A] = true;
12     for (int i = 1; i <= n; i++) {
13         int a;
14         scanf("%d", &a);
15         if (a == A)    cntA++;
16         else {
17             if (mark[a])
18                 continue;
19             else if (cnt[a] < cntA)
20                 mark[a] = true;
21             else    cnt[a]++;
22         }
23     }
24     for (int i = 1; i <= 1e6; i++)
25         if (!mark[i] && cnt[i] >= cntA) {
26             cout << i << endl;
27             return 0;
28         }
29     puts("-1");
30     return 0;
31 }```
View Code

BZOJ1011，鬼题勿做。思路根本就不是在求正解，以及迷之SPJ。

``` 1 #include <cstdio>
2 #define db double
3
4 const int maxn = 1e5 + 5;
5 int n;
6 db A;
7 db m[maxn], sum[maxn];
8
9 int main() {
10     scanf("%d%lf", &n, &A);
11     for (int i = 1; i <= n; i++) {
12         scanf("%lf", &m[i]);
13         sum[i] = sum[i-1] + m[i];
14     }
15     for (int i = 1; i <= n; i++) {
16         int k = int(A * db(i) + 1e-8);
17         db ans = 0.0;
18         if (k <= 100) {
19             for (int j = 1; j <= k; j++)
20                 ans += m[i] * m[j] / (i-j);
21         } else {
22             ans = sum[k] * m[i] / (i-k/2);
23         }
24         printf("%.6lf\n", ans);
25     }
26     return 0;
27 }```
View Code

POJ3468，分块。

``` 1 #include <cstdio>
2 #include <cmath>
3 #define ll long long
4 #define maxn 100005
5 #define rep(i, x, y) for (int i = x; i <= y; i++)
6
7 int n, m, t;
8 int L[maxn], R[maxn], pos[maxn];
9 ll a[maxn];
11
12 void Add(int l, int r, int k) {
13     int p = pos[l], q = pos[r];
14     if (p == q) {
15         rep(i, l, r)    a[i] += k;
16         sum[p] += k * (r - l + 1);
17     } else {
18         rep(i, p+1, q-1)    add[i] += k;
19         rep(i, l, R[p])    a[i] += k;
20         sum[p] += k * (R[p] - l + 1);
21         rep(i, L[q], r)    a[i] += k;
22         sum[q] += k * (r - L[q] + 1);
23     }
24 }
25
26 ll query(int l, int r) {
27     int p = pos[l], q = pos[r];
28     ll ans = 0ll;
29     if (p == q) {
30         rep(i, l, r)    ans += a[i];
31         ans += add[p] * (r - l + 1);
32     } else {
33         rep(i, p+1, q-1)    ans += sum[i] + add[i] * (R[i] - L[i] + 1);
34         rep(i, l, R[p])    ans += a[i];
35         ans += add[p] * (R[p] - l + 1);
36         rep(i, L[q], r)    ans += a[i];
37         ans += add[q] * (r - L[q] + 1);
38     }
39     return ans;
40 }
41
42 int main() {
43     scanf("%d%d", &n, &m);
44     rep(i, 1, n)    scanf("%lld", &a[i]);
45
46     t = sqrt(n);
47     rep(i, 1, t) {
48         L[i] = (i-1) * t + 1;
49         R[i] = i * t;
50     }
51     if (R[t] < n) {
52         t++;
53         L[t] = R[t-1] + 1;
54         R[t] = n;
55     }
56     rep(i, 1, t) {
57         rep(j, L[i], R[i]) {
58             pos[j] = i;
59             sum[i] += a[j];
60         }
61     }
62
63     rep(i, 1, m) {
64         char ch[3];
65         int a, b;
66         scanf("%s%d%d", ch, &a, &b);
67         if (ch[0] == ‘C‘) {
68             int c;
69             scanf("%d", &c);
71         } else {
72             printf("%lld\n", query(a, b));
73         }
74     }
75
76     return 0;
77 }```
View Code

#11：假日将尽的挣扎——6

(0)
(0)