D. Magical Array（思维，前缀和 ，CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)）

题目链接.
题意：
操作$1$:选两个数$i,j(1<i<j<m)$,使得$c[i]=c[i]-1,c[j]=c[j]-1,c[i-1]=c[i-1]+1,c[j+1]=c[j+1]+1$。

操作$2$:选两个数$i,j(1<i<j<m-1)$,使得$c[i]=c[i]-1,c[j]=c[j]-1,c[i-1]=c[i-1]+1,c[j+2]=c[j+2]+1$。

有一个初始数组$b$,长度为$m$，有$n$个数组$c$,$n$个数组中有$1$个数组是对$b$进行不限次操作$2$得到的，其余数组是对$b$进行不限次操作$1$得到的。

求哪个数组是通过操作$2$得到的，以及进行操作$2$的次数。

思路：
求数组后缀和的和
操作$1$数组后缀和的和全都相同
操作$2$数组后缀和的和$>$操作$1$数组后缀和的和
操作$2$的次数$=$操作$2$数组后缀和的和$-$操作$1$后缀和的和。

对于操作1：
$a[i-1]\ast (i-1)+a[i]\ast i+a[j]\ast j+a[j+1]\ast (j+1)$
$=(a[i-1]+1)\ast (i-1)+(a[i]-1)\ast i+(a[j]-1)\ast j+(a[j+1]+1)\ast (j+1)$

对于操作2：
$a[i-1]\ast (i-1)+a[i]\ast i+a[j]\ast j+a[j+2]\ast (j+2)$
$<(a[i-1]+1)\ast (i-1)+(a[i]-1)\ast i+(a[j]-1)\ast j+(a[j+2]+1)\ast (j+2)$

#include
#define pii pair<int,int>
#define ll long long
using namespace std;

int n,m;
void solve()
{
    cin>>n>>m;
    ll minn=9e17,maxn=0;
    int id=-1;
    for(int i=1;i<=n;i++)
    {
        ll sum=0;
        for(int j=1;j<=m;j++)
        {
            ll x;cin>>x;
            sum+=x*j;
        }
        minn=min(sum,minn);
        maxn=max(sum,maxn);
        if(maxn==sum)id=i;
    }
    cout<<id<<" "<<maxn-minn<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;cin>>t;
    while(t--)solve();

    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39