AcWing Weekly-85

发布于 2023-01-07  1324 次阅读


image-20230107220145537

感谢Y总,acwing寒假人多的手速场,冲第一了!!

AcWing 4791. 死或生

某国正在以投票的方式决定 2 名死刑犯(编号$1∼2$)的生死。

共有 n 组人员(编号 $1∼n$)参与投票,每组 $10$ 人。

每组成员只参与一名死刑犯的投票,其中第 $i$ 组人员的投票对象是死刑犯 $t_i$,其中 $x_i$ 人认为他无罪,$y_i$ 人认为他有罪。

在所有人员投票结束后,将对投票结果进行统计。

对于每名死刑犯,如果投他无罪的总票数大于或等于投他有罪的总票数,则他得以生还,否则他将被处死。

请你判断每名死刑犯的生死。

输入格式

第一行包含一个整数$n$ 。

接下来 $n$ 行,每行包含三个整数 $t_i,x_i,y_i$。

保证两名犯人都会被投票。

输出格式

如果第一位死刑犯生还,则在第一行输出 LIVE,否则在第一行输出 DEAD

如果第二位死刑犯生还,则在第二行输出 LIVE,否则在第二行输出 DEAD

数据范围

前 33 个测试点满足 $2≤n≤10$。
所有测试点满足$ 2≤n≤1000,1≤t_i≤2,0≤x_i,y_i≤10,x_i+y_i=10$。

输入样例1:

2
1 5 5
2 6 4

输出样例1:

LIVE
LIVE

简单模拟统计每个人被投的票数和总投票 人数即可,比较2倍关系是否满足,简单模拟问题哦

#include <bits/stdc++.h>

using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main() {
    int n;
    cin >> n;
    int suma = 0, sumb = 0, sumal = 0, sumbl = 0;
    while (n--) {
        int s, x, y;
        cin >> s >> x >> y;
        if (s == 1) {
            suma += x + y;
            sumal += x;
        } else {
            sumb += x + y;
            sumbl += x;
        }
    }
    if (sumal * 2 >= suma)
        puts("LIVE");
    else
        puts("DEAD");
    if (sumbl * 2 >= sumb)
        puts("LIVE");
    else
        puts("DEAD");
}

AcWing 4792. 最大价值

已知,小写字母 $a∼z$ 的价值分别为 $w_a,w_b,…,w_z$。

现在,给定一个由小写字母构成的字符串 $S$,请你在这个字符串中插入 $k$ 个小写字母,要求最终得到的字符串的价值尽可能大。

注意:

  • 插入的位置可以随意选。
  • 插入的字母也可以随意选,可以插入不同字母。

输出最大可能价值。

输入格式

第一行包含一个字符串 $S$。

第二行包含一个整数 $k$。

第三行包含 $26$ 个整数 $w_a,w_b,…,w_z$。

输出格式

一个整数,表示最大可能价值。

数据范围

前 $3$ 个测试点满足,S的长度范围 $[1,5]$。
所有测试点满足,SS 的长度范围$ [1,1000]$,$0≤k≤10^3$,$w_a∼w_z$ 的取值范围 $[0,1000]$。

输入样例:

abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出样例:

41

贪心构造

1、求一下最大价值所对应的字母 ch
2、构造最大价值字符串:在 s 后加入 k 次 ch

#include <bits/stdc++.h>

using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main() {
    string s;
    cin >> s;
    ll n, a = 1, mx = 0, b = s.size(), j = 0, z = 0;
    cin >> n;
    vector<ll> v(26);
    for (ll i = 1; i <= 26; i++) {
        cin >> v[i];
        if (mx < v[i]) {
            mx = v[i];
        }
    }
    ll ans = 0;
    for (ll i = 0; i < n + b; i++) {
        if (i < s.size()) {
            ans = ans + ((i + 1) * v[s[i] - 'a' + 1]);
        } else {
            ans = ans + ((i + 1) * mx);
        }

    }
    cout << ans;
}

AcWing 4793. 危险程度

有 $n$ 种化学物质,编号 $1∼n$。

其中,有 $m$ 对物质之间会发生反应。

现在,要将这些化学物质逐个倒入同一个试管之中,具体倒入顺序不限。

我们需要计算一下试管的危险值。

已知,空试管的危险值为 $1$,每倒入一种化学物质,如果该物质能够与之前倒入试管中的一种或多种物质发生反应,则试管的危险值将乘以 $2$。

请你计算并输出,通过合理安排所有化学物质的倒入顺序,能够得到的试管的最大危险值。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行,每行包含两个整数 $x,y$,表示化学物质 $x$ 和化学物质 $y$ 之间会发生反应。保证同一对化学物质在输入中最多出现一次。

输出格式

一个整数,表示最大危险值。

数据范围

前 44 个测试点满足 $1≤n≤10$。
所有测试点满足 $1≤n≤50$,$0≤m<\frac{n(n−1)}2$,$1≤x<y≤n$。

输入样例1:

1 0

输出样例1:

1

实际上就是找联通块数量,如果几个之间能反应,就是一个联通块,因此采用并查集搞一个联通块判断就ok了

#include <bits/stdc++.h>

using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0i128)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(int i = from;i<to;i++)
#define rrep(i, from, to) for(i128 i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define i128 __int128
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

struct DSU {
    vector<int> p, cnt;

    DSU(int n) : p(n), cnt(n, 1) { iota(p.begin(), p.end(), 0); }

    int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (cnt[x] < cnt[y]) swap(x, y);
        cnt[x] += cnt[y];
        p[y] = x;
        return true;
    }

    int size(int x) {
        return cnt[find(x)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    long long ans = 1;
    DSU d(n);
    while (m--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        if (d.merge(x, y)) {
            ans <<= 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

绝对不是恋爱脑!