NFLS-DAY 10

Posted on By 张, 高畅 NFLS-DAY 10无评论

T0

无话可说，明天继续
不过Tourists终于过了。

T1

给出一个字符串,请找出第一个只出现一次的字符.

签个到，避免爆0

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int n;
char s[N];
unordered_map<char, int> mp;
int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++) mp[s[i]]++;
    for (int i = 1; i <= n; i++) {
        if (mp[s[i]] == 1) {
            putchar(s[i]);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

T2

小C上课觉得无聊了,就会开始填数字里的洞.
数码0,6,9,有1个洞可以填;数码8,有2个;其他数码没有
他想知道,在区间[A,B]里,哪个数字拥有最多的洞.

这题刚看到的时候吓了一跳，以为T2就开始数位DP了。
不过数据范围非常小，暴力解决啦。

#include <bits/stdc++.h>
using namespace std;
int l, r, res = -1, resnum;
int check(int x) {
    int ans = 0;
    while (x) {
        int t = x % 10;
        if (t == 0 || t == 6 || t == 9)
            ans++;
        else if (t == 8)
            ans += 2;
        x /= 10;
    }
    if (res < ans) {
        res = ans;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d", &l, &r);
    for (int i = l; i <= r; i++) {
        if (check(i))
            resnum = i;
    }
    printf("%d", resnum);
    return 0;
}

T3

有n个男生和n个女生希望参加Dylan举办的化装舞会。现在给出n个男生和n个女生的身高，身高为正值表示这个男生(或女生)希望找到一个身高比他高的女生(或男生)，身高为负值表示这个男生(或女生)希望找到一个比他矮的女生(或男生)。
你的任务是统计最多有多少对舞伴可以参加Dylan的舞会

将每个性别分为两部分，正与负分两部分。
共四部分。
随后进行匹配。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, res;
vector<int> bh, bl, gh, gl;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x > 0)
            bh.push_back(x);
        else
            bl.push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x > 0)
            gh.push_back(x);
        else
            gl.push_back(x);
    }
    sort(bh.begin(), bh.end());
    reverse(bh.begin(), bh.end());
    sort(bl.begin(), bl.end());
    reverse(bl.begin(), bl.end());
    sort(gh.begin(), gh.end());
    sort(gl.begin(), gl.end());
    for (int i = 0, j = 0; i < bh.size() && j < gl.size();) {
        if (bh[i] + gl[j] < 0) {
            i++;
            j++;
            res++;
        } else
            i++;
    }
    for (int i = 0, j = 0; i < bl.size() && j < gh.size();) {
        if (bl[i] + gh[j] < 0) {
            i++;
            j++;
            res++;
        } else
            i++;
    }
    printf("%d", res);
    return 0;
}

T4

一个IPv6地址是一个128位的数。为了方便，这个数会采用分块表示，并且一块用一个16进制的数去表示16位，块之间用“：”分割，一共有8块，每块有4个16进制位。另外还有一些缩写的形式。把开头的0去掉.
还有一些连续0的情况，可以缩写成“::”,可以看看下面的例子：
你要做的，就是将缩写，还原成标准的形式。

直接模拟。

#include <bits/stdc++.h>
using namespace std;
void work() {
    string str, t = "";
    vector<string> V;
    V.clear();
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == &#039;:&#039;) {
            if (t.size() == 4)
                V.push_back(t);
            else {
                while (t.size() != 4) t = &#039;0&#039; + t;
                V.push_back(t);
            }
            t = "";
            if (i + 1 < str.size() && str[i + 1] == &#039;:&#039;) {
                V.push_back("----");
                i++;
            }
        } else
            t += str[i];
    }
    if (t.size() == 4)
        V.push_back(t);
    else {
        while (t.size() != 4) t = &#039;0&#039; + t;
        V.push_back(t);
    }
    int flag = 0;
    for (int i = 0; i < V.size(); i++) {
        if (V[i] != "----") {
            if (flag)
                putchar(&#039;:&#039;);
            cout << V[i];
            flag = 1;
        } else {
            for (int j = 1; j <= 8 - V.size() + 1; j++) {
                if (flag)
                    putchar(&#039;:&#039;);
                printf("0000");
                flag = 1;
            }
        }
    }
    puts("");
}
int main() {
    int n;
    scanf("%d", &n);
    while (n--) work();
    return 0;
}

T5

在电车上，大部分的乘客表现的都很文明，经常会给老人和小孩让座，但是还是有这么一群粗鲁的乘客，他们什么都不管，只管自己有没有座位坐，所以他们会不顾一切地冲向空的座位。电车又到站了，有许多的椅子空了出来，粗鲁的乘客们开始行动了！
每位粗鲁的乘客都会冲向离自己最近的座椅；但是如果他发现有人比他离那张椅子更近的话，他不会去那个人竞争，而是转向离自己第二近的椅子，依次类推；如果有两位粗鲁的乘客的目标椅子一致且离这张椅子的距离也相同的话，他们会一起高速冲向那张椅子，导致相撞发生爆炸并且连人带椅子炸得支离破碎！当每个乘客都找到了自己的合法的目标椅子后，他们会一起冲向目标椅子。一张椅子只能做一名乘客。
现在给你一张电车的座位表，共有R行C列，其中用‘X’表示粗鲁的乘客，用‘L’表示空椅子，用‘.’表示文明的乘客，你可以认为粗鲁的乘客不顾一切可以直接踩在的乘客身上冲向椅子= =(没有任何障碍)。请你帮忙算一算到所有的椅子都被占有（或者都被炸飞），或者所有粗鲁的乘客都已经心满意足地坐在了自己的位置上时，一共发生了几场爆炸？

大模拟，先枚举椅子，再枚举人。

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, chair, passenger, st[150005], dist[150005], ans[150005];
char s[55][55];
typedef long long LL;
struct node {
    int a, b, c;
} P[150005];
int cmp(node x, node y) { return x.c < y.c; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == &#039;L&#039;) {
                chair++;
                passenger = 0;
                for (int k = 1; k <= n; k++) {
                    for (int l = 1; l <= m; l++) {
                        if (s[k][l] == &#039;X&#039;)
                            P[++cnt] = { chair, ++passenger, (i - k) * (i - k) + (j - l) * (j - l) };
                    }
                }
            }
        }
    }
    sort(P + 1, P + cnt + 1, cmp);
    for (int i = 1; i <= cnt; i++) {
        if (!st[P[i].b] && !dist[P[i].a] || P[i].c == dist[P[i].a]) {
            st[P[i].b] = 1;
            ans[P[i].a]++;
            dist[P[i].a] = P[i].c;
        }
    }
    int res = 0;
    for (int i = 1; i <= passenger; i++) {
        if (ans[i] > 1)
            res++;
    }
    printf("%d", res);
    return 0;
}

T6

在AC之城中住着n个居民，每个人都欠给其他人中的一个人一些钱，现在他们要还钱了，但是刚经过双11的洗礼，他们居然都变成穷光蛋了！
于是责任到了镇长KY身上，他希望通过给一些人一定数量的钱来解决问题。而当人们收到钱时，就会发生连锁反应：举个栗子，当A收到钱时，他会把欠的钱还给B，而B又会去找C还钱。然而如果B的钱还不够还的，他就会原地坐等钱够了再说。而且如果一个人的钱比要还的钱多，他会把多余的钱塞入自己的腰包。
另一个栗子：如果AC之城中有2个人，他们互相欠对方￥100，那么KY必须给他们其中的一个￥100来解决纠纷。
而你的任务是计算KY最少要花多少钱。

你在期待什么？还是模拟。
先用topsort预处理，留下的则为在环上的。
对于每一个环，模拟枚举。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, res;
int d[N], f[N], v[N], w[N];
stack<int> stk;
void get(int u) {
    int Min = 1e9;
    for (int j = f[u]; d[j]; u = j, j = f[j]) {
        d[j] = 0;
        int t = max(0, v[j] - w[u]);
        res += t;
        Min = min(Min, v[j] - t);
    }
    res += Min;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &f[i], &w[i]);
        d[f[i]]++;
        v[i] = w[i];
    }
    for (int i = 1; i <= n; i++) {
        if (!d[i])
            stk.push(i);
    }
    while (stk.size()) {
        int u = stk.top();
        stk.pop();
        res += v[u];
        v[f[u]] = max(0, v[f[u]] - w[u]);
        if (!(--d[f[u]]))
            stk.push(f[u]);
    }
    for (int i = 1; i <= n; i++) {
        if (d[i])
            get(i);
    }
    printf("%d", res);
    return 0;
}
训练日志

发表回复