HNOI2013解题报告

发表于 | 分类于

HNOI2013解题报告

Author: Pengyihao

Day1 T1 比赛

思路

这是一道搜索的题目。

一个重要的优化就是，因为球队的分数排序后是不影响后面的答案的，所以判重的时候可以很方便。

然后还有就是 \(28^{10}\) 是不会爆 long long 的……

代码

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
#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 == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
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> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
const int MAXN = 20, MOD = 1000000007;
LL a[MAXN];
std::map<LL, LL>mp;
LL hash(int now)
{
    LL res = now, tmp[MAXN];
    FOR(i, 1, now) tmp[i] = a[i];
    std::sort(tmp + 1, tmp + now + 1, std::less<int>());
    FOR(i, 1, now) res += res * 28 + tmp[i];
    return res;
}
LL DFS(int now, int n)
{
    if (a[n] > 3 * (n - now)) return -1;
    LL res = 0;
    if (now == n) {
        if (n == 1) return 1;
        else {
            LL h = hash(n - 1);
            if (mp[h]) return mp[h];
            return mp[h] = DFS(1, n - 1);
        }
    }
    
    if (a[n] >= 3) {
        LL tmp = 0;
        a[n] -= 3, tmp = DFS(now + 1, n);
        if (tmp != -1) (res += tmp) %= MOD;
        a[n] += 3;
    }
    
    if (a[n] && a[now]) {
        LL tmp = 0;
        a[n]--, a[now]--, tmp = DFS(now + 1, n);
        if (tmp != -1) (res += tmp) %= MOD;
        a[n]++, a[now]++;
    }
    
    if (a[now] >= 3) {
        LL tmp = 0;
        a[now] -= 3, tmp = DFS(now + 1, n);
        if (tmp != -1) (res += tmp) %= MOD;
        a[now] += 3;
    }
    
    return res ? res : -1;
}
int n;
int main()
{
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    in(n);
    FOR(i, 1, n) in(a[i]);
    std::sort(a + 1, a + n + 1, std::less<int>());
    
    printf("%lld\n", DFS(1, n));
    
    return 0;
}

Day1 T2 消毒

思路

可以发现最优的话一定要是，选择的区域中的一维为 \(1\)，另外两维为最大值。

因为 \(abc\leq 5000\)，所以它们中的最小值是小于 \(20\) 的。

把这一维看作高，然后枚举每一层选不选。

然后剩下的就转化成了二维问题。

这就是个典型的二分图最小点覆盖，网络流跑就可以了。

时间复杂度为 \(O(\)松\()\) 。注意要进行常数优化。

代码

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
#include <bits/stdc++.h>
typedef long long LL;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#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 == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
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> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
using std::vector;
const int MAXN = 5002;
bool chose[20];
int a[4], ans;
bool map[MAXN][MAXN];
std::vector<std::vector<int> >g[MAXN];
void init()
{
    ans = 0x3f3f3f3f;
    
    FOR(i, 1, 3) in(a[i]);
    FOR(i, 0, a[1] + 1) {
        g[i].resize(a[2] + 2);
        FOR(j, 0, a[2] + 1) g[i][j].resize(a[3] + 2);
    }
   
    FOR(i, 1, a[1]) {
        FOR(j, 1, a[2]) FOR(k, 1, a[3]) in(g[i][j][k]);
    }
}
const int ss = 0, tt = 5008, INF = 0x3f3f3f3f;
using std::queue;
queue<int>q;
bool link[MAXN];
int dis[5010], cur[5010];
int cnt, head[5010], data[20010], flow[20010], nxt[20010];
void add(int x, int y, int z)
{
    nxt[cnt] = head[x]; data[cnt] = y; flow[cnt] = z; head[x] = cnt++;
    nxt[cnt] = head[y]; data[cnt] = x; flow[cnt] = 0; head[y] = cnt++;
}
int times, maxx = 1, alledge;
struct Edge {
    int x, y;
    Edge(int a=0, int b=0): x(a), y(b) {}
};
std::vector<Edge>edge[20];
bool bfs()
{
    dis[ss] = times; q.push(ss);
    while (!q.empty()) {
        int now = q.front(); q.pop();
        for (int i = head[now]; i != -1; i = nxt[i]) {
            if (dis[data[i]] < times && flow[i]) {
                dis[data[i]] = dis[now] + 1;
                q.push(data[i]);
                chkmax(maxx, dis[now] + 1);
            }
        }
    }
    return dis[tt] >= times;
}
int dfs(int now, int fl)
{
    if (now == tt) return fl;
    int flo;
    for (int i = head[now]; i != -1; i = nxt[i]) {
        if (flow[i] && dis[data[i]] == dis[now] + 1) {
            if (flo = dfs(data[i], Min(fl, flow[i]))) {
                flow[i] -= flo;
                flow[i ^ 1] += flo;
                return flo;
            }
        }
    }
    return 0;
}
void check(int minx)
{
    int tmptot = 0;
    FOR(i, 1, minx) if (chose[i]) tmptot++;
    if (tmptot >= ans) return;
    cnt = 0;
    int tot = tmptot;
// ***********************************************
// make_Edge
    int Addition;
    if (minx == a[1]) Addition = a[2];
    else if (minx == a[2]) Addition = a[1];
    else Addition = a[1];
    FOR(k, 1, minx) if (!chose[k]) {
        FOR(i, 0, edge[k].size() - 1) {
            int fr = edge[k][i].x, to = edge[k][i].y + Addition;
            if (!map[fr][to - Addition]) {
                add(fr, to, 1);
                if (!link[fr]) {link[fr] = true; add(ss, fr, 1);}
                if (!link[to]) {link[to] = true; add(to, tt, 1);}
            }
        }
    }
    
// ***********************************************
    
    int fl = 0;
    times = maxx + 1;
    
    while (bfs()) {
        //memcpy(cur, head, sizeof head);
        int tmp;
        while (tmp = dfs(ss, INF)) fl += tmp;
        times = maxx + 1;
    }
    chkmin(ans, fl + tot);
    FOR(k, 1, minx) if (!chose[k]) FOR(i, 0, edge[k].size() - 1) {
        map[edge[k][i].x][edge[k][i].y] = false;
        link[edge[k][i].x] = link[edge[k][i].y + Addition] = false;
        head[edge[k][i].x] = head[edge[k][i].y + Addition] = -1;
    }
    head[ss] = head[tt] = -1;
}
void search(int now, int minx)
{
    chose[now] = false;
    if (now == minx) check(minx);
    else search(now + 1, minx);
    chose[now] = true;
    if (now == minx) check(minx);
    else search(now + 1, minx);
    chose[now] = false;
}
void work()
{
    memset(head, -1, sizeof head);
    
    int minx = 5000;
    FOR(i, 1, 3) chkmin(minx, a[i]);
    alledge = 0;
    FOR(i, 1, minx) {
        edge[i].clear();
    }
    
    if (minx == a[1]) {
        FOR(k, 1, a[1]) {
            FOR(i, 1, a[2])    FOR(j, 1, a[3])
                if (g[k][i][j]) edge[k].push_back(Edge(i, j));
        }
    }
    else if (minx == a[2]) {
        
            FOR(i, 1, a[1]) FOR(k, 1, a[2]) { FOR(j, 1, a[3])
                if (g[i][k][j]) edge[k].push_back(Edge(i, j));
        }
    }
    else {
        
            FOR(i, 1, a[1]) FOR(j, 1, a[2]) FOR(k, 1, a[3]) {
                if (g[i][j][k]) edge[k].push_back(Edge(i, j));
            }
    }
    
    search(1, minx);
    printf("%d\n", ans);
    debug("%d\n", ans);
}
int main()
{
    freopen("clear.in", "r", stdin);
    freopen("clear.out", "w", stdout);
    
    int tcase; in(tcase);
    while (tcase--) {
        init();
        work();
    }
    
    return 0;
}

Day1 T3 旅行

这是一道很难的题目。我看了题解也暂时无法解决此题，所以决定跳过它。

Day2 T1 数列

思路

考虑差分数列。

差分数列的可能数量为 \(m^{k-1}\)。

于是答案就为 \(\sum{n-\sum_{i=1}^{k-1}{a_i}}\)

其中 \(a_i\) 表示差分数列的第 \(i\) 项，最前面的 \(\sum\) 表示枚举的差分数列。

\(n\) 可以提出来，而 \(a_i\) 的贡献是独立的。

所以最后答案为

\[m^{k-1}\times n - m(m+1)/2\times (k-1)\times m^{k-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
#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 == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
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> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
LL ans = 0;
LL n, k, m, p;
LL power(LL x, LL y, LL p)
{
    x %= p;
    
    LL ret = 1;
    while (y) {
        if (y & 1) ret = 1ll * ret * x % p;
        x = 1ll * x * x % p;
        y >>= 1;
    }
    return ret;
}
int main()
{
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);
    
    in(n); in(k); in(m); in(p);
    n %= p;
    
    ans = 1ll * power(m, k - 1, p) * n % p;
    ans = ((ans - 1ll * (1ll * m * (m + 1) / 2) % p *
           (k - 1) % p * power(m, k - 2, p) % p) % p + p) % p;
    printf("%lld\n", ans);
    
    return 0;
}

Day2 T2 游走

思路

我们可以贪心来做——求出每条边走过的期望次数，然后从大到小分配从 \(1\) 到 \(m\) 的编号。

边的期望次数的求法是一个裸的高斯消元，这里就不再赘述。

代码

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
#include <bits/stdc++.h>
 
const int MAXN = 510;
 
bool f[MAXN][MAXN];
int n, m, du[MAXN], all;
long double matrix[MAXN][MAXN], times[MAXN], timess[MAXN * MAXN];
 
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();
}
 
void gauss() {
    for (int j = 1; j <= n; j++) {
        long double maxu = -1;
        int maxv = 0;
        for (int i = j; i <= n + 1; i++)
            if (maxu < fabs(matrix[i][j])) {
                maxu = fabs(matrix[i][j]);
                maxv = i;
            }
        for (int i = 1; i <= n + 1; i++) {
            long double t = matrix[j][i];
            matrix[j][i] = matrix[maxv][i];
            matrix[maxv][i] = t;
        }
        long double eps = matrix[j][j];
        if (fabs(eps) < 1e-10) continue;
        for (int i = 1; i <= n + 1; i++)
            matrix[j][i] /= eps;
        for (int i = 1; i <= n + 1; i++)
            if (i != j) {
                long double epss = matrix[i][j];
                if (fabs(epss) < 1e-10) continue;
                for (int k = 1; k <= n + 1; k++)
                    matrix[i][k] -= matrix[j][k] * epss;
            }
    }
    for (int i = 1; i <= n; i++)
        times[i] = matrix[i][n + 1] / matrix[i][i];
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (f[i][j]) {
                if (j == n) timess[++all] = times[i] / du[i];
                else timess[++all] = times[i] / du[i] + times[j] / du[j];
            }
    std::sort(timess + 1, timess + all + 1);
    long double ans = 0;
    for (int i = 1; i <= all; i++) {
        ans += timess[i] * (all - i + 1);
    }
    printf("%.3Lf\n", ans);
}
 
int main() {
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    in(n); in(m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        in(u); in(v);
        f[u][v] = f[v][u] = true;
        if (u != n) du[u]++;
        if (v != n) du[v]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++)
            if (f[i][j])
                matrix[i][j] = (long double)(1) / du[j];
        matrix[i][i] = -1;
        if (i == 1) matrix[i][n + 1] = -1;
    }
    matrix[n + 1][n] = 1;
    matrix[n + 1][n + 1] = 1;
    gauss();
    return 0;
}

Day2 T3 切糕

思路

对于每一个位置，从所有层向上一层连边，容量为点权。

对于每一个位置，从第 \(i\) 层向相邻位置的 \(i-d\) 层连边，容量为 \(+\infty\)。

对于每一个位置，从源点向第一层连边，容量为 \(+\infty\)。

对于每一个位置，从最高层向汇点连边，容量为 \(+\infty\)。

代码

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
#include <bits/stdc++.h>
#define PLA(i, j, k) ((i) * 2500 + (j) * 50 + (k))
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 == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
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> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
int p, qs, r, d;
int height[50][50][50];
int cnt, dis[200010], head[200010], data[200010 << 1], flow[200010 << 1], cur[200010], nxt[200010 << 1];
using std::queue; queue<int>q;
const int ss = 0, tt = 200009, INF = 0x3f3f3f3f;
bool bfs()
{
    memset(dis, -1, sizeof dis);
    dis[ss] = 0; q.push(ss);
    while (!q.empty()) {
        int now = q.front(); q.pop();
        for (int i = head[now]; i != -1; i = nxt[i]) {
            if (dis[data[i]] == -1 && flow[i]) {
                dis[data[i]] = dis[now] + 1;
                q.push(data[i]);
            }
        }
    }
    return dis[tt] != -1;
}
int dfs(int now, int fl)
{
    if (now == tt) return fl;
    int flo;
    for (int &i = cur[now]; i != -1; i = nxt[i]) {
        if (flow[i] && dis[data[i]] == dis[now] + 1) {
            if (flo = dfs(data[i], Min(fl, flow[i]))) {
                flow[i] -= flo;
                flow[i ^ 1] += flo;
                return flo;
            }
        }
    }
    return 0;
}
void add(int x, int y, int z)
{
    nxt[cnt] = head[x]; data[cnt] = y; flow[cnt] = z; head[x] = cnt++;
    nxt[cnt] = head[y]; data[cnt] = x; flow[cnt] = 0; head[y] = cnt++;
}
int main()
{
    freopen("cake.in", "r", stdin);
    freopen("cake.out", "w", stdout);
    
    memset(head, -1, sizeof head);
    
    in(p); in(qs); in(r); in(d);
    
    FOR(i, 1, r) {
        FOR(j, 1, p) FOR(k, 1, qs) in(height[i][j][k]);
    }
    
    FOR(i, 1, p) FOR(j, 1, qs) {
        add(ss, PLA(i, j, 1), INF);
        FOR(k, 1, r) {
            add(PLA(i, j, k), PLA(i, j, k + 1), height[k][i][j]);
        }
        add(PLA(i, j, r + 1), tt, INF);
    }
    FOR(i, 1, p) FOR(j, 1, qs) {
        FOR(k, d + 1, r + 1) {
            if (i != p) add(PLA(i, j, k), PLA(i + 1, j, k - d), INF);
            if (i != 1) add(PLA(i, j, k), PLA(i - 1, j, k - d), INF);
            if (j != qs) add(PLA(i, j, k), PLA(i, j + 1, k - d), INF);
            if (j != 1) add(PLA(i, j, k), PLA(i, j - 1, k - d), INF);
        }
    }
    int fl = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof head);
        int tmp; while (tmp = dfs(ss, INF)) fl += tmp;
    }
    printf("%d\n", fl);
    
    return 0;
}