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

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

$\mathcal{「P2723」}$ 丑数

$92$分$STL$做法

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

#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]$大的丑数

代码

#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$个队列:

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

代码

#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建边,邻接表也可以

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

---

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