「Luogu P2723 P1631 P2850」小练习-题解

战神留的还有一道「P3378」堆,但是是模板,就不用多说了吧

$\mathcal{「P2723」}$ 丑数

$92$分$STL$做法

思路很简单,每次弹出堆顶,依次乘$S$集合内的数,再压入优先队列($priority\_queue$)和集合($set$,目的是去重)中,输出最后一个堆顶即可
然而第$4$个点卡了十多秒,$92$分

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

const int maxk = 110;

long long k, n, a[maxk], i, t;
priority_queue<long long, vector<long long>, greater<long long> > q;
set<long long> s;

int main() {
scanf("%lld %lld", &k, &n);
for (long long i = 1; i <= k; ++i) {
scanf("%lld", &a[i]);
}
q.push(1); s.insert(1);
while (i++ <= n) {
t = q.top(); q.pop();
for (long long j = 1; j <= k; ++j) {
long long num = t * a[j];
if (!s.count(num)) {
s.insert(num);
q.push(num);
}
}
}
printf("%lld\n", t);
return 0;
}
/* 92points TLE with O2 */

$100$分循环做法

思路

由题可知,当前产生的第$i$个丑数$s[i]$,是之前的某个丑数$\times a[j]$
某个丑数$\times a[j]$需要大于$s[i-1]$,而且要尽可能的小
于是我们可以枚举$j$,然后找到最小的一个丑数$minn$使$minn\times a[j]>s[i-1]$

但是..三重循环可能还会$TLE$

很容易发现满足条件的丑数$x\times a[j]>s[i-1]$,一定满足条件$x\times a[j]>s[i-2]$
于是我们就可以从满足$x\times a[j]>s[i-2]$的丑数$x$的位置往后枚举,找到满足条件$x\times a[j]>s[i-1]$的丑数
代码里$b[j]$表示$a[j]$至少与第几小丑数相乘才能得到一个比$s[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;

const int maxk = 110;
const int maxn = 100010;

long long k, n, a[maxk], i, t, s[maxn], b[maxk];

int main() {
scanf("%lld %lld", &k, &n);
for (long long i = 1; i <= k; ++i) {
scanf("%lld", &a[i]);
}
s[0] = 1;
for (long long i = 1; i <= n; ++i) {
long long minn = (long long)1 << 61;
for (long long j = 1; j <= k; ++j) {
while (a[j] * s[b[j]] <= s[i - 1]) {
b[j]++;
}
if (a[j] * s[b[j]] < minn) {
minn = a[j] * s[b[j]];
}
}
s[i] = minn;
}
printf("%lld\n", s[n]);
return 0;
}
/* 101ms 1584kB */

$\mathcal{「P1631」}$ 序列合并

思路

参考Red_w1nE

把$A$和$B$两个序列分别从小到大排序
这样,从$A$和$B$中各任取一个数相加得到$n^2$个和,可以把这些和看成形成了$n$个队列:

1
2
3
4
a[1] + b[1] <= a[1] + b[2] <= ... <= a[1] + B[n]
a[2] + b[1] <= a[2] + b[2] <= ... <= a[2] + B[n]
... ... ... ...
a[n] + b[1] <= a[n] + b[2] <= ... <= a[n] + B[n]

接下来,将这$n$个队列进行合并:

  • 将这$n$个队列中的第一个元素放入优先队列中;
  • 每次取出优先队列中的最小值,若这个最小值来自于第$k$个队列,那么,就将第$k$个队列的下一个元素放入优先队列中。
    我们可以使用一个结构体来记录队列中一个节点的值val,队列号id,下一个元素nxt

代码

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

const int maxn = 100010;

struct Node {
int val, id, nxt;
Node(int v, int i, int n): val(v), id(i), nxt(n) {}
};

bool operator < (const Node& a, const Node& b) {
return a.val > b.val;
}

int n, a[maxn], b[maxn];
priority_queue<Node> q;

int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
for (int i = 0; i < n; ++i) {
q.push(Node( a[i] + b[0], i, 1 ));
}
for (int i = 0; i < n; ++i) {
Node t = q.top(); q.pop();
printf("%d ", t.val);
q.push(Node( a[t.id] + b[t.nxt], t.id, t.nxt + 1 ));
}
return 0;
}
/* 402ms 3196kB */

$\mathcal{「P2850」}$ 虫洞

思路

判断__负环__的模板题

每条小路连接边权为正的无向边,每个虫洞连接边权为负的无向边
存在负环,则可以回到过去
使用$SPFA$算法判断负环($Floyd$也可以,但不开O2优化会$TLE$)

$SPFA$判断负环:如果任意一条边被修改大于$n$次,这个图内一定存在至少一个负环

代码

使用vector建边,邻接表也可以

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>
using namespace std;

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 = 510;

struct Edge {
int from, to, val;
Edge(int u, int v, int w): from(u), to(v), val(w) {}
};

vector<Edge> edges;
vector<int> G[maxn];

void add(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
int mm = edges.size();
G[u].push_back(mm - 1);
}

int dist[maxn], vis[maxn], cnt[maxn];
int n, m, w;

bool SPFA(int s) {
queue<int> q;
q.push(s);
dist[s] = 0; vis[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = 0; i < G[u].size(); ++i) {
Edge& e = edges[G[u][i]];
if (dist[e.to] > dist[u] + e.val) {
dist[e.to] = dist[u] + e.val;
if (!vis[e.to]) {
vis[e.to] = 1;
q.push(e.to);
cnt[e.to]++; //统计修改次数
}
if (cnt[e.to] > n) { //修改大于n次
return true; //存在负环
}
}
}
}
return false;
}

void clear() {
edges.clear();
for (int i = 0; i < maxn - 5; ++i) {
G[i].clear();
}
memset(cnt, 0, sizeof(cnt));
memset(vis, 0, sizeof(vis));
memset(dist, 0x7f, sizeof(dist));
}

int main() {
int T = read();
while (T--) {
clear();
n = read(); m = read(); w = read();
for (int i = 0; i < m; ++i) {
int u = read(), v = read(), d = read();
add(u, v, d); add(v, u, d);
}
for (int i = 0; i < w; ++i) {
int u = read(), v = read(), d = read();
add(u, v, -d);
}
if (SPFA(1)) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
/* 164ms 1024kB */

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

「Luogu P2723 P1631 P2850」小练习-题解

https://blog.tonycrane.cc/p/1faf5003.html

作者

TonyCrane

发布于

2019-05-17

更新于

2020-05-05

许可协议