2020牛客暑期多校训练营（第六场）
额，睡了一下午，直接错过了比赛。。。
@[toc]
A African Sort
题意：
题解：
代码：
B Binary Vector
C Combination of Physics and Maths
题意：
一个矩阵的底面积定义为最后一行的数的和，重量定义为矩阵内所有数的和（含最后一行），给一个正整数矩阵，找一个压强（压强等于重量/面积）最大的可非连续子矩阵
题解：
其实单列矩阵就是最大情况
如果一个子矩阵有多列，那么可以拆成两个行数不变的更小子矩阵，且其中一个一定不比原情况差
证明：
所以我们只需要求出每一列矩阵的压强值，从上到下选入所以元素
代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=210;
int a[MAX_N][MAX_N];
int sum[MAX_N][MAX_N];
int main(void){
int T,n,m,i,j;
cin>>T;
while(T--){
scanf("%d%d",&n,&m);
double maxl=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-1][j]+a[i][j];
//求以a[i][j]为底，的压强
maxl=max(maxl,1.0*sum[i][j]/(1.0*a[i][j]));
}
}
printf("%.8f\n",maxl);
}
return 0;
} D Data structure
E Easy Construction
题意：
给定n，k，问是否可以构造一个1 ~ n的排列p，使得对于1 ~ n中任意的数i，p都存在一个长度为i的子区间，其和模n余k。有解输出任意一组
题解：
当i=n时，也就是子区间为整个p时，如果此时模n不余k，那就说明无解，如果余k就说明存在解
换句话也就是n*(n+1)/2%n==k
当k满足条件时，存在解。
如果n为奇数，那k=0；（因为（n+1)/2肯定为偶数，那n的偶数倍模n肯定为0），那p可以为{n,1,n-1,2,n-2,......}。这样无论i为几，选i个数之和都是n的倍数
如果n为偶数，那k=n/2，那p可以为{n,n/2,1,n-1,2,n-2,...}
本题关键在于n如果确定，k也相应的确定，那p就好确定
代码：
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=4000100;
const int up=100000;
int a[maxn],ans[maxn];
int main(void)
{
int n,k;
scanf("%d%d",&n,&k);
int sum=0;
for(int i=1;i<=n;i++)
{
a[i]=i;
sum+=i;
}
if(sum%n!=k)
{
printf("-1\n");
return 0;
}
int cnt=0;
int l=1,r=n-1;
bool flag=true;
while(cnt<n-1)
{
if(flag)
a[++cnt]=l++,flag^=1;
else
a[++cnt]=r--,flag^=1;
}
a[++cnt]=n;
for(int i=1;i<=n;i++)
{
if(i!=1) putchar(' ');
printf("%d",a[i]);
}
return 0;
} 
京公网安备 11010502036488号