Codeforces-570-div3解题报告

div3都能给我打掉分，我真的是个菜狗了。。

A - Nearest Interesting Number

给出一个数$ n $问大于等于它的哪个数的每个位相加起来和是4的倍数

枚举

int a;

int main(){
    cin >> a;
    for(int i = a;i <= 2000;i++){
        int tmp = i;
        int x = 0;
        while(tmp){
            x += tmp % 10;
            tmp /= 10;
        }
        if(x % 4 == 0){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

B - Equalize Prices

给出一个数列$a_i$,问能不能找到一个尽量大的数使得把所有数变成这一个数之后与原来的数的绝对值不超过$k$

贪心
考虑最小的直接加$k$即可
然后这题第二个循环变量我还是用$i$调了十多分钟。。

ll q;
ll n,k,sum;
ll B,a[200],b[200];

int main(){
    cin>>q;
    for(ll i = 1;i <= q;i++){
        cin>>n>>k;
        B = INF;
        for(ll j = 1;j <= n;j++) {
            cin >> a[j];
            B = min(a[j] + k,B);
        }
        for(ll j = 1;j <= n;j++) {
            if(abs(B - a[j]) > k){
                B = -1;
                break;
            }
        }
        cout<<B<<endl;
    }
    return 0;
}

C - Computer Game

给出电脑一开始的电量$ k $，要玩$ n $轮游戏，不充电玩的时候一轮消耗$ a $的电量，充电玩的时候一轮消耗$ b $的电量，$a > b$，求出在不充电的情况下能玩多少游戏，如果$ n $轮游戏都无法完成的话输出$ - 1 $

二分
考虑n轮游戏下来，不充电玩了$ x $轮，那么n轮后花费就是$ax + b(n - x)$，又因为$a > b$，所以$ax + b(n - x)$是单调的，直接二分即可
然后我初始值没有设成0导致疯狂wa就卡在这题了。。

ll q;
ll n,k,a,b;

bool check(ll now){
    ll sum = now * a + (n - now) * b;
    if(sum < k) return true;
    else return false;
}

int main(){
    cin>>q;
    for(ll i = 1;i <= q;i++){
        cin>>k>>n>>a>>b;
        ll l,r;
        l = 0,r = n;
        ll ans = 0;
        while(l <= r){
            ll mid = l + (r - l)/2;
            if(check(mid)){
                l = mid + 1LL;
                ans = mid;
            }
            else {
                r = mid - 1LL;
            }
        }
        if(check(ans)) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

D - Candy Box (easy version)

给出$ q $个询问，然后每个询问给出$ n $个数，选出最多数使得每个数出现的次数都不一样

贪心 排序
就记一下出现次数然后排序从高到底开始选取就可以了。。
看了题解里面有一个比较巧妙的用法以前没见过
定义了一个vector cnt(n + 1)，然后排序的时候是sort(cnt.rbegin().cnt.rend())就直接是降序了
vector的rbegin()和rend()是反向迭代器的用法

int q,n;

int main(){
    cin>>q;
    for(int i = 1;i <= q;i++){
        cin >> n;
        vector<int> cnt(n + 1);
        int tmp;
        for(int j = 1;j <= n;j++){
            cin>>tmp;
            cnt[tmp] ++;
        }
        sort(cnt.rbegin(),cnt.rend());
        int ans = cnt[0],lst = cnt[0];
        for(int j = 1;j <= n;j++){
            if(lst == 0) break;
            else if(cnt[j] >= lst){
                ans += lst - 1;
                lst -= 1;
            }
            else {
                ans += cnt[j];
                lst = cnt[j];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

E - Subsequences (easy version)

给出两个整数$ n $，$ k $以及字符串$ s $，问能不能删除字符串的一些字符不改变顺序得到一个大小为$ k $的子串集合，并且总共删除的字符要最少

bfs 字符串
~~你以为我是字符串，其实我是bfs哒，cf脑洞题惹不起惹不起~~
每次删除某个位置的字符，用set检查出现过没有，没有的话加入队列，然后统计答案

int n,k;
string s;
queue<string> q;
set<string> st;
int ans = 0;

int main(){
    f_read;
    cin>>n>>k;
    cin>>s;
    q.push(s);
    st.insert(s);
    while(!q.empty() && int(st.size()) < k){
        string now = q.front();
        q.pop();
        int len = int(now.size());
        for(int i = 0;i < len;i++){
            string tmp = now;
            tmp.erase(i,1);
            if(!st.count(tmp) && int(st.size()) + 1 <= k){
                q.push(tmp);
                st.insert(tmp);
                ans += n - tmp.size();
            }
        }
    }
    if(int(st.size()) < k) cout<< -1 << endl;
    else cout<<ans<<endl;
    return 0;
}

（于是在打了一个多小时群星后只看了题意。。。。）

F - Topforces Strikes Back

给出$ n $个数，找出里面的三个数不存在整除的关系并且要最大

set 暴力 贪心
考虑把每个数依次加到set里面，先取最大的，如果说这个最大的数除以2、3、5之后的数在set里面，那么就先把答案定为这三个之和
然后遍历集合，依次把能整除最大的筛掉，选出三个到答案的vector里面，最后求和即可
康题解学到了accumulate函数的用法,包含在头文件<numeric>里面，之后还得去学学c++11里面的一些用法。。。

int q;
int n;
int tmp,anss;
set<int> a;
vector<int> ans;

int main(){
    cin>>q;
    for(int query = 1;query <= q;query ++){
        cin>>n;
        a.clear();
        ans.clear();
        for(int i = 1;i <= n;i++){
            cin>>tmp;
            a.insert(tmp);
        }

        anss = 0;
        int maxx = *a.rbegin();
        if(maxx % 2 == 0 && maxx % 3 == 0 && maxx % 5 == 0){
            if(a.count(maxx / 2) && a.count(maxx / 3) && a.count(maxx / 5)){
                anss = max(anss,maxx / 2 + maxx / 3 + maxx / 5);
            }
        }
        while(!a.empty() && ans.size() < 3){
            int t = *a.rbegin();
            a.erase(prev(a.end()));
            bool flag = 1;
            for(auto it : ans) flag &= (it % x != 0);
            if(flag) ans.push_back(t);
        }

        anss = max(anss,accumulate(ans.begin(),ans.end(),0));

        cout<<anss<<endl;
    }
    return 0;
}