题目链接

因为都是有官方题解的,咱这个蒟蒻就在记录一下赛时通过以及后来补得一些题?

A. 旷野之息

考虑将一个人 \(i\)选上对答案的贡献，即 \(a_i/ \sum a - 1/ n\)，若贡献大于 \(0\)，将其加上即可。需要预处理 \(\sum a\)，时间复杂度 \(\mathcal{O}(n)\)。

#include  <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

int n,m,t;
void solve()
{
    scanf("%Ld",&n);
    vector<int> a(n + 1);
    int sum = 0;
    for(int i = 1;i <= n;i ++){
        scanf("%Ld",&a[i]);
        sum += a[i];
    }
    double ans = 0;
    for(int i = 1;i <= n;i ++){
        double x = 1.0 / n, y = a[i] * 1.0 / sum;
        if(a[i] * n > sum){
            ans += (y - x);
        }
    }
    printf("%.9lf",ans * 100);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
   //cin >> Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

F. 自建一始

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e6+10, M = 998244353;

typedef unsigned long long ll;
typedef pair<int,int> PII;

int n,m,t,k;
map<int,int> mp;
priority_queue<int> QQ;
deque<int> Q;
vector<int> deg(510);
vector<vector<int>> g(510,vector<int>(510));

void solve() {
    cin >> n >> m;
    for(int i = 0;i < m;i ++){
        int x,y;
        cin >> x >> y;
        deg[x]++;
        deg[y]++;
        g[x][y] = g[y][x] = 1;
    }

    auto check = [&](int x)-> int{
        auto gg = g;
        auto du = deg;
        while(true){
            bool ctn = false;
            for(int i = 1;i <= n;i ++){
                for(int j = 1;j <= n;j ++){
                    if(i == j)
                        continue;
                    if(du[i] + du[j] >= x && !gg[i][j]){
                        gg[i][j] = gg[j][i] = 1;
                        du[i]++;
                        du[j]++;
                        ctn = true;
                    }
                }
            }
            if(!ctn)
                break;
        }
        bool f = false;
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= n;j ++){
                if(i == j)
                    continue;
                if(g[i][j] != gg[i][j]){
                    f = true;
                    break;
                }
            }
        }
        if(!f)
            return false;

        for(int i = 1;i <= n;i ++){
            if(du[i] != n - 1)
                return false;
        }
        return true;
    };

    int l = 0, r = 2 * (n - 1);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        //cout << mid << endl;
        if(check(mid))
            l = mid ;
        else
            r = mid - 1;
    }

    cout << l << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    // cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}

J. 余料建造

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define  inf 0x3f3f3f3f

using namespace std;

int n,m,t,k;
void solve()
{
    cin >> n;
    string s,ans = "";
    cin >> s;
    for(int i = 0,j = n - 1;i <= j;){
        if(s[i] > s[j]){
            ans += s[j];
            j--;
        }else if(s[i] < s[j]){
            ans += s[i];
            i++;
        }else{
            int pos1 = i,pos2 = j;
            while(s[pos1] == s[pos2] && pos1 <= pos2)
                pos1 ++ ,pos2 --;
            if(s[pos1] > s[pos2]){
                ans += s[j];
                j--;
            }else{
                ans += s[i];
                i++;
            }
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
    //cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}

K. 倒转乾坤

#include  <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
#define LB long double

using namespace std;

int n,m,t;
void solve()
{
    int d;
    scanf("%Ld %Ld",&d,&n);
    printf("%.8lf",(double)4 * d * n);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
   //cin >> Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}