牛客多校，第六场。
若有公式图片无法正常显示，请使用梯子访问！
C - Combination of Physics and Maths
-
题意:
一个矩阵的底面积定义为最后一行的数之和，重量为矩阵中所有数之和。给一个正整数矩阵，找一个“压强” （即为重量/底面积）最大的可非连续子矩阵。 -
思路:
这题卡输入TLE了。。真恶心- 若选择的子矩阵有多列，那么如果把这个子矩阵拆成两个行数不变的更小子矩阵，这个“压强”还能更小。这是因为如有
,必然有
。
- 若选择的子矩阵有多列，那么如果把这个子矩阵拆成两个行数不变的更小子矩阵，这个“压强”还能更小。这是因为如有
- 那么就可知我们的最优子矩阵一定是某一列中的一个子段（应该是数组而并不能叫做“矩阵”），那么可以跑一遍二维前缀和找到 （当前数的前缀和/当前数） 的最大值即可。
double s[210][210], p[210][210];
int main()
{
int T;
int n, m;
scanf("%d",&T);
while (T--)
{
memset(p, 0, sizeof(p));
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lf",&s[i][j]);
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
p[i][j] = p[i - 1][j] + s[i][j];
double ans = 0.0;
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
ans = max(ans, p[i][j] / s[i][j]);
printf("%.8lf\n", ans);
}
return 0;
}
E - Easy Construction
-
题意:
构造出一个由1~n组成的序列，要求里面存在长度为1,2,3，…n的连续子数组其元素的总和%n==k. -
思路:
- 首先k一定等于n(n+1)%n,因为取长度为n的子数组时，即为这个1~n的总和，并且需要使这个总和n(n+1)%n==k.
- 所以当n为偶数时，令k=n/2,可以构造出序列: n,k,1,n-1,2,n-2…，因为除了k以外，其他所有数可以组合成%n=0的形式，再与k组合即为%n=k
- 当n为奇数时，即取k=0，构造序列n,1,n-1,2,n-2… ,原理同上
int main()
{
IOS;
int n, k;
cin >> n >> k;
if ((n % 2 == 0 && k == n / 2) || (n % 2 == 1 && k == 0))
{
if (n % 2 == 0)
{
cout << n << " " << k;
for (int i = 1; i < k; i++)
cout << " " << i << " " << n - i;
}
else
{
cout << n;
for (int i = 1; i <= n / 2; i++)
cout << " " << i << " " << n - i;
}
}
else
cout << -1;
return 0;
}