2020牛客暑期多校训练营（第六场）

BCEGK

B. Binary Vector

题意

大概是说有一个A={0,1}，每天可以在Aⁿ (n维空间) 中生成一个新的二进制向量，n天中生成的向量线性无关的概率是fn，求f₁​⊕f₂​⊕...⊕f_n​。

题解

由于这N个向量线性无关,则这N个向量张成的空间秩为N,考虑将每次随机的向量加入之前向量的空间，那么最后N个向量秩为N当且仅当每次加入的向量都不属于之前的空间。

• 线性无关的意思是一组向量中任意一个向量都不能由其它几个向量线性表示.
• 假设第一天生成了向量a，那么和它线性有关的向量有2个：0，a。
• 第二天生成的向量是b，那么和它线性有关的向量有4个：0，a，b，a+b。
• 第三天生成的向量是c，那么和它线性有关的向量有8个：0，a，b，a+b，c，a+c，b+c，a+b+c。

那么就可以推测出第 i 天线性无关的向量是(2ⁿ−2ⁱ)/2ⁿ​。那么n天中生成的向量线性无关的概率 f_n​ 就是∏(i=0,n-1) ((2ⁿ−2ⁱ)/2ⁿ)​。化简可得∏(i=1,n)​ ((2ⁱ−1​)/2ⁱ)。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
 
const ll mod=1e9+7;
 
ll quick_pow(ll a,ll b)
{
    ll sum=1;
    while(b){
        if (b&1) sum=(sum*a)%mod;
        b/=2;
        a=a*a%mod;
    }
    return sum;
}
 
ll a[20010000];
 
int main()
{
    ll x=quick_pow(2,mod-2);
    ll p=x,q=2;
    a[1]=x;
    for(ll i=2;i<=20000010;i++){
        p*=x;p%=mod;
        q*=2;q%=mod;
        a[i]=a[i-1]*p%mod*(q-1+mod)%mod;
    }
    for(int i=2;i<=20000010;i++) a[i]^=a[i-1];
    int t;
    scanf("%d",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        printf("%lld
",a[n]);
    }
    return 0;
}

C. Combination of Physics and Math

题意

给你一个矩阵 A=[a_ij] ，可以将题目的意思转换为删去某些行和列，使得压力P=（剩下的矩阵A的各个元素值之和（F） / 最底行的元素之和（S））值最大。

题解

可以发现若a/b​≤c/d​，则a/b​≤(a+c)/(b+d)​≤c/d​。可以先计算每列以第 i 行为底的矩形的压力P的，根据前边的公式可以看出，两列叠加的大小并不会比单独的一列值更大了。故只要按列找出P最大的值即可。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
 
double a[220][220];
 
int main()
{
 
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%lf",&a[i][j]);
        double ans=0;
        for(int i=0;i<m;i++){
            double p=0;
            for(int j=0;j<n;j++){
                p+=a[j][i];
                ans=max(ans,p/a[j][i]);
            }
        }
        printf("%.8f
",ans);
 
    }
    return 0;
}

E. Easy Construction

题意

给定n和k，找到一个1~n的排列P，使得每个iϵ[1,n]，P都有一个子序列，使得所有的这些不同长度的子序列各自之和对n取模的结果等于k。若这样的排列P不存在，则输出-1。

题解

• 首先如果P存在，则对于长度为n的子序列一定有((1+n)*n/2)%n==k。如果没有，则输出-1。
• 然后多写几组可以发现：如果n 是奇数，可知k=0，并且令P = {n, 1, n-1, 2, n-2, ...} ；如果n是偶数，可知k=n/2，并且令P = {n, n/2, 1, n-1, 2, n-2, ...} 。

代码

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(((1+n)*n/2)%n!=k){
        printf("-1
");
        return 0;
    }
    if(k==0){
        printf("%d ",n);
        for(int i=1;i<=n/2;i++){
            printf("%d %d ",n-i,i);
        }
    }
    else {
        printf("%d %d ",n,n/2);
        for(int i=1;i<n/2;i++){
            printf("%d %d ",i,n-i);
        }
    }
    return 0;
}

G. Grid Coloring

题意

有一个n*n的的网络格，现在要用k中颜色给每个边上色，要求：

• 每种颜色的边个数相等
• 一种颜色的边不能成环
• 一条线上至少有两种颜色

题解

首先看一下无解的情况：如果n=1和k=1肯定是不行的，当k不能整除2*n*(n+2)的时候所有颜色出现的次数不一样，也是不行的。

剩下的情况都是有解的。分成两种：

• n%k==0

按照1~k的顺序依次上色，这样相邻的边将会是同一种颜色，可以考虑将他们每次移一位，直接横纵坐标相加对k取余+1即可。

• n%k!=0

直接从1~k顺序依次涂色就好了。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
 
int a[300][300],b[300][300];
int p[100100];
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        int x=2*(n+1)*n;
        if(x%m||m==1||n==1){
            printf("-1
");
            continue;
        }
        if(n%m==0){
            for(int i=0;i<2*n+2;i++){
                for(int j=0;j<n;j++){
                    printf("%d ",(i+j)%m+1);
                }
                puts("");
            }
        }
        else{
            int k=0;
            for(int i=0;i<2*n+2;i++){
                for(int j=0;j<n;j++){
                    printf("%d ",k%m+1);
                    k++;
                }
                puts("");
            }
        }
    }
    return 0;
}

K. K-Bag

题意

给定一个k，一个有效的k-bag是1~k的一些排列连接起来的。给定一个序列，问该序列是否为k-bag的子序列。

题解

算是尺取瞎搞吧....先判断一下是否有小于1或者大于k的元素，有的话输出-1。然后找到第一个出现两次的元素，k1记录第一次出现的位置，k2记录第二次出现的位置。如果每个元素只出现了一次，直接输出YES。否则尺取判断，如果左边界大于k2的话，第一段就会有两个重复元素，不是全排列，输出NO。否则往后判断以当前 l 为第二段开头是否能成立，不成立就l++，成立则输出YES。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
 
int a[2001000];
unordered_map<int,int>mp;
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        mp.clear();
        scanf("%d%d",&n,&k);
        int flag=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            if(a[i]<1||a[i]>k) flag=1;
        }
        if(flag){
            printf("NO
");
            continue;
        }
        int k1=-1,k2=-1;    //k1:第一个出现第二次的元素的第一次出现位置   k2:第一个出现第二次元素的当前位置
        for(int i=1;i<=n;i++){
            if(mp[a[i]]){
                k1=mp[a[i]];
                k2=i;
                break;
            }
            mp[a[i]]=i;
        }
        if(k1==-1) {
            printf("YES
");
            continue;
        }
        mp.clear();
        int num=0;
        int l=k1+1,r=k1+1;
        flag=1;
        int p=0;
        while(1){
            if(l>k2){
                flag=0;
                break;
            }
            int f=1;
            while(r<=n&&num<k){
                if(mp[a[r]]==p){
                    num++;
                    mp[a[r]]++;
                    r++;
                }
                else{
                    f=0;
                    break;
                }
            }
            if(!f){
                mp[a[l]]--;
                num--;
                l++;
            }
            else if(num==k){
                num=0,p++;
            }
            if(r==n+1) break;
        }
        if(flag) printf("YES
");
        else printf("NO
");
    }
    return 0;
}