20220802杭电第五场

Bragging Dice

题目大意：
有两个人，每个人的杯子里面有n个骰子，a先
在第一个回合，a可以喊出两个杯子里面有x（x>=1）个骰子的点数是y（1<=y<=6）
接着b可以有两个选择，一是挑战a，如果谁挑战了，游戏就会在这一个回合结束，所有人拿开杯子，如果确实是x个y，a胜利，否则b是胜利。而是b继续喊，不过只能喊有x1（x1>x）个骰子点数是y1（1<=y1<=6）或者有x2(x2=x)个骰子点数是y2(y2>y)
接着两人轮流进行上面的两个选择
特殊规则：
如果有一个人喊出：有x个骰子点数为1，那么点数为1的骰子可以被认为是任何点数
如果所有的骰子都有相同的点数，可以认为还有一个额外的骰子有相同的点数。如果有5个骰子点数为6，那么可以认为有6个骰子点数为6
如果每个骰子都有不同的点数，那么可以认为有0个骰子有1点，0个骰子有2点...

input:
1
5
4 6 4 1 2
3 6 6 2 3

output:
Win!

解：
当双方都是不同点数的时候，先手无论怎么喊都会输，因为第三条规则，除此之外只需要每次含喊最大的x个y就能赢

#include<bits/stdc++.h>

using namespace std;

set<int> s;
int n;

void solve() {
    s.clear();
    cin >> n;
    int x;
    bool is = false;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (s.count(x) >= 1) {
            is = true;
        }
        s.insert(x);
    }
    s.clear();
    for (int j = 1; j <= n; j++) {
        cin >> x;
        if (s.count(x) >= 1) {
            is = true;
        }
        s.insert(x);
    }
    if (is) {//如果有一个人可以有点
        cout << "Win!" << endl;
    } else {
        cout << "Just a game of chance." << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Buy Figurines

题目大意：
给定n个人和m个窗口，然后下面n行给定每个人到达窗口的时间和买东西持续的时间。
每个来到窗口的人都会挑选所有窗口中排队人数最少的窗口进行排队，在此基础上再选择序号最小的窗口排序
请你合理的安排给出最早结束时间

input：
1
5 3
2 4
1 3
5 1
3 4
4 2
7

output：
7

解：
模拟每个窗口的情况，利用双端队列模拟排队，依据题意模拟

#include<bits/stdc++.h>

using namespace std;

#define int long long

deque<pair<int, int>> m[200005];
int renshu[200005];
pair<int, int> person[200005];
int n, mcnt;

int cmp(pair<int, int> p1, pair<int, int> p2) {
    return p1.first < p2.first;
}

void solve() {
    cin >> n >> mcnt;
    for (int i = 1; i <= n; i++) {
        cin >> person[i].first >> person[i].second;
    }
    sort(person + 1, person + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        int start = person[i].first;
        int conti = person[i].second;
        int index = -1;
        int minj = INT32_MAX;
        bool is = false;
        for (int j = 1; j <= mcnt; j++) {
            while (!m[j].empty() && m[j].front().second <= start) {
                renshu[j]--;
                m[j].pop_front();
            }
            if (!is) {//如果没有遇到空的窗口
                if (m[j].empty()) {
                    index = j;
                    is = true;
                } else {
                    if (renshu[j] < minj) {
                        index = j;
                        minj = renshu[j];
                    }
                }
            }
        }
        if (renshu[index] == 0) {//空窗口
            pair<int, int> pair1(start, start + conti);
            m[index].push_back(pair1);
            renshu[index]++;
        } else {
            pair<int, int> pair1(start, conti + m[index].back().second);
            m[index].push_back(pair1);
            renshu[index]++;
        }
    }
    int maxtime = INT32_MIN;
    for (int i = 1; i <= mcnt; i++) {
        if (!m[i].empty()) {
            maxtime = max(maxtime, m[i].back().second);
        }
    }
    cout << maxtime << endl;
}


signed main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Slipper

题目大意：
给定一个n个节点的树，根节点为1，有一个指标power，给定一个k，如果两个点之间深度绝对值之差等于k，那么这两个点可以相互跳转，消耗p的power，同时如果两个点之间有边，那么这两点之间相互走消耗边权个power
给定s，t，求s到t的最小power。

input：
1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8//k p
6 5

output：
12

解：
考虑到有特殊的跳转方法，我们可以对这棵树进行加边来解决这个问题，然后就用最短路求出s到t的最短路
对每一层添加一个超级源点，与该层所有点的距离都是0
对每一层的超级源点去按照k连边
最后跑最短路算法


#include<bits/stdc++.h>

using namespace std;

struct edge {
    int v;
    int w;
};

const int N = 2e6 + 5;
int n, k, p;
int maxlayer;
vector<edge> v[N];
vector<int> layer[N];
int ceng[N];
int dis[N];
int vis1[N];
int vis2[N];


void bfs() {
    queue<int> q;
    q.push(1);
    ceng[1] = 1;
    vis1[1] = 1;
    layer[1].push_back(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int nowceng = ceng[cur];
        for (edge e: v[cur]) {
            int to = e.v;
            if (to == cur || vis1[to]) {
                continue;
            }
            vis1[to] = 1;
            maxlayer = max(maxlayer, nowceng + 1);
            ceng[to] = nowceng + 1;
            q.push(to);
            layer[nowceng + 1].push_back(to);
        }
    }
}

void djs(int s) {
    priority_queue<pair<int, int>> pq;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    pq.push({0, s});
    while (pq.size()) {
        auto t = pq.top();
        pq.pop();
        int u = t.second;
        if (vis2[u]) {
            continue;
        }
        vis2[u] = 1;
        for (auto ed: v[u]) {
            int to = ed.v;
            int we = ed.w;
            if (dis[to] > dis[u] + we) {
                dis[to] = dis[u] + we;
                pq.push({-dis[to], to});
            }
        }
    }
}

void solve() {
    //状态重置
    maxlayer = 0;
    for (int i = 1; i < 2000000; i++) {
        v[i].clear();
        dis[i] = 0;
        ceng[i] = 0;
        layer[i].clear();
        vis1[i] = 0;
        vis2[i] = 0;
    }
    //输入
    cin >> n;
    int x, y, w, s, t;
    for (int i = 1; i <= n - 1; i++) {
        cin >> x >> y >> w;
        v[x].push_back({y, w});
        v[y].push_back({x, w});
    }

    cin >> k >> p >> s >> t;

    bfs();

    //加边
    int cn = n;
    //每一层建立一个超级源点
    for (int i = 1; i <= maxlayer; i++) {
        for (int cur: layer[i]) {
            v[cn + 1].push_back({cur, 0});
            v[cur].push_back({cn + 1, 0});
        }
        cn++;
    }

    //超级源点之间相互连接，连接条件为k
    for (int i = 1; i <= maxlayer; i++) {
        if (i + k <= maxlayer) {
            v[n + i].push_back({n + i + k, p});
        }
        if (i - k >= 1) {
            v[n + i].push_back({n + i - k, p});
        }
    }

    djs(s);
    cout << dis[t] << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}