牛客周赛 Round 35

A

签到题

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

void solve(){
    string s;
    cin>>s;
    int n = s.size();
    for(int i =0;i<n;i++){
        cout<<s[i];
        if(i==n/2-1) cout<<endl;
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
}

B

相同的两两配对，配对不了就输出-1

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

void solve(){
    int n ;
    cin>>n;
    vector<int> a(2*n);
    for(int&x:a) cin>>x;
    sort(a.begin(),a.end());
    for(int i =0;i<2*n;i+=2){
        if(a[i]!=a[i+1]){
            cout<<-1;
            return;
        }
    }
    for(int i =0;i<2*n;i+=2){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    for(int i =1;i<2*n;i+=2){
        cout<<a[i]<<" ";
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
}

C

先排序，然后双指针，找在k范围内最多可以包含多少个，计为dis，答案就是dis/n

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

void solve(){
    int n ,k;cin>>n>>k;
    vector<int> a(n);
    for(int i =0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end());
    int l = 0;
    int dis= 0 ;
    for(int i =0;i<n;i++){
        while(a[i]-a[l]>k) l++;
        dis = max(dis,i-l+1);
    }
    cout<<1.0*dis/n;
}

int main(){
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
}

D

贪心，先查找哪些可以不用动，然后把剩下的要修改的修改一下就行了

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

void solve(){
    int n;cin>>n;
    vector<pair<int,int>> a(n);
    for(int i =0;i<n;i++){
        cin>>a[i].first;
        a[i].second = i+1;
    }
    sort(a.begin(),a.end());
    vector<int> need(n+1,0);
    vector<pair<int,int>> vp;
    vector<int> vis(n,0);
    for(int i =0;i<n;i++){
        if(a[i].first > n) continue;
        if(need[a[i].first]==0){
            need[a[i].first] = 1;
            vis[i] = 1;
            continue;
        }
    }
    int p = 1;
    for(int i = 0;i<n;++i){
        if(vis[i]==0){
            while(need[p]==1) p++;
            need[p] = 1;
            vp.push_back({a[i].second,p});
        }
    }
    cout<<vp.size()<<endl;
    for(auto p:vp){
        cout<<p.first<<" "<<p.second<<endl;
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
}

E

构造 可以先按照距离进行分层 如果发现中间某一层数量为0，那么输出-1 对于每一层，可以先把每一层的节点连接到上一层的第一个节点，先形成树 如果m>n-1,那么我们可以考虑看哪些边还可以再次添加 不难发现： 第i层的节点可以互相连接 第i层和第i+1层的节点可以互相连接

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

void solve(){
    int n ,m;cin>>n>>m;
    vector<vector<int>> adj(n);
    vector<int> a(n);
    for(int&x:a) cin>>x;
    for(int i =1;i<n;i++)
        if(a[i]==0){
            cout<<-1;
            return;
        }
    for(int i =0;i<n;i++) adj[a[i]].push_back(i);
    while(adj.back().size()==0) adj.pop_back();
    vector<pair<int,int>> ans;
    for(int i =1;i<adj.size();i++){
        if(adj[i].size()==0) {
            cout<<-1;
            return;
        }
    }

    for(int i =1;i<adj.size();i++){
        for(int x:adj[i]){
            ans.push_back({adj[i-1][0],x});
        }
    }
    m-=n-1;
    if(m<0){
        cout<<-1;
        return;
    }
    for(int i =0;i<adj.size()-1&&m;i++){
        for(int j = 0;j<adj[i].size()&&m;j++){
            for(int k = 0;k<adj[i+1].size()&&m;k++){
                if(j==0) continue;
                ans.push_back({adj[i][j],adj[i+1][k]});
                m--;
            }
        }
    }
    for(int i =0;i<adj.size()&&m;i++){
        for(int j = 0;j<adj[i].size()&&m;j++){
            for(int k = j+1;k<adj[i].size()&&m;k++){
                ans.push_back({adj[i][j],adj[i][k]});
                m--;
            }
        }
    }
    if(m){
        cout<<-1;
        return;
    }
    for(auto p:ans){
        cout<<p.first+1<<" "<<p.second+1<<endl;
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
}

F/G

只要三种数字1，2，3 我们可以先不选1，因为没有影响 假设选了i个2，j个3，那么的因数的数量就是表示选了多少个2,3拼起来的因数 好开始统计答案，我们可以枚举选取的i的数量，选取i个2的时候，答案就是 不难发现右边部分是常数，所以我们可以先算这个常数，然后再枚举i 统计完之后，我们再去看1的影响，无非就是选与不选，那么就是ans = (ans * pow(2,cnt[1])) 最后发现全部都不选不在答案里面，所以ans--

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long
const ll   mod = 1000000007;
long long qpow(long long a, long long b) {
    ll m = mod;
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

void solve(){
    ll n ;
    cin>>n;
    vector<ll> a(n);
    for(ll&x:a)cin>>x;
    ll cnt[4]={0};
    for(ll x:a) cnt[x]++;
    ll q = cnt[3];
    ll r = 1;
    ll comb = 1;
    for(ll j =1;j<=q;j++){
        comb = (comb*(q-j+1))%mod;
        comb = (comb*qpow(j,mod-2))%mod;
        r = (r + (j+1)*comb)%mod;
    }
    ll p = cnt[2];
    ll ans = r;
    comb = 1;
    for(ll i = 1;i<=p;i++){
        comb = (comb*(p-i+1))%mod;
        comb = (comb*qpow(i,mod-2))%mod;
        ans = (ans + (i+1)*comb%mod*r%mod)%mod;
    }
    ans = ans*qpow(2,cnt[1])%mod;
    ans = (ans-1)%mod+mod;
    ans%=mod;
    cout<<ans;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ll t = 1;
    while(t--)
        solve();
}

写在最后