Day7

扫描线

一般使用线段树维护，具体地，维护区间和及区间非零个数。

[NOI2023] 方格染色

横竖线就是扫描线板题。斜线最多只有 \(5\) 个，暴力将能够合并的斜线合并，然后遍历所有横竖线判断是否有交。懒得写离散化了，直接动态开点线段树也能过。
code 
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
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=1e5+10;
int tot,n,m,q,C,cnt,type3cnt,cnt1,cnt2;
ll ans;
bool vis[114];
struct line{
    int t,x1,y1,x2,y2;
}a[N],b[114],c[114];
struct change{
    int x,y1,y2,k;
    bool operator<(const change &temp)const{return x<temp.x;}
}p[N<<1];
struct Node{
    Node *ls,*rs;
    int val,tag;
}tree[N<<5];
Node *root;
inline Node *new_node(){return &tree[++tot];}
inline void push_up(Node *u,int l,int r){
    if(u->tag) u->val=r-l+1;
    else if(l==r) u->val=0;
    else{
        u->val=0;
        u->val+=u->ls?u->ls->val:0;
        u->val+=u->rs?u->rs->val:0;
    }
}
void modify(Node*&u,int l,int r,int x,int y,int k){
    if(u==nullptr) u=new_node();
    if(x<=l&&y>=r){
        u->tag+=k;
        push_up(u,l,r);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(u->ls,l,mid,x,y,k);
    if(y>mid) modify(u->rs,mid+1,r,x,y,k);
    push_up(u,l,r);
}
int main(){
    read(C,n,m,q);
    for(int i=1,t,x1,y1,x2,y2;i<=q;i++){
        read(t,x1,y1,x2,y2);
        if(t!=3){
            p[++cnt]={x1-1,y1,y2,1};
            p[++cnt]={x2,y1,y2,-1};
            a[++cnt1]={t,x1,y1,x2,y2};
        }
        else b[++type3cnt]={3,x1,y1,x2,y2};
    }
    sort(p+1,p+1+cnt);
    for(int i=1;i<=cnt;i++){
        modify(root,1,1e9,p[i].y1,p[i].y2,p[i].k);
        ans+=root->val*(p[i+1].x-p[i].x);
    }
    
    bool flag=1;
    while(flag){
        flag=0;
        for(int i=1;i<=type3cnt;i++){
            if(vis[i]) continue;
            for(int j=1;j<=type3cnt;j++){
                if(i==j||vis[j]) continue;
                if(b[j].x2-b[i].x1==b[j].y2-b[i].y1&&b[j].x1<=b[i].x2&&b[j].x2>=b[i].x2){
                    b[i].x1=min(b[i].x1,b[j].x1);
                    b[i].y1=min(b[i].y1,b[j].y1);
                    b[i].x2=max(b[i].x2,b[j].x2);
                    b[i].y2=max(b[i].y2,b[j].y2);
                    vis[j]=1;
                    flag=1;
                }
            }
        }
    }
    for(int i=1;i<=type3cnt;i++){
        if(vis[i]) continue;
        c[++cnt2]=b[i];
    }
    
    for(int i=1;i<=cnt2;i++){
        set<pair<int,int>> st;
        for(int j=1;j<=cnt1;j++){
            if(a[j].t==1){
                int tx=c[i].x1+a[j].y1-c[i].y1;
                if(tx<c[i].x1||tx>c[i].x2||tx<1||tx>n) continue;
                if(tx<a[j].x1||tx>a[j].x2) continue;
                pair<int,int> temp={tx,a[j].y1};
                if(st.find(temp)==st.end())
                    --ans,st.insert(temp);
            }
            else if(a[j].t==2){
                int ty=c[i].y1+a[j].x1-c[i].x1;
                if(ty<c[i].y1||ty>c[i].y2||ty<1||ty>m) continue;
                if(ty<a[j].y1||ty>a[j].y2) continue;
                pair<int,int> temp={a[j].x1,ty};
                if(st.find(temp)==st.end())
                    --ans,st.insert(temp);
            }
        }
        ans+=c[i].x2-c[i].x1+1;
    }
    printf("%lld\n",ans);
    return 0;
}

[SHOI2007] 园丁的烦恼

将一个询问拆成四个询问的差分形式，扫描线维护二维前缀和，动态开点线段树代替离散化。
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=5e5+10;
int n,m;
struct node{
    int x,y;
    bool operator<(const node &a)const{return x<a.x;}
}p[N];
int tot,ans[N];
struct Query{
    int x,y,belong,f;
    bool operator<(const Query &a)const{return x<a.x;}
}q[N<<2];
struct Tree{
    int sum;
    Tree *ls,*rs;
}tree[N<<5],*root;
int node_cnt;
inline Tree* new_node(){return &tree[++node_cnt];}
#define val(x) (x==nullptr?0:x->sum)
void modify(Tree *&u,int l,int r,int x){
    if(u==nullptr) u=new_node();
    if(l==r){
        ++u->sum;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(u->ls,l,mid,x);
    else modify(u->rs,mid+1,r,x);
    u->sum=val(u->ls)+val(u->rs);
}
int query(Tree *u,int l,int r,int x,int y){
    if(u==nullptr) return 0;
    if(x<=l&&y>=r) return u->sum;
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(u->ls,l,mid,x,y);
    if(y>mid) res+=query(u->rs,mid+1,r,x,y);
    return res;
}
int now;
int main(){
    read(n,m);
    for(int i=1;i<=n;i++) read(p[i].x,p[i].y);
    sort(p+1,p+1+n);
    for(int i=1,a,b,c,d;i<=m;i++){
        read(a,b,c,d);
        if(a-1>=0&&b-1>=0) q[++tot]={a-1,b-1,i,1};
        q[++tot]={c,d,i,1};
        if(a-1>=0) q[++tot]={a-1,d,i,-1};
        if(b-1>=0) q[++tot]={c,b-1,i,-1};
    }
    sort(q+1,q+1+tot);
    for(int i=1;i<=tot;i++){
        while(now<n&&p[now+1].x<=q[i].x)
            modify(root,0,1e7,p[++now].y);
        ans[q[i].belong]+=query(root,0,1e7,0,q[i].y)*q[i].f;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

[IOI 1998][USACO5.5] 矩形周长 Picture

横线和竖线分开算。注意若出现多条线重合，则必须先处理加再处理删。
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=2e4+10;
int n,val[N<<2],sum[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
inline void push_up(int u,int l,int r){
    if(sum[u]) val[u]=r-l+1;
    else if(l==r) val[u]=0;
    else val[u]=val[ls]+val[rs];
}
void modify(int u,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
        sum[u]+=k;
        push_up(u,l,r);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,k);
    if(y>mid) modify(rs,mid+1,r,x,y,k);
    push_up(u,l,r);
}
struct node{
    int x,a,b,k;
    bool operator<(const node &y)const{return x^y.x?x<y.x:k>y.k;}
}p[N<<1],q[N<<1];
int tot1,tot2,ans;
int main(){
    read(n);
    for(int i=1,a,b,c,d;i<=n;i++){
        read(a,b,c,d);
        p[++tot1]={a,b,d-1,1};
        p[++tot1]={c,b,d-1,-1};
        q[++tot2]={b,a,c-1,1};
        q[++tot2]={d,a,c-1,-1};
    }
    sort(p+1,p+1+tot1);
    sort(q+1,q+1+tot2);
    for(int i=1;i<=tot1;i++){
        int temp=val[1];
        if(p[i].a>p[i].b) swap(p[i].a,p[i].b);
        modify(1,-1e4,1e4,p[i].a,p[i].b,p[i].k);
        ans+=abs(temp-val[1]);
    }
    for(int i=1;i<=tot2;i++){
        int temp=val[1];
        if(q[i].a>q[i].b) swap(q[i].a,q[i].b);
        modify(1,-1e4,1e4,q[i].a,q[i].b,q[i].k);
        ans+=abs(temp-val[1]);
    }
    printf("%d\n",ans);
    return 0;
}

Day8

树上技巧

树的直径的求法：
- 两遍 dfs/bfs（无法处理负边权） - 树形 DP（可以处理负边权）

这两种方法的时间复杂度均为 \(O(n)\)。
树形 DP 具体求法：
设 \(dp_{u,0/1}\) 表示以 \(u\) 为根的子树中从根向下能延伸的最长/非严格次长路径。则答案为 \(dp_{u,0}+dp_{u,1}\) 的最大值。

[APIO2010] 巡逻

老题了。考虑贪心，\(k=1\) 时连接直径两端是显然的。设直径为 \((u_1,v_1)\)，加入的第二条边为 \((u_2,v_2)\)，二者不交时答案显然为 \(dis(u_1,v_1)+dis(u_2,v_2)\)，若两路径有交，形如
则答案为 \(dis(u_1,v_2)+dis(u_2,v_1)\)。由此可以看出，若仍要选在直径上的边，代价会更大。则我们将直径的边权全部设为 \(-1\)，再找一个新的直径。
code 
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
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10;
int n,k,ans,dis[N],a,b,pre[N],head[N],dp[N][2],maxn;
bool vis[N],tag[N];
vector<int> e[N];
void dfs1(int u,bool flag,int &x){
    vis[u]=1;
    for(int v:e[u]){
        if(vis[v]) continue;
        dis[v]=dis[u]+1;
        if(flag) pre[v]=u;
        if(dis[v]>dis[x]) x=v;
        dfs1(v,flag,x);
    }
}
void dfs2(int u,int fa){
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs2(v,u);
        int w=tag[u]&&tag[v]?-1:1;
        int temp=dp[v][0]+w;
        if(temp>dp[u][0])
            dp[u][1]=dp[u][0],dp[u][0]=temp;
        else if(temp>dp[u][1])
            dp[u][1]=temp;
        maxn=max(maxn,dp[u][0]+dp[u][1]);
    }
}
int main(){
    read(n,k);
    for(int i=1,a,b;i<n;i++){
        read(a,b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs1(1,0,a);
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    dfs1(a,1,b);
    if(k==1){
        ans=(n-1)*2-dis[b]+1;
        printf("%d\n",ans);
        return 0;
    }
    for(int i=b;i;i=pre[i]) tag[i]=1;
    dfs2(1,0);
    ans=n*2-dis[b]-maxn;
    printf("%d\n",ans);
    return 0;
}

[NOI2021] 轻重边

结论：每次修改操作染不同颜色，重边数等于区间内相邻两点颜色相同的点对数。树剖+线段树维护即可。精细处理树剖的查询部分。
code 
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
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10;
int t,n,m,siz[N],son[N],dep[N],fa[N],dfn[N],dfncnt,top[N];
vector<int> e[N];
void dfs1(int u,int f){
    fa[u]=f;
    siz[u]=1;
    son[u]=0;
    dep[u]=dep[f]+1;
    for(int v:e[u]){
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int topf){
    dfn[u]=++dfncnt;
    top[u]=topf;
    if(son[u]) dfs2(son[u],topf);
    for(int v:e[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
struct node{
    int lc,rc,cnt;
    inline friend node operator+(const node &a,const node &b){
        if(a.lc==-1) return b;
        if(b.lc==-1) return a;
        node res;
        res.lc=a.lc,res.rc=b.rc;
        res.cnt=a.cnt+b.cnt;
        if(a.rc==b.lc&&a.rc) ++res.cnt;
        return res;
    }
}tree[N<<2];
int tag[N<<2];
int P,DEP;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline void push_down(int u,int siz){
    if(!tag[u]) return;
    tree[ls(u)]=tree[rs(u)]={tag[u],tag[u],(siz>>1)-1};
    tag[ls(u)]=tag[rs(u)]=tag[u];
    tag[u]=0;
}
inline void modify(int l,int r,int k){
    l+=P-1,r+=P+1;
    for(int i=DEP;i;i--) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
    int siz=1;
    while(l^1^r){
        if(~l&1) tree[l^1]={k,k,siz-1},tag[l^1]=k;
        if(r&1) tree[r^1]={k,k,siz-1},tag[r^1]=k;
        l>>=1,r>>=1,siz<<=1;
        tree[l]=tree[ls(l)]+tree[rs(l)];
        tree[r]=tree[ls(r)]+tree[rs(r)];
    }
    for(l>>=1;l;l>>=1) tree[l]=tree[ls(l)]+tree[rs(l)];
}
inline node query(int l,int r){
    node resl={-1},resr={-1};
    l+=P-1,r+=P+1;
    for(int i=DEP;i;i--) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
    while(l^1^r){
        if(~l&1) resl=resl+tree[l^1];
        if(r&1) resr=tree[r^1]+resr;
        l>>=1,r>>=1;
    }
    return resl+resr;
}
void change(int x,int y,int k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        modify(dfn[top[x]],dfn[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(dfn[x],dfn[y],k);
}
int ask(int x,int y){
    int ans=0,c1=0,c2=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]){
            swap(x,y);
            swap(c1,c2);
        }
        node res=query(dfn[top[x]],dfn[x]);
        ans+=res.cnt;
        if(res.rc==c1&&c1) ++ans;
        c1=res.lc;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
        swap(c1,c2);
    }
    node res=query(dfn[x],dfn[y]);
    ans+=res.cnt;
    if(res.rc==c2&&c2) ++ans;
    if(res.lc==c1&&c1) ++ans;
    return ans;
}
int cnt,op,a,b;
int main(){
    read(t);
    while(t--){
        dfncnt=0;
        for(int i=1;i<=n;i++) e[i].clear();
        read(n,m);
        for(int i=1,u,v;i<n;i++){
            read(u,v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs1(1,0);
        dfs2(1,1);
        memset(tree,0,sizeof(node)*(n*4+10));
        memset(tag,0,sizeof(int)*(n*4+10));
        P=1,DEP=0;
        while(P<=n+1) P<<=1,++DEP;
        cnt=0;
        while(m--){
            read(op,a,b);
            if(op==1) change(a,b,++cnt);
            else printf("%d\n",ask(a,b));
        }
    }
    return 0;
}

[十二省联考 2019] 春节十二响

贪心策略：令两条链上各自权值最大的比较，次大的比较……则可以在每个节点开一个堆，启发式合并。不同于可并堆，节点 \(u\)，\(v\) 的堆合并后的大小为 \(\max(size_u,size_v)\) 而非 \(size_u+size_v\)，时间复杂度为 \(O(n\log n)\)。
code 
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
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=2e5+10;
int n,m[N];
ll ans;
vector<int> e[N];
priority_queue<int> q[N];
inline void merge(int x,int y){
    vector<int> temp;
    if(q[x].size()<q[y].size()) swap(q[x],q[y]);
    while(q[y].size()){
        temp.push_back(max(q[x].top(),q[y].top()));
        q[x].pop(),q[y].pop();
    }
    for(int k:temp) q[x].push(k);
}
void dfs(int u){
    for(int v:e[u]){
        dfs(v);
        merge(u,v);
    }
    q[u].push(m[u]);
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(m[i]);
    for(int i=2,f;i<=n;i++)
        read(f),e[f].push_back(i);
    dfs(1);
    while(!q[1].empty()) ans+=q[1].top(),q[1].pop();
    printf("%lld\n",ans);
    return 0;
}

Day9

数论

「TAOI-2」喵了个喵 Ⅳ

神秘题。\(n\) 为偶数时显然。\(n\) 为奇数时先求出所有数的最大公约数 \(d\)，此时取 \(x=2\)，将所有数都约去 \(d\)，此时若有奇数个奇数，则会有偶数个偶数，必然无解，反之则可以按照奇偶容易地构造一组解。最后答案为 \(2d\)。
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10;
int n,a[N],d,cntodd,cnteven;
bool ans[N];
int main(){
    read(n);
    if(n&1){
        for(int i=1;i<=n;i++){
            read(a[i]);
            d=__gcd(d,a[i]);
        }
        for(int i=1;i<=n;i++){
            a[i]/=d;
            if(a[i]&1) ++cntodd;
            else ++cnteven;
        }
        if(cntodd&1){
            printf("-1\n");
            return 0;
        }
        for(int i=1,cnt=0;i<=n&&cnt<cntodd/2-1;i++)
            if(a[i]&1) ans[i]=1,++cnt;
        for(int i=1,cnt=0;i<=n&&cnt<(cnteven+1)/2;i++)
            if(~a[i]&1) ans[i]=1,++cnt;
        printf("%d\n",2*d);
        for(int i=1;i<=n;i++)
            printf("%d",ans[i]);
    }
    else{
        printf("1\n");
        for(int i=1;i<=n/2;i++)
            printf("1");
        for(int i=1;i<=n/2;i++)
            printf("0");
    }
    return 0;
}

[CTSC2017] 吉夫特

这题的转化真是神了。发现题目中 \(\bmod 2\) 很特殊，\(\dbinom{a_{b_1}}{a_{b_2}} \times \dbinom{a_{b_2}}{a_{b_3}} \times \cdots \times \dbinom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 >0\) 成立当且仅当对于任意 \(k>1\)，\(\dbinom{a_{b_{k-1}}}{a_{b_k}}\bmod 2=1\)，我们尝试使用 Lucas 定理展开
\[\binom{a_{b_{k-1}}}{a_{b_k}}\equiv \binom{\lfloor a_{b_{k-1}}/2\rfloor}{\lfloor a_{b_k}/2\rfloor}\binom{a_{b_{k-1}}\bmod 2}{a_{b_k}\bmod 2}\pmod 2\] 持续展开，不难发现其等于两数二进制拆分后每一位的组合数相乘，又因为
\[\binom{1}{1}=\binom{1}{0}=\binom{0}{0}=1\] \[\binom{0}{1}=0\] 所以 \(\dbinom{a_{b_{k-1}}}{a_{b_k}}\bmod 2=1\) 当且仅当 \(a_{b_k}\) 在二进制下是 \(a_{b_{k-1}}\) 的子集，即 \(a_{b_{k-1}} \operatorname{bitand} a_{b_k}=a_{b_k}\)。则我们可以推出 DP 方程，设 \(dp_{i}\) 表示以 \(i\) 为结尾的子序列方案数：
\[dp_{a_i}=\sum_{a_i\in a_j\land j<i}(dp_{a_j}+1)\] \(O(3^{\log{\max(a_i)}})\) 子集枚举即可。
code 
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
#include<cstdio>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int mod=1000000007,N=233350;
int n,a,dp[N],ans;
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a);
        for(int s=(a-1)&a;s;s=(s-1)&a)
            dp[s]=(dp[s]+dp[a]+1)%mod;
        ans=(ans+dp[a])%mod;
    }
    printf("%d\n",ans);
    return 0;
}

Day10

线性代数

[USACO07NOV] Cow Relays G

我们使用 \(\min\) 和 \(+\) 代替原矩阵乘法中的 \(+\) 和 \(\times\)，也就是
\[C_{i,j}=\min(A_{i,k}+B_{k,j})\] 设 \(A_{i,j}\) 表示 \(i\) 到 \(j\) 的最短路，则走 \(n\) 步后的最短路即为 \(A_{i,j}^n\)。
设离散化后点有 \(m\) 个，时间复杂度 \(O(m^3\log n)\)。
code 
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1010,M=210;
int n,t,s,e,a[N],cnt;
struct Edge{int u,v,w;}edge[M];
struct Matrix{
    int x[M][M];
    Matrix(){memset(x,0x3f,sizeof(x));}
    Matrix operator*(const Matrix &a)const{
        Matrix res;
        for(int k=1;k<=cnt;k++)
            for(int i=1;i<=cnt;i++)
                for(int j=1;j<=cnt;j++)
                    res.x[i][j]=min(res.x[i][j],x[i][k]+a.x[k][j]);
        return res;
    }
}b;
Matrix qpow(Matrix a,int b){
    Matrix res=a;
    --b;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int main(){
    read(n,t,s,e);
    for(int i=1,u,v,w;i<=t;i++){
        read(w,u,v);
        if(!a[u]) a[u]=++cnt;
        if(!a[v]) a[v]=++cnt;
        b.x[a[u]][a[v]]=b.x[a[v]][a[u]]=w;
    }
    b=qpow(b,n);
    printf("%d\n",b.x[a[s]][a[e]]);
    return 0;
}

【模板】矩阵求逆

本题中的矩阵均为方阵。
矩阵的逆：在模 \(p\) 意义下，若 \(B\times A=A\times B=I\)，则 \(B\) 称为模 \(p\) 意义下 \(A\) 的逆矩阵，记作 \(A^{-1}\)。模 \(p\) 意义下,一个矩阵若有逆矩阵，则必然只有一个逆矩阵。
矩阵的逆可以用高斯-约旦消元求出。原理：使用初等行变换将矩阵 \(A\) 转化为单位矩阵 \(I\)，同时对一个初始的单位矩阵 \(I\) 进行相同的初等行变换，最终得到的就是逆矩阵 \(A^{-1}\)。
例如，我们构造原矩阵 \([A\mid I]\)，进行一系列初等行变换后，得到 \([I\mid A^{-1}]\)。我们发现，高斯-约旦消元的过程就是将矩阵的左半部分变为单位矩阵的过程，非常适合求解矩阵的逆。
无解判断：若消元过程中，主元与 \(p\) 不互质则无解。
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int mod=1e9+7,N=410;
int n,a[N][N*2];
ll qpow(ll a,int b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(a[i][j]);
    for(int i=1;i<=n;i++)
        a[i][i+n]=1;
    for(int i=1,cur,line=1;i<=n;i++){
        cur=line;
        for(int j=line+1;j<=n;j++)
            if(a[j][i]>a[cur][i])
                cur=j;
        if(__gcd(a[cur][i],mod)!=1){
            printf("No Solution");
            return 0;
        }
        ll inv=qpow(a[cur][i],mod-2);
        for(int j=1;j<=(n<<1);j++)
            swap(a[cur][j],a[line][j]),a[line][j]=a[line][j]*inv%mod;
        for(int j=1;j<=n;j++)
            if(j!=line){
                ll temp=a[j][i];
                for(int k=1;k<=(n<<1);k++)
                    a[j][k]=((a[j][k]-a[line][k]*temp)%mod+mod)%mod;
            }
        ++line;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j+n]);
        printf("\n");
    }
    return 0;
}

Day11/12

离散与组合数学

[HAOI2008] 硬币购物

背包+容斥。首先求出没有任何限制下每种价值的方案数，设 \(dp_s\) 表示价值为 \(s\) 的方案数。子集枚举计算哪些硬币超出限制，若钦定第 \(i\) 中硬币超出限制，则该硬币至少总价值为 \(c_i\times (d_i+1)\)，容斥计算即可。
code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=1e5+10;
int n,c[4],d[4],s;
ll dp[N];
int main(){
    read(c[0],c[1],c[2],c[3],n);
    dp[0]=1;
    for(int i=0;i<4;i++)
        for(int j=c[i];j<=1e5;j++)
            dp[j]+=dp[j-c[i]];
    while(n--){
        read(d[0],d[1],d[2],d[3],s);
        ll ans=dp[s];
        for(int i=0;i<(1<<4);i++){
            ll sum=0;
            int cnt=0;
            for(int j=0;j<4;j++)
                if(i>>j&1) sum+=c[j]*(d[j]+1ll),++cnt;
            int k=cnt&1?-1:1;
            if(s-sum<0||sum==0) continue;
            ans+=k*dp[s-sum];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Devu and Flowers

在无限制时，通过隔板可以得到答案为 \(\dbinom{n+s-1}{n-1}\)，若加上限制则考虑容斥。枚举子集，则状态 \(S\) 中所有子集元素均不合法的方案数为 \(\dbinom{s-\sum_{i\in S}f_i-|S|-1}{n-1}\)。这里不方便直接预处理阶乘算组合数，但是注意到 \(\dbinom{n}{m}\) 中，\(n\) 和 \(m\) 相差不会太大，所以可以直接通分后暴力计算。
code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=25,mod=1e9+7;
typedef long long ll;
int n;
ll qpow(ll a,int b=mod-2){
    a%=mod;
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll s,f[N],inv[N],ans,fact[N];
ll C(ll n,int m){
    if(n<0||m<0||n<m) return 0;
    ll res=1;
    for(ll i=n-m+1;i<=n;i++)
        res=res*(i%mod)%mod;
    return res*inv[m]%mod;
}
int main(){
    read(n,s);
    fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
    inv[n]=qpow(fact[n]);
    for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=0;i<n;i++) read(f[i]);
    for(int i=0;i<(1<<n);i++){
        int cnt=0;
        ll sum=0;
        for(int j=0;j<n;j++)
            if(i>>j&1)
                ++cnt,sum+=f[j];
        int k=cnt&1?-1:1;
        ans=(ans+k*C(s-sum-cnt+n-1,n-1)%mod)%mod;
    }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}

[CSP-S2019 江西] 多叉堆

并查集+组合。考虑合并过程。根一定是 \(0\)，设合并前的大小为 \(size_x\) 和 \(size_y\)，方案数为 \(cnt_x\) 和 \(cnt_y\)，由于子树之间互不干扰，所以 \[cnt_{sum}=cnt_x\cdot cnt_y\cdot \binom{size_x+size_y-1}{size_x}\]
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int mod=1e9+7,N=3e5+10;
ll qpow(ll a,int b=mod-2){
    ll res=1;
    a%=mod;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int n,q,fact[N],inv[N],siz[N],fa[N],cnt[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
ll C(int n,int m){return (ll)fact[n]*inv[m]%mod*inv[n-m]%mod;}
int op,x,y,ans;
int main(){
    read(n,q);
    fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=(ll)fact[i-1]*i%mod;
    inv[n]=qpow(fact[n]);
    for(int i=n-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
        cnt[i]=1;
    }
    while(q--){
        read(op,x);
        x=find((x+ans)%n+1);
        if(op==1){
            read(y);
            y=find((y+ans)%n+1);
            fa[x]=y;
            siz[y]+=siz[x];
            cnt[y]=(ll)cnt[y]*cnt[x]%mod*C(siz[y]-1,siz[x])%mod;
        }
        else{
            ans=cnt[x];
            printf("%d\n",ans);
        }
    }
    return 0;
}

[CEOI 2016] kangaroo

连续段 DP，一种很强的东西。\(dp_{i,j}\) 表示考虑放前 \(i\) 个数，构成 \(j\) 个合法连续段的方案数。在加入一个数时，可以有以下几种情况：
- 并入某一个块，\(dp_{i-1,j}\times j\) 种情况。
- 自成一个新块，\(dp_{i-1,j-1}\times j\) 种情况。
- 将原来的两个块连接，合并成一个块，\(dp_{i-1,j+1}\times j\) 种情况。
特判 \(s\) 和 \(t\) 的限制。
code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=2e3+10,mod=1e9+7;
typedef long long ll;
int n,s,t,dp[N][N];
int main(){
    read(n,s,t);dp[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++){
            if(i==s||i==t) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
            else{
                dp[i][j]=(ll)(j-(i>s)-(i>t))*dp[i-1][j-1]%mod;
                dp[i][j]=(dp[i][j]+(ll)dp[i-1][j+1]*j)%mod;
            }
        }
    printf("%d\n",dp[n][1]);
    return 0;
}

[CSP-S2019] Emiya 家今天的饭

考虑使用总方案数减不合法方案数得到答案。总方案数为 \[\prod_{i=1}^n\left(1+ \sum_{j=1}^ma_{i,j}\right)-1\] 由于超过 \(\lfloor\dfrac{k}{2}\rfloor\) 的食材最多只可能有一个，所以考虑直接枚举是哪一个食材超限。\(dp_{i,j}\) 表示前 \(i\) 种烹饪方案选菜后，选择的菜品数与已选的总数之差为 \(j\)，转移见代码
code 
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
#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=110,M=2010,mod=998244353;
typedef long long ll;
int n,m,a[N][M],sum[N],dp[N][N<<1];
ll ans;
int main(){
    read(n,m);
    ans=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(a[i][j]);
            sum[i]=(sum[i]+a[i][j])%mod;
        }
        ans=ans*(sum[i]+1)%mod;
    }
    ans=(ans-1+mod)%mod;
    for(int i=1;i<=m;i++){
        memset(dp,0,sizeof(dp));
        dp[0][n]=1;
        for(int j=1;j<=n;j++)
            for(int k=n-j;k<=n+j;k++)
                dp[j][k]=(dp[j-1][k]+(ll)dp[j-1][k-1]*a[j][i]%mod+(ll)dp[j-1][k+1]*(sum[j]-a[j][i]+mod)%mod)%mod;
        for(int j=1;j<=n;j++)
            ans=(ans-dp[n][j+n]+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Day13

摆摆摆。

Day14/15

单调队列优化 DP

没错又是我。

[HAOI2007] 修筑绿化带

我们可以将所有 \(C\times D\) 的矩形权值和缩为一个点记录在二维平面上（例如记录在 \(C\times D\) 矩形的右下角），那么题目就是对于每一个 \(A\times B\)，在二维平面上取一个矩形内的最小值，这可以使用单调队列。具体地，按行扫一遍，记录答案，然后再按列扫一遍即可。
code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1010;
int n,m,a,b,c,d,x[N][N],sum[N][N],l,r,minn[N][N],ans;
struct node{int val,id;}q[N];
inline int val(int t1,int t2,int t3,int t4){
    return sum[t3][t4]-sum[t1-1][t4]-sum[t3][t2-1]+sum[t1-1][t2-1];
}
int main(){
    read(n,m,a,b,c,d);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            read(x[i][j]);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x[i][j];
        }
    for(int i=c;i<=n;i++)
        for(int j=d;j<=m;j++)
            minn[i][j]=val(i-c+1,j-d+1,i,j);
    for(int i=1;i<=n;i++){
        l=1,r=0;
        for(int j=1;j<=m;j++){
            while(l<=r&&q[r].val>=minn[i][j]) --r;
            while(l<=r&&j-q[l].id>=b-d-1) ++l;
            q[++r]={minn[i][j],j};
            minn[i][j]=q[l].val;
        }
    }
    for(int i=1;i<=m;i++){
        l=1,r=0;
        for(int j=1;j<=n;j++){
            while(l<=r&&q[r].val>=minn[j][i]) --r;
            while(l<=r&&j-q[l].id>=a-c-1) ++l;
            q[++r]={minn[j][i],j};
            minn[j][i]=q[l].val;
        }
    }
    for(int i=a;i<=n;i++)
        for(int j=b;j<=m;j++)
            ans=max(ans,val(i-a+1,j-b+1,i,j)-minn[i-1][j-1]);
    printf("%d\n",ans);
    return 0;
}

[HAOI2007] 理想的正方形

code 
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<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1010;
int n,m,a[N][N],minn[N][N],maxn[N][N],l,r,x,ans;
struct node{int val,id;}q[N];
int main(){
    read(n,m,x);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        read(a[i][j]),minn[i][j]=maxn[i][j]=a[i][j];
    for(int i=1;i<=n;i++){
        l=1,r=0;
        for(int j=1;j<=m;j++){
            while(l<=r&&j-q[l].id+1>x) ++l;
            while(l<=r&&q[r].val>minn[i][j]) --r;
            q[++r]={minn[i][j],j};
            minn[i][j]=q[l].val;
        }
        l=1,r=0;
        for(int j=1;j<=m;j++){
            while(l<=r&&j-q[l].id+1>x) ++l;
            while(l<=r&&q[r].val<maxn[i][j]) --r;
            q[++r]={maxn[i][j],j};
            maxn[i][j]=q[l].val;
        }
    }
    for(int i=1;i<=m;i++){
        l=1,r=0;
        for(int j=1;j<=n;j++){
            while(l<=r&&j-q[l].id+1>x) ++l;
            while(l<=r&&q[r].val>minn[j][i]) --r;
            q[++r]={minn[j][i],j};
            minn[j][i]=q[l].val;
        }
        l=1,r=0;
        for(int j=1;j<=n;j++){
            while(l<=r&&j-q[l].id+1>x) ++l;
            while(l<=r&&q[r].val<maxn[j][i]) --r;
            q[++r]={maxn[j][i],j};
            maxn[j][i]=q[l].val;
        }
    }
    ans=2e9;
    for(int i=x;i<=n;i++)
        for(int j=x;j<=m;j++)
            ans=min(ans,maxn[i][j]-minn[i][j]);
    printf("%d\n",ans);
    return 0;
}

斜率优化 DP

给定一个长为 \(n\) 的序列，每个位置 \(i\) 有 \(a_i,b_i\)，\(a_i\) 单调递增。
对每个位置 \(i\) 求 \(\max_{j<i}(a_jc_i+b_j)\)。
当 \(c_i\) 单调时，显然可以使用单调队列 \(O(n)\) 解决。
对于每一个 \(a_i,b_i\)，都对应一条直线 \(y=a_ix+b_i\)，直接使用单调队列维护一个上凸壳。

[HNOI2008] 玩具装箱

设 \(dp_i\) 表示考虑前 \(i\) 个玩具时的最小总费用，设 \(sum_i\) 表示 \(C_i\) 的前缀和，容易得到状态转移方程 \[dp_i=\min_{j=0}^{i-1}(dp_j+((sum_i-sum_j)+(i-j-1)-L)^2)\] 设 \(s_i=sum_i+i,L'=L+1\)，方程改写为 \[\begin{aligned} dp_i&=\min_{j=0}^{i-1}(dp_j+(s_i-s_j-L')^2)\\ &=s_i^2-2L's_i+\min_{j=0}^{i-1}(-2s_is_j+dp_j+s_j^2+2L's_j) \end{aligned}\] 容易发现，斜率 \(a_j=-2s_j\)，截距 \(b_j=dp_j+s_j^2+2L's_j\)，这样就可以使用单调队列优化了。时间复杂度 \(O(n)\)。
code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=5e4+10;
int n,L,c[N],l,r,q[N];
ll sum[N],dp[N],s[N];
inline ll X(int j){return s[j];}
inline ll Y(int j){return dp[j]+s[j]*s[j]+2*(L+1)*s[j];}
inline double slope(int i,int j){
    return (double)(Y(j)-Y(i))/(X(j)-X(i));
}
int main(){
    read(n,L);
    for(int i=1;i<=n;i++)
        read(c[i]),sum[i]=sum[i-1]+c[i],s[i]=sum[i]+i;
    int l=1,r=0;
    q[++r]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&slope(q[l],q[l+1])<=2*s[i]) ++l;
        int j=q[l];
        dp[i]=dp[j]+(s[i]-s[j]-(L+1))*(s[i]-s[j]-(L+1));
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r-1],i)) --r;
        q[++r]=i;
    }
    printf("%lld\n",dp[n]);
    return 0;
}

数位 DP

[SCOI2009] windy 数（加强版）

\(dp_{i,j,0/1}\) 表示前 \(i\) 位数（高位），第 \(i\) 位为 \(j\)，是/否被最大限制时的方案数。其中 \(j=10\) 表示高位前导 \(0\)。
code 
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
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[20][11][2],a,b;
string s;
ll dfs(int pos,int pre,bool limit){
    if(pos==(int)s.length()) return (pre!=10);
    if(dp[pos][pre][limit]!=-1) return dp[pos][pre][limit];
    int up=limit?s[pos]-'0':9;
    ll res=0;
    for(int i=0;i<=up;i++){
        if(pre==10){
            if(i==0) res+=dfs(pos+1,10,limit&&(i==up));
            else res+=dfs(pos+1,i,limit&&(i==up));
        }
        else if(abs(i-pre)>=2)
            res+=dfs(pos+1,i,limit&&(i==up));
    }
    dp[pos][pre][limit]=res;
    return res;
}
ll solve(ll x){
    if(x==0) return 0;
    memset(dp,-1,sizeof(dp));
    s=to_string(x);
    return dfs(0,10,1);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<'\n';
    return 0;
}

Day16/17

思维技巧

qmd 学长真的很强啊 orz。
讲了一种很强的思维方式：观察终态。
终态一般代指某个函数/解的形态。

  • 一些题目中需要观察解长什么样子，寻找解可行的必要条件，并尝试证明它们是充要的。这种思路常用于无法通过简单方式描述解的场合。

  • 另一些题目中需要调整，找到并剔除可能出现的不优的结构。这种思路常用于解集过于庞大，合法解缺少特殊性的场合。

  • 还有一些题目中需要观察解的上下界。应用场合为最优化或构造问题。

LIS on Tree 2

首先排列是假的，我们直接考虑 dfs 序。LIS 难以以较低复杂度求出，我们重点关注 \(f(i)\)。一个重要的限制是 \[f(fa_i)\le f(i)\le f(fa_i)+1,\] \[f(1)=1,\] 这样，我们就可以将树划分为若干连通块，每个块内的点对答案贡献相同。构造连通块的方式就是将连通块内的 dfs 序反转，这样就只保留了连通块根部的贡献。这样问题就转化为选择一些子树，使得它们的 \(size\) 之和等于 \(K\)。那么，按照 \(size\) 从大到小贪心地选是正确的，证明考虑剥叶子。这主要运用了第一个思想。

另一种方法叫做规约。

  • 首先我们需要解决一个问题，称为问题 1；

  • 再加如一个问题 2；

  • 若任何能解决问题 1 的算法都能解决问题 2，则说明问题 2 是不强于问题 1 的；

以上就是规约的步骤。容易发现，它实质上是对问题的转化。

Delete AAB or BAA

规约：考虑将原问题转化为：给一个只含 A 和 B 的串，按照 AAB 或 BAA 的形式删除，问能否删成空串。尝试观察终态，发现：

  • 一个子串能被删空的必要条件是 A 的数量是 B 数量的 \(2\) 倍；

  • 若一个串被切成两个子串，且这两个子串能被删空，则它也必然能被删空；

根据观察 2，我们考虑不能被断开但是能被删空的串 ABAAAB 如何描述。
结论：

  • 符合观察 1，且串首位不同的串是可被删空的串。

接下来研究原问题：
约定：\([l,r]\) 表示 \(S\) 从 \(S_l\) 到 \(S_r\) 之间含 \(S_l,S_r\) 的子串。
考虑 dp。设 \(f_i\) 表示 \([1,i]\) 中最多执行的操作数。转移： \[f_i=\max(f_{i-1},\max_{i\le j\le \lfloor i/3\rfloor \land [i-3j+1,i] 能被删空}f_{i-3j}+j)\]