题意
给定 \(n\) 个长度为 \(m\) 的数组，对于每一个数组选择下面任意一种操作进行若干次（操作二只能被一个数组选出）。
- \(c_{t,i} - 1,c_{t,i - 1} + 1,c_{t,j} - 1,c_{t,j - 1} + 1\)。
- \(c_{t,i} - 1,c_{t,i - 1} + 1,c_{t,j} - 1,c_{t,j - 2} + 1\)。
最后输出选择操作二的数组的编号，及其使用操作二的次数。
思路
我们不难发现一个普遍性的规律。
如果已知操作一号的数组，操作前和操作后的 \(\sum_{i = 1}^{i \leq m}c_{t,i} \times i\) 是不变的。
原因如下：
我们直接看有变化的部分即可。
操作前：\(c_{t,i - 1} \times (i - 1) + c_{t,i} \times i + c_{t,j - 1} \times (j - 1) + c_{t,j} \times j\)。
操作后：\((c_{t,j - 1} - 1) \times (i - 1) + (c_{t,i} + 1) \times i + (c_{t,j - 1} - 1) \times (j - 1) + (c_{t,j} + 1) \times i\)。
我们将上式化简：\(c_{t,i - 1} \times (i - 1) + c_{t,i} \times i + c_{t,j - 1} \times (j - 1) + c_{t,j} \times j\)。
发现两式相等，证毕。
我们可以通过这一点，用 \(s\) 维护一个 \(c_{t,i} \times i\) 的前缀和，来寻找出这个与众不同的数组。
这里还有一个奇妙的规律，需要大家去体会体会。
就是，那个选择操作二的数组的操作次数一定是：\(\max(s_i) - \min(s_i)\)。
因为，我们上文说过，选择操作一的 \(\sum_{i = 1}^{i \leq m}c_{t,i} \times i\) 不变，那么，我们再根据上面的推导过程再次推导一遍可以发现，没操作一次操作二，对于我们的 \(\sum_{i = 1}^{i \leq m}c_{t,i} \times i\) 每次加 \(1\)。
因此，我们就得出了上面的结论。
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 1e5 + 10,inf = 1e18 + 10;
int T,n,m;
int s[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
signed main(){
T = read();
while (T--){
int Max = -inf,Min = inf;
memset(s,0,sizeof(s));//初始化
n = read();
m = read();
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= m;j++){
int x;
x = read();
s[i] += x * j;//前缀和
}
Max = max(Max,s[i]);//最大值
Min = min(Min,s[i]);//最小值
}
for (re int i = 1;i <= n;i++){
if (Max == s[i]){//输出答案
printf("%lld %lld\n",i,Max - Min);
break;
}
}
}
return 0;
}