欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-11 22:58:25
CCombination of Physics and Maths题目传送门Combination of Physics and Maths思路首先明确:矩阵的底面积定义为最后一行的数的和,重量定义为所有数的和所以只需要找到单列中出现的最大压力即可(单列的必定优于双列的)代码#include#include#includeusing namespace std;#define INF 0...

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,我是**
就是求一个1n1-n的排列p,对于每个 i(i属于1n1-n),该排列中存在长度为 i 的连续的子序列,它的和对n取模后为k
很明显当i=n的时候,子序列即为本身,易得(n(n+1)/2)%n=k(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

思路

逆元知识点:逆元
线代知识了,直接看官方题解吧
2020牛客暑期多校训练营(第六场)题解C、E、B、K

代码

#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

思路

可以先看看官方题解
2020牛客暑期多校训练营(第六场)题解C、E、B、K

元素过大,10910^{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