Magical Array（GOOD）

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

• 对任何一个数组$c_i,i\ne k$，选择下标p,q,p$c_i[p],c_i[q]$减1。使得$c_i[p-1],c_i[q+1]$加1。
• 对数组$c_k$，选择下标p,q,p$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 
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;
}
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
40

Chip Move(前缀和优化dp)

题意：一维数轴上欲从点0移动到点$n^{,}$（只能向右移动）。第i次移动距离必须是(k+i-1)的倍数（不等于0）。问当$n^{,}$从1取值到n时问移动种类数分别是多少。
数据范围：

题解：
设移动的次数设为h，则h最大值满足$(h+1)h\le n$，则$h$是$O(\sqrt{n})$级别的。因此设$dp[i][j]$为使用i次移动移动到点j的方案数。

则总状态数量为$O(n\sqrt{n})$的。
状态转移方程：
$$dp[i][j]=dp[i-1][j-(k+i-1)]+dp[i-1][j-2(k+i-1)]+\cdots$$
只要$j-q\cdot (k+i-1)\ge 0$
复杂度不可接收
但可以将上述和维护成一个前缀和。
初始时：
$$pre[i-1][j]=dp[i-1][j]$$
从小到大遍历j每一次只需：
$$pre[i-1][j]+=pre[i-1][j-(k+i-1)]$$
这样就有：
$$dp[i][j]=pre[i-1][j]$$
注意上述转移是i-1到i的，因此可以利用滚动数组优化。

#include 
using namespace std;
typedef long long ll;
const ll mod = 998244353;



int main()
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll pre[n+1],dp[n+1],ans[n+1];
    memset(dp,0,(n+1)*sizeof(ll));
    memset(ans,0,(n+1)*sizeof(ll));
    dp[0] = 1;
    for(ll i = k;(k + i) * (i - k + 1) / 2<= n;i++)
    {
        //更新前缀和
        for(int j  = 0;j<=n;j++){pre[j]=dp[j]; if(j- i >= 0) pre[j] = (pre[j] + pre[j - i]) % mod;}
        //利用前缀和更新dp值
        for(int j = 0;j<=n;j++) {if(j - i >= 0) dp[j] = pre[j-i]; else dp[j] = 0;}
        for(int j = 1;j<=n;j++) ans[j] = (ans[j] + dp[j]) % mod;
    }  
    for(int i  =1;i<n;i++) printf("%d ",(int)ans[i]);
    printf("%d",(int)ans[n]);
    system("pause");
    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

Robot in a Hallway(very very good)

题意：给定2行m列的矩阵每个格点有一个数字。机器人初始时在格点(0,0)处。每个格点(i,j)上有一个数字a[i][j]，表明在a[i][j]后该格点会解锁。格点只有在解锁后机器人才能进入(即机器人可能最早进入(i,j)的时间为a[i][j]+1)。每单位时间机器人可以上下左右移动到相邻的格点。求机器人在不访问同一格点两次及以上的情况下，机器人访问完所有格点所需最少时间。
数据范围：$m\le 2e^5$
题解：
我认为这道题非常好，结合了许多知识点又有一定的思维量，将这道题严谨的过程写一下。
首先，由不访问一个结点两次及以上，只可能是如下的访问路径：
全直走：

部分Z字形走+剩下直走（由从上结点开始和从下结点开始共2种情形）

全Z字形走：

其中全直走，全Z字形走的情形根据递推关系$dp=max(dp+1,a[i][j]+1)$关系即可求出。关键在于部分Z字形的情况，而部分Z字形的Z字形也可以根据上述递推关系求解。于是问题变为如何快速求解部分Z字形后直走的部分所用时间，当然也可以根据递推关系求解但是不断求解显然时间复杂度不可接收，能否找到一些增量关系呢？
考察一下递推关系$dp=max(dp+1,a[i][j]+1)$，最开始dp值就是将部分Z字形路径走完后的时间。
假设我们递推n次。在这n次递推中，我们可能每一次都是令当前的dp加1，也有可能是直接取$a[i][j]+1$这个值。关键在于一旦取了$a[i][j]+1$这个值后，前面的所有路径都无关了。因此如果假设某个$a[i][j]+1$在递推过程中在max函数中被取到我们可以仅仅考察最后一次取到的对应的$a[i^{,}][j^{,}]$，这意味着如果在其前面有a[i][j]+1在max函数中被取到则加上差值后仍然小于$a[i^{,}][j^{,}]+1$，对$a[i^{,}][j^{,}]$后面所有点意味着从其出发加上时间差值大于等于后面所有点的解锁时间。这引导我们将时间差信息融合到a[i][j]本身。因此如果假设$a[i^{,}][j^{,}]+1$在第q次递推取到，显然其$a[i^{,}][j^{,}]+(n-q)$具有最大值。反之若该值最大则考察一下差值则也容易证明其是最后一次被取到。
于是递推式的最终结果就是$max(d{p}_0+n-1,a[i^{,}][j^{,}]+(n-q))$
推广到本题，就是维护后缀每个$a[i][j]+j$和$a[i][j]-j$的最大值。我这里使用栈来实现。

#include 
using namespace std;
typedef long long ll;
const ll mod = 998244353;



int main()
{
    int t; cin>>t;
    for(int  i = 0;i<t;i++)
    {
        int m;scanf("%d",&m);
        ll a[2][m];
        for(int p = 0;p<2;p++) for(int q = 0;q<m;q++) scanf("%lld",&a[p][q]);
        stack<pair<ll,int>> sufmmax1,sufmmax2,sufpmax1,sufpmax2;
        sufmmax1.push({a[0][m-1]-(m-1),m-1}); sufmmax2.push({a[1][m-1]-(m-1),m-1});
        sufpmax1.push({a[0][m-1]+(m-1),m-1}); sufpmax2.push({a[1][m-1]+m-1,m-1});
        for(int q = m - 2;q>=0;q--)
        {
            if(a[0][q] - q > sufmmax1.top().first) sufmmax1.push({a[0][q]-q,q});
            if(a[1][q] - q > sufmmax2.top().first) sufmmax2.push({a[1][q]-q,q});
            if(a[0][q] + q > sufpmax1.top().first) sufpmax1.push({a[0][q]+q,q});
            if(a[1][q] + q > sufpmax2.top().first) sufpmax2.push({a[1][q]+q,q});
        }
        ll ans;
        ll curtime = 0;
        for(int q = 1;q<m;q++) curtime = max(curtime + 1,a[0][q] + 1);
        curtime = max(curtime + 1,a[1][m- 1] + 1);
        for(int q = m  - 2;q>=0;q--) curtime = max(curtime + 1,a[1][q] + 1);
        ans = curtime;
        ll i_ = 0,j_ = 0;
        //z字形走位
        curtime = 0;
        while(j_ <= m - 1)
        {
            if(sufmmax1.top().second == j_) sufmmax1.pop();
            if(sufmmax2.top().second == j_) sufmmax2.pop();
            if(sufpmax1.top().second == j_) sufpmax1.pop();
            if(sufpmax2.top().second == j_) sufpmax2.pop();
            i_ = i_ ^ 1;
            curtime  = max(curtime + 1,a[i_][j_] + 1);
            if(m - j_ -1 >= 2) ans = min(ans,max(curtime +2*m - 2*j_ - 2,max(2*m - j_ - 1 + sufmmax2.top().first,-j_ + sufpmax1.top().first)));
            j_++;
            if(j_ > m - 1) break;
            curtime = max(curtime + 1,a[i_][j_] + 1);
            if(sufmmax1.top().second == j_) sufmmax1.pop();
            if(sufmmax2.top().second == j_) sufmmax2.pop();
            if(sufpmax1.top().second == j_) sufpmax1.pop();
            if(sufpmax2.top().second == j_) sufpmax2.pop();
            i_ = i_ ^ 1;
            curtime = max(curtime + 1,a[i_][j_] + 1);
            if(m - j_ - 1 >= 2) ans = min(ans,max(curtime + 2*m - 2*j_ -2,max(-j_ + sufpmax2.top().first,2*m - j_ - 1 + sufmmax1.top().first)));
            j_++;
            if(j_ <= m - 1) curtime = max(curtime + 1,a[i_][j_] + 1);
        }
        ans = min(ans,curtime);
        printf("%lld\n",ans);
        
    }
    system("pause");
    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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

Tournament Countdown（交互1800）

题意：编号1-n的人两两进行单淘汰赛。即1号2号比赛，胜者进入下一轮，3号4号比赛，胜者进入下一轮，以此类推，如图所示。

每次可以查询任意两个编号人物获胜次数大小比较情况（给出大于，小于，等于三种回复）。要求查询次数不超
的前提下求出最终胜者。

题解：查询次数很像等比数列和。即
$$2+2\cdot 4+2\cdot 4^2+\cdots 2\cdot 4^{\frac{n}{2}-1}=\frac{2^{n+1}-2}{3}$$
因此考虑每4个一组求出答案。假设现在只剩4个对比1号3号大小后分类讨论即可。注意这道题隐含条件是对这4个人有2个最小的相等次数（第一轮被淘汰的两个人）以及2个较大的次数且这两个较大次数一定是不相等的。2次查询就可以获取最终的胜者。递归应用上述结论即可。
ps：另一种解读$\lceil \frac{1}{3}\cdot 2^{n+1}\rceil$的方法是要求每2个query可以划去3个数字。

#include 
using namespace std;
typedef long long ll;
const ll mod = 998244353;



int main()
{
    int t;
    scanf("%d",&t);
    for(int i  = 0;i<t;i++)
    {
        int n; scanf("%d",&n);
        fflush(stdin); fflush(stdout);
        vector<int> a;
        for(int k = 1;k<=(1 << n);k++) a.push_back(k);
        while(a.size() >= 4)
        {
            vector<int> b;
            for(int k = 0;k<=a.size() - 4;k+=4)
            {
                int q = a[k],w = a[k+1],e=a[k+2],r=a[k+3];
                printf("? %d %d\n",q,e);
                fflush(stdout);
                fflush(stdin);
                int o; scanf("%d",&o);
                fflush(stdout); fflush(stdin);
                if(o == 0)
                {
                    printf("? %d %d\n",w,r);fflush(stdout); fflush(stdin);
                    int o; scanf("%d",&o);
                    b.push_back(o == 1?w:r);
                }
                else if(o == 1)
                {
                    printf("? %d %d\n",q,r);fflush(stdout); fflush(stdin);
                    int o; scanf("%d",&o);
                    b.push_back(o == 1?q:r);
                }
                else
                {
                    printf("? %d %d\n",w,e);fflush(stdout); fflush(stdin);
                    int o; scanf("%d",&o);
                    b.push_back(o == 1?w:e);
                }
            }
            a.clear();
            for(int v:b) a.push_back(v); 
        }
        fflush(stdout);
        fflush(stdin);
        printf("? %d %d\n",a[0],a[1]);
        fflush(stdout);
        fflush(stdin);
        int o; scanf("%d",&o);
        if(o == 1) printf("! %d\n",a[0]); else printf("! %d\n",a[1]);
        fflush(stdout);
        fflush(stdin);
    }
    system("pause");
}

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

重要结论：