发表更新题解18 分钟读完 (大约2701个字)0次访问

「NOIp2018」题解

emmm，今天开始从2018向前做NOIp的真题，并写一些题解，太蒻了Orz

$D1T1$ 铺设道路

嗯～13年原题，__贪心AC__

题解

对区间进行“填坑”
贪心策略：

1
if (d[i] > d[i - 1]) ans += d[i] - d[i - 1];

$proof:$
假设现在有一个坑，旁边还有一个坑。
那肯定会同时填上两个坑，所以__小的坑会被大的坑带着填上__，及__小坑免费，大坑减少a[i] - a[i - 1]__
$Q.E.D$
结果还要加上a[1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

int n, d[maxn];
long long ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &d[i]);
    }
    for (int i = 2; i <= n; ++i) {
        if (d[i] > d[i - 1]) {
            ans += d[i] - d[i - 1];
        }
    }
    printf("%lld", ans + d[1]);
    return 0;
}
/* 41ms 1220kB */

$D1T2$ 货币系统

表面上是数论，其实就是个__动态规划__

题解

首先设$A = (n, a) \ \ B = (m, b)$
可以证明$B \subseteq A$
$proof:$
我们设$x\in A$且$x$不能被$A$集合内除它以外的元素组成。
然后我们假设$x \notin B$，那么就说明$B$集合中必然存在一些元素能够组成$x$。
那么这些元素至少存在一个不在集合$A$内并且不能被集合$A$里的元素组成的数（因为如果不存在的话集合$A$内的元素就可以组成$x$了），可以看到这与集合$B$的定义产生了矛盾。
综上所述，$A$集合内不能被其它数组成的数必然存在于$B$集合内
$Q.E.D$

然后动态规划
dp[i]表示$i$面值最多能被几张钱表示
则若其不能被表示dp[i] = -inf
能表示且只有它自己则dp[i] = 1
初始化dp[] = -inf; dp[0] = 0
状态转移方程为dp[j] = max(dp[j], dp[j - a[i]] + 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
#include <bits/stdc++.h>
using namespace std;

int n, T, ans, a[1010], dp[30010];

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(dp, -0x3f, sizeof(dp));
        memset(a, 0, sizeof(a));
        ans = 0; dp[0] = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = a[i]; j <= 25010; ++j) {
                dp[j] = max(dp[j], dp[j - a[i]] + 1);
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (dp[a[i]] == 1) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
/* 862ms 944kB */

$D1T3$ 赛道修建

这题比较复杂，先得部分分

$I.$ $m = 1$ 时

最简单的情况
求一条最长链，即求树的直径（记录一下最大值和次大值，每次把最大值传到它的父亲）
可以通过第$1,4,5,6$个点，$20$分

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
namespace Meq1 {
    int dfs(int now, int fa) {
        int res1 = 0, res2 = 0;
        for (int i = head[now]; i; i = edges[i].nxt) {
            int to = edges[i].to;
            if (to == fa) continue;
            res2 = max(res2, dfs(to, now) + edges[i].val);
            if (res2 > res1) swap(res1, res2);
        }
        ans = max(ans, res1 + res2);
        return res1;
    }

    void solve() {
        dfs(1, 0);
        printf("%d\n", ans);
        return ;
    }
}

$II.$ $a_i = 1$ 时

即一个菊花图
把所有边权记录下来，从大到小排序。设边权为$w$，答案即为$w_1+w_{2m-1},w_2+w_{2m-2},…,w_m+w_{m+1}$的最小值
可以通过$1,5,7,8$四个点，$20$分，加上$m = 1$的情况共$35$分

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
namespace Aeq1 {
    int arr[maxn];
    
    bool cmp(int a, int b) {
        return a > b;
    }

    void solve() {
        for (int i = head[1]; i; i = edges[i].nxt) {
            int to = edges[i].to;
            arr[to - 1] = edges[i].val;
        }
        sort(arr + 1, arr + n, cmp);
        ans = inf;
        for (int i = 1; i <= m; ++i) {
            ans = min(ans, arr[i] + arr[2 * m - i + 1]);
        }
        printf("%d\n", ans);
        return ;
    }
}

$III.$ $b_i = a_i + 1$ 时

为一条链
把所有边权记录下来，这种情况等价于将序列分割成$m$段，使$m$段区间和的最小值最大
那么二分$m$段区间和的最小值，然后贪心扫一遍
可以通过$2,9,10,11$四个点，$20$分，加上一共$55$分

代码

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
namespace BeqApl1 {
    int arr[maxn], ans;

    int Dfs(int now, int fa) {
        int res1 = 0, res2 = 0;
        for (int i = head[now]; i; i = edges[i].nxt) {
            int to = edges[i].to;
            if (to == fa) continue;
            res2 = max(res2, Dfs(to, now) + edges[i].val);
            if (res2 > res1) swap(res1, res2);
        }
        ans = max(ans, res1 + res2);
        return res1;
    }

    void dfs(int now, int fa) {
        for (int i = head[now]; i; i = edges[i].nxt) {
            int to = edges[i].to;
            if (to == fa) continue;
            dfs(to, now);
            arr[now] = edges[i].val;
        }
    }

    bool judge(int x) {
        int t = 0, now = 0;
        for (int i = 1; i < n; ++i) {
            if (now + arr[i] >= x) {
                now = 0;
                t++;
            } else {
                now += arr[i];
            }
        }
        return t >= m;
    }

    void solve() {
        dfs(1, 0);
        Dfs(1, 0);
        int l = 1, r = ans, mid;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (judge(mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
        return ;
    }
}

正解

最小值最大，显然是二分这个最小值$lim$
对于一个节点$u$，我们可以记录一个连接到$u$的赛道的长度$val_i$，那么可以分成两种情况进行讨论：
$$\begin{cases} val_i+dis \geq lim \text{直接给答案+1} \\ val_i+dis< lim \text{利用优先队列维护}\end{cases}$$

代码

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
#include <bits/stdc++.h>
using namespace std;

void read(int& x) {
    x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
}

const int maxn = 50050;
const int inf  = 0x3f3f3f3f;

int n, m, cnt, num, s[maxn], mid;

struct Edge {
    int from, to, val;
    Edge(int u, int v, int w) : from(u), to(v), val(w) {}
};
vector<Edge> G[maxn];
void add(int u, int v, int w) {
    G[u].push_back(Edge(u, v, w));
    G[v].push_back(Edge(v, u, w));
}

int dfs(int u, int fa) {
    priority_queue<int> lh;
    priority_queue<int, vector<int>, greater<int> > sh;
    int ln = 0, sn = 1;
    for (int i = 0; i < G[u].size(); ++i) {
        if (G[u][i].to != fa) {
            int d = G[u][i].val + dfs(G[u][i].to, u);
            sh.push(d); lh.push(d);
            ln++;
        }
    }
    while (ln > 0 && lh.top() >= mid) {num++; lh.pop(); ln--;}
    int now = 0;
    while (ln > sn) {
        if (u != 1 && lh.top() + sh.top() >= mid) {
            int cnt = 0;
            while (ln > sn && lh.top() + sh.top() >= mid) {s[++cnt] = lh.top(); lh.pop(); ln--;}
            num++; sh.pop(); sn++;
            while (cnt > 1) {lh.push(s[--cnt]); ln++;}
        } else if (u == 1 && lh.top() + sh.top() >= mid) {
            lh.pop(); sh.pop(); ln--; sn++; num++;
        } else {
            now = sh.top(); sh.pop(); sn++;
        }
        if (num >= m) break;
    }
    if (ln >= sn && !lh.empty()) return lh.top();
    else return now;
}

bool check() {
    num = 0;
    dfs(1, 0);
    if (num >= m) return true;
    else return false;
}

int main() {
    read(n); read(m); int all = 0;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        read(u); read(v); read(w);
        add(u, v, w);
        all += w;
    }
    int l = 0, r = all / m, ans = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check()) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}
/* 1050ms 11964kB with O2 */

$D2T1$ 旅行

分两种情况讨论

$I.$ $m = n - 1$

即无环，只要给一个点所能到达的点的编号进行一次从小到大的排序，在树上dfs一遍即可解决
样例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
namespace SolveOne {
    int cnt = 0;
    bool vis[maxn];
    void dfs(int u, int fa) {
        ans[++cnt] = u;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if (!vis[v]) {
                dfs(v, u);
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(1, 0);
        for (int i = 1; i <= n; ++i) {
            printf("%d ", ans[i]);
        }
    }
}
/* 1050ms 11964kB with O2 */

$II.$ $m = n$

存在一个环（基环树）
手算一下样例2可以发现，有且仅有一条边不会通过
逐个删边尝试即可，删边后和$m = n - 1$相同
样例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
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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;
const int inf  = 0x3f3f3f3f;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch))  {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}

int n, m, ans[maxn], in[maxn][2];

vector<int> G[maxn];

namespace SolveOne {
    int cnt = 0;
    bool vis[maxn];
    void dfs(int u, int fa) {
        ans[++cnt] = u;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if (!vis[v]) {
                dfs(v, u);
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(1, 0);
        for (int i = 1; i <= n; ++i) {
            printf("%d ", ans[i]);
        }
    }
}

namespace SolveTwo {
    int cnt = 0, res[maxn], du, dv;
    bool vis[maxn];
    bool notdel(int u, int v) { //判断该边是否被删
        if ((u == du && v == dv) || (u == dv && v == du)) {
            return false;
        }
        return true;
    }
    void dfs(int u, int fa) {
        res[++cnt] = u;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if (!vis[v] && notdel(u, v)) {
                dfs(v, u);
            }
        }
    }
    bool judge() { //判断是否为更优情况
        for (int i = 1; i <= n; ++i) {
            if (ans[i] != res[i]) {
                return ans[i] > res[i];
            }
        }
        return false;
    }
    void solve() {
        memset(ans, 0x3f, sizeof(ans));
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        for (int i = 1; i <= m; ++i) {
            cnt = 0;
            memset(res, 0, sizeof(res));
            memset(vis, 0, sizeof(vis));
            du = in[i][0]; //删边
            dv = in[i][1];
            dfs(1, 0);
            if (judge() && cnt == n) { //如果更优则更改ans[]
                memcpy(ans, res, sizeof(res));
            }
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", ans[i]);
        }
    }
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
        in[i][0] = u;  //存储输入信息
        in[i][1] = v;
    }
    if (m == n - 1) {
        SolveOne::solve();
    } else {
        SolveTwo::solve();
    }
    return 0;
}
/* 2244ms 1276kB */

$D2T2$ 填数游戏

暴力推柿子
首先明确一个概念:本文的对角线指的是从左下方到右上方的有向线段
Lemma I.
$\mathcal{Lemma}\ I.$ 对角线上的数只会相同或递减
$proof:$
由上图两条黑线和题目描述即可证明
$Q.E.D$

Lemma II.
$\mathcal{Lemma}\ II.$ 若$(x-1, y)$与$(x, y-1)$的数相同,则以$(x,y)$为左上角,整个图形右下角的子矩阵的每条对角线(蓝)上填的数字相同
$proof:$
由图上两条橙线及题目描述即可证明
$Q.E.D$

$\mathcal{Lemma}\ III.$ $Ans(n,m)=Ans(m,n)$

正式推式子(默认$n \leq m$)

$I.$ $n = 1$ 时


每个格内都有2种填法,故$\Ans(1,m)=2^{m}$

$II.$ $n = 2$ 时


两个角上各两种,剩余$m-1$条对角线每条有3种(11,10,00)
故$Ans(2,m)=2\times 2\times 3^{m-1}=4\times 3^{m-1}$

$III. $ $n \geq 4$ 时 (只考虑$n = m$时)

$case I.$ 左上角两数相同


图中数字表示每条对角线方案数
可以得出$Ans(caseI.)=2\times 2\times 4^{n-2}\times 2^{n-1}=8^{n-1}$

$case II.$ 第三条对角线数字相同


图中红色数字表示方案数
可以得出$Ans(caseII.)=2\times 2\times 5\times 4^{n-4}\times 2^{n-1}=5\times 2^{3n-7}$

$case III.$ 第三条对角线上数字不同


可以发现左侧两行只能填01,所以可能会再次出现对角数字相同的情况

第一个出现

红色表示方案数

最后一个出现

倒数第二个出现

没有出现

注意第三条对角线可能有100,110两种情况
所以$Ans(case III.)=2\times (2\times 4\times 5\times 2^{n-1}\times \sum_{i=0}^{n-5}{4^i} + 2\times 4\times 3\times 2^{n-2} + 2\times 3\times 2^{n-2})$

$Ans(n, n)=Ans(case I.) + Ans(case II.) + Ans(case III.)$
$$Ans(n,n)=\frac{83\times 8^n + 5\times 2^{n+7}}{384}$$

$IV.$ $n = 3$

证明与前类似
$$Ans(3,m)=112\times 3^{m-3}$$

$V.$ $n \neq m$ 时

与前类似
$$Ans(n,n+1)=\frac{83\times 8^n + 2^{n+8}}{128}$$
同时易证得$Ans(n,m+1)=3\times Ans(n,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
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long LL;

int n, m;

LL poww(LL a, LL b) {
    LL res = 1; 
    for ( ; b; a = a * a % mod, b >>= 1){
        if (b & 1) {
            res = res * a % mod;
        }
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    if (n > m) swap(n, m);
    if (n == 1) printf("%lld\n", poww(2, m));
    else if (n == 2) printf("%lld\n", 4 * poww(3, m - 1) % mod);
    else if (n == 3) printf("%lld\n", 112 * poww(3, m - 3) % mod);
    else {
        if (m == n) printf("%lld\n", ((83 * poww(8, n) % mod + 5 * poww(2, n + 7) % mod) * 190104168 % mod));
        else printf("%lld\n", ((83 * poww(8, n) % mod + poww(2, n + 8)) * poww(3, m - n - 1) % mod * 570312504 % mod ));
    }
    return 0;
}
/* 55ms 1048kB */

$D2T3$ 保卫王国

动态DP,树剖,蒟蒻不会

逃

如有疑问,可以在下方评论区留言

「NOIp2018」题解

https://blog.tonycrane.cc/p/34a76f7d.html

作者

TonyCrane

发布于

2019-04-12

更新于

2020-05-05

许可协议

#
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
图论2
学习1
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记29
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×