HNOI2011解题报告

发表于 | 分类于

HNOI2011解题报告

Author: Pengyihao

Day1 T1 数学作业

题意

给出正整数 \(n\), \(m\)，要求将 \(1-n\) 这 \(n\) 个数连接起来，问连接起来的数对 \(m\) 取模的结果是多少。

\(1\leq n\leq 10^{18}, 1\leq m\leq 10^9\)

思路

如果连接的数的位数一样，那么可以用矩阵乘法进行优化。因为有 \[nowans = lastans * 10^k + now\]

这个恒定的递推式（对于位数一样的数），所以可以分段矩阵乘法。

因为只有 \(lg(n)\) 个位数，所以可以解决这个问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (LL i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define REP(i, a, b) for (LL i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
LL n; LL m;
LL ten[20];
LL tmpans;
LL ret[4][4], tmp[4][4];
void mul(LL x[4][4], LL y[4][4], LL z[4][4])
{
    LL t[4][4];
    memset(t, 0, sizeof t);
    FOR(i, 1, 3) FOR(j, 1, 3) FOR(k, 1, 3)
        t[i][j] = (t[i][j] + 1ll * x[i][k] * y[k][j] % m) % m;
    memcpy(z, t, sizeof t);
}
bool work(LL x)
{
    bool flagend = false;
    LL ci = ten[x] - ten[x - 1], fr = ten[x - 1] % m;
    
    if (n < ten[x]) {
        ci = n - ten[x - 1] + 1;
        flagend = true;
    }
    memset(ret, 0, sizeof ret);
    FOR(i, 1, 3) ret[i][i] = 1;
    memset(tmp, 0, sizeof tmp);
    tmp[1][1] = 1; tmp[1][2] = 1; tmp[2][2] = 1;
    tmp[2][3] = 1; tmp[3][3] = ten[x] % m;
    while (ci) {
        if (ci & 1) mul(ret, tmp, ret);
        mul(tmp, tmp, tmp);
        ci >>= 1;
    }
    tmpans = (
        1ll * ret[1][3] % m +
        1ll * fr * ret[2][3] % m +
        1ll * tmpans * ret[3][3] % m
    ) % m;
    if (flagend) {
        printf("%lld\n", tmpans);
        return true;
    }
    return false;
}
int main()
{
    freopen("homework.in", "r", stdin);
    freopen("homework.out", "w", stdout);
    
    in(n); in(m);
    ten[0] = 1;
    FOR(i, 1, 18) ten[i] = ten[i - 1] * 10;
    
    FOR(i, 1, 18) if (work(i)) break;
    return 0;
}

Day1 T2 勾股定理

这个题目有点问题，我在网上看题解的时候，发现这题的做法其实是不靠谱的，意思是说这是一道玄学的题目。

对于题目所给的数据范围，标程不一定都能在合理的时间内跑出答案。

所以我就跳过了这道题目。

Day1 T3 赛车游戏

思路

首先可以用拉格朗日乘数法证明，如果要达到最优成绩，那么每条路上的速度要尽可能相等。

于是就可以二分这个速度，然后计算耗油量。

注意如果某条路上耗油量为负数，那么就不能在这条路上用当前二分的速度来计算，因为可能耗油量为负数。

所以我们可以把这条路上的速度设置为令耗油量为0的速度。

这样就可以正确地计算耗油量和跑的时间了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MAXN = 10010;
int T, n;
double a, b, vmax, f;
double s[MAXN], k[MAXN], sv[MAXN];
const int LIMITS = 1000;
double check(double _v)
{
    double sum = 0;
        
    FOR(i, 1, n) {
        if (_v < sv[i]) {
            sum = sum + Max(0., a * sv[i] + b * k[i]) * s[i];
        }
        else sum = sum + Max(0., a * _v + b * k[i]) * s[i];
    }
    return sum;
}
int main()
{
    freopen("race.in", "r", stdin);
    freopen("race.out", "w", stdout);
    
    in(T);
    
    while (T--) {
        scanf("%lf%lf%lf%lf", &a, &b, &vmax, &f);
        in(n);
        FOR(i, 1, n) {
            double x, y;
            scanf("%lf%lf", &x, &y);
            x /= 1000.0; y /= 1000.0;
            
            s[i] = sqrt(x * x + y * y);
            k[i] = y / x;
            if (k[i] < 0) sv[i] = Min(-b * k[i] / a, vmax);
            else sv[i] = 0;
        }
        
        double l = 0, r = 1000000000;
        
        FOR(i, 1, LIMITS) {
            double mid = (l + r) / 2;
            if (mid > vmax || check(mid) > f) r = mid;
            else l = mid;
        }
        if (check(l) > f) puts("IMPOSSIBLE");
        else {
            double ret = 0;
            
            FOR(i, 1, n) {
                if (sv[i] > l) ret += s[i] / sv[i];
                else ret += s[i] / l;
            }
            printf("%.5lf\n", ret);
        }
    }
    
    return 0;
}

Day1 T4 括号修复

思路

首先对于一个括号序列，如何计算它最少需要改多少个括号呢？

我们发现如果把可以匹配的括号一层一层去掉，那么最后一定会变成下面这个样子：

))))))))(((((((((

就是左边一连串的括号，右边一连串的括号。

假设左边有 \(l\) 个括号，右边有 \(r\) 个括号。

那么一共要改

\[\lfloor \frac{l+1}{2}\rfloor + \lfloor\frac{r+1}{2}\rfloor\]

个括号。

根据“维修数列”这一题的经验，我们可以用splay来维护括号序列。

用+1表示’(‘，用-1表示’)’，那么左边的括号数量就是从左开始的最小子段和，右边的括号数量就是从右开始的最大子段和。

操作1：直接打标记。

操作2：直接打标记。

操作3：变换一下从左开始的最小、最大子段和，从右开始的最小、最大子段和。

操作4：直接取值。

怎么合并标记呢？

当打区间赋值标记的时候，可以直接清空反转标记。

当打反转标记的时候，要将赋值标记乘上-1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
template <typename Tp> void swap(Tp &x, Tp &y) {Tp z = x; x = y; y = z;}
struct Node {
    bool isa, ist_dn, isset;
    
    Node *ch[2], *fa;
    int lmax, lmin, rmax, rmin, data, sum, sz, wt_set;
    void update();
    void pushdown();
    void rotate();
    void splay(Node*);
};
const int MAXN = 100010;
Node *nul, *rot, *to[MAXN];
int n, m;
char str[MAXN];
void push(Node *hr, Node *top)
{
    if (hr != nul) push(hr -> fa, top);
    if (hr != nul) hr -> pushdown();
}
void Node::splay(Node *top)
{
    push(this, nul);
    if (ch[0] != nul) ch[0] -> pushdown();
    if (ch[1] != nul) ch[1] -> pushdown();
    while (fa != top) {
        if (fa -> fa != top) {
            bool t = (fa -> fa -> ch[0] == fa ? 0 : 1);
            if (fa -> ch[t] == this) {
                fa -> rotate(); rotate();
            }
            else rotate(), rotate();
        }
        else rotate();
    }
    if (top == nul) rot = this;
}
void Node::rotate()
{
    Node *pa = fa;
    fa = pa -> fa;
    if (fa != nul) {
        bool t = (fa -> ch[0] == pa ? 0 : 1);
        fa -> ch[t] = this;
    }
    
    pa -> fa = this;
    
    bool t = (pa -> ch[0] == this ? 0 : 1);
    
    pa -> ch[t] = ch[t ^ 1];
    if (ch[t ^ 1] != nul) ch[t ^ 1] -> fa = pa;
    ch[t ^ 1] = pa;
    pa -> update(); update();
}
void Node::update()
{
    if (ch[0] != nul) ch[0] -> pushdown();
    if (ch[1] != nul) ch[1] -> pushdown();
    
    sum = data; sz = 1;
    if (ch[0] != nul) sum += ch[0] -> sum, sz += ch[0] -> sz;
    if (ch[1] != nul) sum += ch[1] -> sum, sz += ch[1] -> sz;
    lmin = Min(0, Min(ch[0] -> lmin, ch[0] -> sum + data + ch[1] -> lmin));
    rmin = Min(0, Min(ch[1] -> rmin, ch[1] -> sum + data + ch[0] -> rmin));
    
    lmax = Max(0, Max(ch[0] -> lmax, ch[0] -> sum + data + ch[1] -> lmax));
    rmax = Max(0, Max(ch[1] -> rmax, ch[1] -> sum + data + ch[0] -> rmax));
}
void Node::pushdown()
{
    if (ist_dn) {
        ist_dn = false;
        int tlmin = lmin, trmin = rmin;
        int tlmax = lmax, trmax = rmax;
        data = -data; sum = -sum;
 
        lmin = -tlmax; lmax = -tlmin;
        rmax = -trmin; rmin = -trmax;
        wt_set = -wt_set;
        
        if (ch[0] != nul) {
            ch[0] -> ist_dn ^= 1;
//            if (ch[0] -> isset)
//                ch[0] -> wt_set = -ch[0] -> wt_set;
        }
        if (ch[1] != nul) {
            ch[1] -> ist_dn ^= 1;
//            if (ch[1] -> isset)
//                ch[1] -> wt_set = -ch[1] -> wt_set;
        }
    }
    if (isset) {
        isset = false;
        if (ch[0] != nul)
            ch[0] -> isset = true, ch[0] -> wt_set = wt_set, ch[0] -> ist_dn = false;
        if (ch[1] != nul)
            ch[1] -> isset = true, ch[1] -> wt_set = wt_set, ch[1] -> ist_dn = false;
        
        data = wt_set; sum = wt_set * sz;
        lmin = rmin = wt_set < 0 ? wt_set * sz : 0;
        lmax = rmax = wt_set > 0 ? wt_set * sz : 0;
    }
    if (isa) {
        isa = false;
        if (ch[0] != nul) ch[0] -> isa ^= 1;
        if (ch[1] != nul) ch[1] -> isa ^= 1;
        swap(lmin, rmin);
        swap(lmax, rmax);
        swap(ch[0], ch[1]);
    }
}
void start()
{
    nul = new Node;
    nul -> sz = 0;
    nul -> data = nul -> sum = 0;
    nul -> isa = nul -> ist_dn = nul -> isset = false;
    
    nul -> ch[0] = nul -> ch[1] = nul -> fa = nul;
    
    nul -> lmax = nul -> rmax = 0;
    nul -> lmin = nul -> rmin = 0;
}
void insert(int now)
{
    to[now] = new Node;
    if (now == 1) rot = to[now];
    to[now] -> sz = 1;
    to[now] -> isa = to[now] -> isset = to[now] -> ist_dn = false;
    
    to[now] -> ch[0] = to[now] -> ch[1] = to[now] -> fa = nul;
    if (now != 1) to[now] -> fa = to[now - 1], to[now - 1] -> ch[1] = to[now];
    to[now] -> data = (str[now] == '(' ? 1 : -1);
    to[now] -> sum = to[now] -> data;
}
Node *find_key(int rnk)
{
    Node *x = rot;
    while (1) {
        x -> pushdown();
        int rrnk = (x -> ch[0] == nul ? 1 : x -> ch[0] -> sz + 1);
        if (rrnk == rnk)
            return x;
        if (rrnk >  rnk)
            x = x -> ch[0];
        else {
            x = x -> ch[1];
            rnk -= rrnk;
        }
    }
}
char command[20];
int main()
{
    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout);
    
    in(n); in(m);
    scanf("%s", str + 1);
    start();
    
    FOR(i, 1, n) insert(i);
    DNF(i, n, 1) to[i] -> update();
    FOR(i, 1, m) {
        scanf("%s", command);
        if (command[0] == 'R') {
            int x, y;
            in(x); in(y);
            scanf("%s", command);
            Node *hr;
            if (x == 1 && y == n) hr = rot;
            if (x == 1 && y != n) {
                find_key(y + 1) -> splay(nul);
                hr = rot -> ch[0];
            }
            if (x != 1 && y == n) {
                find_key(x - 1) -> splay(nul);
                hr = rot -> ch[1];
            }
            if (x != 1 && y != n) {
                find_key(x - 1) -> splay(nul);
                find_key(y + 1) -> splay(rot);
                hr = find_key(y + 1) -> ch[0];
            }
            hr -> pushdown();
            hr -> ist_dn = false; hr -> isset = true;
            hr -> wt_set = (command[0] == '(' ? 1 : -1);
            hr -> pushdown();
            while (hr -> fa != nul) {
                hr = hr -> fa;
                hr -> update();
            }
        }
        else if (command[0] == 'Q') {
            int x, y;
            in(x); in(y);
            Node *hr;
            if (x == 1 && y == n) hr = rot;
            if (x == 1 && y != n) {
                find_key(y + 1) -> splay(nul);
                hr = rot -> ch[0];
            }
            if (x != 1 && y == n) {
                find_key(x - 1) -> splay(nul);
                hr = rot -> ch[1];
            }
            if (x != 1 && y != n) {
                find_key(x - 1) -> splay(nul);
                find_key(y + 1) -> splay(rot);
                hr = find_key(y + 1) -> ch[0];
            }
            hr -> pushdown();
            printf("%d\n", (-(hr -> lmin) + 1) / 2 + (hr -> rmax + 1) / 2);
        }
        else if (command[0] == 'S') {
            int x, y;
            in(x); in(y);
            Node *hr;
            if (x == 1 && y == n) hr = rot;
            if (x == 1 && y != n) {
                find_key(y + 1) -> splay(nul);
                hr = rot -> ch[0];
            }
            if (x != 1 && y == n) {
                find_key(x - 1) -> splay(nul);
                hr = rot -> ch[1];
            }
            if (x != 1 && y != n) {
                find_key(x - 1) -> splay(nul);
                find_key(y + 1) -> splay(rot);
                hr = find_key(y + 1) -> ch[0];
            }
            hr -> isa ^= 1;
            hr -> pushdown();
        }
        else if (command[0] == 'I') {
            int x, y;
            in(x); in(y);
            Node *hr;
            if (x == 1 && y == n) hr = rot;
            if (x == 1 && y != n) {
                find_key(y + 1) -> splay(nul);
                hr = rot -> ch[0];
            }
            if (x != 1 && y == n) {
                find_key(x - 1) -> splay(nul);
                hr = rot -> ch[1];
            }
            if (x != 1 && y != n) {
                find_key(x - 1) -> splay(nul);
                find_key(y + 1) -> splay(rot);
                hr = find_key(y + 1) -> ch[0];
            }
            hr -> ist_dn ^= 1;
            hr -> pushdown();
            while (hr -> fa != nul) {
                hr = hr -> fa;
                hr -> update();
            }
        }
    }
    
    return 0;
}

Day2 T1 任务调度

这是一道随机出答案的题目，所以我没有做，直接跳过了。

Day2 T2 XOR和路径

思路

这是一个简单的概率DP。

因为是XOR，所以我们可以逐位求出期望。

假设当前在处理第 \(k\) 位，设 \(f[i]\) 表示从 \(i\) 到 \(n\) 异或值为 \(1\) 的概率。

则对于 \(i\) 的一个连出去的边所指向的节点 \(j\)，如果边权为 \(1\)，则对 \(f[i]\) 的贡献为

\[\frac{1-f[j]}{deg[i]}\]

如果边权为 \(0\)，则对 \(f[i]\) 的贡献为

\[\frac{f[j]}{deg[i]}\]

最后别忘了 \(f[n]=0\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MAXN = 110, MAXM = 10010;
const double eps = 1e-8;
int n, m, cnt, du[MAXN];
int head[MAXN], data[MAXM << 1], nxt[MAXM << 1], flow[MAXM << 1];
double matrix[MAXN][MAXN];
void add(int x, int y, int z)
{
    nxt[cnt] = head[x]; data[cnt] = y; flow[cnt] = z; head[x] = cnt++;
    if (x != y) {nxt[cnt] = head[y]; data[cnt] = x; flow[cnt] = z; head[y] = cnt++;}
}
void gauss_george()
{
    FOR(i, 1, n) {
        double maxv = -1; int maxq;
        FOR(j, i, n) {
            if (fabs(matrix[j][i]) > maxv) {
                maxv = fabs(matrix[j][i]);
                maxq = j;
            }
        }
        if (fabs(matrix[maxq][i] - maxv) > eps) {
            assert(0);
        }
        if (fabs(matrix[maxq][i]) < eps) continue;
        
        FOR(j, 1, n + 1) {
            double tmp = matrix[i][j];
            matrix[i][j] = matrix[maxq][j];
            matrix[maxq][j] = tmp;
        }
        double chu = matrix[i][i];
        FOR(j, 1, n + 1) matrix[i][j] /= chu;
        FOR(j, 1, n) {
            if (j != i) {
                if (fabs(matrix[j][i]) < eps) continue;
                double chu = matrix[j][i];
                FOR(k, 1, n + 1)
                    matrix[j][k] -= matrix[i][k] * chu;
            }
        }
    }
}
int main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    
    in(n); in(m);
    memset(head, -1, sizeof head);
    
    FOR(i, 1, m) {
        int u, v, w;
        in(u); in(v); in(w);
        add(u, v, w);
        du[v]++; if (u != v) du[u]++;
    }
    double ans = 0;
    
    FOR(i, 1, 31) {
        memset(matrix, 0, sizeof matrix);
        FOR(j, 1, n - 1) {
            matrix[j][j] = du[j];
            for (int k = head[j]; k != -1; k = nxt[k]) {
                if (flow[k] & (1 << (i - 1))) {
                    matrix[j][data[k]] += 1.0;
                    matrix[j][n + 1] += 1.0;
                }
                else
                    matrix[j][data[k]] -= 1.0;
            }
        }
        matrix[n][n] = 1;
        gauss_george();
        ans += (1 << (i - 1)) * matrix[1][n + 1] / matrix[1][1];
    }
    printf("%.3lf\n", ans);
    
    return 0;
}

Day2 T3 数矩形

思路

这又是一道玄学题。

我们找到每条线段的中点，然后按照中点为第一关键字，线段的长度为第二关键字进行排序。

然后对于每个线段，暴力找前面所有跟它中点重合且长度相等的线段……

这样就可以过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(), f = 1; x = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') ch = getchar(), f = -1;
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MAXN = 2010;
struct Node {
    LL lenth;
    int posx, posy, rposx[2], rposy[2];
} pos[MAXN * MAXN];
int n, cnt, x[MAXN], y[MAXN];
LL two(LL x) {return x * x;}
bool cmp(const Node &x, const Node &y)
{
    bool t1 = x.posx < y.posx;
    bool t2 = x.posx == y.posx && x.posy < y.posy;
    bool t3 = x.posx == y.posx && x.posy == y.posy && x.lenth < y.lenth;
    return t1 || t2 || t3;
}
LL abs(LL x) {return x > 0 ? x : -x;}
int main()
{
    freopen("rectangle.in", "r", stdin);
    freopen("rectangle.out", "w", stdout);
    
    in(n);
    FOR(i, 1, n) {
        in(x[i]); in(y[i]);
    }
    FOR(i, 1, n) FOR(j, i + 1, n) {
        pos[++cnt].posx = x[i] + x[j], pos[cnt].posy = y[i] + y[j];
        pos[cnt].lenth = two(x[i] - x[j]) + two(y[i] - y[j]);
        pos[cnt].rposx[0] = x[i]; pos[cnt].rposx[1] = x[j];
        pos[cnt].rposy[0] = y[i]; pos[cnt].rposy[1] = y[j];
    }
    std::sort(pos + 1, pos + cnt + 1, cmp);
    LL ans = -1;
    
    FOR(i, 1, cnt) {
        for (int j = i - 1;
             j >= 1 && pos[j].lenth == pos[i].lenth
                 && pos[i].posx == pos[j].posx && pos[i].posy == pos[j].posy;
             j--)
            chkmax(ans,
                   abs(2ll * pos[i].rposx[0] * pos[j].rposy[0] - 2ll * pos[i].rposy[0] * pos[j].rposx[0]
                   + 1ll * pos[j].rposx[0] * pos[i].posy - 1ll * pos[j].rposy[0] * pos[i].posx
                       + 1ll * pos[i].posx * pos[i].rposy[0] - 1ll * pos[i].posy * pos[i].rposx[0]));
    }
    printf("%lld\n", ans);
    
    return 0;
}

Day2 T4 卡农

思路

我们可以先算出可以记片段之间顺序的方案数，因为两两不同，所以最后除以 \(m!\) 就可以了。

设 \(f[i]\) 表示前 \(i\) 个片段满足题意的方案数。

如果前 \(i-1\) 个片段已经决定了，那么第 \(i\) 个片段也可以由奇偶关系决定了。

那么答案就为 \(P(2^n-1, i-1)\) 减去不合法的方案。

这里的 \(P(2^n-1, i-1)\) 可以递推求。

不合法的方案只有两种可能：

  1. 前 \(i-1\) 个片段已经满足偶数要求了，那么第 \(i\) 个片段必须是空集合，不符合规定。 所以要减去 \(f[i-1]\)。

  2. 被决定出来的第 \(i\) 个片段重复了。 那么与它重复的那个片段有 \(i-1\) 个位置可以选择。 并且如果除了这两个片段之外，其它的片段均满足偶数条件，那么这两个片段一定相同。 而这个片段本身也有 \(2^n-1-(i-2)\) 种可能。 所以要减去 \(f[i-2]\times (i-1)\times (2^n-1-(i-2))\)

所以就可以直接求了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MOD = 100000007;
const int MAXN = 1000010;
int n, m;
LL f[MAXN];
LL power(LL x, LL y)
{
    LL ret = 1;
    while (y) {
        if (y & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ret;
}
int main()
{
    freopen("canon.in", "r", stdin);
    freopen("canon.out", "w", stdout);
    
    in(n); in(m);
    LL pre = 1, po = (power(2, n) - 1 + MOD) % MOD;
    pre = pre * po % MOD;
    po = (po - 1 + MOD) % MOD;
    f[0] = 1; f[1] = 0;
    FOR(i, 2, m) {
        f[i] = pre;
        f[i] = (f[i] - f[i - 1] + MOD) % MOD;
        f[i] = (f[i] - f[i - 2] * (i - 1) % MOD * (power(2, n) - 1 - (i - 2)) % MOD + MOD) % MOD;
        pre = pre * po % MOD;
        po = (po - 1 + MOD) % MOD;
    }
    LL ret = 1; FOR(i, 1, m) ret = ret * i % MOD;
    printf("%lld\n", f[m] * power(ret, MOD - 2) % MOD);
    
    return 0;
}