NOIP 2021

报数

水题，筛法解决。

数列

不取模，100→10\color{red}{100 \rightarrow 10} 恐怖。

dpdp 真是太好了，样例解释真是太好了。

题意

求长度为 nn 的序列。

  • 序列中的元素 0≤ai≤m0\le a_i\le m。

  • 序列 {ai}\{a_i\} 满足整数 S=2a1+2a2+⋯+2anS = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n} 的二进制表示中 11 的个数不超过 kk。

求贡献总和，贡献为 va1×va2×⋯×vanv_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}。

这个样例解释挺好的，理解了就会做正解了。

由于 k=1k = 1，而且由 n≤S≤n×2mn \leq S \leq n \times 2^m 知道 5≤S≤105 \leq S \leq 10，合法的 SS 只有一种可能：S=8S = 8，这要求 aa 中必须有 22 个 00 和 33 个 11，于是有 (52)=10\binom{5}{2} = 10 种可能的序列，每种序列的贡献都是 v02v13=4v_0^2 v_1^3 = 4，权值和为 10×4=4010 \times 4 = 40。

保证 1≤k≤n≤301 \leq k \leq n \leq 30，0≤m≤1000 \leq m \leq 100，1≤vi≤9982443531\le v_i \le 998244353。

  • 爆搜 O(mn)O(m^n)，20pts\color{red}{20pts}
  • 记忆化，记录到第 ii 位权值为 xx 的贡献，fi,xf_{i,x}，复杂度 O(n×n×2m×m)O(n\times n\times 2^m \times m)，根据记忆化数组大小以及计算贡献复杂度求复杂度，50pts\color{red}{50pts}
  • dpdp，100pts\color{red}{100pts}

通过发现最后的答案序列不就是多个二进制相加吗。

考虑设置状态我们发现有 kk 的限制这不就启发我们考虑二进制运算，对于 nn 个数每个数可以选无限种，但是 11 的个数最多只有 ll 个，不同的数之间选多选少肯定是有进位的。

直接涉及 fi,j,k,lf_{i,j,k,l} 当前考虑到二进制位 ii，序列中已经有 jj 个数，当前对 i+1i+1 位有 kk 的进位，当前序列已经有了 ll 个 11。

此处二进制位从 00 开始。

从低位到高位无后效性，因此可以转移。

fi+1,j+t,⌊t+k2⌋,l+(t+k)mod⁡2←fi,j,k,l(n−jt)vit,0≤t≤mf_{i+1,j+t,\lfloor \frac{t+k}{2} \rfloor,l+(t+k)\operatorname{mod}2 } \leftarrow f_{i,j,k,l} \binom{n-j}{t} v_i^t,0\le t\le m

注：对于 dpdp 初始化考虑实际意义即可。

细节

到最后可能还有进位那么就需要多考虑以为把进位都加进去。

复杂度

O(m×n4)≈8.1×107O(m\times n^4)\approx 8.1\times 10^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
#include<iostream>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
template<typename T>inline void read(T& x){
    x=0;int f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch=='-'){f=-1;} ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
template<typename T>inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int mod=998244353;
const int N=33;
const int M=108;
int C[N][N];
int pv[M][N];
int dp[M][N][N/2][N];
void init(int n,int m){
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    for(int i=0;i<=m;i++){
        pv[i][0]=1;
        for(int j=2;j<=n;j++){
            pv[i][j]=(1ll*pv[i][j-1]*pv[i][1])%mod;
        }
    }
}
int popcount(int val){
    int res=0;
    while(val){
        val-=lowbit(val);
        res++;
    }
    return res;
}
int n,m,K;
signed main(){
    read(n),read(m),read(K);
    for(int i=0;i<=m;i++){
        read(pv[i][1]);
    }
    init(n,m);
    dp[0][0][0][0]=1;
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n/2;k++){
                for(int l=0;l<=K;l++){
                    for(int t=0;t<=n-j;t++){
                        dp[i+1][j+t][(t+k)/2][l+(t+k)%2]=(dp[i+1][j+t][(t+k)/2][l+(t+k)%2]+1ll*dp[i][j][k][l]*C[n-j][t]%mod*pv[i][t]%mod)%mod;
                    }
                }
            }
        }
    }
    long long ans=0;
    for(int k=0;k<=n/2;k++){
        for(int l=0;l<=K;l++){
            if(l+popcount(k)<=K){
                ans+=dp[m+1][n][k][l];
                ans%=mod;
            }
        }
    }
    write(ans);
    return 0;
}

NOIP 2020

移球游戏

在 820000820000 内次操作将 nn 个栈，每个栈有 mm 个元素，还原成规则栈。

限制：总共有 nn 种元素，每种元素有 mm 个。

数据范围：n≤50,2≤m≤400n\le 50,2\le m\le400

分析

借助样例 22，我们模拟一下，考虑还原颜色只用 33 个栈，这样是优秀的，并不会影响别的栈。

那么 66 种操作结束。

先设定一种颜色为 00，另一种颜色为 11，那么可以考虑，最终序列为全 00 栈，全 11 栈，空栈。

设 11 栈中 00 的个数为 ss。

  • 22 栈移走s到 33 栈 s\color{red}{s}
  • 11 栈移 00 到 22 ，移 11 到 33 栈 m\color{red}{m}
  • 移 22 栈全 00 个数 ss 到 11 ，移 33 栈全 11 个数 m−sm-s 到 11 栈 m\color{red}{m}
  • 移 22 栈剩下的 m−sm-s 到 33 栈 m−s\color{red}{m-s}
  • 移 11 栈 m−sm-s 个全 11 到 22 栈 m−s\color{red}{m-s}
  • 移 33 栈为 00 到 11 ，移 33 栈全 11 到 22 栈 m\color{red}{m}

总计 5m−s5m-s 次操作。

显然这种操作只适用于两栈只有两种相同的颜色，但是对于 nn 个栈颜色肯定都是乱序的，那我们就强行固定一个顺序，那么考虑分治，对于每一个位置代表一种颜色，对于移动的 ss 是什么当然肯定就是考虑当前 ≤mid\le mid 放左，>mid>mid 放右，通过多次当最后相等的时候也就完成了操作，这里有一个优化，因为我们的操作是 5m−s5m-s，ss 与个数有关，那么就考虑选更多的去匹配，我们考虑 midmid 左右依次匹配，细节见下。

请注意一个小细节，如果是偶数肯定每个都会匹配一次，但对于奇数也不慌，随着递归奇偶会变化，因为我们保证了他是归一方的。

细节

  • 具体的实现细节，我们可以考虑将栈的转移规定成一个函数，最后好输出操作，与喵了个喵相似。
  • 每次递归下去一定是可以保证栈中元素为 mm 的，但是对于连个栈操作的时候可能存在一种元素严格大于另一种，注意别让栈超过 mm 即可。
  • 请注意是从栈顶依次取哦。

时间复杂度

O(5n2mlog⁡n)=3×107O(5n^2m \log n)=3\times 10^7

操作次数

T(n)=2T(n/2)+5mn=5mnlog⁡n≈6×105<8.2×105\begin{aligned} T(n)&=2T(n/2)+5mn\\ &=5mn\log n\\ &\approx6\times 10^5 <8.2\times 10^5 \end{aligned}

复杂度是是严格可以的。

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
153
#include<iostream>
#include<cstring>
#include<assert.h>
using namespace std;
template<typename T>inline void read(T& x){
    x=0;int f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch=='-'){f=-1;} ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
template<typename T>inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int N=50+8;
const int M=400+8;
const int K=82e4+8;
int a[N][M],top[N],n,m,ans[K][2],tot;
bool flag[N];
void pour(int x,int y){
    ans[++tot][0]=x,ans[tot][1]=y;
    a[y][++top[y]]=a[x][top[x]--];
}
void solve(int l,int r){
    if(l==r) return ;
    int mid=l+r>>1;
    memset(flag,0,sizeof flag);
    // for(int i=1;i<=n;i++){
    //     assert(top[i]==m);
    // }
    for(int i=l;i<=mid;i++){
        for(int j=mid+1;j<=r;j++){
            if(flag[i]||flag[j]) continue;
            int s=0;
            for(int k=1;k<=m;k++){
                s+=(a[i][k]<=mid);
            }
            for(int k=1;k<=m;k++){
                s+=(a[j][k]<=mid);
            }
            //s+m+s+(m-s)+(m-s)+(m-s)+m=5m-s
            if(s>=m){
                s=0;
                for(int k=1;k<=m;k++){
                    s+=(a[i][k]<=mid);
                }
                //s
                for(int k=1;k<=s;k++){
                    pour(j,n+1);
                }
                //m
                //请注意是从栈顶依次取哦
                while(top[i]){
                    if(a[i][top[i]]<=mid){
                        pour(i,j);
                    }
                    else{
                        pour(i,n+1);
                    }
                }
                //s
                for(int k=1;k<=s;k++){
                    pour(j,i);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(n+1,i);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(j,n+1);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(i,j);
                }
                //m
                //这就是一种元素严格大于另一种不能爆栈
                while(top[n+1]){
                    if(top[i]==m||a[n+1][top[n+1]]>mid) pour(n+1,j);
                    else pour(n+1,i);
                }
                flag[i]=1;
            }
            else{
                s=0;
                for(int k=1;k<=m;k++){
                    s+=(a[j][k]>mid);
                }
                //s
                for(int k=1;k<=s;k++){
                    pour(i,n+1);
                }
                //m
                while(top[j]){
                    if(a[j][top[j]]>mid){
                        pour(j,i);
                    }
                    else{
                        pour(j,n+1);
                    }
                }
                //s
                for(int k=1;k<=s;k++){
                    pour(i,j);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(n+1,j);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(i,n+1);
                }
                //m-s
                for(int k=1;k<=m-s;k++){
                    pour(j,i);
                }
                //m
                while(top[n+1]){
                    if(top[j]==m||a[n+1][top[n+1]]<=mid) pour(n+1,i);
                    else pour(n+1,j);
                }
                flag[j]=1;
            }
        }
    }
    solve(l,mid);
    solve(mid+1,r);
}
int main(){
    // freopen("D:\\newfile\\in\\ball3.in","r",stdin);
    // freopen("ball.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            read(x);
            a[i][++top[i]]=x;
        }
    }
    solve(1,n);
    write(tot);
    putchar('\n');
    for(int i=1;i<=tot;i++){
        write(ans[i][0]);
        putchar(' ');
        write(ans[i][1]);
        putchar('\n');
    }
    return 0;
}

NOIP 2018

赛道修建

考虑每个节点的子树对该节点的贡献，选择最大的去贡献就好。

O(nlog⁡n2)O(n \log n^2)

保卫王国

无修改操作的树上问题考虑倍增，并且一条边至少选择一个节点，显然考虑 dpdp。

设 fi,0/1f_{i,0/1} 以 ii 为根的子树，当前选择或不选择这个根节点 ii 的最小代价。

gi,0/1g_{i,0/1} 除去以 ii 为根的子树（包含 ii 节点），当前选择或不选择这个根节点 ii 的最小代价。

dpi,j,0/1,0/1dp_{i,j,0/1,0/1} 以 ii 为起点，状态为 kk，跳到 2j2^j 的父亲，父亲状态为 ll 的这段 (i,i+2j](i,i+2^j]（即不含 ii 节点）区间的最小代价。

显然 min⁡(fi,0+gi,0,fi,1+gi,1)\min(f_{i,0}+g_{i,0},f_{i,1}+g_{i,1}) 就是全局无限制的答案。

有限制就倍增就好。

时间复杂度为 O((n+q)log⁡nO((n+q)\log n。

附上转移方程。

若选 uu，vv 可选可不选。
不选 uu，vv 必选。

fu,0=∑v∈ufv,1fu,1=∑v∈umin⁡(fv,1,fv,0)f_{u,0}=\sum_{v\in u}f_{v,1}\\ f_{u,1}=\sum_{v\in u}\min(f_{v,1},f_{v,0})

容斥即可。

gv,0=gu,1+fu,1−min⁡(fv,0+fv,1)gv,1=min⁡(gu,0+fu,0−fv,1,gu,1+fu,1−min⁡(fv,0+fv,1))g_{v,0}=g_{u,1}+f_{u,1}-\min(f_{v,0}+f_{v,1})\\ g_{v,1}=\min(g_{u,0}+f_{u,0}-f_{v,1},g_{u,1}+f_{u,1}-\min(f_{v,0}+f_{v,1}))\\

倍增预处理过于简单，就是从小的向大的更新。

处理答案从大的向小的更新，倍增时记录一下最优的答案，一直跳父亲就行，知道跳到一个父亲，因此有在一条链和不是的两种情况，就是类似于倍增求 LCALCA。

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
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
template<typename T>inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
template<typename T>inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int N=1E5+8;
const int M=N*2;
//2^17=131072>1E5
long long g[N][2],f[N][2],dp[N][18][2][2];
int h[N],e[M],ne[M],idx;
int n,q,val[N];
set<pair<int,int> > st;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
char op[5];
int father[N][18];
int dep[N];
void dfs_f(int u,int fa){
    f[u][1]=val[u];
    father[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa) continue;
        dfs_f(v,u);
        f[u][1]+=min(f[v][0],f[v][1]);
        f[u][0]+=f[v][1];
    }
}
void dfs_g(int u,int fa){
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==fa) continue;
        g[v][0]=g[u][1]+f[u][1]-min(f[v][0],f[v][1]);
        g[v][1]=min(g[u][0]+f[u][0]-f[v][1],g[v][0]);
        dfs_g(v,u);
    }
}
long long solve(int x,int a,int y,int b){
    if(dep[x]<dep[y]) swap(x,y),swap(a,b);
    //确定住
    long long tx[2],ty[2];
    memset(tx,0x3f,sizeof tx);
    memset(ty,0x3f,sizeof ty);
    //中转
    long long nx[2],ny[2];
    tx[a]=f[x][a];
    ty[b]=f[y][b];
    for(int i=17;i>=0;i--){
        if(dep[father[x][i]]>=dep[y]){
            nx[0]=nx[1]=1e17;
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    nx[j]=min(nx[j],tx[k]+dp[x][i][k][j]);
                }
            }
            tx[0]=nx[0],tx[1]=nx[1],x=father[x][i];
        }
    }
    if(x==y){
        return tx[b]+g[y][b];
    }
    for(int i=17;i>=0;i--){
        if(father[x][i]!=father[y][i]){
            ny[0]=ny[1]=nx[0]=nx[1]=1e17;
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    nx[j]=min(nx[j],tx[k]+dp[x][i][k][j]);
                    ny[j]=min(ny[j],ty[k]+dp[y][i][k][j]);
                }
            }
            tx[0]=nx[0],tx[1]=nx[1],x=father[x][i];
            ty[0]=ny[0],ty[1]=ny[1],y=father[y][i];
        }
    }
    int lca=father[x][0];
    return min(f[lca][0]+g[lca][0]-f[x][1]-f[y][1]+tx[1]+ty[1],
    f[lca][1]+g[lca][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(tx[0],tx[1])+min(ty[0],ty[1]));
}
int main(){
    memset(h,-1,sizeof h);
    read(n),read(q);
    scanf("%s",op);
    for(int i=1;i<=n;i++){
        read(val[i]);
    }
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        add(u,v);
        add(v,u);
        st.insert({u,v}),st.insert({v,u});
    }
    dfs_f(1,0);//f包含本身
    dfs_g(1,0);//g是出去本身
    for(int i=1;i<=n;i++){
        dp[i][0][0][0]=1e17;
        //下面是开区间，上面是闭区间
        dp[i][0][0][1]=f[father[i][0]][1]-min(f[i][0],f[i][1]);
        dp[i][0][1][0]=f[father[i][0]][0]-f[i][1];
        dp[i][0][1][1]=f[father[i][0]][1]-min(f[i][0],f[i][1]);
    }
    for(int i=1;i<=17;i++){
        for(int j=1;j<=n;j++){
            father[j][i]=father[father[j][i-1]][i-1];
            for(int k=0;k<2;k++){
                for(int l=0;l<2;l++){
                    dp[j][i][k][l]=1e17;
                    for(int m=0;m<2;m++){
                        dp[j][i][k][l]=min(dp[father[j][i-1]][i-1][m][l]+dp[j][i-1][k][m],dp[j][i][k][l]);
                    }
                }
            }
        }
    }
    while(q--){
        int a,b,x,y;
        read(a),read(x),read(b),read(y);
        if(!x&&!y&&st.find({a,b})!=st.end()){
            puts("-1");
            continue;
        }
        write(solve(a,x,b,y)),putchar('\n');
    }
    return 0;
}

NOIP 2017

列队

参考博客 这是一篇讲具体操作的博客。

不会平衡树，但会主席树，因此用线段树来做。

考虑每次修改真正会移动的点只有 ((n+m−1)×q)((n+m-1)\times q)，每次也就相当于删去一个点，然后再末尾添加一个点。

那么由于空间限制我们使用动态开点线段树空间复杂度 qlog⁡nq\log n。

考虑前 nn 行的 [1,m−1][1,m-1]，和第 mm 列建立 n+1n+1 颗线段树。

每次操作相当于。

  • 删去一个点
  • 末尾添加一个点
  • 查询第 kk 小的点

显然这是可做的。

时间复杂度 qlog⁡nq \log n

代码实现难度不高，主要是考虑在原区间上加点建立新节点的操作，以及每次操作求值，因为没被开过的点一定是原来的定点；还有就是对于未开的点我们每次可以求出这个区间有多少个数，以及我们对于还未添加的区间虽然已经保留了值域，但是绝对不能添加信息，因为这是不只有在添加时我们增加 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
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
#include<iostream>
using namespace std;
template<typename T>inline void read(T& x){
    x=0;int f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch=='-'){f=-1;} ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
template<typename T>inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int N=3e5+8;
struct node{
    int sz;
    int ls,rs;
    long long val;
}tr[N<<5];
//q log n 2^32保证
int n,m,q,x,y;
int now;//现在需要操作的是那一颗线段树
int rt[N+1];
int cnt;
int ins[N+1];
struct SEGEMENTTREE{
    //不动的点是时候加进来了
    int len(int l,int r){
        if(now==n+1){
            if(r<=n) return (r-l+1);
            else if(l<=n) return (n-l+1);
            return 0;
        }
        else{
            if(r<=m-1) return (r-l+1);
            else if(l<=m-1) return (m-1-l+1);
            return 0;
        }
    }
    //插入查询出来的新人到末尾
    void modify(int &u,int l,int r,int pos,long long num){
        if(!u){
            u=++cnt;
            tr[u].sz=len(l,r);    
            if(l==r) tr[u].val=num;
        }
        tr[u].sz++;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(pos<=mid) modify(tr[u].ls,l,mid,pos,num);
        else modify(tr[u].rs,mid+1,r,pos,num);
    }
    long long query(int &u,int l,int r,int pos){
        if(!u){
            u=++cnt;
            tr[u].sz=len(l,r);
            if(l==r){
                if(now==n+1) tr[u].val=(1ll*l*m);
                else tr[u].val=(1ll*(now-1)*m)+l;
            }
        }
        //查询到就意味着删除，即保证每个点都是有值的
        tr[u].sz--;
        if(l==r) return tr[u].val;
        int mid=(l+r)>>1;
        //pos与线段树实际下标无关只与类似于主席树查询k小有关
        if((!tr[u].ls&&len(l,mid)>=pos)||(tr[tr[u].ls].sz>=pos)){
            return query(tr[u].ls,l,mid,pos);
        }
        else{
            int tmp;
            if(!tr[u].ls) tmp=len(l,mid);
            else tmp=tr[tr[u].ls].sz;
            return query(tr[u].rs,mid+1,r,pos-tmp);
        }
    }
}T;
int range;
int main(){
    read(n),read(m),read(q);
    range=max(n,m)+q;
    while(q--){
        read(x),read(y);
        long long ans=0;
        if(y==m){
            now=n+1;
            ans=T.query(rt[now],1,range,x);
        }
        else{
            now=x;
            ans=T.query(rt[now],1,range,y);
        }
        write(ans),putchar('\n');
        now=n+1;
        T.modify(rt[now],1,range,n+(++ins[now]),ans);
        if(y!=m){
            ans=T.query(rt[now],1,range,x);
            now=x;
            T.modify(rt[now],1,range,m-1+(++ins[now]),ans);
        }
    }
    return 0;
}

小凯的疑惑

结论：a,ba,b 可以表示 >a×b−a−b,gcd(a,b)=1>a\times b-a-b,gcd(a,b)=1

NOIP 2016

换教室

跟据期望线性性即可。

设 fi,j,0/1f_{i,j,0/1} 表示前 ii 个考虑完，当前用几个，当前这位的状态是什么。

转移式就是将所有情况加起来，太长了懒了。

关于期望

NOIP 2012

疫情控制

参考博客

这个题求的是最小代价，但是每个点可以走一整棵树的所有权值，而权值很大，考虑二分答案。

若一个时间限制满足条件，那么剩下的都满足条件，因此二分具有单调性。

考虑二分中如何判断当次是否合法，因为每个军队都是独立的，那么我们单独考虑这么多点即可。

性质：对于一个可以在一定范围内移动的点，走深度越小一定是最优的，因为堵住分叉越多肯定是更好的。

那对于那么多的点，如果有些点到了根节点的儿子还能移动，那么说明可以跨子树移动，保存下这些点，对于不能的我们就将他固定住即可。

现在先判断一下，那个节点还需要占据，考虑对于一个可以移动到别处的点，移动到根节点的儿子显然是最优的。

那么现在对于那些可移动的点有两种情况，一种是该点不动，一种是跨子树。

考虑什么情况不动比较好，如果移动任意一步无法回去的，那么静止不动是更好的。

剩下的大配大，小配小贪心即可，显然是最优的。（经典最优选取模型）

对于移动我们倍增预处理，距离，考虑二进制位分解进行移动。

无解情况即都不合法即 checkcheck 永远不会返回真。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
template<typename T>inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
template<typename T>inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int N=5E4+8;
const int M=N*2;
int n,m;
int at[N];
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int fa[N][17],dist[N][17],dep[N];
void dfs(int u,int father){
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    for(int i=1;(1<<i)<dep[u];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        dist[u][i]=dist[u][i-1]+dist[fa[u][i-1]][i-1];
    }
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==father) continue;
        dist[v][0]=w[i];
        dfs(v,u);
    }
}
pair<int,int> tmp[N];
bool st[N];
bool need[N];
int change[N];
int least[N];
bool dfsforget(int u,int father){
    bool son=0;
    if(st[u]){
        return 1;
    }
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(v==father) continue;
        son=1;
        if(!dfsforget(v,u)) return 0;
    }
    if(!son) return 0;
    else return 1;
}
bool check(int lim){
    memset(st,0,sizeof st);
    memset(need,0,sizeof need);
    int top=0;
    for(int i=1;i<=m;i++){
        int x=at[i],cnt=0;
        for(int j=16;j>=0;j--){
            if(fa[x][j]>1&&cnt+dist[x][j]<=lim){
                cnt+=dist[x][j];
                x=fa[x][j];
            }
        }
        if(fa[x][0]==1&&cnt+dist[x][0]<=lim){
            tmp[++top]={lim-cnt-dist[x][0],x};
        }
        else{
            st[x]=true;
        }
    }
    for(int i=h[1];~i;i=ne[i]){
        int v=e[i];
        if(!dfsforget(v,1)){
            need[v]=1;
        }
    }
    sort(tmp+1,tmp+top+1);
    int tot=0;
    for(int i=1;i<=top;i++){
        if(need[tmp[i].second]&&tmp[i].first<dist[tmp[i].second][0]){
            need[tmp[i].second]=0;
        }
        else{
            change[++tot]=tmp[i].first;
        }
    }
    int netot=0;
    for(int i=h[1];~i;i=ne[i]){
        int v=e[i];
        if(need[v]){
            least[++netot]=dist[v][0];
        }
    }
    if(tot<netot) return 0;
    sort(change+1,change+1+tot);
    sort(least+1,least+netot+1);
    int i=1,j=1;
    while(i<=netot&&j<=tot){
        if(change[j]>=least[i]){
            i++,j++;
        }
        else j++;
    }
    if(i>netot) return 1;
    return 0;
}
signed main(){
    memset(h,-1,sizeof h);
    read(n);
    int l=0,r=0;
    for(int i=1;i<n;i++){
        int u,v,val;
        read(u),read(v),read(val);
        add(u,v,val);
        add(v,u,val);
        r+=val;
    }
    dfs(1,0);
    read(m);
    for(int i=1;i<=m;i++){
        read(at[i]);
    }
    int ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    write(ans);
    return 0;
}

NOIP 2011

观光公交

参考博客

此题有几个值 nn 站，mm 人，kk 次加速机会，ii 站到 i+1i+1 站的行驶时间 did_{i}，每个人的到达 AiA_i 站的时间 TiT_i，目的站 BiB_i，加速可以让 Di−1(Di≥1)D_i -1(D_i\ge 1) 。

分析

k=0k=0 的情况我们先考虑一下，我们把考虑把每个人对答案的贡献记到每个人的终点站，那么现在贡献记录在每个站上，因此答案即为 ans=∑i=1nnumi×arrivetimei−∑i=1mTians=\sum_{i=1}^n num_i \times arrivetime_i-\sum_{i=1}^mT_i，numinum_i 为到 ii 站下车的人的个数，arrivetimeiarrivetime_i 为到达 ii 站的时间。

考虑一次加速会影响公交到达这段路终点站的时间，相当于影响下之后恰好要等待的那个站之前，之前直到现在这个加速后终点站的区间范围，即 [l,r)[l,r)，ll 是加速器使用的段的终点站坐标，rr 是下次恰好要等待的站。

既然如此我们就可以算出使用一次可以影响多少人，我们选择影响最多的显然是最优的。

那么枚举加速器每次更新统计答案就好。

此题我们关键在于考虑贡献是如何求得，每次加速会影响什么。

还有个非常重要的东西，对于贡献类似一与边与点的关系，我们总是考虑将贡献记录到边更靠右的点

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
int main(){
    read(n),read(m),read(k);
    for(int i=2;i<=n;i++){
        read(D[i]);
    }
    for(int i=1;i<=m;i++){
        read(T[i]),read(A[i]),read(B[i]);
        ans-=T[i];
        cnt[B[i]]++;
        mx[A[i]]=max(T[i],mx[A[i]]);
    }
    for(int i=2;i<=n;i++){
        arr_tim[i]=max(arr_tim[i-1],mx[i-1])+D[i];
    }
    for(int i=1;i<=k;i++){
        for(int j=n;j>=2;j--){
            wait[j]=cnt[j];
            if(arr_tim[j]>mx[j]) wait[j]+=wait[j+1];
        }
        int mxx=0;
        int id=0;
        for(int j=2;j<=n;j++){
            if(D[j]>0&&mxx<wait[j]){
                mxx=wait[j];
                id=j;
            }
        }
        D[id]--;
        for(int j=id;j<=n;j++){
            arr_tim[j]=max(arr_tim[j-1],mx[j-1])+D[j];
        }
    }
    for(int i=2;i<=n;i++){
        ans+=arr_tim[i]*cnt[i];
    }
    write(ans);
    return 0;
}

注明：以上所有的参考博客，就是参考的题解。

__END__