【Codeforces】879D. Teams Formation 思维+模拟

题意

给定$n$个数，重复拼接$m$次，相邻$k$个重复的可消除，问最后序列中有多少个数

首先可以发现当$k>=n$时，如果要使$n$个数可以被消除，那么$n$个数必须一样，否则$n$个数不能被消除

当$k<n$时，首先对序列能够消除的消除，用栈记录每个数和这个数的相同的相邻个数$f$，将序列压缩，考虑一次拼接，记$L$为第二个序列的开始元素，$R$为第一个序列的最后一个元素，如果$L!=R$那么所有序列将不能压缩，如果$LR,f_L+f_R!=k$，那么这两个序列拼接之后会合并成一个不可被消去的元素，减去$m-1$次的贡献得到答案，如果$LR,f_L+f_R==k$，那么这两个可以完全被消除，那么按照相同方式计算$L+1,R-1$对应的贡献，最后如果整个序列都能合并到最后，如果$n$为奇数，表示最后会剩下一个元素，计算这个元素对应答案，如果$n$为偶数，那么答案为$0$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int st[100100], f[100100];

int n, k, m, a, flag = 0, top = 1;

LL ans = 0;

int main() {

    scanf("%d%d%d", &n, &k, &m);

    st[0] = 0;

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

        scanf("%d", &a);

        if(st[top - 1] != a) st[top] = a, f[top++] = 1;

        else  {

            if(f[top - 1] + 1 < k) f[top - 1] += 1;

            else if(f[top - 1] + 1 == k)  top--;

        }

    }

    if(k >= n) {

        for(int i = 1; i < top - 1; ++i) if(st[i] != st[i + 1]) flag = 1;

        if(!flag) cout << 1LL * n * m % k << endl; else cout << 1LL * n * m << endl;

        return 0;

    }

    for(int i = 1; i < top; ++i) ans += f[i];

    if(m == 1 || ans == 0) {cout << ans << endl; return 0;}

    ans = 1LL * m * ans;

    int L = 1, R = top - 1;

    while(L < R) {

        if(st[L] != st[R]) {cout << ans << endl; return 0;}

        if(f[L] + f[R] == k) {L++; R--;ans -= 1LL * (m - 1) * k; continue;}

        if(f[L] + f[R] > k) ans -= 1LL * (m - 1) * k;

        cout << ans << endl; return 0;

    }

    if(L > R) {cout << 0 << endl; return 0;}

    if(L == R) {

        LL x = 1LL * f[L] * m;

        if(x % k == 0) {cout << 0 << endl;}

        else {cout << ans - x / (LL)k * (LL)k << endl;}

    }

    return 0;

}

巴特西

【Codeforces】879D. Teams Formation 思维+模拟

题意

代码

最新文章

热门文章