ZR2423

一个第一次见到的套路：我们考虑转化一下两个儿子都走这个选择，我们可以考虑建第三个儿子，它的子树中的每个节点的权值等于之前两个儿子对应权值的异或和，则显然，如果接下来没有选择两个儿子都走的话，走第三个儿子正确性是显然的，如果又选择了两个儿子都走，那么就可以对于某个节点再建第三个儿子。

综上，我们可以把二叉树扩展成三叉树，这样第三个选择就变成了走第三个儿子，DP 算出 $f_{k,0/1}$ 表示 $k$ 结点往下先手能否得到 $0$ 和 $1$，即偶数或者是奇数，转移就考虑假设 $a_k=0$，如果 $k$ 想得到 $0$，至少有一个儿子得不到 $1$。$a_k=1$ 同理。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 20000010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int ch[N][3],ans[N][2],n,a[N],rt,tot;
bool vis[N];

inline void add(int x,int y,int z){
    a[z]=a[x]^a[y];
    if(!ch[x][0]) return;
    ch[z][0]=++tot;ch[z][1]=++tot;
    add(ch[x][0],ch[y][0],ch[z][0]);
    add(ch[x][1],ch[y][1],ch[z][1]);
}
inline void build(int k){
    ch[k][2]=++tot;
    add(ch[k][0],ch[k][1],ch[k][2]);
    if(!ch[k][0]) return;
    build(ch[k][0]);build(ch[k][1]);build(ch[k][2]);
}
inline void dfs(int k){
    if(!ch[k][0]){
        if(a[k]) ans[k][1]=1;
        else ans[k][0]=1;
        return;
    }
    dfs(ch[k][0]);dfs(ch[k][1]);dfs(ch[k][2]);
    rep(i,0,2) ans[k][0]|=(ans[ch[k][i]][1]==0);
    rep(i,0,2) ans[k][1]|=(ans[ch[k][i]][0]==0);
    if(a[k]) swap(ans[k][0],ans[k][1]);
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);tot=n;
    rep(i,1,n){
        int l,r,c;read(l);read(r);read(c);
        vis[l]=vis[r]=1;a[i]=c;
        ch[i][0]=l;ch[i][1]=r;
    }
    rep(i,1,n) if(!vis[i]){rt=i;break;}
    build(rt);dfs(rt);
    rep(i,1,n){
        if(ans[i][0]) puts("Alice");
        else puts("Bob");
    }
}

ZR2438

考虑 $k=2$，一定是 $aabaa$，考虑 $k=3$，一定是先有一个 $bbcbb$，然后往里尽可能少的插入 $a$，且尽可能字典序最小，使得合法。

我们在最前面放一个 $aa$，然后再每一个 $b$ 后面都放上一个 $a$，在最后放一个 $aa$，然后再每个 $b$ 前面都有一个 $a$，最后只需要保证两个相邻的 $b$ 之间只有一个 $a$，这样显然是最优的，若只看 $a,b$，我们构造出来的答案应该是 $aababababaa$，考虑放 $c$，显然有 $aababacbabaa$。用这种思路可以构造出 $k$ 其余情况，然后考虑每个字母的填的个数是等差数列上升的，可以算出序列长度。然后找输出规律可以简化代码。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N number
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int t,n,Q;

int main(){
    read(t);
    while(t--){
        read(n);read(Q);
        int m=(1+(1+(Q-1)*3))*Q/2;
        if(n<m){puts("-1");continue;}
        if(Q==1){
            rep(i,1,n) putchar('a');
            puts("");
            continue;
        }
        rep(i,m+1,n) putchar('a');
        rep(i,1,Q-1){
            dec(j,0,i-1) putchar('a'+j);
            dec(j,0,i-1) putchar('a'+j);
        }
        putchar('a'+Q-1);
        dec(j,0,Q-2) putchar('a'+j);
        dec(i,1,Q-1){
            dec(j,0,i-1) putchar('a'+j);
        }
        puts("");
    }
    return 0;
}

ZR2440

考虑一个 DP，设 dfs(k,v1,v2,s) 表示目前填到了 $k$，并且 $k$ 填在点 $v1$ 上，$k-1$ 填在点 $v2$ 上，目前填过数的点为 $s$，发现这个加个记忆化就过了。

转移的话暴力枚举下一个数填在哪里即可。

为什么？因为其实所有合法的状态是在可接受范围内。首先填完 $k+1$ 之后必须要满足 $v2$ 被填完，并且这个状态必须满足把整棵树中的 $v1,v2$ 删掉之后，其余的连通块，要么都填上数了，要么都没填。因为每个点的度数最多为 $4$，所以复杂度为 $n^32^7$。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 61
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n;
vi e[N];
bool vis[N];
unordered_map<int,int> f[N][N][N];

inline bool Dfs(int s,int k,int fat){
    for(int to:e[k]){
        if(to==fat||vis[to]==1) continue;
        if(!Dfs(s,to,k)) return 0;
        if(fat!=0){
            if(((s>>(to-1))&1)!=((s>>(k-1))&1)) return 0;
        }
    }
    return 1;
}

inline bool chk(int s,int a,int b){
    vis[a]=1;vis[b]=1;
    if(!Dfs(s,a,0)){
        // printf("a=%d BAN\n",a);
        return 0;
    }
    if(!Dfs(s,b,0)){
        // printf("b=%d BAN\n",b);
        return 0;
    }
    vis[a]=0;vis[b]=0;
    return 1;
}

//v1 is k, v2 is k-1
//s is used
inline int dfs(int k,int v1,int v2,int s){
    // printf("Enter: k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
    if(k==n){
        // printf("k=%d\n",k);
        return 1;
    }
    // puts("Here");
    if(f[k][v1][v2].find(s)!=f[k][v1][v2].end()) return f[k][v1][v2][s];
    // puts("Here");
    // f[k][v1][v2][s]=0;
    int &ans=f[k][v1][v2][s];
    ans=0;
    // puts("Here");
    if(v1&&v2&&!chk(s,v1,v2)){
        ans=0;
        // printf("chk no k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
        return 0;
    }
    // puts("Here");
    if(v2==0){
        rep(i,0,n-1){
            if((s>>i)&1) continue;
            int nw=i+1;
            ans=(ans+dfs(k+1,nw,v1,s|(1ll<<i)))%mod;
        }
    }
    else{
        int cnt=0,id=-1;
        for(int to:e[v2]){
            if(((s>>(to-1))&1)==0){
                cnt++;id=to;
            }
        }
        if(cnt>1){
            // printf("cnt>1 k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
            return (ans=0);
        }
        if(cnt==1){
            ans=(ans+dfs(k+1,id,v1,s|(1ll<<(id-1))))%mod;
        }
        else{
            rep(i,0,n-1){
                if((s>>i)&1) continue;
                int nw=i+1;
                ans=(ans+dfs(k+1,nw,v1,s|(1ll<<i)))%mod;
            }
        }
    }
    // printf("End: k=%d v1=%d v2=%d s=%d ans=%d\n",k,v1,v2,s,ans);
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);
    rep(i,1,n-1){
        int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
    }
    int Ans=dfs(0,0,0,0);
    printf("%lld\n",Ans);
    return 0;
}

ZR2370

二分答案，考虑构造出来一个序列是困难的，所以我们不妨想把从原序列删数制止合法。首先显然是把数字从大往小删，如果一个数与它左右相邻的数不合法，那么就删掉，用一个链表来维护删除即可。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 500010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
#define ll long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,K,a[N],L[N],R[N],b[N];

inline void del(int k){
    R[L[k]]=R[k];
    L[R[k]]=L[k];
}
inline bool chk(int mid){
    rep(i,1,n) L[i]=i-1,R[i]=i+1;
    R[n]=1;L[1]=n;
    int tot=n;
    rep(i,1,n){
        int l=L[b[i]],r=R[b[i]];
        if(a[l]+a[b[i]]>mid||a[r]+a[b[i]]>mid) del(b[i]),tot--;
    }
    return tot>=K;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(K);rep(i,1,n) read(a[i]);
    rep(i,1,n) b[i]=i;
    sort(b+1,b+n+1,[&](int i,int j){return a[i]>a[j];});
    ll l=1,r=2e9;
    while(l<r){
        // printf("l=%d r=%d\n",l,r);
        int mid=(l+r)>>1;
        if(chk(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

ZR2446

首先我们可以固定一个左端点，接下来就是选择一个右端点。

容易发现，右端点的选取与一些后缀之间的排序有关，但是这些后缀后面还有可能会接一些东西， 场上一直在想 SA，这就导致了这个题没有思路。

但实际上，后面的那些接上去的东西，一样是字符串的一些后缀，而他们的哈希值都是可以提前预处理出来的，这提示我们可以在 $\log$ 的时间复杂度比较出两个字符串的大小。

ZR2448

首先可以建出括号序，而我们的路径很像是先往祖先走，然后按着兄弟走，然后再往下走，大致这样的一个过程。

于是我们可以预处理出每个点走 $2^i$ 步能够走到的最左边最右边的点是什么。

注意程序中的预处理。这样预处理的正确性可以归纳证明，若 $i-1$ 时的值都是我们想要的，考虑 $i$ 时的值，只需要考虑前 $2^{i-1}$ 步到底是想要走到一个最左边的点，还是最右边的点，由于括号序列的特殊性，如果往左边走，那么走到最左边一定是最优的，如果往右边走，那么走到最右边一定是最优的。

这个证明非常不严谨，但是感受一下应该是对的，目前博主才疏学浅并不能够证明，但是感性理解尽可能往左走和尽可能往右走总有一个是正确的。

由此，我们接下来对于每个询问相当于让 $x,y$ 都走到 $x,y$ 之间的一个任意一个点即可，只要这个点在最优路径上，就可以保证正确性，我们只需要从 $x$ 开始，尽可能往 $y$ 走而不超过 $y$ 即可，然后接下来再让 $y$ 走，这相当于在能走的情况下让 $x$ 走到尽可能往右的点，根据上面的正确性，我们要维护两个值，一个是往左走的最优值，一个是往右走的最优值。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 400010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

char s[N];
int sta[N],top,n,a[N],L[N][21],R[N][21],m;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    rep(i,1,n){
        if(s[i]=='(') sta[++top]=i;
        else{
            a[i]=sta[top];
            a[sta[top]]=i;
            top--;
        }
    }
    rep(i,1,n){
        L[i][0]=max(min(i-1,a[i]),0);
        R[i][0]=min(max(i+1,a[i]),n);
    }
    rep(j,1,20){
        rep(i,1,n){
            L[i][j]=min(L[L[i][j-1]][j-1],L[R[i][j-1]][j-1]);
            R[i][j]=max(R[R[i][j-1]][j-1],R[L[i][j-1]][j-1]);
        }
    }
    read(m);
    rep(i,1,m){
        int x,y;read(x);read(y);
        if(x==y){
            puts("0");continue;
        }
        if(x>y) swap(x,y);
        int l,r;
        l=r=x;
        int ans=0;
        dec(i,0,20){
            int nl=min(L[l][i],L[r][i]);
            int nr=max(R[l][i],R[r][i]);
            if(nr<y){
                l=nl;r=nr;ans+=(1<<i);
            }
        }
        x=r;l=r=y;
        // printf("ans=%d x=%d\n",ans,x);
        dec(i,0,20){
            int nl=min(L[l][i],L[r][i]);
            int nr=max(R[l][i],R[r][i]);
            // printf("i=%d nl=%d nr=%d\n",i,nl,nr);
            if(nl>x){
                l=nl;r=nr;ans+=(1<<i);
            }
        }
        // printf("ans=%d l=%d\n",ans,l);
        ans++;
        printf("%d\n",ans);
    }
    return 0;
}

ZR2457

原题：LOJ 花火

考虑能够作为左端点的值一定是前缀 $\max$ 所在点，能够作为右端点的值一定是后缀 $\min$ 的所在点，而交换这两个点的贡献等价于把 $(i,a_i)$ 放在二维平面上，以 $(l,a_l)$ 作为左上角 $(r,a_r)$ 作为右下角内部矩形的点的个数乘上 $2$ 再加 $1$。

这样一共还是要做 $n^2$ 次矩阵询问，不妨考虑内部一个点能够做贡献的区间，不难发现点 $(i,a_i)$ 能够做贡献的点对对于左端点和右端点都是一段区间，也就是一个矩形，这转化成了 $n$ 个矩形加，求全局最大值。求操作区间需要二分，其余扫描线即可。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 1000100
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,a[N],b[N],c[N];

struct Ques{
    int l,r,v;
    inline Ques(){}
    inline Ques(int l,int r,int v) : l(l),r(r),v(v) {}
};
vc<Ques> q[N];
struct Node{
    int maxx,tag;
}p[N<<2];
struct SegmentTree{
    #define ls(k) k<<1
    #define rs(k) k<<1|1
    inline void pushup(int k){
        p[k].maxx=max(p[ls(k)].maxx,p[rs(k)].maxx);
    }
    inline void A(int k,int x){
        p[k].maxx+=x;
        p[k].tag+=x;
    }
    inline void pushdown(int k){
        if(p[k].tag){
            A(ls(k),p[k].tag);A(rs(k),p[k].tag);p[k].tag=0;
        }
    }
    inline void change(int k,int l,int r,int z,int y,int x){
        if(z<=l&&r<=y){
            A(k,x);return;
        }int mid=(l+r)>>1;pushdown(k);
        if(z<=mid) change(ls(k),l,mid,z,y,x);
        if(mid<y) change(rs(k),mid+1,r,z,y,x);
        pushup(k);
    }
}st;

inline int binale(int l,int r,int v,int *f){
    if(l>r)  return -1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(a[f[mid]]<=v) l=mid;
        else r=mid-1;
    }
    if(a[f[l]]<=v) return l;
    return -1;
}
inline int binage(int l,int r,int v,int *f){
    if(l>r) return -1;
    while(l<r){
        int mid=(l+r)>>1;
        if(a[f[mid]]>=v) r=mid;
        else l=mid+1;
    }
    if(a[f[l]]>=v) return l;
    return -1;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]);
    b[1]=1;
    rep(i,2,n){
        if(a[i]>a[b[i-1]]) b[i]=i;
        else b[i]=b[i-1];
    }
    c[n]=n;
    dec(i,1,n-1){
        if(a[i]<a[c[i+1]]) c[i]=i;
        else c[i]=c[i+1];
    }
    rep(i,1,n){
        int l=binage(1,i-1,a[i],b);
        int r=binale(i+1,n,a[i],c);
        // printf("i=%d l=%d r=%d\n",i,l,r);
        if(l==-1||r==-1) continue;
        q[l].pb(i+1,r,2);q[i].pb(i+1,r,-2);
        // printf("id=%d l=%d r=%d v=%d\n",l,i+1,r,2);
        // printf("id=%d l=%d r=%d v=%d\n",i,i+1,r,-2);
    }
    // rep(i,1,n){
    //     int l=binale(1,i-1,a[i],b);
    //     int r=binale(i+1,n,a[i],c);
    //     if(l==-1||r==-1) continue;
    //     printf("i=%d\n",i);
    //     q[1].pb(i+1,r,-1);q[l+1].pb(i+1,r,1);
    //     printf("id=%d l=%d r=%d v=%d\n",1,i+1,r,-1);
    //     printf("id=%d l=%d r=%d v=%d\n",l+1,i+1,r,1);
    // }
    // rep(i,1,n){
    //     int l=binage(1,i-1,a[i],b);
    //     int r=binage(i+1,n,a[i],c);
    //     if(l==-1||r==-1) continue;
    //     printf("i=%d\n",i);
    //     q[l].pb(r,n,-1);q[i].pb(r,n,1);
    //     printf("id=%d l=%d r=%d v=%d\n",l,r,n,-1);
    //     printf("id=%d l=%d r=%d v=%d\n",i,r,n,1);
    // }
    int ans=0;
    rep(i,1,n){
        for(Ques now:q[i]){
            st.change(1,1,n,now.l,now.r,now.v);
        }
        ans=max(ans,p[1].maxx);
    }
    printf("%d\n",ans+1);
    return 0;
}

ZR2459

若给定排列，如果加油量减耗油量小于 $0$，那么答案一定为 $0$，否则我们把从 $1$ 开始的折线画出来，发现如果以最靠左的最小值作为开始点一定能满足条件。

设这个折线上的点为 $S$，那么从 $S$ 往左走是一个总大于 $0$ 的折线，向右走是一个总大于等于 $0$ 的折线，考虑预处理 $f_s$ 表示用 $s$ 中的点凑成一条大于 $0$ 的折线，$g_s$ 表示用 $s$ 中的带你凑成一条大于等于 $0$ 的折线，然后就可以计算答案了。

考虑如何计算 $f_s$，首先从 $S$ 往左走，相当于把之前的操作反号，所以要求是 $sum_s<0$，因为加点一定是往左边加，所以我们不妨枚举最后一个加进来的点，直接加即可，需要满足去掉最后一个加进来的点，剩下的也满足 $sum<0$，这样才能满足加点前后总是大于 $0$。

$g_s$ 的转移同样分析即可。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 21
#define M 2000100
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,a[N],b[N],c[N],f[M],g[M],sum[M];

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);rep(i,1,n) read(a[i]),read(b[i]),c[i]=a[i]-b[i];
    rep(i,1,n) sum[(1<<(i-1))]=c[i];
    rep(i,0,(1<<n)-1){
        sum[i]=sum[i&(-i)]+sum[i^(i&(-i))];
    }
    if(sum[(1<<n)-1]<0){puts("0");return 0;}
    g[0]=f[0]=1;
    rep(i,0,(1<<n)-1){
        if(sum[i]>=0){
            rep(j,0,n-1) if((i>>j)&1) (g[i]+=g[i^(1<<j)])%=mod;
        }
        else{
            rep(j,0,n-1) if((i>>j)&1) (f[i]+=f[i^(1<<j)])%=mod;
        }
    }
    int ans=0;
    rep(i,0,(1<<n)-1){
        ans=(ans+f[i]*g[((1<<n)-1)^i]%mod*(__builtin_popcountll(i)+1)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

ZR2458

这里只说明 $80$ 分做法，首先考虑容斥，首先如果在两个不能相邻的点之间连边，限制成一条链，我们一定是钦定有 $i$ 对点不满足条件，而这 $i$ 对点不满足条件，等价于把那条长度为 $m$ 的限制链划分成 $m-i$ 段，我们先填这些钦定的东西，然后把每个划分出来链看做一个整体，与剩下的做一个全排列，于是我们有：

$$
\sum\limits_{i=0}^mf_{m,i}(n-m+i)!(-1)^{m-i}
$$

其中，$f_{m-i}$ 可以在 $m^2$ 时间复杂度内算出，$f_{m,i}$ 表示把一条长度为 $m$ 的链划分成 $i$ 段的方案数。

瓶颈在求阶乘上，不过我们可以利用分块打表，在可以接受的时间复杂度内预处理所有可能需要的阶乘。

ZR2461

场上想用线段树合并来维护每个节点的值，其实不用，依然是从大往小加边的思路，不过我们只需要维护连通块内答案最小的点就行了，所以我们可以简单分析一些性质让我们维护尽可能少的值。

ZR2463

设质数 $p,q$，若 $x=pq$，那么 $n=pq-(p-1)(q-1)\Rightarrow n+1=pq$，而 $n+1$ 是一个偶数，根据哥德巴赫猜想，我们一定能够找到一个 $p$ 和一个 $q$ 满足条件，并且，实践证明，较小的那个质数不会很大。

ZR2462

其实这种题目和哈夫曼树半点关系没有，但是我被吓傻了。

首先显然有一个树的结构，而根节点的每个儿子把所有的点划分成了若干区间，这就提示我们区间 DP。

设 $f_{l,r,k}$ 表示把 $l,r$ 这一段分成 $k$ 段，每段代表一个子树，目前来说还是一个森林的贡献，$ans_{l,r}$ 表示把 $l,r$ 合并成一棵树的贡献，转移只需要枚举最后一段是哪一段即可，而 $ans_{l,r}$ 就等于把 $l,r$ 分成若干段，最后加一遍 $l,r$ 每个点的频率即可。

容易发现如果一个点所有的子节点不都是儿子，那么这个点一定有 $K$ 个儿子，这样才能满足最优。所以我们相当于是只需要知道最后 $f_{l,r,K}$ 的值，所以我们只需要知道 $f_{l,r,i}$ 表示把区间分成 $2^i$ 段的值，然后类似的再设一个状态，把 $K$ 二进制拆分，用来得到 $f_{l,r,K}$ 的值即可。

实现细节较多。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 510
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=1e18;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,K,a[N],f[N][N][6],ans[N][N],lg2[N],g[N][N][6],dk[6],sp;

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(K);rep(i,1,n) read(a[i]);
    rep(i,0,5) dk[i]=-1;
    rep(i,0,5) dec(j,0,i) if((K>>j)&1){
        dk[i]=j;break;
    }
    // rep(i,0,5){
        // printf("dk[%d]=%d\n",i,dk[i]);
    // }
    lg2[0]=-1;rep(i,1,K) lg2[i]=lg2[i>>1]+1;
    sp=lg2[K&(-K)];
    // printf("sp=%d\n",sp);
    rep(i,1,n){
        f[i][i][0]=0;ans[i][i]=0;
        rep(j,1,5) f[i][i][j]=INF;
    }
    rep(i,2,n){
        rep(j,1,n-i+1){
            int l=j,r=j+i-1;
            int len=r-l+1;
            rep(k,0,5) f[l][r][k]=INF,g[l][r][k]=INF;
            rep(o,1,5)if(len>=(1<<o)){
                rep(k,l,r) f[l][r][o]=min(f[l][r][o],f[l][k][o-1]+f[k+1][r][o-1]);
            }
            rep(o,0,5){
                if(dk[o]==-1){
                    g[l][r][o]=INF;
                    continue;
                }
                if(dk[o]==sp){
                    g[l][r][o]=f[l][r][dk[o]];
                }
                else{
                    rep(k,l,r){
                        g[l][r][o]=min(g[l][r][o],g[l][k][dk[o]-1]+f[k+1][r][dk[o]]);
                    }
                }
            }
            // printf("g[1][4][1]=%d\n",g[1][4][1]);
            if(len<=K){
                rep(k,l,r) ans[l][r]+=a[k];
                f[l][r][0]=ans[l][r];
                rep(o,0,5) if(dk[o]==0) g[l][r][o]=ans[l][r];
            }
            else{
                ans[l][r]=g[l][r][5];
                rep(k,l,r) ans[l][r]+=a[k];
                f[l][r][0]=ans[l][r];
                rep(o,0,5) if(dk[o]==0) g[l][r][o]=ans[l][r];
            }
            // rep(o,0,5){
            //     printf("f[%lld][%lld][%lld]=%lld\n",l,r,o,f[l][r][o]);
            //     printf("g[%lld][%lld][%lld]=%lld\n",l,r,o,g[l][r][o]);
            // }
        }
    }
    printf("%lld\n",ans[1][n]);
    return 0;
}

ZR2464

考虑这样奇怪的数据范围一定是折半搜索，我们考虑先分成两半。又有一个转化：$[2|c]\Leftrightarrow\frac{1+(-1)^c}{2}$，这提示我们可以把一个点集的贡献记为 $-1$ 的这个点集的导出子图的边集大小次方。

考虑贡献分为三部分，左边集合，右边集合，左右集合之间的边。

固定一个左边集合，对于右边集合中的每一个点，如果这个点到左边集合的边数量为偶数，那么等价于这些边都不存在，所以我们只需要关注那些到左边集合边数为奇数的右边集合的点，设 $\varphi(S)$ 表示对于一个左边集合 $S$，右边满足上述条件的点的集合。

考虑如果直接枚举左右两边集合，复杂度不会减少，不如对于右边集合预处理一个 $f_T$ 表示所有 $\varphi(S)=T$ 的集合 $S$ 的贡献之和，设 $g_T$ 为右边集合 $T$ 的贡献，那么答案为：

$$
\sum\limits_{A,B}f_Ag_B(-1)^{|A\cap B|}
$$

容易发现对于每个 $A$ 来说，$g_B(-1)^{|A\cap B|}$ 的形式恰好是一个异或卷积，所以 FWT 就做完了。

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
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 50
#define M 23
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int B,e[N],n,m,f[1ll<<M],g[1ll<<M],bit[1ll<<M],h[1ll<<M];
unordered_map<ll,int> lg2;

inline void FWTxor(int *f,int n){
    for(int mid=1;mid<=(n>>1);mid<<=1)
        for(int l=0;l<n;l+=(mid<<1))
            for(int i=l;i<=l+mid-1;i++){
                int a=f[i],b=f[i+mid];
                f[i]=(a+b)%mod;f[i+mid]=(a-b)%mod;
            }
}
inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,1,m){
        int u,v;read(u);read(v);
        e[u]|=(1ll<<(v-1));
        e[v]|=(1ll<<(u-1));
    }
    // rep(i,1,n){
    //     printf("i=%d e[i]=%d\n",i,e[i]);
    // }
    // lg2[0]=-1;
    B=n/2;
    rep(i,0,(1ll<<(max(B,n-B)))-1) bit[i]=bit[i>>1]^(i&1);
    rep(i,0,n) lg2[1ll<<i]=i;
    // rep(i,1,(1ll<<(max(B,n-B)))-1) lg2[i]=lg2[i>>1]+1;
    rep(i,0,(1ll<<B)-1){
        h[i]=h[i^(i&(-i))]^bit[e[lg2[i&(-i)]+1]&i];
        // assert((e[lg2[i&(-i)]+1]&i)<=(1ll<<(max(B,n-B)))-1);
        // printf("h[%d]=%lld\n",i,h[i]);
        int now=0;
        rep(j,B+1,n){
            if(bit[e[j]&i]){
                // assert((e[j]&i)<=(1ll<<(max(B,n-B)))-1);
                now|=(1ll<<(j-B-1));
            }
        }
        // printf("i=%d now=%d\n",i,now);
        if(h[i]) f[now]--;
        else f[now]++;
    }
    // printf("lg2[1]=%d\n",lg2[1]);
    rep(i,0,(1ll<<(n-B))-1){
        h[i]=0;
        if(!i){
            g[0]=1;
            continue;
        }
        h[i]=h[i^(i&(-i))]^bit[(e[lg2[i&(-i)]+B+1]&(i<<(B)))>>B];
        // assert(((e[lg2[i&(-i)]+B+1]&(i<<(B)))>>B)<=(1ll<<(max(B,n-B)))-1);
        // printf("i=%lld i&(-i)=%lld,val=%lld,e[lg2[i&(-i)]+B+1]=%d\n",i,i&(-i),lg2[i&(-i)]+B+1,e[lg2[i&(-i)]+B+1]);
        if(h[i]) g[i]--;
        else g[i]++;
    }
    // exit(0);
    rep(i,0,(1ll<<(n-B))-1){
        // printf("f[%lld]=%lld\n",i,f[i]);
        // printf("g[%lld]=%lld\n",i,g[i]);
        f[i]%=mod;
        g[i]%=mod;
    }
    FWTxor(g,1ll<<(n-B));
    rep(i,0,(1ll<<(n-B))-1) f[i]=f[i]*g[i]%mod;
    int ans=0;
    rep(i,0,(1ll<<(n-B))-1) ans=(ans+f[i])%mod;
    // printf("ans=%lld\n",ans);
    (ans+=((1ll<<(n))%mod))%=mod;
    ans=ans*inv(2)%mod;
    printf("%lld\n",ans);
    return 0;
}

ZR2447

考虑若小于等于 $12$ 可以直接枚举最小表示，否则，我们拿出 dfs 树出来，那么把所有返祖边的祖先节点弄为特殊点，先枚举所有祖先节点的最小表示，然后可以设 DP $f_{k,c}$ 表示 $k$ 的颜色是 $c$，因为枚举最小表示，所以 $c$ 一定是小于等于 $11$ 的，可以跑过去。

因为自己实现的太丑以至于调不出来，这里来一份别人的简单易懂代码。

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
#include<cstdio>
using namespace std;
const int o=210,MOD=1e9+7;
int T,n,m,K,h[o],cnt,mp[o][o],dif[o],sam[o],coef[o],col[o],d[o],f[o][o],g[o],b[o],tot,asd,ans;bool tr[o],sp[o];
struct Edge{int v,p,id;}e[o];
inline void ad(int U,int V,int ID){e[++cnt].v=V;e[cnt].p=h[U];e[h[U]=cnt].id=ID;} 
void Dfs(int nw,int fa){
	d[nw]=d[fa]+1;
	for(int i=h[nw];i;i=e[i].p) if(e[i].v^fa)
		if(d[e[i].v]>d[nw]) sp[nw]=1;
		else if(!d[e[i].v]) tr[i]=1,d[e[i].v]=d[nw]+1,Dfs(e[i].v,nw);
	if(sp[nw]) b[++tot]=nw;
}
void dfs(int nw,int fa){
	for(int i=0;i<=asd;++i) f[nw][i]=(col[nw]==i||!sp[nw]);
	for(int i=h[nw];i;i=e[i].p) if(e[i].v^fa)
		if(!tr[i]){if(d[nw]>d[e[i].v]) for(int j=0;j<=asd;++j) f[nw][j]=f[nw][j]*1ll*(col[e[i].v]==j?sam[e[i].id]:dif[e[i].id])%MOD;}
		else{
			dfs(e[i].v,nw);
			for(int j=0;j<=asd;++j) f[nw][j]=((g[e[i].v]+MOD-f[e[i].v][j])*1ll*dif[e[i].id]+f[e[i].v][j]*1ll*sam[e[i].id])%MOD*f[nw][j]%MOD;
		}
	g[nw]=f[nw][0]*1ll*(K-asd)%MOD;
	for(int i=1;i<=asd;++i) g[nw]=(g[nw]+f[nw][i])%MOD;
}
void ddfs(int nw){
	if(nw>tot){dfs(1,0);ans=(ans+coef[asd]*1ll*g[1])%MOD;return;}
	for(int i=1;i<=asd;++i) col[b[nw]]=i,ddfs(nw+1);
	col[b[nw]]=++asd;ddfs(nw+1);--asd;
}
int main(){
	for(scanf("%d",&T);T--;printf("%d\n",ans),ans=cnt=tot=0){
		scanf("%d%d%d",&n,&m,&K);
		for(int i=1;i<=n;++i) h[i]=d[i]=col[i]=0;
		for(int i=1;i<=2*m;++i) tr[i]=sp[i]=0;
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) mp[i][j]=0;
		for(int i=1,u,v,a,b;i<=m;++i){
			scanf("%d%d%d%d",&u,&v,&a,&b);
			if(!mp[u][v]) dif[i]=a,sam[i]=b,mp[u][v]=mp[v][u]=i,ad(u,v,i),ad(v,u,i);
			else dif[mp[u][v]]=dif[mp[u][v]]*1ll*a%MOD,sam[mp[u][v]]=sam[mp[u][v]]*1ll*b%MOD;
		}
		for(int i=coef[0]=1;i<=n;++i) coef[i]=coef[i-1]*(K-i+1ll)%MOD;
		Dfs(1,0);ddfs(1);
	}
	return 0;
}