神了，网络赛真神了。
2026 ICPC 网络赛(Ⅰ)
准备补 A、J、N
C. Permutation Inversions
题意
求解一个排列。满足 m 个要求，每个要求是：排列中在[l,r]区间的数字，满足给定的大小关系，大小关系用一个长度为[r-l+1]的排列表示。求逆序对个数最小的解。
做法
可以想到，不考虑逆序对最少，可以使用建图+拓扑排序求解。每一个要求中编号小的位置往编号大的数字建边。得到解再转换一下。如果无法拓扑排序说明无解。但是怎么找到最优解呢？ 我们很容易找到字典序最小的解，怎么证明此题中，字典序最小就是逆序对最少呢？
首先我们拿来拓扑排序的元素是答案排列的“编号”，编号越小的越靠前，感觉上来说解更优。
针对这道题。假设当前入度为 0 的最小元素为 'x'，假设我们选一个同样入度为 0 的元素 'y'，有 y > x。最后得到的合法拓扑序中 y 和 x 之间一定没有小于 x 的元素。
反证，假设 y 和 x 之间有一个 z < x。那么，位置是：y, z, x，满足 z < x < y。
这说明，肯定有一个要求覆盖了 [z, y]。那么就不可能在 x 入度为 0 的同时，y 也入度为 0。他们一定不是同一层的。
所以，当我们先选 'y' (y > x)，假设 y 和 x 之间有 k-1 个数，那么这样就增加了 k 个逆序对。所以我们每次选最小的元素，一定是最优解。如果不这样，逆序对个数会增加。
点击查看代码#include
using namespace std; int T, n, m;
int in[1000006], ans[1000006];
vector vec[1000006];
struct compare {bool operator()(int a, int b) {return a > b; }
};
int main() {cin >> T; while(T --) {cin >> n >> m; map, int> mp; for(int i = 0; i < m; i ++) {int l, r; cin >> l >> r;int u = -1, v = 0; for(int j = l; j <= r; j++) {cin >> v; if(u == -1) {u = v; continue; }if(mp[{u, v}]) {u = v; continue; }mp[{u, v}] = 1; vec[u].push_back(v); in[v] ++; u = v; }} //buildpriority_queue, compare> q; for(int i = 1; i <= n; i++) {if(in[i] == 0) q.push(i); }int cnt = 1; int flag = q.empty(); while(!q.empty()) {int top = q.top(); q.pop(); ans[top] = cnt; cnt ++; for(int i = 0; i < vec[top].size(); i++) {int v = vec[top][i]; in[v] --; if(in[v] == 0) q.push(v); }if(cnt == n + 1 && !q.empty()) {flag = 1; break; }}for(int i = 1; i <= n; i++) {vec[i].clear(); in[i] = 0; }if(flag || cnt != n + 1) {cout << -1 << endl; continue; }for(int i = 1; i <= n; i++) {cout << ans[i] << ' '; }cout << endl; }return 0;
}
A. Recall
题意
略，，
做法
在每个数最后一次要用的时候把它删掉。默认 + x 后立刻删掉，如果有 T x ，那么到最后的一次 T x 删掉。记录完之后，再遍历一遍，用栈模拟一次，如果当前栈顶应该删掉的位置，<= 在遍历到的位置，那么就删。除此以外不能删。以防万一，最后剩余的都删掉。
#include
using namespace std; int T;
int n, need[1000006], op[1000006], in[1000006]; int main() {cin >> T;while(T --) {cin >> n; map last; for(int i = 0; i < n; i ++) {char ch; cin >> ch; cin >> in[i]; int x = in[i]; if(ch == '+') {op[i] = 1; last[x] = i; need[i] = i; }if(ch == 'T') {op[i] = 2; need[last[x]] = i; need[i] = i; }}stack > st; for(int i = 0; i < n; i ++) {if(op[i] == 1) {cout << '+'; st.push({i, in[i]}); if(need[i] == i) {cout << '-'; st.pop(); }} else if(op[i] == 0) {cout << '?'; } else {cout << '?'; // cout << st.size() << endl; int id = st.top().first; int x = st.top().second; while(st.size() && need[id] <= i) {st.pop(); cout << '-'; if(st.size()) {id = st.top().first; x = st.top().second; }}}}while(st.size()) {cout << '-'; st.pop(); }cout << endl; for(int i = 0; i <= n; i++) {need[i] = op[i] = in[i] = 0; }}return 0;
}
J. String
题意
给你一个只带 H 或 N 的字符串。\(T\) 次操作。每次操作给定三个参数：\(op_i, p_i, k_i\)，表示第 \(i\) 次操作，方式是 \(op\)，起始位置 \(p\)，重复 \(k\) 次。
做法
通过暴力模拟可以发现，实际上这道题可以转换成二进制高精度加减法问题。有的是正常加，有的是把整个数字翻转过来加。
1.0 可以单独设置一个数组，记录翻转过来的运算，最后再翻转加到原数组里。唉，高精度。我记得大一上的程序设计大作业，就包含有高精度加减法。当时犯懒用 Claude 写了，赛场上被反噬了，短时间内根本写不出来……
2.0 写了半天高精度的我宛如一个小丑。OK啊完全想错了，根本不能先翻转过来然后最后再加，因为翻转加的结果也会影响当前结果，下一次操作的结果更是依托于当前结果。而且翻转加根本就不能等同于加。gpt告诉我用线段树。我去我不会。有没有不用线段树的做法？翔哥告诉我可以用bitset直接模拟。查了一下，利用异或运算和与运算可以模拟加法，试一下。
仍然一筹莫展……待会再写。
3.0 我们可以只直接处理位置 p 左/右 60 位的数。再往外只有 +1 或是 -1 的进位。+1 等同于找到离当前最近的一位 0，中间的 1 全部赋值为 0，那个 0 赋值为 1。-1 反之。那这样的话不就还是需要线段树吗，呵呵。 如果60个数字一组的话，我们可以轻松知道每个组 1 的个数、0的个数。这样的话可以很快速地改变。
凭借快 200 行的屎山居然真过了。这期神了。
点击查看代码#include
#include
using namespace std; int n, T;
string S; long long bl[2000], tmp[100005];
long long allOne = (1ll << 60)-1; void addOne(int op, int p) {// op : 1 2 -> p + 60// op : 3 4 -> p - 60int find = -1; // op & 1 -> +1 -> nearest 0// else -> -1 -> nearest 1if(op == 1) {int i = p + 60; for( ; i < n && i % 60 != 0; i++) {if(bl[i/60] & tmp[i]) {bl[i/60] &= (~tmp[i]); continue; }find = i; break; }while(find < 0 && i < n) {if(bl[i/60] == allOne) {bl[i/60] ^= allOne; i += 60; continue; }for( ; i < n; i ++) {if(bl[i/60] & tmp[i]) {bl[i/60] &= (~tmp[i]); continue; }find = i; break; }}if(find >= 0) {bl[find/60] |= tmp[find]; }} else if(op == 2) {int i = p + 60; for( ; i < n && i % 60 != 0; i++) {if(bl[i/60] & tmp[i]) {find = i; break; }bl[i/60] |= tmp[i]; continue; }while(find < 0 && i < n) {if(bl[i/60] == 0) {bl[i/60] ^= allOne; i += 60; continue; }for( ; i < n; i ++) {if(bl[i/60] & tmp[i]) {find = i; break; }bl[i/60] |= tmp[i]; continue; }}if(find >= 0) {bl[find/60] &= (~tmp[find]); }} else if(op == 3) {int i = p - 60; for( ; i >= 0 && i % 60 != 59; i--) {if(bl[i/60] & tmp[i]) {bl[i/60] &= (~tmp[i]); continue; }find = i; break; }while(find < 0 && i >= 0) {if(bl[i/60] == allOne) {bl[i/60] ^= allOne; i -= 60; continue; }for( ; i >= 0; i --) {if(bl[i/60] & tmp[i]) {bl[i/60] &= (~tmp[i]); continue; }find = i; break; }}if(find >= 0) {bl[find/60] |= tmp[find]; }} else {int i = p - 60; for( ; i >= 0 && i % 60 != 59; i--) {if(bl[i/60] & tmp[i]) {find = i; break; }bl[i/60] |= tmp[i]; continue; }while(find < 0 && i >= 0) {if(bl[i/60] == 0) {bl[i/60] ^= allOne; i -= 60; continue; }for( ; i >= 0; i --) {if(bl[i/60] & tmp[i]) {find = i; break; }bl[i/60] |= tmp[i]; continue; }}if(find >= 0) {bl[find/60] &= (~tmp[find]); }}
}void add(int op, int p, long long k) {long long origin = 0, one; if(op <= 2) {for(int i = p; i < p+60 && i < n; i++) {one = (1ll << (i-p)); if(bl[i/60] & tmp[i]) origin |= one; }} else {for(int i = p; i > p-60 && i >= 0; i--) {one = (1ll << (p-i)); if(bl[i/60] & tmp[i]) origin |= one; }}// cout << origin << " ori" << endl; if(op & 1) origin += k; else origin -= k; int flag = (origin >= (1ll << 60)) || (origin < 0); if(origin < 0) origin += (1ll << 60); origin %= (1ll << 60); if(op <= 2) {for(int i = p; i < p+60 && i < n; i++) {int ch = origin & 1; bl[i/60] &= ~tmp[i]; if(ch) bl[i/60] |= tmp[i]; origin >>= 1; }} else {for(int i = p; i >= 0 && i > p-60; i--) {int ch = origin & 1; bl[i/60] &= ~tmp[i]; if(ch) bl[i/60] |= tmp[i]; origin >>= 1; }}if(flag) {addOne(op, p); }
}int main() {cin >> n >> T; cin >> S; for(int i = 0; i < n; i ++) {tmp[i] = (1ll << (59 - i%60));if(S[i] == 'H') bl[i/60] |= tmp[i];}while(T --) {int op, p; long long k; cin >> op >> p >> k; p--; add(op, p, k); }for(int i = 0; i < n; i++) {if(bl[i/60] & tmp[i]) cout << 'H'; else cout << 'N'; }cout << endl; return 0;
}