假设我们能维护出最终序列的长度L和最终序列出现最多的数的个数cnt，假设$cnt\leq\frac L 2$ ，那么答案是L,这时候我们把序列升序和降序对起来就构造出n的结果。
假设$cnt>\frac L 2$,那么答案是$2(L-cnt)$，我们仍然把序列升序和降序对应起来，答案是$L-(cnt-(L-cnt))=2*(L-cnt)$
比如
“`
1 2 3 3 3 3 3
3 3 3 3 3 2 1
“`
中间有3个3是重了的，那么重的部分有cnt-(L-cnt)个，其中L-cnt表示的是`1 2`的长度，所以总答案是L-(cnt-(L-cnt))
现在的问题在于如何维护出这个众数，并且判定$cnt\leq \frac L 2$是否成立。
考虑一种线性时间求求序列众数(出现次数大于一半)的方法：
令f(i)表示我们从头开始扫到第i个元素的时候(用$a_i$表示)，序列中出现次数最多的数与其他的数出现次数之和的差值。同时我们需要维护这个数是多少(用x来表示)。
每次扫到$a_i$的时候:
– 如果$a_i=x$，那么f(i)=f(i-1)+1,x不变
– 如果$a_i\neq x$,那么f(i)=f(i-1)-1，然后如果$f(i)<0$,那么x变为$a_i$，同时$f(i)$取反。
对于这个题，如果我们要使用这种求众数的方法，核心在于如何考虑操作2（合并两个序列时）如何处理。
我们维护每个序列的f和x，合并两个序列的时候：
– 如果他们的f相同，那么新序列的f不变，x相加。
– 如果他们的f不同，那么考虑下两个序列的哪一个的x比较大。如果他们相同，那么新序列的f就写为0(这时候可能存在两个众数)，x从原来的x里随便选一个。如果他们不同，那x选择为f较大的那一个，同时f设置为较大值减掉较小值。
所以对于这个题，我们先用这种求众数的方法算出来最终序列的众数。
但此时求出来的众数，仅仅是在保证`存在一个出现次数超过序列长度一半时候`的众数，如果不存在这样子的众数，也会得出来一个结果，但是并不具有意义。
所以我们再跑一遍递推，求出来我们上一步求的众数的出现次数，然后我们就可以照着前文所述来算答案了。
*此外，这个题卡常*
我跑了半天性能分析后大概知道了几个卡常的点:
1. 输入量非常巨大，请考虑一次性读入输入数据后自行用缓冲区处理输入。
2. `std::vector`的构造函数非常慢(性能分析显示,$10^6$次调用大约花了80ms)，所以不要使用vector来存储变长的序列，考虑自行分配-回收内存。
3. `State`结构体的构造函数占了大概40ms的时间，考虑强制内联。
另外，读入函数千万不要写错了！不要写成`chr>=’9’`！
#pragma GCC optimize("O2")
#include <assert.h>
#include <inttypes.h>
#include <algorithm>
#include <iostream>
#include <vector>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6;
char inputbuf[(int(2e8) / 1024) * 1024];
char* head = inputbuf;
inline char nextchar() {
return *(head++);
}
void initinput() {
fread(inputbuf, 1024, sizeof(inputbuf) / 1024, stdin);
}
struct State {
int64_t len;
int_t mostval;
int64_t mostcount;
inline State(int64_t len = 0, int_t mostval = 0, int64_t mostcount = 0)
: len(len), mostval(mostval), mostcount(mostcount) {}
State operator+(const State& rhs) const {
State result(len + rhs.len, 0, 0);
if (mostval == rhs.mostval)
result.mostval = mostval,
result.mostcount = mostcount + rhs.mostcount;
else {
if (mostcount > rhs.mostcount) {
result.mostcount = mostcount - rhs.mostcount;
result.mostval = mostval;
} else {
result.mostcount = rhs.mostcount - mostcount;
result.mostval = rhs.mostval;
}
}
return result;
}
};
std::ostream& operator<<(std::ostream& os, const State& state) {
os << "State{len=" << state.len << ",mostval=" << state.mostval
<< ",mostcount=" << state.mostcount << "}";
return os;
}
struct Opt {
int_t type;
int_t* data;
int_t datalen;
int_t x1, x2;
int64_t mostcount = 0;
} opts[LARGE + 1];
State dp[LARGE + 1];
int_t n;
template <class T>
void read(T& x) {
x = 0;
char chr = nextchar();
while (chr < '0' || chr > '9')
chr = nextchar();
while (chr >= '0' && chr <= '9') {
x = x * 10 + chr - '0';
chr = nextchar();
}
assert(x >= 0);
}
template <class T>
void write(T x) {
assert(x >= 0);
if (x > 9)
write(x / 10);
putchar('0' + x % 10);
}
int main() {
// freopen("input.txt", "r", stdin);
initinput();
int_t T;
read(T);
while (T--) {
read(n);
for (int_t i = 1; i <= n; i++) {
auto& ref = opts[i];
if (ref.data) {
delete[] ref.data;
ref.data = nullptr;
}
dp[i] = State();
read(ref.type);
if (ref.type == 1) {
int_t k;
read(k);
int_t sum = 0, val = 0;
ref.data = new int_t[k + 1];
ref.datalen = k;
for (int_t i = 1; i <= k; i++) {
int_t x;
read(x);
ref.data[i] = x;
if (x == val)
sum++;
else
sum--;
if (sum < 0) {
sum *= -1, val = x;
}
}
// ref.seq.shrink_to_fit();
dp[i] = State(k, val, sum);
} else {
read(ref.x1);
read(ref.x2);
}
}
for (int_t i = 1; i <= n; i++) {
const auto& ref1 = opts[i];
if (ref1.type == 2) {
dp[i] = dp[ref1.x1] + dp[ref1.x2];
}
}
#ifdef DEBUG
for (int_t i = 1; i <= n; i++) {
cout << "dp " << i << " = " << dp[i] << endl;
}
#endif
int_t mostval = dp[n].mostval;
for (int_t i = 1; i <= n; i++) {
auto& ref = opts[i];
if (ref.type == 1)
ref.mostcount = std::count(ref.data + 1,
ref.data + 1 + ref.datalen, mostval);
else
ref.mostcount = opts[ref.x1].mostcount + opts[ref.x2].mostcount;
}
int64_t mostcount = opts[n].mostcount;
#ifdef DEBUG
cout << "final len " << dp[n].len << endl;
cout << "mostcount " << mostcount << endl;
cout << "mostval " << mostval << endl;
#endif
if (mostcount * 2 <= dp[n].len) {
write(dp[n].len);
} else {
write(2 * (dp[n].len - mostcount));
}
puts("");
}
return 0;
}
发表回复