「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 */

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

作者

TonyCrane

发布于

2019-05-03

更新于

2020-05-05

许可协议

评论