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

Combination of Physics and Maths

题意：给出一个矩阵，求出它的一个子矩阵，使得这个子矩阵中F/S最大，F指的是这个矩阵中所有数字的和，s指的是最后一列的元素的和。
思路：一个贪心的思路。刚开始想复杂了，后面仔细一想，我只要对每列求一下平均，取最大的即可。为什么呢？可以这样想，我假设目前已经得知了一个最大的数值，1、如果后面都没出现比它更大的值，那我显然直接选这个就是答案，2、但如果后面出现比它更大的值的话，我就抛弃这个值而选那个最大的那个值。综上，直接枚举每列，然后去最大的值为ans即可。
代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[220][220];
int pre[220][220];
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(pre,0,sizeof(pre));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%lld",&a[i][j]);
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                pre[j][i]=pre[j-1][i]+a[j][i];  //预处理前缀和
            }
        }
//        for(int i=1;i<=n;i++){
//            for(int j=1;j<=m;j++){
//                printf("%lld ",pre[i][j]);
//            }
//            cout<<endl;
//        }
        double ans=-1e9;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                double sum=pre[i][j];
                double num=a[i][j];
                double temp=sum/num;
                ans=max(ans,temp);
            }
        }
        printf("%.10lf\n",ans);
    }
    return 0;
}

Binary Vector

题意：随机n个01向量，询问着n个向量线性无关的概率
思路：首先，我们先搞懂什么是线性无关，就是n个向量不能由其余n-1个向量相互表示出来，则称这n个向量是线性无关的向量。对于一个n维的空间，我们可以找到个向量，然后我们考虑选择n个向量，当我们选择第一个向量的时候，其中由个向量线性相关，当我们选择第2个向量的时候，就有个向量线性相关，当我们选择第i个向量的时候，就有个向量线性相关，也就是由个向量线性无关，那么概率就是的概率选到线性无关的向量。也就是最后的答案就是,先进行预处理，然后线性处理求解即可。
代码：

#include<iostream>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=2e7+7;
ll ans[maxn];
int main(){
    ans[1]=5e8+4;
    ll up=1,down=ans[1];
    for(int i=2;i<=2e7;i++){
        up=(up*2+1)%mod;
        down=(ans[1]*down)%mod;
        ans[i]=(ans[i-1]*up)%mod*down%mod;
    }
    for(int i=2;i<=2e7;i++)  ans[i]=ans[i]^ans[i-1];
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<ans[n]<<endl;
    }
    return 0;
}

Easy Construction

题意：给定n，k，询问是否可以构造一个1-n的排列，使得其中任意一个数i，p都存在一个长为i的子区间，区间内的和模n余k，有则输出任意一组，没有输出-1.
思路：模拟题。我们发现，当k+k=n或者n为奇数，同时k为0的时候，只要间隔输出1-（n-1）两端的值即可。否则就是不存在符合的解。
代码：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    if(n==1&&k==0){
        cout<<1<<endl;
    }
    else{  //对n和k分情况讨论
        vector<int> v;
        if(k+k==n){
            v.push_back(n);
            v.push_back(n/2);
            int l=1,r=n-1;
            while(l!=r){
                v.push_back(l);
                v.push_back(r);
                l++,r--;
            }
            int len=v.size();
            for(int i=0;i<len;i++){
                cout<<v[i];
                if(i<len-1)  cout<<" ";
            }
            cout<<endl;
        }
        else{
            if(n%2==1&&k==0){
                v.push_back(n);
                int l=1,r=n-1;
                while(l<=r){
                    v.push_back(l);
                    v.push_back(r);
                    l++,r--;
                }
                int len=v.size();
                for(int i=0;i<len;i++){
                    cout<<v[i];
                    if(i<len-1)  cout<<" ";
                }
                cout<<endl;
            }
            else  cout<<"-1"<<endl;
        }
    }
    return 0;
}