Day7

扫描线

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

[NOI2023] 方格染色

横竖线就是扫描线板题。斜线最多只有 55 个，暴力将能够合并的斜线合并，然后遍历所有横竖线判断是否有交。懒得写离散化了，直接动态开点线段树也能过。

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;
}

Day8

树上技巧

树的直径的求法：

  • 两遍 dfs/bfs（无法处理负边权）
  • 树形 DP（可以处理负边权）

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

[APIO2010] 巡逻

老题了。考虑贪心，k=1k=1 时连接直径两端是显然的。设直径为 (u1,v1)(u_1,v_1)，加入的第二条边为 (u2,v2)(u_2,v_2)，二者不交时答案显然为 dis(u1,v1)+dis(u2,v2)dis(u_1,v_1)+dis(u_2,v_2)，若两路径有交，形如

则答案为 dis(u1,v2)+dis(u2,v1)dis(u_1,v_2)+dis(u_2,v_1)。由此可以看出，若仍要选在直径上的边，代价会更大。则我们将直径的边权全部设为 −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] 春节十二响

贪心策略：令两条链上各自权值最大的比较，次大的比较……则可以在每个节点开一个堆，启发式合并。不同于可并堆，节点 uu，vv 的堆合并后的大小为 max⁡(sizeu,sizev)\max(size_u,size_v) 而非 sizeu+sizevsize_u+size_v，时间复杂度为 O(nlog⁡n)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」喵了个喵 Ⅳ

神秘题。nn 为偶数时显然。nn 为奇数时先求出所有数的最大公约数 dd，此时取 x=2x=2，将所有数都约去 dd，此时若有奇数个奇数，则会有偶数个偶数，必然无解，反之则可以按照奇偶容易地构造一组解。最后答案为 2d2d。

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] 吉夫特

这题的转化真是神了。发现题目中  mod 2\bmod 2 很特殊，(ab1ab2)×(ab2ab3)×⋯×(abk−1abk) mod 2>0\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>1k>1，(abk−1abk) mod 2=1\dbinom{a_{b_{k-1}}}{a_{b_k}}\bmod 2=1，我们尝试使用 Lucas 定理展开

(abk−1abk)≡(⌊abk−1/2⌋⌊abk/2⌋)(abk−1 mod 2abk mod 2)(mod2)\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

持续展开，不难发现其等于两数二进制拆分后每一位的组合数相乘，又因为

(11)=(10)=(00)=1\binom{1}{1}=\binom{1}{0}=\binom{0}{0}=1

(01)=0\binom{0}{1}=0

所以 (abk−1abk) mod 2=1\dbinom{a_{b_{k-1}}}{a_{b_k}}\bmod 2=1 当且仅当 abka_{b_k} 在二进制下是 abk−1a_{b_{k-1}} 的子集，即 abk−1bitand⁡abk=abka_{b_{k-1}} \operatorname{bitand} a_{b_k}=a_{b_k}。则我们可以推出 DP 方程，设 dpidp_{i} 表示以 ii 为结尾的子序列方案数：

dpS=∑S∈i(dpai+1)dp_{S}=\sum_{S\in i} (dp_{a_i}+1)

O(3log⁡max⁡(ai))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⁡\min 和 ++ 代替原矩阵乘法中的 ++ 和 ×\times，也就是

Ci,j=min⁡(Ai,k+Bk,j)C_{i,j}=\min(A_{i,k}+B_{k,j})

设 Ai,jA_{i,j} 表示 ii 到 jj 的最短路，则走 nn 步后的最短路即为 Ai,jnA_{i,j}^n。
设离散化后点有 mm 个，时间复杂度 O(m3log⁡n)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;
}