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

发布于 2020-07-27  0 次阅读


C. Combination of Physics and Maths

思路:

首先明确:矩阵的底面积定义为最后一行的数的和,重量定义为所有数的和
所以只需要找到单列中出现的最大压力即可(单列的必定优于双列的),解释如下:
设a / b > c / d,则a ∗ d > b ∗ c ,左右同时加上a ∗ b,为a ∗ d + a ∗ b > b ∗ c + a ∗ b
即为a ∗ ( b + d ) / b ∗ ( a + c ) 移项,a / b > ( a + c ) / ( b + d )
所以单列更优

AC Code:

#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

思路:

赛中没看懂题,赛后秒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, …}

AC Code:

#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(线代)

思路:

逆元
线代知识了,直接看官方题解吧

在这里插入图片描述

AC Code:

#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;
}

G. Grid Coloring(构造)

思路:

首先特判一下-1的情况,n = 1 ,k = 1, 2 ∗ ( n + 1 ) ∗ n
对于n % k = 0 ,直接按顺序输出1 − k ,行输出完了接着输出列
对于n % k ! = 0 ,输出完一次1 − k 后,让后面的提一位到前面,例:第一次1 2 3,第二次 2 1 3
附3 4的图

在这里插入图片描述

AC Code:

#include<cstdio>
#include<iostream>
using namespace std;
int T, n, k, x, ans, i, j;
void solve(){
    scanf("%d %d", &n, &k);
    if(n==1 || k==1 || 2*(n+1)*n %k!=0) {printf("-1\n");; return ;}
    if(n%k!=0){
        for(i=1; i<=(n+1)*n; i++){
            x=(i-1) %k+1;
            printf("%d ", x);
            if(i%n==0)  printf("\n");
        }
        for(i; i<=2*(n+1)*n; i++){
            x=(i-1) %k+1;
            printf("%d ", x);
            if(i%n==0)  printf("\n");
        }
    }
    else{
        ans=0;
        for(i=1; i<=(n+1)*n; i++){
            x=(i-1+ans) %k+1;
            printf("%d ", x);
            if(i%n==0)  printf("\n"), ans++;
        }
        for(i; i<=2*(n+1)*n; i++){
            x=(i-1+ans) %k+1;
            printf("%d ", x);
            if(i%n==0)  printf("\n"), ans++;
        }
    }
    return ;
}

int main(){
    scanf("%d", &T);
    while(T--)  solve();
    return 0;
}

K. K-Bag(离散化)

思路:

可以先看看官方题解

K-Bag

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

AC Code:

#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;
}

H. Harmony Pairs(数位DP)

题目大意:

求1 < = A < = B < = N ,满足S ( A ) > S ( B ) 的( A , B )个数 s 是数码和

思路:

很明显的数位DP,但是不会…,所以补一下
最大为10100,所以最大的数的每位都是9,最小0,所以每个位的差值不会超过1000,所以用1000为底防止负数
DP[109][2009][2][2]; //分别对应 位数、两数的各位差、第一位的最高位的限制、第二位最高位的限制

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
// #define TDS_ACM_LOCAL
typedef long long ll;
const int mod=1e9 + 7;
const int init=1000;    //两数之差的初始化(防止负数出现,+-1000)
int len;
string s;
ll DP[109][2009][2][2]; //分别对应 位数、两数的各位差、第一位的最高位的限制、第二位最高位的限制
int DFS(int pos, int ans, bool signa, bool signb){
    if(pos<0)   return ans>init;
    if(DP[pos][ans][signa][signb]!=-1)  return DP[pos][ans][signa][signb];
    ll res=0;
    ll lima= signa ? s[pos]-'0':9;          //对数是否有限制
    for(int i=0; i<=lima; i++){
        for(int j=0; j<=(signb ? i:9); j++){   //题意第二个数i大于第一个数j(即为:i>j
            res=(res+DFS(pos-1, ans+j-i, signa&&i==lima, signb&&i==j))%mod;
        }
    }
    return DP[pos][ans][signa][signb]=res;
}

void solve(){
    memset(DP, -1, sizeof(DP));         //初始化DP
    cin>>s;
    len=s.length();
    for(int i=0; i<len/2; i++)  swap(s[i], s[len-1-i]);     //交换N的位次
    cout<<DFS(len-1, init, 1, 1)<<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
    solve();
    return 0;
}


平平无奇的大学在读本科生