Dylan's Blog
0%

Posted on Edited on In

问题描述：

给你一张有n个节点的图，其中有（n-1)条“主要边”构成一棵树，和m条“附加边”。你需要把这张图分为两个不连通的部分，你可以切除一条“主要边”和一条“附加边”，问你有多少种方案。

输入：

第一行两个整数n, m $(1<=m, n<=100000)$ 接下来n-1行表示n-1条主要边 接下来m行表示附加边

输出：

输出方案总数

思路：

这道题目的思路比较巧妙。首先考虑当我们切除一条主要边时，把树分为了两部分，但这两部分可能有附加边让它们保持联通。显然，如果没有附加边让它们保持联通，那么就有m种方案（随便切一条就OK了）。如果有一条附加边让它们联通，那么就只有1种方案，如果有大于一条附加边时，就没有符合要求的方案。

我们可以记录每一条附加边两端之间的树上路径，那么路径上的每一条边都有一条附加边让它们联通。这时我们就可以利用树上差分+LCA统计出每一条主要边有多少条附加边让它们保持联通，最后算出答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 1000005
using namespace std;

int n, m, ans, cnt, id, head[MAXN], num[MAXN], tag[MAXN], dfn[MAXN], ver[MAXN], dep[MAXN], logn[MAXN], f[MAXN][30];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void solve(int x, int fa)
{
    num[x]+=tag[x];
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        solve(to, x);
        num[x]+=num[to];
    }
    if(x==1) return;
    if(num[x]==0) ans+=m;
    if(num[x]==1) ans++;
}

void dfs(int x, int fa, int deep)
{
    dfn[x]=++id; ver[id]=x; dep[id]=deep;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to, x, deep+1);
        ver[++id]=x;
        dep[id]=deep;
    }
}

void init()
{
    logn[1]=0;
    for(int i=1; i<=n*2-1; i++) f[i][0]=i;
    for(int i=2; i<=n*2-1; i++) logn[i]=logn[i/2]+1;
    for(int i=1; (1<<i)<=n; i++)
    {
        for(int j=1; j+(1<<i)-1<=n*2-1; j++)
        {
            int x=f[j][i-1], y=f[j+(1<<(i-1))][i-1];
            if(dep[x]<dep[y]) f[j][i]=x;
            else f[j][i]=y;
        }
    }
}

int rmq(int l, int r)
{
    int k=logn[r-l+1];
    int x=f[l][k], y=f[r-(1<<k)+1][k];
    if(dep[x]<dep[y]) return ver[x];
    else return ver[y];
}

int lca(int x, int y)
{
    int l=dfn[x], r=dfn[y];
    if(l>r) swap(l, r);
    return rmq(l, r);
}

int main()
{
    int x, y;
    scanf("%d%d", &n, &m);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs(1, 0, 0);
    init();
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        tag[x]++; tag[y]++;
        tag[lca(x, y)]-=2;
    }
    solve(1, 0);
    printf("%d\n", ans);
}

Posted on Edited on In

6月23日 AtCoder Regular Contest 99 题目链接：https://arc099.contest.atcoder.jp/

C - Minimization

思路： 最后序列的所有元素一定是序列中的最小值，然后每一次操作都能让序列中k-1个元素变为最小值，直接扫一遍就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define  LL long long
using namespace std;

int n, k;
LL ans;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i+=k) ans++, i--;
    printf("%lld\n", ans);
}

D - Snuke Numbers

思路： 比较神奇的一题！我们设一个增量为d，即下一个数比这个数大d。d开始是为1，后面d要么保持不变，要么乘上10，这样我们就对每一个数都计算d需不需要乘10就可以了。（其实不是很明白为什么，有一点迷）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;

LL k, n, d=1;

int s(LL x)
{
    int sum=0;
    while(x) sum+=x%10, x/=10;
    return sum;
}

int main()
{
    scanf("%lld", &k);
    for(int i=1; i<=k; i++)
    {
        if((n+d*10)*s(n+d)<(n+d)*s(n+d*10)) d*=10;
        n+=d;
        printf("%lld\n", n);
    }
}

E - Independence

思路： 特别好的一题。题目简化来说就是要你找两个完全子图，并且使子图中的边数最少。

考虑这张图的补图，如果补图是二分图，则存在着两个完全子图，否则输出-1。（这个画一下应该不难发现）我们对补图进行二分图染色，但要注意补图可能不连通，所以有多种染色方法。这时染成同一种颜色的节点在原图中是构成了完全图的，于是我们记录所有可能的染色方法，对于所有方法计算答案并去其中的最小值就OK了。

代码：

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

int n, m, a, b, s1, s2, ans=INF, temp[1500], col[705], f[705];
bool mmp[705][705], vis[1005];

void dfs(int x, int color)
{
    if(vis[x])
    {
        if(col[x]!=color) {printf("-1\n"); exit(0);}
        return;
    }
    vis[x]=1; col[x]=color;
    if(color==1) s1++;
    else s2++;
    for(int i=1; i<=n; i++)
    {
        if(mmp[x][i]==0) continue;
        dfs(i, 3-color);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &a, &b);
        mmp[a][b]=mmp[b][a]=1;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j) mmp[i][j]=0;
            else mmp[i][j]^=1;
        }
    }
    f[0]=1;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]) continue;
        s1=s2=0;
        dfs(i, 2);
        for(int i=0; i<=n; i++)
        {
            temp[i+s1]|=f[i];
            temp[i+s2]|=f[i];
        }
        for(int i=0; i<=n; i++)
        {
            f[i]=temp[i];
            temp[i]=0;
        }
    }
    for(int i=0; i<=n; i++) 
        if(f[i]) ans=min(ans, i*(i-1)/2+(n-i)*(n-i-1)/2);
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述：

在一个地区中有n(3≤n≤100000)个村庄，编号为 1, 2, …, n。有 n – 1 条道路连接着这些村 庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号 为 1 的村庄里，每天巡警车总是从警察局出发，最终又回到警察局。

为了减少总的巡逻距离，该地区准备在这些村庄之间建立 K 条新的道路， 每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束。 一条新道路甚至可以是一个环，即，其两端连接到同一 个村庄。 由于资金有限，K 只能是 1 或 2。同时，为了不浪费资金，每天巡警车必须 经过新建的道路正好一次。

试编写一个程序，读取村庄间道路的信息和需要新建的道路数，计算出最佳 的新建道路的方案使得总的巡逻距离最小，并输出这个最小的巡逻距离。

输入：

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1 行，每行两个整数 a, b， 表示村庄 a 与 b 之间有一条道路(1 ≤ a, b ≤ n)。

输出：

输出一个整数，表示新建了 K 条道路后能达到的最小巡逻距离。

思路：

我们先考虑k=1的情况，这应该不难想到就是求树的直径（最长链），然后答案就是$(n-1)*2-len+1$($len$为直径）。

然后考虑k=2的情况，也可以用同样的思路，找树的直径。同样先找出第一个最长链然后更新答案，但第二次找最长链时要考虑第一个最长链造成的影响。这时我们可以想到将第一条直径上边权取反然后再找第二条边就OK了，然后再用长度更新答案$ans=ans-len+1$。

我们考虑如何找直径，一般有两种放方法，第一种是树形DP，还有一种是两边bfs。这个地方要注意最长链取反之后会出现负边权，用bfs的方法会出现BUG，只能用树形DP的方法。

我码完了BFS的代码后跑样例才发现了这个BUG，先弄清思路再开始码真的很重要！！！

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
using namespace std;

int n, k, root, cnt=1, ans, temp, vis[MAXN], dis[MAXN], head[MAXN], son1[MAXN*2], son2[MAXN*2];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=1;
    head[from]=cnt;
}

int dfs(int x, int fa)
{
    int len1=0, len2=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int len=dfs(to, x)+edge[i].dis;
        if(len>len1)
        {
            len2=len1; len1=len;
            son2[x]=son1[x]; son1[x]=i;
        }
        else if(len>len2) len2=len, son2[x]=i;
    }
    if(len1+len2>temp) temp=len1+len2, root=x;
    return len1;
}

int main()
{
    scanf("%d%d", &n, &k);
    ans=n*2-2;
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs(1, 0);
    ans-=temp-1;
    if(k==2)
    {
        temp=0;
        for(int i=son1[root]; i; i=son1[edge[i].to]) edge[i].dis=edge[i^1].dis=-1;
        for(int i=son2[root]; i; i=son1[edge[i].to]) edge[i].dis=edge[i^1].dis=-1;
        dfs(1, 0);
        ans-=temp-1;
    }
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述：

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)

输入：

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号。

输出：

对于操作3,4,5,6每行输出一个数，表示对应答案。

思路：

模板题，也没什么好说的呢。

代码：

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

int n, ans, tot, root;

struct Treap {int l, r, val, rank, cnt, size;} t[MAXN];

void update(int p)
{
    t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt;
}

int findrank(int p, int val)
{
    if(p==0) return 0;
    if(val==t[p].val) return t[t[p].l].size+1;
    if(val<t[p].val) return findrank(t[p].l, val);
    return findrank(t[p].r, val)+t[t[p].l].size+t[p].cnt;
}

int findval(int p, int rank)
{
    if(p==0) return 0;
    if(t[t[p].l].size>=rank) return findval(t[p].l, rank);
    if(t[t[p].l].size+t[p].cnt>=rank) return t[p].val;
    return findval(t[p].r, rank-t[t[p].l].size-t[p].cnt);
}

void zig(int &p)
{
    int q=t[p].l;
    t[p].l=t[q].r; t[q].r=p; p=q;
    update(t[p].r); update(p);
}

void zag(int &p)
{
    int q=t[p].r;
    t[p].r=t[q].l; t[q].l=p; p=q;
    update(t[p].l); update(p);
}

void insert(int &p, int val)
{
    if(p==0)
    {
        t[++tot].val=val; t[tot].rank=rand();
        t[tot].cnt=t[tot].size=1; p=tot;
        return;
    }
    if(val==t[p].val) t[p].cnt++;
    if(val<t[p].val)
    {
        insert(t[p].l, val);
        if(t[p].rank<t[t[p].l].rank) zig(p);
    }
    if(val>t[p].val)
    {
        insert(t[p].r, val);
        if(t[p].rank<t[t[p].r].rank) zag(p);
    }
    update(p);
}

void remove(int &p, int val)
{
    if(p==0) return;
    if(val==t[p].val)
    {
        if(t[p].cnt>1)
        {
            t[p].cnt--;  update(p);
            return;
        }
        if(t[p].l*t[p].r==0) p=t[p].l+t[p].r;
        else if(t[t[p].l].rank>t[t[p].r].rank) zig(p), remove(p, val);
        else zag(p), remove(p, val);
    }
    if(val<t[p].val) remove(t[p].l, val);
    if(val>t[p].val) remove(t[p].r, val);
    update(p);
}

void findpre(int p, int x)
{
    if(p==0) return;
    if(t[p].val<x) ans=p, findpre(t[p].r, x);
    else findpre(t[p].l, x);
}

void findnext(int p, int x)
{
    if(p==0) return;
    if(t[p].val>x) ans=p, findnext(t[p].l,x);
    else findnext(t[p].r,x);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if(opt==1) insert(root, x);
        if(opt==2) remove(root, x);
        if(opt==3) printf("%d\n", findrank(root, x));
        if(opt==4) printf("%d\n", findval(root, x));
        if(opt==5) ans=0, findpre(root, x), printf("%d\n", t[ans].val);
        if(opt==6) ans=0, findnext(root, x), printf("%d\n", t[ans].val);
    }
}

Posted on Edited on In

问题描述：

给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段） 请你写一个程序依次完成这m个操作。

输入：

第一行包含2个整数n和m，分别表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜色 下面n-1行每行包含两个整数x和y，表示x和y之间有一条无向边。 下面m行每行描述一个操作： “C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c； “Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出：

对于每个询问操作，输出一行答案。

思路：

数据结构题。。。思维含量不高，要注意很多细节

首先对于树上路径的操作和询问一般不难想到用树剖。然后就考虑如果维护一个序列的颜色段数量，以及修改操作。这种序列问题一般用线段树维护，线段树节点储存：左端及右端颜色，区间颜色段总数，lazytag。up函数也稍微修改一下。这样就解决了在序列上的问题。

接着考虑树剖，对于树上区间的合并要注意特殊处理链的左右端点问题，要分别记录两条链的端点颜色，在合并时要分清是那一条链。

代码：

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
154
155
156
157
158
159
#include<bits/stdc++.h>
#define ls (root<<1)
#define rs (root<<1|1)
#define mid (l+r>>1)
#define MAXN 100005
using namespace std;

int n, m, ans, cnt, head[MAXN], w[MAXN];
int sum[MAXN*4], lcol[MAXN*4], rcol[MAXN*4], tag[MAXN*4];
int ind, Lcol, Rcol, val[MAXN], id[MAXN], f[MAXN], size[MAXN], dep[MAXN], son[MAXN], top[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void up(int root)
{
    sum[root]=sum[ls]+sum[rs];
    if(rcol[ls]==lcol[rs]) sum[root]--;
    lcol[root]=lcol[ls];
    rcol[root]=rcol[rs];
}

void down(int root, int l, int r)
{
    if(!tag[root]) return;
    sum[rs]=sum[ls]=1;
    lcol[ls]=rcol[ls]=tag[root];
    lcol[rs]=rcol[rs]=tag[root];
    tag[ls]=tag[rs]=tag[root];
    tag[root]=0;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        sum[root]=1;
        lcol[root]=rcol[root]=val[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    up(root);
}

void update(int root, int l, int r, int x, int y, int k)
{
    if(l>y || r<x) return;
    if(l>=x && r<=y)
    {
        sum[root]=1;
        tag[root]=rcol[root]=lcol[root]=k;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, k);
    update(rs, mid+1, r, x, y, k);
    up(root);
}

void query(int root, int l, int r, int x, int y)
{
    if (l>y || r<x) return;
    if(l==x) Lcol=lcol[root];
    if(r==y) Rcol=rcol[root];
    if(x<=l && y>=r)
    {
        ans+=sum[root];
        return;
    }
    down(root, l, r);
    query(ls, l, mid, x, y);
    query(rs, mid+1, r, x, y);
    if(mid>=x && mid+1<=y && rcol[ls]==lcol[rs]) ans--;
}

void dfs1(int x, int fa)
{
    int maxson=-1; f[x]=fa; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        size[x]+=size[to];
        if(size[to]>maxson) son[x]=to, maxson=size[to];
    }
}

void dfs2(int x, int topf)
{
    id[x]=++ind; val[ind]=w[x]; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f[x] && to!=son[x]) dfs2(to, to);
    }
}

void update1(int x, int y, int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y);
        update(1, 1, n, id[top[x]], id[x], k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y);
    update(1, 1, n, id[x], id[y], k);
}

int query1(int x, int y)
{
    int last1=0, last2=0; ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y), swap(last1, last2);
        query(1, 1, n, id[top[x]], id[x]);
        if(Rcol==last1) ans--;
        last1=Lcol;
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y), swap(last1, last2);
    query(1, 1, n, id[x], id[y]);
    if(Lcol==last1) ans--;
    if(Rcol==last2) ans--;
    return ans;
}

int main()
{
    int x, y, a, b, c; char opt;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%d%d", &opt, &a, &b);
        if(opt=='C') {scanf("%d", &c); update1(a, b, c);}
        if(opt=='Q') printf("%d\n", query1(a, b));
    }
}