假设我们能维护出最终序列的长度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'！|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#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; } |