CodeTon Round 2 D. Magical Array

题目分析

给定$n$arrays with the same initial value,共有两种操作：

• 操作$1$：选择一对$(i,j)$,$a[i-1]$加$1$,$a[i]$减去$1$,$a[j]$减去$1$,$a[j+1]$加$1$.
• 操作$2$：选择一对$(i,j)$,$a[i-1]$加$1$,$a[i]$减去$1$,$a[j]$减去$1$,$a[j+2]$加$1$.

Only one array is executed several times$2$操作,Ask which array the operation was performed on$2$,操作了多少次

令$s[]$表示数组$a[]$的前缀和,We analyze the two operations on the prefix sum：

• 操作$1$：Strip unaffected intervals：$[1,i-2],[i+1,j-1],[j+2,n]$,We denote array sums as prefix-segmented sums：
  $$s[i-2]+(s[j-1]-s[i])+(s[n]-s[j+1])+a[i-1]+a[i]+a[j]+a[j+1]$$
  经过$1$次操作后：Because the affected elements are continuous,So prefixes and elements are subject to$-1$Immediately after impact$+1$影响,不变
  $$s[i-2]+(s[j-1]-s[i])+(s[n]-s[j+1])+(a[i-1]+1)+(a[i]-1)+(a[j]-1)+(a[j+1]+1)$$
  Found that prefixes and array sums are not affected

• 操作$2$：同上,Write the summation first：
  $$s[i-2]+(s[j-1]-s[i])+(s[n]-s[j+2])+(s[j+1]-s[j])+a[i-1]+a[i]+a[j]+a[j+2]$$
  经过$1$次操作后,We start by analyzing the elements that are affected：$a[i-1],a[i],a[j],a[j+2]$,But found discontinuities due to affected elements,因此$s[j+1],s[j+2]$会受影响,But the impact is there$a[j+2]$offset,也就是$s[j+2]$上的$-1$Effects are eliminated.那么：
  $$s[i-2]+(s[j-1]-s[i])+(s[n]-s[j+2])+((s[j+1]-1)-s[j])+(a[i-1]+1)+(a[i]-1)+(a[j]-1)+(a[j+1]+1)$$
  Found prefix and array sum to be$-1$.

• 操作$2$effect on the total,We can analyze it from the point of view of formula：
  $$\sum _{i=1}^n\sum _{j=1}^{i}a[j]$$
  对$a[x]$元素$+1$,$a[x+1]-1$
  $$\sum _{i=1}^{x-1}\sum _{j=1}^{i}a[j]+\sum _{i=x}^x\sum _{j=1}^{i}a[j]+\sum _{i=x}^{n}1+\sum _{i=x+1}^n\sum _{j=1}^{i}a[j]-\sum _{i=x+1}^{n}1=(\sum _{i=1}^n\sum _{j=1}^{i}a[j])+1$$
  再分析$a[y]-1$, $a[x+2]$元素$+1$:
  $$\sum _{i=1}^{x-1}\sum _{j=1}^{i}a[j]+\sum _{i=x}^x\sum _{j=1}^{i}a[j]-\sum _{i=x}^{n}1+\sum _{i=x+1}^n\sum _{j=1}^{i}a[j]+\sum _{i=x+2}^{n}1=(\sum _{i=1}^n\sum _{j=1}^{i}a[j])-2$$
  The impact was found to be：$-1$.Then according to the above conclusion,The affected arrays and the number of operations can be found.

  同理,Action-Affect is $0$.

  Code

  #include <bits/stdc++.h>
  #pragma gcc optimize("O2")
  #pragma g++ optimize("O2")
  #define int long long
  #define endl '\n'
  using namespace std;
  
  const int N = 1e6 + 10;
  
  int flag[N];
  
  inline void solve(){
        
      int n, m; cin >> n >> m;
      memset(flag, 0, (n + 5) * sizeof(int));
      int **a = (int **)malloc((n + 2) * sizeof(int**));
      int i, j;
      for (i = 0; i <= n; i++) {
        
          a[i] = (int*)malloc((m + 2) * sizeof(int));
      }
      for(int i = 1; i <= n; i++){
        
          for(int j = 1; j <= m; j++) cin >> a[i][j];
      }
      for(int i = 1; i < m; i++){
        
          int minn = *min_element(a[j] + 1, a[j] + 1 + n);
          for(int j = 1; j <= n; j++){
        
              flag[j] += (a[j][i] -= minn);
              a[j][i + 1] += a[j][i];
          } 
      }
      int pos = 1;
      for(int i = 2; i <= n; i++)
          if(flag[pos] > flag[i]) pos = i;
      if(pos == 1) cout << pos << ' ' << flag[2] - flag[1] << endl;
      else cout << pos << ' ' << flag[1] - flag[pos] << endl;
  }
  
  signed main(){
        
      ios_base::sync_with_stdio(false), cin.tie(0);
      int t = 1; cin >> t;
      while(t--) solve();
      return 0;
  }