A.
考场上SB了，一个小细节写挂以为自己思路错误，直接就给弃了。
点击查看代码
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#warning fastread!
using namespace std;
const int N = 1E5 + 10,M = N, S = 2E6+10, TR = 4 * S, Q = N;
struct segment_tree{
struct node{
int sum;
}tree[TR];
void push_up(int rt){
tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void update(int rt, int v){
tree[rt].sum += v;
}
void add(int rt, int l, int r, int s, int v){
if(l >= r){
assert(l == s);
return update(rt, v);
}
int mid = (l + r) >> 1;
if(s <= mid) add(rt<<1, l, mid, s, v);
if(s > mid) add(rt<<1|1, mid + 1, r, s, v);
push_up(rt);
}
int kth(int rt, int l, int r, int k){
assert(k <= tree[rt].sum);
if(l >= r){
assert(tree[rt].sum >= 1);
return l;
}
int mid = (l + r) >> 1;
if(k <= tree[rt<<1].sum)
return kth(rt<<1, l, mid, k);
else
return kth(rt<<1|1, mid + 1, r, k - tree[rt<<1].sum);
}
int rank(int rt, int l, int r, int s){ // <= 的元素个数
if(l >= r){
return tree[rt].sum;
}
int mid = (l + r) >> 1;
if(s <= mid)
return rank(rt<<1, l, mid, s);
else
return tree[rt<<1].sum + rank(rt<<1|1, mid + 1, r, s);
}
}segt;
struct segment_tree_2{
struct node{
int mn, laz;
}tree[TR];
void update(int rt, int val){
tree[rt].mn += val;
tree[rt].laz+= val;
}
void push_down(int rt){
if(tree[rt].laz != 0){
update(rt<<1, tree[rt].laz);
update(rt<<1|1, tree[rt].laz);
tree[rt].laz = 0;
}
}
void push_up(int rt){
tree[rt].mn = min(tree[rt<<1].mn, tree[rt<<1|1].mn);
}
void modify(int rt, int l, int r, int s, int t, int val){
if(s <=l && r <= t){
return update(rt, val);
}
int mid = (l + r) >> 1;
push_down(rt);
if(s <= mid)
modify(rt<<1, l, mid ,s ,t, val);
if(t > mid)
modify(rt<<1|1, mid + 1, r, s, t, val);
push_up(rt);
}
int query(){
return tree[1].mn;
}
}bit;
vector<int> add[N];
int disc[S];
int a[N];
int myrk[M];
int sum[M];
int n, m, q;
struct t_q{
int x, y, z;
}que[Q];
void prtrk(){
cerr<<"rank = " << endl;
for(int i = 1; i <= m; ++i){
cerr<<myrk[i] <<" ";
}
cerr<<endl;
}
void reviewdata(){
for(int i = 1; i <= n; ++i){
cerr<< a[i] <<" ";
}
cerr<<endl;
for(int i = 1; i <= m; ++i){
cerr<<add[i].size() <<" ";
for(int j = 0; j < add[i].size(); ++j){
cerr<<add[i][j] <<" ";
}
cerr<<endl;
}
for(int i = 1; i <= q; ++i){
cerr<<que[i].x <<" " << que[i].y <<" " << que[i].z <<endl;
}
cerr<<endl;
}
int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
do{x = x * 10 + ch -'0', ch = getchar();} while(isdigit(ch));
return x;
}
int main(){
n = read(), m = read(), q = read();
for(int i = 1; i <= n; ++i) a[i] = read(), disc[++disc[0]] = a[i];
for(int i = 1; i <= m; ++i){
int x;
x = read();
for(int j = 1; j <= x; ++j){
int y;
y = read();
add[i].push_back(y);
disc[++disc[0]] = y;
}
}
for(int i = 1; i <= q; ++i){
int x, y, z;
x = read(), y = read(), z = read();
--y;
que[i] = {x, y, z};
disc[++disc[0]] = z;
}
sort(disc + 1, disc + 1 + disc[0]);
disc[0] = unique(disc + 1, disc + 1 + disc[0]) - disc - 1;
for(int i = 1; i <= n; ++i){
a[i] = lower_bound(disc + 1, disc + 1 + disc[0], a[i]) - disc;
}
for(int i = 1; i <= m; ++i){
for(int j = 0; j < add[i].size(); ++j){
add[i][j] = lower_bound(disc + 1, disc + 1 + disc[0], add[i][j]) - disc;
}
sum[i] = sum[i - 1] + add[i].size();
}
for(int i = 1; i<= q; ++i){
que[i].z = lower_bound(disc + 1, disc + 1 + disc[0], que[i].z) - disc;
}
int rk = 0;
for(int i = 2; i <= n; ++i){
// segt.add(1, 1, disc[0], a[i], 1);
if(a[i] < a[1]) ++ rk;
}
for(int i = 1; i <= m; ++i){
myrk[i] = rk - sum[i];
for(int j = 0; j < add[i].size(); ++j){
// segt.add(1, 1, disc[0], add[i][j], 1);
if(add[i][j] < a[1]) ++rk;
}
}
for(int i = 1; i <= m; ++i)
bit.modify(1, 1, m, i, i, myrk[i]);
bool curans = true;
curans = bit.query() >= 0;
for(int i = 1; i <= q; ++i){
int x = que[i].x, y = que[i].y, z = que[i].z;
if((add[x][y] < a[1] && z < a[1]) || (add[x][y] > a[1] &&z > a[1])){
} else if(add[x][y] < a[1] && z > a[1]){
bit.modify(1, 1, m, x + 1, m, -1);
curans = bit.query() >= 0;
}else{
assert(add[x][y] > a[1] && z < a[1]);
bit.modify(1, 1, m, x + 1, m, 1);
curans = bit.query() >= 0;
}
add[x][y] = z;
printf("%d\n", (int)curans);
}
return 0;
}
B.连续段形预设DP
\(f(i, j)\)表示 选了\(i\)个数字，段数为\(j\)，每次考虑往里面加入连续段或者合并连续段或者延伸连续段
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400+10;
ll f[N][N];
int n;
ll mod;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> mod;
f[0][0] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
f[i][j] = (f[i][j] + f[i - 1][j - 1] * j % mod) % mod;
f[i][j] = (f[i][j] + f[i - 1][j] * 2 * j % mod) % mod;
if(i >= 2) f[i][j] = (f[i][j] + f[i - 2][j] * 2 * j % mod) % mod;
if(i >= 2) f[i][j] = (f[i][j] + f[i - 2][j + 1] * j * 2 %mod) % mod;
if(i >= 3) f[i][j] = (f[i][j] + f[i - 3][j + 1] * j% mod) % mod;
}
}
cout <<f[n][1] << endl;
return 0;
}
C暴力的平均复杂度\(O(2^n)\)，没有卡，直接水过去了
D 构造题
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
char str[N];
bool mp[N][N];
int n;
struct DSU{
int fa[N], mx[N], mn[N], siz[N];
void init(int len){
for(int i = 1; i <= len; ++i) fa[i] = i, siz[i] = 1, mn[i] = i, mx[i] = i;
}
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
fa[y] = x;
mn[x] = min(mn[x], mn[y]);
mx[x] = max(mx[x], mx[y]);
}
int gmax(int u){
return mx[find(u)];
}
int gmin(int u){
return mn[find(u)];
}
}un;
void solve(int l, int r){
// cerr<<"enter " << endl;
vector<int> v;
for(int i = l; i <= r; i = un.gmax(i) + 1) v.push_back(i);
for(int i = 1; i < v.size(); ++i) un.merge(v.front(), v[i]);
assert(v.size() > 3);
cout << v.front() <<" " << v.back() <<endl;
cout << v[1] <<" " << v.back() <<endl;
for(int i = 2; i + 1 < v.size(); ++i){
cout << v.front() << " "<< v[i] <<endl;
}
// cerr<<"out " << endl;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> (str + 1);
for(int j = i, k = 1; j <= n; ++j, ++k){
mp[i][j] = str[k] - '0';
}
}
// cerr<<"!"<<endl;
un.init(n);
for(int d = 2; d <= n; ++ d){
for(int i = 1, j = i + d - 1; j <= n; ++i, ++j){
if(mp[i][j] == 0) continue;
if(un.find(i) == un.find(j)) continue;
// cerr<<"i, j" << i <<" " << j << endl;
if(un.gmax(i) + 1 == un.gmin(j)){
cout << i <<" " << j << endl;
un.merge(i, j);
}else solve(i, j);
}
}
return 0;
}