topcoder srm 710 div1 -23

1、给定两个长度都为$n$的数组$A,B$，给出一个操作序列将$A$变成$B$。每个操作可以是以下两种之一：（1）选择一个$i,0\leq i <n$且$A_{i} \neq 0$，令$t=A_{i}$，然后置$A_{i}=0$，最后令$i$位置后的连续$t$个位置分别加1。这个是循环的，$n-1$之后是位置$0$。可能有些位置最后增加的值会超过1；（2）选择一个$i,0\leq i <n$且$A_{i} \neq 0$，然后从$i$开始(包括$i$)向前，每个位置的数字减去1，直到一个位置是$0$，然后把刚刚减去的值的和加到这个位置上。

思路：可以看出操作（2）是操作（1）的逆操作。可以先将$A$只使用操作（1）变成除了$A_{0}$外其余位置都是0，$B$也这样操作，操作序列分别为$P,Q$，那么$P$加上$Q$的逆操作就是答案。

#include <iostream>

#include <map>

#include <string>

#include <stdio.h>

#include <vector>

#include <set>

#include <algorithm>

#include <string.h>

#include <queue>

using namespace std;

int n;

vector<int> get(vector<int> s,int tag)

{

    vector<int> ans;

    int sum=0;

    for(int i=0;i<n;++i) sum+=s[i];

    while(s[0]!=sum)

    {

        int p=1;

        while(!s[p]) ++p;

        if(!tag) ans.push_back(p);

        else ans.push_back((p+s[p])%n+n);

        int cur=s[p]; s[p]=0;

        p=(p+1)%n;

        while(cur) ++s[p],--cur,p=(p+1)%n;

    }

    return ans;

}

class ReverseMancala

{

public:

    vector<int> findMoves(vector<int> S,vector<int> T)

    {

        n=(int)S.size();

        vector<int> p=get(S,0);

        vector<int> q=get(T,1);

        for(int i=(int)q.size()-1;i>=0;--i) p.push_back(q[i]);

        return p;

    }

};

巴特西

topcoder srm 710 div1 -23

最新文章

热门文章