Posted on | In

普通treap：

参考https://www.csdn.net/gather_2a/MtTacg3sMTE0NS1ibG9n.html

cf702f：

将所有人的钱数放入平衡树，每次按照可选衣服的价格将树一分为二，对于有购买能力的一棵树上的人钱数减去衣服价格，然后将剩余钱数小于c-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
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
#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define ls ch[now][0]
#define rs ch[now][1]
int n,m,root;
pair<int,int>a[N];
int val[N],ch[N][2],lzy_val[N],lzy_cnt[N],rnd[N],cnt[N];
void pushdown(int now){	//将修改的根节点的值扩散下去
    if(!now)
        return;
    if(lzy_val[now]){
        val[ls]+=lzy_val[now];val[rs]+=lzy_val[now];
        lzy_val[ls]+=lzy_val[now];lzy_val[rs]+=lzy_val[now];
        lzy_val[now]=0;
    }
    if(lzy_cnt[now]){
        cnt[ls]+=lzy_cnt[now];cnt[rs]+=lzy_cnt[now];
        lzy_cnt[ls]+=lzy_cnt[now];lzy_cnt[rs]+=lzy_cnt[now];
        lzy_cnt[now]=0;
    }
}
/*
void pushup(int now){
    siz[now]=siz[ls]+siz[rs]+1;
}
*/
//按值split,如果按树的规模split需要再pushup一次
void split(int rt,int &x,int &y,int v){
    if(!rt){ x=y=0;return;}
    pushdown(rt);
    if(val[rt]<=v){
        x=rt;
        split(ch[rt][1],ch[x][1],y,v);
    }else{
        y=rt;
        split(ch[rt][0],x,ch[y][0],v);
    }
}
int merge(int x,int y){
    if(!x||!y)
        return x+y;
    if(rnd[x]<rnd[y]){
        pushdown(x);
        ch[x][1]=merge(ch[x][1],y);
        //pushup(x);
        return x;
    }else{
        pushdown(y);
        ch[y][0]=merge(x,ch[y][0]);
        //pushup(y);
        return y;
    }
}
int insert(int rt,int x){
    int r1=0,r2=0;
    split(rt,r1,r2,val[x]);
    r1=merge(r1,x);
    rt=merge(r1,r2);
    return rt;
}

void down(int now){
    if(!now)
        return;
    pushdown(now);
    down(ls);down(rs);
}
int main(){
    scanf("%d",&n);
    for(int i=1,c,q;i<=n;i++){
        scanf("%d%d",&c,&q);
        a[i]=make_pair(-q,c);
    }
    sort(a+1,a+1+n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&val[i]);
        rnd[i]=rand();
        root=insert(root,i);
    }
    for(int i=1;i<=n;i++){
        int c=a[i].second;
        int r1=0,r2=0,r3=0,r4=0;
        split(root,r1,r2,c-1);
        val[r2]-=c;lzy_val[r2]-=c;
        cnt[r2]++;lzy_cnt[r2]++;
        split(r2,r3,r4,c-2);
        queue<int> q;
        q.push(r3);
        while(!q.empty()){
            int now=q.front();
            pushdown(now);
            q.pop();
            if(ls){
                q.push(ls);
                ls=0;
            }
            if(rs){
                q.push(rs);
                rs=0;
            }
            r1=insert(r1,now);
        }
        root=merge(r1,r4);
    }
    down(root);
    for(int i=1;i<=m;i++)
        printf("%d ",cnt[i]);
    return 0;
}

可持久性treap模板：

洛谷P3835

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+4;
int n;

struct node{
    int l,r,rand,val,siz;
}tree[40*maxn];	//保险吧，其实30*就够
int rt[maxn];

struct pir{
    int first,second;
    pir(int _fi,int _se){
        first=_fi;
        second=_se;
    }
};


int new_node(int val=0){
    static int cnt;
    cnt++;
    tree[cnt].val=val;
    tree[cnt].rand=rand();
    tree[cnt].siz=1;
    return cnt;
}

int cpy_node(int src){
    int now=new_node();
    tree[now]=tree[src];
    return now;
}

void pushup(int o){
    tree[o].siz=tree[tree[o].l].siz+tree[tree[o].r].siz+1;
}

pir split(int k,int val){   //<=val的为第一棵树，>val的在第二棵树中
    pir res(0,0);
    if(!k)
        return res;
    int now=cpy_node(k);
    if(val<tree[k].val){
        res=split(tree[k].l,val);
        tree[now].l=res.second;
        res.second=now;
    }
    else{
        res=split(tree[k].r,val);
        tree[now].r=res.first;
        res.first=now;
    }
    pushup(now);
    return res;
}

int merge(int x,int y){ //按参数传递顺序保证有序性
    if(x==0 || y==0)
        return x+y;
    if(tree[x].rand<tree[y].rand){
        tree[x].r=merge(tree[x].r,y);
        pushup(x);
        return x;
    }
    else{
        tree[y].l=merge(x,tree[y].l);
        pushup(y);
        return y;
    }
}

void insert(int pre,int now,int val){   //pre是在哪个版本上操作
    pir tmp=split(rt[pre],val);
    rt[now]=merge(tmp.first,merge(new_node(val),tmp.second));
}

//对着别人的模板实现的时候，两次错误都出在这里
void del(int pre,int now,int val){
    pir l=split(rt[pre],val-1);
    pir r=split(l.second,val);
    r.first=merge(tree[r.first].l,tree[r.first].r); //对于可能有多个val的情况，这一步使得只去掉一个val
    rt[now]=merge(l.first,merge(r.first,r.second));
}

int v2r(int pre,int now,int val){   //val to rank
    pir rt1=split(rt[pre],val-1);
    int res=tree[rt1.first].siz;//由于有-INF，不再+1
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int r2v(int now,int rnk){
    int k=now;
    while(rnk<=tree[tree[k].l].siz||rnk>tree[tree[k].l].siz+1){
        if(rnk<=tree[tree[k].l].siz)
            k=tree[k].l;
        else{
            rnk-=(tree[tree[k].l].siz+1);
            k=tree[k].r;
        }
    }
    return tree[k].val;
}

int r2v(int pre,int now,int rnk){
    rt[now]=rt[pre];
    return r2v(rt[now],rnk+1);  //考虑到插入的-INF
}

int pred(int pre,int now,int val){	//比val小的上一个元素
    pir rt1=split(rt[pre],val-1);
    int res=r2v(rt1.first,tree[rt1.first].siz);
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int succ(int pre,int now,int val){	//比val大的下一个元素
    pir rt1=split(rt[pre],val);
    int res=r2v(rt1.second,1);
    rt[now]=merge(rt1.first,rt1.second);
    return res;
}

int main(){
    srand(time(0));
    insert(0,0,-2147473647);
    insert(0,0,2147483647);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v,opt,x;
        cin>>v>>opt>>x;
        if(opt==1){
            insert(v,i,x);
        }else if(opt==2){
            del(v,i,x);
        }else if(opt==3){
            cout<<v2r(v,i,x)<<endl;
        }else if(opt==4){
            cout<<r2v(v,i,x)<<endl;
        }else if(opt==5){
            cout<<pred(v,i,x)<<endl;
        }else{
            cout<<succ(v,i,x)<<endl;
        }
    }
    return 0;
}

Posted on | In

本质是记忆化搜索，一般求解区间[l,r]内有多少数字满足要求。我们可以拆分问题为solve(r)-solve(l-1)或solve(r)-solve(l)+judge(l)。注意到整个区间（例如[0,999]）在很多地方重复使用，所以对它记录。

例题：cf628D

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
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int maxn=2e3+1;
const int maxm=2e3+1;
char a[maxn],b[maxn];
int num[maxn];
int m,d;
#define ll long long
ll dp[maxn][maxm];
int len;

int judge(const char* s,int lena){
    int mod=0;
    for(int i=1;i<=lena;i++){
        mod=(mod*10+s[i])%m;
        if((i&1)==0&&s[i]!=d){
            return 0;
        }
        if((i&1)&&s[i]==d)
            return 0;
    }
    return (mod==0);
}
int val[maxn];
ll dfs(int pos,int mod,bool limit){
    if(pos==len+1){
        /*if(mod==0){
            for(int i=1;i<pos;i++)
                printf("%d",val[i]);
            puts("");
        }*/
        return mod==0;
    }
    if(!limit&&dp[pos][mod]!=-1)
        return dp[pos][mod];
    int up=(limit?num[pos]:9);
    ll res=0;
    for(int i=0;i<=up;i++){
        int tmod=(mod*10+i)%m;  //模拟除法
        if((pos&1)&&(i==d))
            continue;
        if(!(pos&1)&&(i!=d))
            continue;
        //val[pos]=i;
        res=(res+dfs(pos+1,tmod,limit&&i==up))%MOD;
    }
    if(!limit)      //当处于非limit的时候，ans才是整个区间的值
        dp[pos][mod]=res;
    return res;
}

ll solve(const char* s,int lena){
    for(int i=1;i<=lena;i++)
        num[i]=s[i];
    len=lena;
    memset(dp,-1,sizeof(dp));
    return dfs(1,0,true)%MOD;
}

int main(){
    cin>>m>>d;
    cin>>(a+1);
    cin>>(b+1);
    int lena=strlen(a+1),lenb=strlen(b+1);
    for(int i=1;i<=lena;i++)
        a[i]-='0';
    for(int i=1;i<=lenb;i++)
        b[i]-='0';
    cout<<((solve(b,lenb)-solve(a,lena)+judge(a,lena))%MOD+MOD)%MOD<<endl;      //注意+MOD的操作，因为取MOD后可能会导致solve(a)>solve(b)
    return 0;
}

Posted on | In

​ 直接介绍复杂度最低（O(n+m)）的Hierholzer方法。它能帮我们找到一条欧拉回路。

​ 欧拉回路指不重复经过所有边的一条回路，在有向图中，如果满足每个点入度=出度则存在欧拉回路。在无向图中，满足每个点度数为偶数则存在欧拉回路。它具有这样的性质，即从一个欧拉图中去除一个小欧拉图，剩下的仍是欧拉图，去除一个点及其所连边同样。由此产生了Hierholzer算法。

​ 算法整体是一个dfs过程，总是尝试用一个回路来代替点u，于是我们对从u发出的边，只要是未标记的，就沿着它去搜下一个点，同时利用“引用”技巧将搜过确定下来的边删除，这样复杂度就不会退化。如果需要记录路径，选择用栈，在搜索过一个点所有的边后压栈这个点，这个时候栈中已经存了从该点出去的所有环。如果需要求字典序最小的，对边预先排序即可。

​ 对于无向图，我们依然建双向有向图，然后每次检查时要两条边均未标记才继续。

例题：cf547d

给出2e5棋盘上若干点，要求将其染成黑白两色，使得每一行每一列黑白数量之差不超过1.

我们作这样一个变换：将横纵坐标单独视为点，棋子所在的点视为x、y之间连边，意义就是通过对x染色，对y也产生了影响，我们可以将x点的边按出入分开染成不同的颜色，每条边都代表一个实际的（x，y）点，这样只要出边入边数量相差不超过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
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+3;

struct edge{
    int to,next;
}es[maxn<<2];
int head[maxn<<1];
int cnt=1;
inline void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
    es[++cnt]=(edge){u,head[v]};
    head[v]=cnt;
}
int du[maxn<<1];
int vis[maxn<<2];   //标记某条边是否被涂色

void dfs(int x){
    for(int &i=head[x];i;i=es[i].next){	//引用是降低复杂度的关键
        if(vis[i]||vis[i^1])			//如果一对边均未染色
            continue;
        vis[i]=1;
        dfs(es[i].to);
    }
    //记录回路就在这记录x即可
}
int n;
int main(){
    cin>>n;
    int x,y;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        y+=2e5;
        add(x,y);
        du[x]++,du[y]++;
    }
    int lst=0;
    for(int i=1;i<=4e5;i++){
        if(du[i]&1){
            if(lst) add(lst,i),lst=0;
            else lst=i;
        }
    }
    for(int i=1;i<=4e5;i++){
        if(du[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;++i)
        putchar(vis[i<<1]?'b':'r'); //由于两条边中的一条肯定被标记，只需认定偶数边是一种颜色即可
    puts("");
    return 0;
}

Posted on | In

二分用于在单调序列上以logn的时间确定某个值，三分则用在凸函数上，即先增后减序列，可以找它的极值。我们需要mid=(l+r)/2和midmid=(mid+r)/2这两个分界点，前者大则令r=midmid，否则令l=mid。

例题：cf939E

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+1;

double a[maxn];
double sum[maxn];

int p,q;

#define cal(k) (a[p]-(a[p]+sum[k])/(k+1))


int main(){
    cin>>q;
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            double x;
            cin>>x;
            a[++p]=x;
            sum[p]=sum[p-1]+a[p];
        }else{
            int l=1,r=p;	//三分
            while(l<r-1){
                int mid=(l+r)/2;
                int midmid=(mid+r)/2;
                if(cal(mid)<cal(midmid)){
                    l=mid;
                }else{
                    r=midmid;
                }
            }
            double ans=max(cal(l),cal(r));
            printf("%.6f\n",ans);
        }
    }
    return 0;
}

Posted on | In ,

lca即最近公共祖先，倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。

思路：预处理出fa[n][i]数组，表示第n号点的第（1<<i）个父亲，之后在寻找u、v的lca时，可以对二进制上的每一位进行向上跳跃。

例题：cf1304E

给出一棵树，有q个询问，格式（x，y，a，b，k）。意为对x，y点连边，求问此时从a到b有无一条长为k的路径，边可以重复走。

分析：边可以重复走说明如果一条路径长度小于k，且与k奇偶性相同，那么就可以重复走某些边来满足要求。添加bian（x，y）后，我们一共有三条可行的基础路径（a，b）、（a，x）+1+（y，b）、（a，y）+1+（x，b）。依次检查即可。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+1;

struct edge{
    int to,next;
}es[maxn*2];
int head[maxn];
int cnt;
void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}

int fa[maxn][31],dep[maxn];
void dfs(int o,int from){
    fa[o][0]=from;
    dep[o]=dep[fa[o][0]]+1;
    for(int i=1;i<31;i++){      //处理出o点的父亲链
        fa[o][i]=fa[fa[o][i-1]][i-1];
    }
    for(int i=head[o];i;i=es[i].next){
        int v=es[i].to;
        if(v==from) continue;
        dfs(v,o);
    }
}

int lca(int u,int v){
    if(dep[u]>dep[v])
        swap(u,v);
    int cha=dep[v]-dep[u];
    for(int i=0;(1<<i)<=cha;i++){   //拉平深度的差距
        if(cha&(1<<i)){
            v=fa[v][i];
        }
    }
    if(u==v) return u;
    for(int i=30;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[v][0];    //返回lca
}
int n,q;
int main(){
    cin>>n;
    int u,v;
    for(int i=0;i<n-1;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    cin>>q;
    int x,y,a,b,k;
    while(q--){
        cin>>x>>y>>a>>b>>k;
        bool f=false;
        int len=dep[a]+dep[b]-2*dep[lca(a,b)];
        if(len<=k&&(!((k-len)&1)))
            f=true;
        len=dep[a]+dep[x]-2*dep[lca(a,x)]+dep[b]+dep[y]-2*dep[lca(b,y)]+1;
        if(len<=k&&(!((k-len)&1)))
            f=true;
        len=dep[a]+dep[y]-2*dep[lca(a,y)]+dep[b]+dep[x]-2*dep[lca(b,x)]+1;
        if(len<=k&&(!((k-len)&1)))
            f= true;
        printf(f?"YES\n":"NO\n");
    }
    return 0;
}

Posted on | In

cf1304D

题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。

思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约束的结果串。

证明：这种方法利用了全部的上升区间，及下降区间的一侧边界。我们知道对于连续下降区间，最多只能有一个元素被选入LIS，因此整体利用率达到最大。

最短的类似，首先降序n~1，然后不满足约束的reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=0;i<n;i++)
    ans[i]=i+1;
l=0,r=0;
for(int i=0;i<n-1;i++){
    if(cst[i]=='>'){
        r=i+1;
    }else{
        if(l<r)
            reverse(ans+l,ans+r+1);
        l=i+1;
    }
}
if(l<r)
    reverse(ans+l,ans+r+1);
for(int i=0;i<n;i++){
    printf("%d%c",ans[i],(i==n-1?'\n':' '));
}

cf1350D

https://codeforces.com/contest/1350/problem/D

给一个序列，可以将其中任意一段全部改成该段中位数的大小，中位数如果是偶数长度则取n/2位置。问最后能否把序列所有值都改为k。

首先可以发现，如果我们手上有两个连续的k，那么必能实现（一步一步转化）；如果一个k都没有则必不可能实现。如果只有一些不连续的k呢？这个情况稍微复杂一点，我们发现，如果一个k和一个比它大的数相邻，那么可以转化为两个连续k。这里我们为了方便把a的值分为0、1、2，代表小于、等于和大于k。如果有两个相同的值相邻或者只间隔一个数，那么有办法把任意长的序列都转化为该值。那么我们就要求，必定存在一组11、12、22是相邻的或间隔一，如果是前两者那么可以直接从那里构造出等于k的序列，如果是后者则可以构造2序列直到临近k，然后执行12转化；如果说12的间隔都大于1，那么序列最后不可能转化为0以外的数，失败。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;
int a[maxn],t,n,k;

int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        int f=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>k) a[i]=2;
            else if(a[i]==k) f=1,a[i]=1;
            else a[i]=0;
        }
        if(f&&n>1){
            f=0;
            for(int i=1;i<=n-1;i++){
                if((a[i]&&a[i+1])||(i<=n-2&&a[i]&&a[i+2])){
                    f=1;
                    break;
                }
            }
        }
        cout<<(f?"yes":"no")<<endl;
    }
}

cf1365F

对字符串定义这样一种操作：交换前缀和后缀。然后问字符串a经过若干次操作能不能变成b。2e5

最初看的时候理解成前后缀做轴对称，心想那不是简单，结果发现是交换……字符串的方向不变。

可以这样去理解交换操作：两个字符串分别向着彼此的方向移动，直到占据对方的位置。这样来看交换操作又变得对称了起来。然后就很容易发现一个性质：位于对称位置的字符，不管怎么交换，它们依然是一对。这样我们就得出一个结论，要想变换得到b字符串，首先要字符间的成对的关系是一致的。

接下来我们证明如果成对关系一致必然可以转换。我们可以从中间字符开始向两边一一变化，面临的任务就是要把一对靠边近的点转移到靠边远的一对位置上，我们发现最多三次就可以，并且不会用到更靠内的字符。也就是能在不影响之前成果的基础上转移成功。

所以只需要字符的成对关系一致就可以了，存一下pair，排序完比较一下，再特判一下奇数的中间元素相同。

Posted on | In ,

2-sat用于解决这样一类问题：给出n个二元组，每个二元组必选出一个元素，而这些元素间可能有互斥的情况，要求给出合理方案。我们可以知道，对于二元组，如果因为被排斥而不选择某个元素，那么意味着必定选择另一个，这就使得问题可解，3-sat及以上似乎没有多项式算法……？

tarjan方法

利用tarjan算法求出每个点所属scc，如果二元组两个点位于同一个scc中则无解。输出方案时，输出两点中scc编号较小的一个即可，因为它处在这个dag的下游。上游点则会达到下游的点。

例题cf780d：n个俱乐部，两种选缩写方案，一种是俱乐部名字前三个字母，另一种是俱乐部名字前两个字母+城市首字母。

要求缩写不能有重复，且如果有俱乐部选择了方式2，那么不得有名字前三位相同的俱乐部采用方式1。求一种合法取名方案。

思路：每个俱乐部两种方案且各个方案间有互斥关系，故用2-sat解决，用这2n种方案建图，并根据规则连上对应的边。

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
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+1;
struct edge{
    int to,next;
}es[maxn*maxn*4];
int cnt,n;
int head[maxn*2];
void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}

int stk[maxn*2];	//栈中存当前scc的点，可能也会存上一个scc的点
int dfn[maxn*2];//标号，dfs序
int low[maxn*2];//所属scc的最小标号
int scc[maxn*2];//某点属于哪个scc
bool in[maxn*2];//在栈中
int top,tot,ind;    //tot是强连通分量scc的个数
void tarjan(int x){
    stk[++top]=x;
    in[x]=1;
    dfn[x]=low[x]=++ind;
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);  //更新完v后回过头来用v更新x，之所以不用dfn[v]更新是因为dfn[v]大于dfn[x]
        }else if(in[v])
            low[x]=min(low[x],dfn[v]);	//如果发现可达点在栈中，说明已经和它形成环了，
    }
    if(dfn[x]==low[x]){
        tot++;
        do{
            scc[stk[top]]=tot;
            in[stk[top]]=0;
        }while(x!=stk[top--]);	//当=的时候，说明已经到逻辑栈底啦
    }
}
bool solve(){
    for(int i=1;i<=n*2;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(scc[i]==scc[i+n])
            return false;
    }
    return true;
}

inline int shift(int x){
    if(x>n) return x-n;
    return x+n;
}
string name[maxn*2];
int main(){
    cin>>n;
    string team,home;
    for(int i=1;i<=n;i++){
        cin>>team>>home;
        name[i]=team.substr(0,3);
        name[i+n]=team.substr(0,2)+home[0];
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            if(i==j) continue;
            if(name[i]==name[j]){
                add(i,shift(j));
                if(i<=n&&j<=n)
                    add(i+n,j+n);
            }
        }
    }
    if(solve()){
        printf("YES\n");
        for(int i=1;i<=n;i++){
            string res=(scc[i]<scc[i+n]?name[i]:name[i+n]);
            cout<<res<<endl;
        }
    }else{
        printf("NO\n");
    }
    return 0;
}

暴搜方法

思想类似，搜索某个点就意味着要选择某个点，那么搜进去第一步检查一下相对点是否被选择就可以了，如果选择了就直接返回false

Posted on | In

C++标准模板库（STL）封装了大量十分有用的数据结构和算法，熟练使用STL将会使我们的程序编写如虎添翼。接下来会介绍几种在程序竞赛中常用到的STL类。如果想了解更多，推荐直接访问官方文档搜索查阅

[TOC]

bitset

可以理解为bit这个数据类型的数组（即取值只为0/1），大多数情况下，每个元素所占内存确实只有1bit，是bool类型的1/8。方便各种位操作的进行。

构造方法

都需要在定义时指明长度

1
2
3
4
5
6
7
8
默认：
std::bitset<16> foo;	//填充0

整数：
std::bitset<16> foo(0x1111);	//0001000100010001

std::string
std::bitset<4> foo(std::string("1010"));	//1010

位操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[]:
类似数组直接访问

.count():
返回一个bitset中1的个数
    
.size():
返回一个bitset的长度
    
.any():
返回一个bool值，表示这个bitset中是否至少有一个1，与.none()相反

.all():
返回一个bool值，表示这个bitset中是否全为1

.set():
将bitset全置1
.set(size_t pos, bool val = true)
将pos位上元素置val值

整体操作

1
2
3
to_string()	//convert to std::string
to_ulong()	//convert to unsigned long
to_ullong()	//convert to unsigned long long

priority_queue

优先队列（默认）的本质是一个大根堆，它的top元素始终是最大的。

优先队列的底层container默认是vector。

构造方法

1
2
3
std::priority_queue<int, std::vector<int>, std::greater<int> > pq(first,last);
//指定比较函数greater，变为小根堆
//first和last是储存初始化数据的数组指针

成员函数

1
2
3
4
5
.empty(): return true if it's empty
.size(): return size    
.top(): 获取顶部元素
.push(): 插入元素
.pop(): remove top element

pair

保存了一个有序对，两个元素分别为first和second，可以有不同类型

重载函数

1
2
3
4
5
6
7
8
9
10
头文件<utility>
    
关系比较：
先比较first，再比较second

swap(p1,p2):
交换两个同类型的pair object
    
get<I>(pair p)
I为0时返回first元素，为1时返回second

构造

1
2
3
4
5
6
7
8
普通构造方式略。
    
很多其他stl数据结构中有用到make_pair函数
template <class T1,class T2>
  pair<T1,T2> make_pair (T1 x, T2 y)
  {
    return ( pair<T1,T2>(x,y) );
  }

lower_bound

参数(first, last, x)，原数组已从小到达排序

在[first, last)中找到第一个>=x的元素的位置

upper_bound是找到第一个>x的元素位置

这两个函数中，如果找不到满足要求的，返回last

auto

可遍历vector和map

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    map<int, string> mp;
    mp.insert(pair<int,string>(2,"hello"));
    mp.insert(pair<int,string>(1,"miaomiaomiao"));
    mp.insert(pair<int,string>(3,"world"));
    
    for(auto &p : mp)
	    cout << p.first << endl; 
    return 0;
}

输出1、2、3

可见是按照key值遍历组成map的这些pair

string

1
2
string::substr()
string substr (size_t pos = 0, size_t len = npos) const;返回子串

map

1
2
3
4
5
6
重载[](key_type k)
等价于(*((this->insert(make_pair(k,mapped_type()))).first)).second
如果mp中存在匹配到k的pair，则返回这个pair.second的引用
否则插入一个新的pair，second值为0
    
    对于计数类型的输入，我们可以每次mp[x]+=1;它会从0开始向上加

vector

可用vector:reserve(n)进行预先内存分配

vector成员函数

1
2
3
.back()取最后一个元素值
.front()取第一个
.pop_back()弹出最后一个，如果打算删除多个数据用erase

set

内部是一棵红黑树，有序存储元素。（默认升序）

1
2
3
4
5
6
7
set.erase(iterator或value):返回删除元素的下一个iterator	或
set.erase(iterator first,iterator last):抹去[first,last)区间，返回抹去元素数量
                                           
set.lower_bound&upper_bound(value)
                                           
不能存同值元素。
insert插入元素，find寻找值等于某一元素的iterator找不到返回end，count存在返回1否则返回0

Posted on | In

点、线段

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
const double eps=1e-8;
inline int sgn(double x){
    if(fabs(x)<eps) return 0;
    else if(x<0) return -1;
    else return 1;
}

struct Point{
    double x,y;
    Point(){
        x=0;
        y=0;
    }
    Point(double a,double b):x(a),y(b){}
    inline Point operator-(const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
    inline Point operator+(const Point& b)const{
        return Point(x+b.x,y+b.y);
    }
    inline double dot(const Point& b)const{
        return x*b.x+y*b.y;
    }
    inline double cross(const Point&b,const Point& c)const{
        return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);
    }
    double operator^(Point a){return x*a.y-y*a.x;}
    double operator*(Point a){return x*a.x+y*a.y;}
};

double dist(const Point& a, const Point& b){
    return sqrt((b-a).dot(b-a));
}



//得线段交点
Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d) {
     double u = a.cross(b, c), v = b.cross(a, d);
     return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}

//判断线段和直线相交 poj3304
//s-e是直线
bool check(const Point& s,const Point& e){
    if(sgn(dist(s,e))==0) return false;	//注意特殊情况，线段退化为点时会造成共线的误判
    for(int i=0;i<n;i++){
        if(sgn(s.cross(lines[i][0],e))*sgn(s.cross(lines[i][1],e))>0)
           return false;
    }
    return true;
}

凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Point stk[maxn];
bool operator<(const Point& a,const Point& b){
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int Andrew(){	//逆时针扫描
    sort(ps,ps+n);
    int top=0;
    for(int i=0;i<n;i++){
        while(top>1&&sgn((stk[top-1]-stk[top-2])^(ps[i]-stk[top-1]))<=0) top--;
        stk[top++]=ps[i];
    }
    int k=top;
    for(int i=n-2;i>=0;i--){
        while(top>k&&sgn((stk[top-1]-stk[top-2])^(ps[i]-stk[top-1]))<=0) top--;
        stk[top++]=ps[i];
    }
    return top;	//凸包点数
}//结果点集逆时针存放在stk中

半平面交

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
//poj3335求多边形有无核

struct Line {
    Point s, e;
    Line() {}
    Line(Point a, Point b) {s = a, e = b;}
};
double getAngle(Line a){
    return atan2(a.e.y-a.s.y,a.e.x-a.s.x);
}
bool operator<(Line a,Line b){
    double A=getAngle(a);
    double B=getAngle(b);
    if(fabs(A-B)<eps) return ((a.e-a.s)^(b.e-a.s))>0;  //把靠右的排在前面
    else return A<B;
}
Point getIntersectPoint(Line a,Line b){     //用线段b的两点坐标组合成交点坐标
    double u=a.s.cross(a.e,b.e);
    double v=a.e.cross(a.s,b.s);
    return Point((v*b.e.x+u*b.s.x)/(u+v),(v*b.e.y+u*b.s.y)/(u+v));
}


bool onRight(Line a,Line b,Line c){ //判断bc交点是否在a的右边
    Point o=getIntersectPoint(b,c);
    if(((a.e-a.s)^(o-a.s))<0)   //这里不能取等，也许是因为能留下一条边就尽量留？这样tail-head的合法判定更易满足
        return true;
    return false;
}

Line lines[maxn];
Line que[maxn];
Point ps[maxn];
int n;

bool HalfPlaneIntersect(){
    sort(lines,lines+n);
    int head=0,tail=0,cnt=0;
    for(int i=0;i<n-1;i++){
        if(fabs(getAngle(lines[i])-getAngle(lines[i+1]))<eps){
            continue;
        }
        lines[cnt++]=lines[i];
    }
    lines[cnt++]=lines[n-1];

    for(int i=0;i<cnt;i++){
        while(tail-head>1&&onRight(lines[i],que[tail-1],que[tail-2]))   //用新边优化队尾
            tail--;
        while(tail-head>1&&onRight(lines[i],que[head],que[head+1])) //用新边优化队首
            head++;
        que[tail++]=lines[i];
    }
    while(tail-head>1&&onRight(que[head],que[tail-1],que[tail-2]))
        tail--;
    while(tail-head>1&&onRight(que[tail-1],que[head],que[head+1]))
        head++;
    if(tail-head<3)
        return false;
    return true;
}

bool judge() {  //判断点的顺序是逆时针
  double ans = 0;
  for(int i=1; i<n-1; i++) {
    ans += ((ps[i]-ps[0])^(ps[i+1]-ps[0]));
  }
  return ans>0;
}
int t;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>ps[i].x>>ps[i].y;
        if(judge()){
            for(int i=0;i<n;i++)
                lines[i]=Line(ps[i],ps[(i+1)%n]);
        }else{
            for(int i=0;i<n;i++){
                lines[i]=Line(ps[(i+1)%n],ps[i]);
            }
        }
        if(HalfPlaneIntersect()){
            printf("YES\n");
        }else
            printf("NO\n");
    }
    return 0;
}

旋转卡壳

求多边形最长直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//注意它的思想，实际情况中可能求的不是直径
double rotating_caliper(Point* ps){
    double res=0;
    if(n==2){
        res=dist(ps[0],ps[1]);
    }else{
        int j=2;
        ps[n]=ps[0];	//省的再对i取模……
        for(int i=0;i<n;i++){
            while(ps[i].cross(ps[i+1],ps[j])<ps[i].cross(ps[i+1],ps[j+1]))
                j=(j+1)%n;
            res=max(res,max(dist(ps[i],ps[j]),dist(ps[i+1],ps[j])));
        }
    }
    return res;
}

Posted on | In , ,

题目给出一个有向图，要求阻挡其中的一些边，使得从1到n的最短路径变长，阻挡一条边的代价是这条边的长度。

问题其实就转化为，找到从1到n的所有最短路，并在这些路中找到能阻挡最短路的一些边且边权和最小——也就是找到最短路构成图的最小割。

找所有最短路可以贪心地去找合适的边，什么样的边(u, v)是合适的呢？从1到u，从v到n的最短距离之和等于整体最短路减去这条边权时，意味着这条边可以放在一条最短路中。我们就把它加入新图的集合。

然后对新图求最大流即可。Dinic算法，正常复杂度为$n^2m$，在求解二分图最大匹配时复杂度是$m\sqrt{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
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int t,n,m;
const int maxn=1e4+4;
struct edge{
    int to;
    ll cap,flow;
    edge(int _to,ll _cap,ll _flow):to(_to),cap(_cap),flow(_flow){}
};

typedef pair<ll,int> P;
vector<edge> G[maxn],invG[maxn],sG[maxn];
ll d[maxn],invd[maxn];

void dijkstra(){
    priority_queue<P,vector<P>,greater<P>> que;
    memset(d,inf,sizeof(d));
    que.push(P(0,1));
    d[1]=0;
    while(!que.empty()){
        P p=que.top();que.pop();	//队列里存着被更新过的点
        int u=p.second;
        if(p.first>d[u])    //这个点的值已经过时了，且由于在把它从队列里拿出来之前已经更新为更小值，它甚至已经做过跳板，没有必要再做了
            continue;
        for(int i=0;i<G[u].size();i++){
            edge e=G[u][i];
            if(d[u]+e.cap<d[e.to]){
                d[e.to]=d[u]+e.cap;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    memset(invd,inf,sizeof(invd));
    que.push(P(0,n));
    invd[n]=0;
    while(!que.empty()){
        P p=que.top();que.pop();
        int u=p.second;
        if(p.first>invd[u])    //之前有更优的，已经是第二次用这个点，相当于vis[u]=1，就直接弃用
            continue;
        for(int i=0;i<invG[u].size();i++){
            edge e=invG[u][i];
            if(invd[u]+e.cap<invd[e.to]){
                invd[e.to]=invd[u]+e.cap;
                que.push(P(invd[e.to],e.to));
            }
        }
    }
}


struct Dinic {
    int n,m,s, t;
    vector<edge> edges;
    vector<int> G[maxn];	//储存边在edges中的下标
    int d[maxn], cur[maxn];
    bool vis[maxn];

    void init(int n) {
        for(int i = 1; i <= n; i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int cap) {
        edges.push_back(edge(to, cap, 0));
        edges.push_back(edge(from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);	//记录刚加入的两条边
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];	//还有增广路
    }

    ll DFS(int x, ll a) {
        //a是当前可允许的最大流量
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) {
            edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;	//因为一次必定添加一对，所以原边下标是偶数，反向边是奇数
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    ll Maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, inf);
        }
        return flow;
    }
};

int main(){
    cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        int u,v,c;
        for(int i=1;i<=n;i++){
            G[i].clear();
            invG[i].clear();
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&c);
            G[u].push_back(edge(v,c,0));
            invG[v].push_back(edge(u,c,0)); //添加反向边
        }
        dijkstra();
        Dinic dinic;
        dinic.init(n);
        for(int i=1;i<=n;i++){
            for(int j=0;j<G[i].size();j++){
                if(d[i]+G[i][j].cap+invd[G[i][j].to]==d[n]){
                    dinic.AddEdge(i,G[i][j].to,G[i][j].cap);
                }
            }
        }
        cout<<dinic.Maxflow(1,n)<<endl;
    }
    return 0;
}