【题目记录】——2021牛客暑期多校训练营4

￡神魔★判官ぃ 2022-09-01 13:58 68阅读 0赞

### 2021牛客暑期多校训练营4 ###

*  C LCS 思维，模拟
 *  F Just a joke 思维
 *  I Inverse Pair 数学，思维
 *  J Average 最大平均值

题目集地址【 [2021牛客暑期多校训练营4][2021_4]】  
这次训练我们做出了4题C,F,I,J题，虽然可能这次题目集有点简单，但我们还是受到了一些鼓舞,先把这些题目记录一下，题目中一些算法还是不是很熟悉，有参考一些资料。

# C LCS 思维，模拟 #

【[题目地址][Link 1]】  
题意：  
有三个长度相同的字符串，s1，s2，s3，LCS(s1,s2)表示s1字符串和s2字符串的公共子串的长度（公共子串可以不连续）比如abcc和accd，他们的公共子串为acc，长度为3。题目给出四个数字分别表示LCS(s1,s2),LCS(s2,s3),LCS(s1,s3),和3个字符串的长度，要求构造符合要求的3个字符串。  
思路：  
其实构造字符串比较简单，先找出最小的公共子串的长度l1，给三个字符串都添加l1个a字符，然后找出次长度公共子串l2，然后添加l2-l1个b字符，最后添加l3-l1个c字符，最后为每个字符串添加其他不同的字符到指定长度即可。在我们做的过程中遇到的问题是字符串的位置不好确定，我们最后搞了一个多次判断。不过后来我看了几个题解都是一点点判断的。。暂时没有更好的方法  
AC代码：

#include <bits/stdc++.h>
    
    using namespace std;
    int d[3],n,pos,m=1212,len1,len2,len3,mm;
    bool vis[3];
    char s[4][1212],ch='a';
    int main() { 
        ios::sync_with_stdio(0),cin.tie(0);
        cin >>d[0]>>d[1]>>d[2]>>n;
        for(int i=0; i<3; i++)
            if(m>=d[i]) { 
                m=d[i];
                pos=i;
            }
        mm=m;
        for(int i=0; i<m; i++) { 
            s[1][len1++]=ch;
            s[2][len2++]=ch;
            s[3][len3++]=ch;
        }
        ch++;
        m=1212;
        vis[pos]=1;
        for(int i=0; i<3; i++)
            if(m>=d[i]&&!vis[i]) { 
                m=d[i];
                pos=i;
            }
        m-=mm;
        if(pos==0) { 
            for(int i=0; i<m; i++) { 
                s[1][len1++]=ch;
                s[2][len2++]=ch;
            }
        } else if(pos==1) { 
            for(int i=0; i<m; i++) { 
                s[2][len2++]=ch;
                s[3][len3++]=ch;
            }
        } else { 
            for(int i=0; i<m; i++) { 
                s[1][len1++]=ch;
                s[3][len3++]=ch;
            }
        }
        ch++;
        m=1212;
        vis[pos]=1;
        for(int i=0; i<3; i++)
            if(m>=d[i]&&!vis[i]) { 
                m=d[i];
                pos=i;
            }
        m-=mm;
        if(pos==0) { 
            for(int i=0; i<m; i++) { 
                s[1][len1++]=ch;
                s[2][len2++]=ch;
            }
        } else if(pos==1) { 
            for(int i=0; i<m; i++) { 
                s[2][len2++]=ch;
                s[3][len3++]=ch;
            }
        } else { 
            for(int i=0; i<m; i++) { 
                s[1][len1++]=ch;
                s[3][len3++]=ch;
            }
        }
        ch++;
    
    
    
        if(len1>n||len2>n||len3>n)
            cout <<"NO"<<endl;
        else { 
            for(int i=len1; i<n; i++)
                s[1][i]=ch;
            ch++;
            for(int i=len2; i<n; i++)
                s[2][i]=ch;
            ch++;
            for(int i=len3; i<n; i++)
                s[3][i]=ch;
            for(int i=1; i<=3; i++)
                cout <<s[i]<<endl;
        }
    
        return 0;
    }

# F Just a joke 思维 #

题目地址【[F Just a joke][]】  
题意：  
Alice和Bob玩游戏，给出一个图，每次操作只能拿走一个边或者没有环的连通分量，谁不能再进行操作谁就输了，给出这个图的边和点，问谁赢。  
思路：  
我们模拟之后发现，只要是边和点的个数和是偶数就是Bob赢，否则Alice赢。我和队里两个人当时模拟了50分钟找到了这个规律，有的队伍很早就看出来了。。。  
AC代码:

#include <bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n,m;
        cin >>n>>m;
        int a,b;
        for(int i=0;i<m;i++)
            cin >>a>>b;
        if((n+m)%2==1)
            cout <<"Alice"<<endl;
        else
            cout <<"Bob"<<endl;
        return 0;
    }

# I Inverse Pair 数学，思维 #

题目地址【[I Inverse Pair][]】  
题意：  
给定一个序列，可以对序列中的任何一个值加一或者不加，求操作后序列的最小逆序对数。  
思路：  
对类似（5,4）这样的逆序对中的4进行家加一操作才能减少总的逆序对数的数量，这样的操作是有效的，我们只需要按照这个规则对原数列进行操作，然后再计算出操作后序列中的逆序对数即可。  
**重要模板**：归并排序法求逆序对数  
AC代码：

#include <bits/stdc++.h>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define mod 1000000007
    #define lmax 200005
    #define pi 3.141592653589793238462643383279
    #define eps 1e-7
    
    using namespace std;
    typedef long long ll;
    typedef double type;
    int biao[lmax];
    int aw[lmax];
    
    
    ll MergeSort(int s[], int left, int middle, int right)
    { 
        int i = left, j = middle;
        int b[right - left + 1];
        int index = 0;
        ll sum = 0;
        int t = 0;
        while (i < middle && j <= right)
        { 
            if (s[i] > s[j])
            { 
                b[index++] = s[j++];
                t++;
            }
            if (s[i] <= s[j] || j == right + 1)
            { 
                sum +=(ll) t * (middle - i);
                b[index++] = s[i++];
                t = 0;
            }
        }
        //----------------------------------------------------------------
        while (i < middle)
            b[index++] = s[i++];
        while (j <= right)
            b[index++] = s[j++];
    
        index = 0;
        for (int m = left; m <= right; m++)
            s[m] = b[index++];
        return sum ;
    }
    ll k = 0;
    void Merge(int s[], int low, int high)
    { 
        if (low < high)
        { 
            int mid = (low + high) / 2;
            Merge(s, low, mid);
            Merge(s, mid + 1, high);
            k += MergeSort(s, low, mid + 1, high);
        }
    }
    int main()
    { 
        int n;
        int a[lmax];
        cin>>n;
        for(int i=1; i<=n; i++)
        { 
            scanf("%d",&a[i]);
            /*if(a[i]%2==1) a[i]++;*/
            aw[a[i]]=i;
        }
        for(int i=2; i<=n; i++)
        { 
            if(aw[i-1]>aw[i]&&biao[i-1]==0)
            { 
                a[aw[i-1]]++;
                biao[i]=1;
            }
        }
        Merge(a,1,n);
        cout<<k<<endl;
        return 0;
    }

# J Average 最大平均值 #

题目地址【[J Average][]】  
题意：  
给定两个序列a和b，由这两个序列生成一个矩阵w， W i ， j W\_\{i，j\} Wi，j=ai+bj,求矩阵中大小不小于n\*m的子矩阵的最大平均值，输出平均值。  
思路：  
要让子矩阵的平均值最大只需要找两个序列中最大均值的区间相加即可。问题的关键就在于求得序列区间长度不小于n的最大平均值。  
AC代码：

#include <iostream>
    #include <bits/stdc++.h>
    
    const int maxn=1e5+5;
    using namespace std;
    int a[maxn];      //a数组
    double b[maxn];      //a数组减去假设平均值
    double sum[maxn];    //b的前缀和
    
    double judgeAve(int n, double mid, int f)
    { 
        for(int i = 1;i <= n;i++)
        { 
            b[i] = a[i] - mid;
            sum[i] = sum[i - 1] + b[i];
        }
        double min_val = 1e10, max_val = -1e10;
        for(int i = f;i <= n;i++)
        { 
            if(min_val > sum[i - f])
            { 
                min_val = sum[i - f];
            }
            if(max_val < sum[i]-min_val)
            { 
                max_val = sum[i]-min_val;
            }
        }
        return max_val;
    }
    double largestAve(int a[],int n,int f)
    { 
        double mid;
        double l = 0,r = 1e5, eps = 1e-8;
        while(r - l > eps)
        { 
            mid = (r + l) / 2;
            if(judgeAve(n, mid, f) > 0)
            { 
                l = mid;
            }
            else
            { 
                r = mid;
            }
        }
        return r;
    }
    int main()
    { 
        int n, m, x, y;
        scanf("%d%d%d%d",&n,&m,&x,&y);
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",&a[i]);
        }
        double a1 = largestAve(a,n,x);
        for(int i = 1;i <= m;i++)
        { 
            scanf("%d",&a[i]);
        }
        double a2 = largestAve(a,m,y);
        printf("%.10lf\n",a1+a2);
    
        return 0;
    }

[2021_4]: https://ac.nowcoder.com/acm/contest/11255
[Link 1]: https://ac.nowcoder.com/acm/contest/11255/C
[F Just a joke]: https://ac.nowcoder.com/acm/contest/11255/F
[I Inverse Pair]: https://ac.nowcoder.com/acm/contest/11255/I
[J Average]: https://ac.nowcoder.com/acm/contest/11255/J