牛客周赛 35

[题目链接-牛客周赛 Round 35](https://ac.nowcoder.com/acm/contest/76133#question)

A - 小红的字符串切割

题意

给出一个长度为偶数的字符串，分别输出前一半和后一半

思路&代码

按题意输出即可

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    string str;
    cin>>str;
    cout<<str.substr(0,str.length()/2)<<endl;
    cout<<str.substr(str.length()/2,str.length()/2);
}
signed main(){
    int T = 1;
//     cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B - 小红的数组分配

题意

给你一个长度为2*n的数组，问能否分成两个长度为n的数组a,b使得$a_i = b_i$ 。

思路

先对原先的数组排序后 ，依次分别装入a和b即可。 如果在某次装入时值不同则无解。

代码

void solve(){
    int n;
    cin>>n;
    vector<int> vec;
    rep(i,1,2*n){
        int num;cin>>num;
        vec.push_back(num);
    }
    sort(vec.begin(),vec.end());
    vector<int> a;
    for(int i = 0;i<=2*n-1;i+=2){
        if(vec[i] != vec[i+1]) {cout<<-1<<endl;return ;}
        a.push_back(vec[i]);
    }
    for(auto p : a){
        cout<<p<<' ';
    }
    puts("");
    for(auto p : a){
        cout<<p<<' ';
    }
    puts("");
}

C - 小红关鸡

题意

给出一些鸡窝的坐标$x_i$, 以及你的栅栏的长度$k$ , 如果鸡在栅栏围住的区间中，那么他就被抓住。 现在鸡在所有鸡窝中等可能出现，问关注鸡的最大概率是多少。

思路

其实就是问在一个区间$[x,x+k-1]$ 中，最多有几个鸡窝。先对所有的坐标排序，之后可以双指针来找，也可以枚举左端点，然后二分右端点。

代码

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a;
    rep(i,1,n){
        int num; cin>>num;
        a.push_back(num);
    }
    int ans = 0;
    sort(a.begin(),a.end());
    for(int i = 0;i<n;i++){
        int r = a[i]+k;
        int rind = upper_bound(a.begin(),a.end(),r)-a.begin();
        ans = max(ans,rind-i);
    }
    cout<<double(ans)/n;
}

D - 小红的排列构造

题意

给你一个数组，问最少修改几个数能使得这个数组是一个**排列**。给出一种修改方案。

(排列指的是$1,2,3,...,n$以任意顺序组成的数组)

思路

对于1~n这$n$个排列数，如果某个数$x$在原数组中已经存在，那么就一定不需要操作来变成$x$ 。

而对于1~n这$n$个排列数，如果某个数$y$在原数组中不存在，那么一定需要进行一次操作来使某个数变成$y$。

为了得到具体的方案，我们需要记录**“冗余数”**的坐标。冗余数由以下两部分组成：

• 位于1~n区间内，但该数已经出现过。
• 不位于1~n的区间内。

如$n=6$ ，$1,2,3,3,6,10$ 那么第二个$3$和$10$被视为了冗余数。

于是我们使用数组cnt记录1~n中每个数都出现了几次。 然后枚举1~n， 每当$cnt[i] = 0$ 我们就选出随意一个冗余数，将它变为$i$。

代码

int cnt[100005]; //记录1到n每个数都出现了多少次
void solve(){
    int n;
    cin>>n;
    stack<int> st;
    rep(i,1,n){
        int num; cin>>num;
        if(num<1 || num > n){
            st.push(i);
        }else {
            cnt[num]++;
            if(cnt[num]>1) st.push(i);
        }
    }
    int ans = 0;//一共需要修改几个数
    for(int i = 1;i<=n;i++){
        if(cnt[i] == 0) ans++;
    }
    cout<<ans<<"\n";
    for(int i = 1;i<=n;i++){
        if(cnt[i] == 0) {
            cout<<st.top()<<" "<<i<<'\n';
            st.pop();
        }
    }
}

E - 小红的无向图构造

题意

给出你$n$个节点， 以及从这n个节点到达第一个顶点的最短路距离$a_i$ 。现在需要你构造一个有m条边的无向图，图中每条边的边权都为1，使得这个图满足距离限制。无向图中不应该包含重边或者自环。如果无解就输出-1。

保证($a_1 = 0,$对于$i\ge 2,1\le a_i \le n-1$ )

思路

首先我们知道每个节点都能到达1号节点，因此整个图一定是连通图。那么就出现了**第一个限定条件**：$m\ge n-1$ , 否则我们没有足够多的边来将所有顶点连接为一个整体。

接下来我们思考如何满足所有节点的距离限制。 如果我们将这n个节点组成一棵树，树根是1号顶点。 那么每个顶点到达1号顶点的最短路径长度即为这个节点的深度再减去1 。于是我们只需要**将节点按照深度进行分层组成一棵树**然后连接即可满足距离条件。

此时我们便发现了**第二个限定条件** ：若存在距离为$a_k$ 的节点，但不存在距离为$a_k - 1$ 的节点，那么一定无法构建这么一个无向图。若一个节点到达1号节点的最短距离为$a_k$, 那么他一定需要首先走到距离为$a_k - 1$的节点上。

可是我们要构造的是一个m条边的无向图，而不是一个n- 1条边的树。 我们需要在这棵树的基础上增加一些无关紧要的冗余边，使得每个节点到达1号节点的最短距离不变。可以发现，对于位于同一层的顶点，我们让他们任意两条边相连，都不会改变每个点到达1号顶点的最短距离。 同时，若让第$i$ 层的节点与第$i - 1$层的节点两两相连，也不会使得某个节点到达1号节点的最短路径变小。

但是增加冗余边是有上限的，从没有任何边开始加的话，如果第i层的节点有$b_i$个 ，那么我们同层内只能增加undefinedfrac{b_i * (b_i=1)}{2}$条边，而他和上一层可以连接$b_i * b_{i-1}$条边。 于是我们得到了边的最大限度$maxm$.于是就有了**第三个限定条件**$m \le maxm$ 。

代码

vector<int> dis[100005]; //dis[i]记录距离为i的节点的下标都有哪些
void solve(){
    int n,m;
    cin>>n>>m;
    rep(i,1,n){
        int num; cin>>num;
        dis[num].push_back(i);
    }
    if(m<n-1){cout<<-1;return ;} //第一个限制条件
    int maxm;//求边的最大限度
    for(int i = 1;i<n;i++){
        int sz = dis[i].size();
        if(dis[i+1].size() && (dis[i].size() == 0))//如果不满足第二个限制条件就退出
            {cout<<-1;return;}
        int sz2 = dis[i-1].size();
        maxm += sz*(sz-1)/2;//同层
        maxm += sz*sz2;//相邻层
    }
    if(m > maxm) {cout<<-1;return ;}//第三个限制条件
    //特判完毕，开始分配边
    // 第一个二重循环，先建好一棵树。
    for(int i = 1;i<n;i++){
        for(auto p : dis[i]){
            cout<<p<<" "<<dis[i-1][0]<<'\n'; //让每个节点都连接上一层节点(dis[i-1])的第一个节点(dis[i-1][0])
        }
    }
    //分别考察每层能增加的冗余边
    int le = m - (n-1);//还需要加几条冗余边
    for(int i =1;i<n;i++){
        //同层
        int sz = dis[i].size();
        for(int j = 0;j<sz;j++){
            for(int k = j+1;k<sz;k++){
                if(le<=0) {return ;}//如果不需要加了就return
                cout<<dis[i][j]<<" "<<dis[i][k]<<'\n';
                le--;
            }
        }
        //和上一层相连，但是只能从上一层的第二个节点(dis[i-1][1])开始连接
        int sz2 = dis[i-1].size();
        if(sz2 <= 1) continue;//如果上一层没多余的节点
        for(int j = 0;j<sz;j++){
            for(int k=1;k<sz2;k++){
                if(le<=0) {return ;}//如果不需要加了就return
                cout<<dis[i][j]<<" "<<dis[i-1][k]<<'\n';
                le--;
            }
        }
    }
    return ;
}

F/G - 小红的子序列权值和

题意

定义一个数组的权值为 ： 数组中所有元素的乘积的因子数量，如$[1,2,3]$ 的权值是$4$ .

现在**给你一个只有1 ，2，3三种数的数组a**， 问他们的所有**非空**子序列的权值的和是多少。

undefinedF: 1 \le n \le 10^3 , G: 1\le n \le 10^5)$

思路

思路参考自该大佬->[题解链接](https://blog.nowcoder.net/n/58e379f6ec48457b859926673cde4b17)

我们用三个数$cnt1,cnt2,cnt3$来记录$1,2,3$这三个数各自出现了多少次 。 我们先不考虑1的问题，因为1对于一个数组最终的权值没有影响。 那么对于一个子序列，如果他有$i$ 个2 ，$j$个3 ,他就会有undefinedi+1)*(j+1)$个因子（ 选择$0$到$i$个$2$，以及$0$到$j$个$3$, 进行组合) 于是我们就可以枚举$i$从$0$到$cnt2$，$j$从$0$到$cnt3$. 对于每个$i , j$,他对答案的总贡献为 ：$(i+1)*(j+1)*C_{cnt2}^i*C_{cnt3}^j$其中$C_a^b$表示从a中选择b个数的组合数。

之后我们加上1对答案的影响，发现对于这$cnt1$个1，我们可以选择任意个1，于是共有$2^{cnt1}$ 种选择，需要在原先答案的基础上乘上$2^{cnt1}$ ，最终又由于题目要求子序列必须非空，令答案减一即为最终答案。

于是我们可以在$n^2$ 的时间复杂度内完成本题，F题得以通过。

下面考虑如果节时来通过G题， 可以发现在i不变的情况下， 令$j$从$0$到$cnt3$， 贡献的答案为undefinedi+1)*C_{cnt2}^i *(1*C_{cnt3}^0+2*C_{cnt3}^1+…+(cnt3+1)*C_{cnt3}^{cnt3})$，于是我们发现这个贡献中与cnt3有关的部分$1*C_{cnt3}^0+2*C_{cnt3}^1+…+(cnt3+1)*C_{cnt3}^{cnt3}$是一个常数，他的大小和i的取值无关，于是我们可以对他进行预处理， 然后我们枚举i即可， 于是就将计算答案的复杂度降为了$O(n)$。 但由于需要计算n个阶乘以及他们的逆元来求组合数，所以整段代码的复杂度为$O(nlogn)$。

代码

const int N = 1e5+5; // N的上界
const int mod = 1e9+7; //模数
int fac[N];// 阶乘,fac[i]表示 i 的阶乘
int ifac[N]; // 阶乘的逆元 ifac[i] = inv(fac[i])
int qpow(int x,int n){ // 快速幂,用来求逆元
    int ans = 1;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n>>=1;
    }
    return ans;
}
int inv(int x){//求逆元
    return qpow(x,mod-2);
}
void init(){ // 初始化,即预处理fac和ifac数组
    fac[0] = 1;
    for(int i = 1;i<=1e5+2;i++){
        fac[i] = fac[i-1] * i % mod;
    }
    for(int i = 0;i<=1e5+2;i++){
        ifac[i] = inv(fac[i]);
    }
    return ;
}
int C(int a,int b){//求组合数
    return fac[a] * ifac[b] % mod *ifac[a-b] % mod;
}
void solve(){
    init();
    int n;
    cin>>n;
    int cnt1,cnt2,cnt3;
    cnt1 = cnt2 = cnt3 =0;
    for(int i = 1;i<=n;i++){
        int num;cin>>num;
        if(num == 1) cnt1 ++;
        if(num == 2) cnt2 ++;
        if(num == 3) cnt3 ++;
    }
    int tmp = 0; //预处理
    for(int i= 0;i<=cnt3;i++){
        tmp += C(cnt3,i) * (i+1)%mod;
    }
    tmp %= mod;
    int ans = 0;
    for(int i = 0;i<=cnt2;i++){//计算答案
        ans = ans + C(cnt2,i)* (i+1) %mod *tmp %mod;
    }
    ans = ans%mod * qpow(2,cnt1) % mod;//计算1的影响
    cout<<ans-1;//输出ans-1
}