cf 443 D. Teams Formation(细节模拟题)

题意：

给出一个长为\(n\)的序列,重复\(m\)次形成一个新的序列,动态消除所有k个连续相同的数字，问最后会剩下多少个数(题目保证消除的顺序对答案不会造成影响)

\(n <= 10^{5} ,m <= 10^{9} ,k <= 10^{9},a_i <= 10^{5}\)

思路：

直接上题解好了

首先要用栈预处理序列本身，然后考虑处理后的序列

比较头和尾是否能够消除，细节需要处理好。

#include<bits/stdc++.h>

#define P pair<int,int>

#define LL long long

using namespace std;

const int N = 1e5 + 10;

P st[N];

int main(){

   int x,n,k,m;

   while(cin>>n>>k>>m){

    int top = 0;

    for(int i = 1;i <= n;i++){

        scanf("%d",&x);

        if(top && x == st[top].first) st[top].second++;

        else st[++top].first = x,st[top].second = 1;

        if(st[top].second == k) top--;

    }

    if(top == 1){

        cout<<1LL * st[1].second * m % k<<endl;

        continue;

    }

    int res = 0;

    for(int i = 1;i <= top;i++) res += st[i].second;

    if(m == 1) {

        cout<<res<<endl;

        continue;

    }

    int p = 0;

    for(int i = 1;i <= top - i + 1;i++){

        if(st[i].first != st[top - i + 1].first || st[i].second + st[top - i + 1].second != k) break;

        p = i;

    }

    if(p >= top - top / 2) { ///超过一半，全消除的情况

        if(m % 2 == 0) cout<<0<<endl;

        else cout<<res<<endl;

    }else{

        if(top % 2 == 0 || p != top / 2) {

            LL dec = p * k;

            if(st[p+1].first == st[top - p].first) dec += st[p+1].second + st[top - p].second - (st[p+1].second + st[top - p].second)%k;

            cout<<1LL * m * res - (m - 1) * dec<<endl;

        }

        else if(p == top / 2){

            if(1LL * m * st[p + 1].second % k == 0) cout<<0<<endl;

            else {

                res = 0;

                for(int i = 1;i <= p;i++) res += st[i].second + st[top - i + 1].second;

                cout<<res + 1LL * m * st[p + 1].second % k <<endl;

            }

        }

    }

   }

   return 0;

}