2020牛客暑期多校训练营（第六场）题解C、E、B、K

C Combination of Physics and Maths

题目传送门

Combination of Physics and Maths

思路

首先明确:矩阵的底面积定义为最后一行的数的和，重量定义为所有数的和
所以只需要找到单列中出现的最大压力即可（单列的必定优于双列的）

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=209;
int n, m;
int a[N][N], ans[N][N];
double mx, temp;
void solve(){
    scanf("%d %d", &n, &m);
    mx=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++){
            scanf("%d", &a[i][j]);
            if(i==0)    ans[i][j]=a[i][j];
            else        ans[i][j]=ans[i-1][j] + a[i][j];    //列的前缀和
            temp=(double)ans[i][j]/a[i][j];                 //该位置的压力值
            mx=max(temp, mx);
        }     
    printf("%.8lf\n", mx);
}

int main(){

#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while(T--)  solve();
    return 0;
}

E Easy Construction

题目传送门

Easy Construction

思路

赛中没看懂题，赛后秒A，我是**
就是求一个$1-n$的排列p，对于每个 i（i属于$1-n$），该排列中存在长度为 i 的连续的子序列，它的和对n取模后为k
很明显当i=n的时候，子序列即为本身，易得$(n*(n+1)/2)\%n=k$，所以k可以先判断一下 k 的值
对于偶数n，序列应该为 {n， 1， n-1， 2， n-2 ， …}
对于奇数n，序列应该为 {n，n/2，1，n-1， 2， n-2， …}

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=5e3 + 9;
int n, k, ans, flag;
void solve(){
    scanf("%d %d", &n, &k);
    if(k!=n*(n+1)/2 %n) {printf("-1\n"); return ;}    //该种情况无解
    if(k==0){           //n为奇数的情况
        printf("%d ", n);
        for(int i=1; i<=n/2; i++)
            printf("%d %d ", i, n-i);
        printf("\n");
        return ;
    }
    printf("%d %d ", n, n/2);               //n为偶数的情况
    for(int i=1; i<n/2; i++)
        printf("%d %d ", i, n-i);
    printf("\n");
    return ;
}

int main(){
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

B Binary Vector

题目传送门

Binary Vector

思路

逆元知识点：逆元
线代知识了，直接看官方题解吧

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1e9 + 7;
const int N=2e7+9;
ll p[N], inv[N], xor_[N];
ll f;
ll quick_pow(ll a, ll b){ 
	ll res = 1;
	while (b){
		if (b & 1)  res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void init(){
    p[0]=1;
    for(int i=1; i<=N; i++)  p[i]=p[i-1]*2ll %mod;  //2的次方打表
    inv[N]=quick_pow(p[N], mod-2);
    for(int i=N-1; i>0; i--)   inv[i]=inv[i+1]*2%mod;   //1/2的次方的逆元打表
    xor_[1]=f=inv[1];
    for(int i=2; i<=N; i++) f=(f*(p[i]-1) %mod)*inv[i] %mod, xor_[i]=xor_[i-1]^f;   //f的异或打表
    return ;
}
void solve(){
    int n;
    cin>>n;
    cout<<xor_[n]<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    init();
    while(T--)  solve();
    return 0;
}

K K-Bag

题目传送门

K-Bag

思路

可以先看看官方题解

元素过大，$10^{9}$，所以离散化提前处理一下数据
用ans表示在[yk+x, yk+x+k-1]这段中不同的数字，即中间几段互不相等的区间

代码

#include<cstdio>
#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
// #define TDS_ACM_LOCAL
const int N=5e5 + 9;
int a[N],f[N],b[N],vis[N];
void solve(){
    memset(vis,0,sizeof(vis)); 
    memset(f,0,sizeof(f)); 
    f[0]=1;
    int n,k,flag=0, ans=0, len;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i], flag=(a[i]>k ? 1:0), b[i]=a[i];
    if(flag) {cout<<"NO"<<endl; return ;}
    sort(b+1,b+n+1);
    len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=std::lower_bound(b+1,b+len+1,a[i])-b;    //离散化
    for(int i=1;i<=n;i++){                  //ans表示在[yk+x, yk+x+k-1]这段中不同的数字，即中间几段互不相等的区间
        if(i>k) if(!--vis[a[i-k]]) ans--;
        if(!vis[a[i]]) ans++;
        vis[a[i]]++;
        if(i>=k&&ans==k) f[i]=f[i-k];
        if(i<k&&ans==i) f[i]=1;
    }
    ans=0;
    memset(vis,0,sizeof(vis));
    for(int i=n;i>=max(n-k,0);i--){             //查找k个数，判断f=1
        if(f[i]&&ans==n-i) {flag=1; break;}
        if(!vis[a[i]]) ans++;
        vis[a[i]]++;
    }
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

本文地址：https://blog.csdn.net/xmyrzb/article/details/107620627