Codeforce 8.1-8.7做题记录

Magical Array（GOOD）

给定数组b长度为m。现有n个数组$c_i,1\le i\le n$，初始都与数组b相同。从中选择一个数组$c_k$。每次可以进行如下操作：

• 对任何一个数组$c_i,i\ne k$，选择下标p,q,p<q，使得$c_i[p],c_i[q]$减1。使得$c_i[p-1],c_i[q+1]$加1。
• 对数组$c_k$，选择下标p,q,p<q，使得$c_i[p],c_i[q]$减1。使得$c_i[p-1],c_i[q+2]$加1。

在经过上述操作若干次后给定数组$c_1,c_2\cdots c_n$要求找出k，并且求出在其上使用的第二种操作的次数。
思路
这道题需要我们从整体上把握。
物理角度
第一种操作是非常对称的，第二种操作是非常不对称的。如果将$c_i$中每个元素都看作是有质量的物体分别放在数轴上下标i的位置。从物理的角度来看第一种操作好像是在四个比较对称的位置加减质量一样的，直观来看质心不会变化，而第二种操作质心会变化。
编码角度
从整体上把握找出一种“编码方法”使得那个特定的k的编码和其他c数组的编码不同。第一种操作涉及下标为p,q,p-1,q+1，第二种操作涉及下标为p,q,p-1,q+2导致不同所以编码时需要可以涉及这个下标信息。对第一种操作如果将下标与数本身相乘则变化前后涉及下标的项以及常数项会相互抵消，就不会变化。

上述策略指向我们对数组的编码方式是
$$hash(c_i)=\sum _k{c}_i[k]\cdot k$$
对第一种操作，只考虑变化的四个下标p,q,p-1,q+1下标处变化后为:
$$(c_i[p]-1)\cdot p+(c_i[q]-1)\cdot q+(c_i[p-1]+1)\cdot (p-1)+(c_i[q+1]+1)\cdot (q+1)=c_i[p]\cdot p+c_i[q]\cdot q+c_i[p-1]\cdot (p-1)+c_i[q+1]\cdot (q+1)$$
从物理角度说质心不变化。
对第二种操作同理，同理可以发现每操作一次质心向右移动一个单位。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;


int main()
{
    
    int t;
    scanf("%d",&t);
    for(int i = 0;i<t;i++)
    {
    
        int n,m;
        scanf("%d%d",&n,&m);
        vector<ll> m_;
        
        for(int j = 0;j<n;j++)
        {
    
            ll a = 0;
            for(int k = 0;k<m;k++)
            {
       
                ll c; 
                scanf("%lld",&c);
                a += c * (ll)k;
            }
            m_.push_back(a);
        }
        for(int j = 0;j<n;j++)
        {
    
            if(j == 0 && m_[0]!=m_[1] && m_[j + 1] == m_[j + 2])
            {
    printf("%d %lld\n",1,m_[0]-m_[1]);break;}
            else if(j == n - 1 || j!=0 && j < n - 1 && m_[j-1]==m_[j+1] && m_[j] != m_[j-1])
            {
    
                printf("%d %lld\n",j+1,m_[j]-m_[j-1]);break;
            }
        }
    }
    system("pause");
    return 0;
}