Dylan's Blog
0%

Posted on Edited on In

问题描述:

简单来说，就是给你一棵树，在直径上找一个长度不超过s的链，使得偏心距最小。偏心距的定义为：树上到这条链最远的节点到这条链的距离。

输入:

包含n行： 第1行，两个正整数n和s。其中n为树网结点的个数，s为树网的核的长度的上界。 从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。

注：NOIP原题数据:n<=300，BZOJ加强数据:n<=500000

输出:

只有一个非负整数，为指定意义下的最小偏心距。

思路:

首先想NOIP数据范围的做法，因为我们找的链是在直径上。所以我们可以先处理出直径再暴力枚举直径上的链。因为链长要小于等于ｓ，我们可以枚举一个端点，然后尽可能远的在链上找到另一个端点。这样我们就$O(n)$暴力枚举处理所有链，对于每一条链用一次dfs找出偏心距就OK了。

然后再考虑BZOJ加强版数据，枚举一个端点，然后尽可能远的在链上找到另一个端点。但是我们可以不需要对于每一条链都找出偏心距，我们可以利用直径的性质$O(n)$统一处理出答案。

代码:

$O(n^2)$暴力:

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 3005
#define INF 0x3f3f3f3f
using namespace std;

int n, s, root, cnt, ans=INF, ecc, head[MAXN], dis[MAXN], pre[MAXN];
bool vis[MAXN];

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

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

void bfs(int root)
{
    queue<int> q;
    vis[root]=true; q.push(root);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            pre[to]=x; vis[to]=true;
            dis[to]=dis[x]+edge[i].dis;
            q.push(to);
        }
    }
}

void getline()
{
    int maxdis=0;
    bfs(1);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    memset(dis, 0, sizeof(dis));
    bfs(root);
    maxdis=0;
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
}

void dfs(int x, int fa, int dis)
{
    ecc=max(ecc, dis);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dfs(to, x, edge[i].dis+dis);
    }
}

void solve()
{
    for(int x=root; x; x=pre[x])
    {
        int y=0, len=0; ecc=0;
        memset(vis, 0, sizeof(vis));
        for(int i=x; i; i=pre[i])
        {
            for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to==pre[i]) len+=edge[j].dis;
            y=i; vis[i]=true;
            if(len>s) break;
        }
        for(int i=x; ; i=pre[i])
        {
            dfs(i, 0, 0);
            if(i==y) break;
        }
        ans=min(ans, ecc);
    }
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve();
    printf("%d\n", ans);
}

$O(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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define LL long long
#define MAXN 500005

LL min(LL x, LL y) {if(x<y) return x; return y;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

int n, s, lpnt, rpnt, cnt, head[MAXN], pre[MAXN];
LL  ans=1e18, dis[MAXN];
bool vis[MAXN];

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

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

void dfs(int x, int fa)
{
    pre[x]=fa;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dis[to]=dis[x]+edge[i].dis;
        dfs(to, x);
    }
}

void getline()
{
    LL maxdis=0; dis[1]=0;
    dfs(1, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], lpnt=i;
    maxdis=0; dis[lpnt]=0;
    dfs(lpnt, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], rpnt=i;
}

void solve()
{
    int l=rpnt, r=rpnt;
    for(; l; l=pre[l])
    {
        while(pre[r] && dis[l]-dis[pre[r]]<=s) r=pre[r];
        ans=min(ans, max(dis[rpnt]-dis[l], dis[r]));
    }
    for(int i=rpnt; i; i=pre[i]) vis[i]=true;
    for(int i=rpnt; i; i=pre[i]) dis[i]=0, dfs(i, pre[i]);
    for(int i=1; i<=n; i++) ans=max(ans, dis[i]);
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve(); 
    printf("%lld\n", ans);
}

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