求助,不知道这样为什么就错了
查看原帖
求助,不知道这样为什么就错了
237530
rzh123楼主2022/11/8 18:51
#include <bits/stdc++.h>
#define gc IO::fastgc()
#define pc(c) IO::fastpc(c)
typedef long long ll;
typedef long long unsigned llu, ull;
typedef long double lf;
namespace IO {
	char ibuf[1 << 23], obuf[1 << 23], *ip1 = ibuf, *ip2 = ibuf, *o = obuf;
	inline char fastgc() {
		return ((ip1 == ip2) && (ip2 = (ip1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), ip1 == ip2) ? EOF : *ip1++);
	}
	inline void fastpc(char c) {
		*(o++) = c;
	}
	inline ll read() {
		register ll t = 0, f = 1;
		register char c = gc;
		while (c != '-' && (c < '0' || c > '9')) c = gc;
		if (c == '-')
			c = gc, f = -1;
		while (c >= '0' && c <= '9') t = 10 * t + (c ^ 48), c = gc;
		return f * t;
	}
	inline void write(ll x) {
		if (!x)
			return (void)pc('0');
		if (x < 0)
			pc('-'), x = -x;
		static char c[33] = { "" };
		static int cc = 0;
		while (x) c[++cc] = x % 10, x /= 10;
		while (cc) pc(c[cc--] | 48);
	}
	inline void flush() {
		fwrite(obuf, o - obuf, 1, stdout);
	}
	struct _ {
		inline _() {}
		inline ~_() {
			flush();
		}
	} __;
}  // namespace IO
using IO::read;
using IO::write;
using namespace std;
constexpr unsigned N = 1e5 + 7;
ll n, m, kk, a[N], bc;
ll len;
struct Block {
	ll v, l;
} b[N], bb[N];
signed main() {
	int l, r;
	n = read(), kk = read(), m = read();
	for (int i{ 1 }; i <= n; ++i) {
        a[i] = read();
        if (i == 1 || a[i] != b[bc].v) {
            if (bc) {
                b[bc].l %= kk;
                if (!b[bc].l)
                    --bc;			//这就错了 
            }
            b[++bc] = { (int)a[i], 1ll };
        } else {
            ++b[bc].l;
//            b[bc].l%=kk; 
//            if(!b[bc].l)
//            	--bc;			//这就对了 
        }
    }
    if (bc) {
        b[bc].l %= kk;
        if (!b[bc].l)
            --bc;
    }
    for (int i{ 1 }; i <= bc; ++i) {
        bb[i] = b[i];
        len += b[i].l;
    }
    len *= m;
	l = 1, r = bc;
	for (; l < r; ++l, --r) {
		if (l >= r)
			break;
		if (b[l].v == b[r].v) {
			ll l1 = b[l].l, l2 = b[r].l;
			ll c = l1 + l2;
			len -= (c - c % kk) * (m - 1ll);
			if (c % kk)
				break;
		} else {
			break;
		}
	}
	if (l == r) {
		ll lt = b[l].l * m;
		len -= lt / kk * kk;
		if (!(lt % kk)) {
			for (int i { 1 }; i <= bc; ++i) {
				b[i] = bb[i];
			}
			while (1) {
				--l, ++r;
				if (l < 1)
					break;
				if (b[l].v == b[r].v) {
					ll l1 = b[l].l, l2 = b[r].l;
					ll c = l1 + l2;
					len -= c - c % kk;
					if (c % kk)
						break;
				} else {
					break;
				}
			}
		}
	}
	write(len);
	return 0;
}

思路就是把 a1ana_1\cdots a_n 划分成连续相同的段,但是划分的时候不知道为什么错了(见注释)。

2022/11/8 18:51
加载中...