Codeforces Round #318 (Div. 2)

这次也是后来补的,只做了前三道题,ACM练到这个时候,应该多专门做做第3、4题了

A. Bear and Elections

点击打开题目链接

有一些人在拉投票,第一个人想要选票大于所有其他人,可以贿赂投票人,问你最少贿赂多少人。直接用优先队列,优先贿赂票数最多的人。

#include <bits/stdc++.h>
using namespace std;


int main() {
    int n, cur; scanf("%d%d", &n, &cur);
    priority_queue<int> qu;
    for(int i = 1; i < n; ++i) {
        int x; scanf("%d", &x);
        qu.push(x);
    }
    int cnt = 0;
    while(!qu.empty() && qu.top() >= cur) {
        int t = qu.top(); qu.pop();
        ++cur, ++cnt;
        qu.push(t - 1);
    }
    printf("%d\n", cnt);
    return 0;
}

B. Bear and Three Musketeers

点击打开题目链接

给你一个朋友圈的信息,让你选择三个人,这三个人互相认识,并且每个人认识的其他人的总和最小。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 4096, inf = 0x3f3f3f3f;
int n, m;
vector<int> G[maxn];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int best = inf;
    for(int i = 1; i <= n; ++i) {
        if(G[i].size() <= 1) continue;
        for(int j = 0; j < G[i].size(); ++j) {
            for(int k = j + 1; k < G[i].size(); ++k) {
                int a = G[i][j], b = G[i][k];
                if(find(G[a].begin(), G[a].end(), b) != G[a].end()) {
                    int cur = G[i].size()-2 + G[a].size()-2 + G[b].size()-2;
                    best = min(best, cur);
                }
            }
        }
    }
    if(best >= inf) puts("-1");
    else printf("%d\n", best);
    return 0;
}

C. Bear and Poker

点击打开题目链接

给你N个数,你可以对每个数字乘以2或者3,可以多次乘。问你最终是不是能都变成同一个数。用唯一分解定理考虑,把每个数除掉2和3因子,看看除剩下的数是否相等。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    set<int> s;
    while(n--) {
        int x; cin >> x;
        while(x % 2 == 0) x /= 2;
        while(x % 3 == 0) x /= 3;
        s.insert(x);
    }
    if(s.size() == 1) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

欢迎留言