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

「NOIp2017」题解

NOIp2017的题比NOIp2018的题好做一点

$D1T1$ 小凯的疑惑

题解

推柿子(正确性未知)
设$a < b$ 答案为$x$
所以:
$$x \equiv ma \pmod b (1 \leq m \leq b - 1)$$
即$x = ma + nb (1 \leq m \leq b - 1)$
显然当$ n \geq 0$时 $x$可以用$a, b$表示出来，不合题意
因此当$n = -1$时$x$取得最大值，此时$x = ma - b$
显然当$m$取得最大值$b - 1$时$x$最大，此时$x = (b - 1)a - b = ab - a - b$
因此$a, b$所表示不出的最大的数是
$$\boxed{ab - a - b}$$

代码

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

long long a, b;

int main() {
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", a * b - a - b);
    return 0;
}
/* 60ms 948kB */

$D1T2$ 时间复杂度

毒瘤大模拟
没什么好说的,直接上代码

代码

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

string str1, str2;      
int cal, O, NumOfLoop, vis[27], var[27], Onow, Kill, AddO[100], Omax, WhereKill, T;

int main() {
    cin >> T;
    while (T > 0) {
        T--;
        cal = 0; O = 0; Omax = 0; WhereKill = 0; NumOfLoop = 0; Onow = 0; Kill = 0;
        memset(vis, 0, sizeof(vis));
        memset(AddO, 0, sizeof(AddO));
        do {
            str1 = str2;
            cin >> str2;
        } while(str2[0] != 'O');
        for (int i = 0; i < str1.length(); i++) cal = cal * 10 + str1[i] - '0';
        for (int i = 4; i < str2.length() - 1; i++) O = O * 10 + str2[i] - '0';
        while (cal > 0) {
            cal--;
            cin >> str1;
            if (str1[0] == 'F') {
                NumOfLoop++;
                cin >> str1;
                if (vis[str1[0] - 96]) {
                    NumOfLoop = -1;
                } else { 
                	vis[str1[0] - 96] = 1;
                    var[NumOfLoop] = str1[0] - 96;
                } 
                cin >> str1 >> str2;
                if (str1[0] != 'n' && str2[0] == 'n' && Kill == 0) {
                    Onow++;
                    AddO[NumOfLoop] = 1;
                } else if (((str1.length() == str2.length() && str1 > str2) || (str1.length() > str2.length()) || (str1[0] == 'n' && str2[0] != 'n')) && Kill == 0) {
                    Kill = 1;
                    WhereKill = NumOfLoop;
                }
            } else { 
                Omax = max(Omax, Onow);
                vis[var[NumOfLoop]] = 0; 
                if (AddO[NumOfLoop] == 1) {
                    Onow--;
                    AddO[NumOfLoop] = 0;
                } 
                NumOfLoop--; 
                if (WhereKill > 0 && NumOfLoop < WhereKill) {
                    Kill = 0; WhereKill = 0;
                } 
            }
            if(NumOfLoop == -1) {
                printf("ERR\n");
                cal = -1;
            } 
        }
        if (NumOfLoop > 0) printf("ERR\n"); 
        if (NumOfLoop == 0 && Omax == O) printf("Yes\n");
        if (NumOfLoop == 0 && Omax != O) printf("No\n"); 
    }
    return 0;
}
/* 34ms 756kB */

$D1T3$ 逛公园

本题思路来自安妮007的题解

题解

  1. 先SPFA求最短路
  2. 再反向SPFA排除无法到达的边
  3. 再记忆化搜索走冤枉路的最优方案

详细见安妮007的题解

代码

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

const int inf  = 0x7fffffff;
const int maxn = 100010;

struct Node {
    int x, y;
    Node(int x, int y): x(x), y(y) {}
};

int n, m, k, p, T;
vector<Node> v[maxn], s[maxn];
int d[maxn], ans[maxn][60];
bool vis[maxn][60], alive[maxn];
queue<int> q, f;

int dfs(int a, int b) { //a当前点,b允许走的冤枉路长度
    if (b < 0) {
        return 0;
    } else if (vis[a][b] == 1) {  //又回来了
        return -inf;              //无穷多种(-inf用于判断)
    } else if (ans[a][b] != -1) { //算过了
        return ans[a][b];
    } else {
        vis[a][b] = true;
        int key = 0;
        if (a == n) { //到目的地
            key++;
        }
        for (int i = 0; i < v[a].size(); ++i) {
            int g = v[a][i].x, y = v[a][i].y; //g本条边终点,y权值
            int u = d[g] - d[a];
            if (alive[g] == 0) { //不能到终点
                continue;
            }
            int w = dfs(g, b - (y - u));
            if (w == -inf) {
                return -inf;
            } else {
                key = (key + w) % p;
            }
        }
        ans[a][b] = key % p;
        vis[a][b] = false; //回溯
        return key;
    }
}

void safe() { //排除无法到终点的点(反向SPFA)
    f.push(n);
    alive[n] = 1;  //点n自身可以到达
    while (!f.empty()) {
        int h = f.front(); f.pop();
        for (int i = 0; i < s[h].size(); ++i) {
            int g = s[h][i].x;
            if (alive[g] == 0) {
                alive[g] = 1;
                f.push(g);
            }
        }
    }
    return ;
}

void spfa() { //SPFA求最短路
    q.push(1);
    d[1] = 0;
    while (!q.empty()) {
        int h = q.front(); q.pop();
        for (int i = 0; i < v[h].size(); ++i) {
            int g = v[h][i].x, y = v[h][i].y;
            if (d[h] + y < d[g]) {
                d[g] = d[h] + y;
                q.push(g);
            }
        }
    }
    return ;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d %d", &n, &m, &k, &p);
        for (int i = 1; i <= n; ++i) {
            v[i].clear();
            s[i].clear();
            alive[i] = 0;
            for (int j = 0; j <= k; ++j) {
                ans[i][j] = -1;
                vis[i][j] = 0;
            }
        }
        for (int i = 0; i < m; ++i) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back(Node(b, c));     //正向边
            s[b].push_back(Node(a, c));     //反向边
        }
        for (int i = 2; i <= n; ++i) {
            d[i] = inf;
        }
        spfa();  //SPFA求最短路
        safe();
        int z = dfs(1, k);
        if (z == -inf) {
            printf("-1\n");
        } else {
            printf("%d\n", z);
        }
    }
    return 0;
}
/* 6488ms 44632kB with O2 */

$D2T1$ 奶酪

题解

没什么好说的,直接__搜索__
存好每个点,排序,从下向上搜

代码

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

const int maxn = 1010;

bool fini = false, vis[maxn];
int T, n, h, r;

struct Node {
    double x, y, z;
} node[maxn];

bool cmp(Node a, Node b) {
    return a.z > b.z;
}

double dist(Node a, Node b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
}

void dfs(Node now, int num) {
    if (now.z + r >= h) {
        fini = true;
        return;
    }
    vis[num] = true;
    for (int i = 1; i <= n; ++i) {
        if (fini) {
            return;
        } else if (!vis[i] && dist(node[i], now) <= r * 2) {
            dfs(node[i], i);
        }
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        fini = false;
        memset(node, 0, sizeof(node));
        memset(vis, 0, sizeof(vis));
        scanf("%d %d %d", &n, &h, &r);
        for (int i = 1; i <= n; ++i) {
            scanf("%lf %lf %lf", &node[i].x, &node[i].y, &node[i].z);
        }
        sort(node + 1, node + 1 + n, cmp);
        for (int i = 1; i <= n; ++i) {
            if (node[i].z - r <= 0) {
                dfs(node[i], i);
            }
        }
        printf(fini ? "Yes\n" : "No\n");
    }
    return 0;
}
/* 157ms 832kB */

$D2T2$ 宝藏

题解

状压?? 模拟退火?? 不存在的 蒟蒻不会
__搜索+剪枝__能很快AC掉这道紫题
不解释了

代码

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

const int inf  = 0x3f3f3f3f;

int vis[20], dis[20], num[20]; //已访问的点,距1的距离,可以到达的点数
int c[20][20], G[20][20]; //费用,图
int ans = inf, tmp, tot, cnt, n, m, p;

bool cmp(int a, int b) {
    return c[p][a] < c[p][b];
}

void dfs(int u, int node) {
    for (int i = u; i <= cnt; ++i) {
        if(tot + tmp * dis[vis[i]] >= ans) return;
        for (int j = node; j <= num[vis[i]]; ++j) {
            if(!dis[G[vis[i]][j]]) {
                cnt++;
                vis[cnt] = G[vis[i]][j];
                tmp -= c[vis[cnt]][G[vis[cnt]][1]];
                tot += c[vis[i]][vis[cnt]] * dis[vis[i]];
                dis[vis[cnt]] = dis[vis[i]] + 1;
                dfs(i, j + 1);
                tot -= c[vis[i]][vis[cnt]] * dis[vis[i]];
                dis[vis[cnt]] = 0;
                tmp += c[vis[cnt]][G[vis[cnt]][1]];
                cnt--;
            }
        }
        node = 1;
    }
    if(cnt == n) {
        if(tot < ans) ans = tot;
        return;
    }
}

int main() {
    int u, v, w;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            c[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        if(c[u][v] < w) continue;
        if(c[u][v] == inf) {
            G[u][++num[u]] = v;
            G[v][++num[v]] = u;
        }
        c[u][v] = c[v][u] = w;
    }
    for (int i = 1; i <= n; ++i) {
        p = i;
        sort(G[i] + 1, G[i] + 1 + num[i], cmp);
        tmp += c[i][G[i][1]];
    }
    for (int i = 1; i <= n; ++i) {
        tot = 0; cnt = 1;
        vis[1] = i;
        tmp -= c[i][G[i][1]];
        dis[i] = 1; 
        dfs(1, 1);
        dis[i] = 0;
        tmp += c[i][G[i][1]];
    }
    printf("%d", ans);
    return 0;
}
/* 65ms 808kB */

$D2T3$ 列队

平衡树?? $Splay$?? $FHQ\_Treap$?? 不会
模拟拿下$50$分,以后再说,逃

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
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;
}
const int maxn = 300010;

struct Node {
    int x, y;
} a[maxn];
int n, m, q, tot;
LL last[maxn], h[maxn], pos[510][50010], ans;

int main() {
    n = read(); m = read(); q = read();
    for (int i = 1; i <= q; ++i) {
        a[i].x = read();
        a[i].y = read();
        h[i] = a[i].x;
    }
    for (int i = 1; i <= n; ++i) {
        last[i] = last[i - 1] + m;
    }
    sort(h + 1, h + q + 1);                 //排序
    tot = unique(h + 1, h + q + 1) - h - 1; //去重
    LL t;
    for (int i = 1; i <= tot; ++i) { //编号
        t = (LL)(h[i] - 1) * m;
        for (int j = 1; j <= m; ++j) {
            pos[i][j] = ++t;
        }
    }
    int where; //a[i].x在h数组中的位置
    for (int i = 1; i <= q; ++i) { //模拟
        for (int j = 1; j <= tot; ++j) {
            if (h[j] == a[i].x) {
                where = j;
                break;
            }
        }
        if (a[i].y == m) { //在最后一列
            ans = last[h[where]];
        } else {
            ans = pos[where][a[i].y];
        }
        printf("%lld\n", ans);
        if (a[i].y != m) { //向左看齐
            for (int j = a[i].y; j < m - 1; ++j) {
                pos[where][j] = pos[where][j + 1];
            }
            pos[where][m - 1] = last[h[where]];
        }
        for (int j = h[where]; j < n; ++j) { //向前看齐
            last[j] = last[j + 1];
        }
        last[n] = ans;
    }
    return 0;
}
/* 50Points 13662ms 67344kB */

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

「NOIp2017」题解

https://blog.tonycrane.cc/p/c5ac34f0.html

作者

TonyCrane

发布于

2019-05-03

更新于

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

分类

×