Dylan's Blog
0%

Posted on Edited on In

问题描述：

给定一张含有n个节点m条边的无向图。然后执行q次操作，每次向图中添加一条边，并询问无向图中“桥”的数量。

输入：

有多组数据，每组数据以n (n<=100000) m (m<=200000)开始 然后m行，每行两个数a, b表示ab之间存在一条无向边 然后一个整数q，表示q次操作 接下来q行，每行两个数a, b表示在ab之间加一条无向边 输入以两个0结束

输出：

对于每组数据每个操作，输出操作之后无向图中桥的数量。

思路：

题目也很明确的说到了是要求桥的数量，所以算法一定和边双联通分量有关。

首先是缩点，然后剩下来一棵树，我们可以发现这棵树上的每一条边都属于原无向图中的桥。然后考虑加边操作，每一次操作都使得a, b（边的两个端点）树上路径的边不再是桥了，所以我们就可以将答案减去这些不再是桥的边。

然后考虑如何实现。求树上两点路径依然使用lca，只是这次的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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 200005
using namespace std;

int n, m, q, t, ans, cnt, head[MAXN], a[MAXN], b[MAXN], f[MAXN];
int id, tot, top, low[MAXN], dfn[MAXN], c[MAXN], dep[MAXN], fa[MAXN], sta[MAXN];
bool bridge[MAXN*2], tag[MAXN*2], vis[MAXN];

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

void init()
{
    cnt=1; ans=id=tot=top=0;
    for(int i=0; i<=MAXN-5; i++) head[i]=low[i]=dfn[i]=dep[i]=c[i]=vis[i]=0;
    for(int i=1; i<=MAXN; i++) f[i]=i;
    for(int i=0; i<=MAXN*2-5; i++) bridge[i]=tag[i]=0;
}

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

void tarjan(int x, int in)
{
    low[x]=dfn[x]=++id;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!dfn[to])
        {
            tarjan(to, i);
            low[x]=min(low[x], low[to]);
            if(low[to]>dfn[x]) bridge[i]=bridge[i^1]=1;
        }
        else if(i!=(in^1)) low[x]=min(low[x], dfn[to]);
    }
}

void dfs1(int x, int tot)
{
    c[x]=tot; vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(bridge[i] || vis[to]) continue;
        dfs1(to, tot);
    }
}

void dfs2(int x, int father)
{
    fa[x]=father;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==father) continue;
        dep[to]=dep[x]+1; ans++;
        dfs2(to, x);
    }
}

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void lca(int x, int y)
{
    x=find(x); y=find(y);
    while(x!=y)
    {
        if(dep[x]>dep[y]) sta[++top]=x, x=find(fa[x]);
        else sta[++top]=y, y=find(fa[y]);
        ans--;
    }
    while(top) f[sta[top--]]=x;
}

int main()
{
    while(scanf("%d%d", &n, &m) && n && m)
    {
        init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d", &a[i], &b[i]);
            addedge(a[i], b[i]);
            addedge(b[i], a[i]);
        }
        tarjan(1, 0);
        for(int i=1; i<=n; i++) if(!vis[i]) dfs1(i, ++tot);

        cnt=1;
        for(int i=1; i<=MAXN-5; i++) head[i]=0;
        for(int i=1; i<=m; i++)
        {
            if(c[a[i]]==c[b[i]]) continue;
            addedge(c[a[i]], c[b[i]]);
            addedge(c[b[i]], c[a[i]]);
        }
        dfs2(1, 0);

        printf("Case %d:\n", ++t);
        scanf("%d", &q);
        for(int i=1; i<=q; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            lca(c[x], c[y]);
            printf("%d\n", ans);
        }
    }
}

Posted on Edited on In

7月9日 Codeforces Round #494 题目链接：http://codeforces.com/contest/1003

A - Polycarp’s Pockets & B - Binary String Constructing

比较水，不说了。

C - Intense Heat

思路： 比较好的一题。这题用到了一点分数规划的思想。

首先二分答案，设二分的值为$mid$，然后将原序列全部减去$mid$，如果长度大于k的最大子序和大于等于0，则符合要求。有长度限制的最大子序和也是一个比较重要的模型，利用DP的思想进行维护。

代码：

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

int n, k;
double a[5005], b[5005];

bool check(double mid)
{
    for(int i=1; i<=n; i++) b[i]=a[i]-mid, b[i]+=b[i-1];
    double minn=1e9, maxn=-1e9;
    for(int i=k; i<=n; i++)
    {
        minn=min(minn, b[i-k]);
        maxn=max(maxn, b[i]-minn);
    }
    if(maxn>=0) return 1;
    else return 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%lf", &a[i]);
    double l=0, r=5000, mid;
    while(fabs(l-r)>eps)
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.8lf\n", mid);
}

D - Coins and Queries

思路： 这道题比较水。。。

因为硬币面值都是2的整数幂，所以存面值的log2就可以了。然后对于每一个询问，利用类似于二进制分解的操作，看能不能由硬币凑出来。

代码：

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

int n, q, num[50], temp;

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &temp);
        num[(int)log2(temp)]++;
    }
    for(int i=1; i<=q; i++)
    {
        scanf("%d", &temp);
        int ans=0;
        for(int j=(int)log2(temp); j>=0; j--)
        {
            int t=temp/(1<<j);
            temp-=min(t, num[j])*(1<<j);
            ans+=min(t, num[j]);
            if(temp==0) break;
        }
        if(temp==0) printf("%d\n", ans);
        else printf("-1\n");
    }
}

E - Tree Constructing

思路： 构造题。。码力是真的不够，菜死了QWQ。。。

首先满足直径的条件，先构造一个长度为d的链。然后再满足其它条件，对于链上的每一个点进行拓展，在这个点上尽可能多的放子节点。如果还有节点放不下，就是无解啦。。 代码：

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

int n, d, k, tot;

vector< pair<int, int> > edge;

void dfs(int x, int deg, int dep)
{
    if(dep==0) return;
    for(int i=0; i<deg; i++)
    {
        if(tot>=n) return;
        int y=++tot;
        edge.push_back({x, y});
        dfs(y, k-1, dep-1);
    }
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    if(k==1 && n>2) {printf("NO\n"); return 0;}
    for(int i=1; i<=d; i++) edge.push_back({i, i+1});
    tot=d+1;
    for(int i=2; i<=d; i++) dfs(i, k-2, min(i-1, d-i+1));
    if(n==tot)
    {
        printf("YES\n");
        for(int i=0; i<edge.size(); i++) printf("%d %d\n", edge[i].first, edge[i].second);
    }
    else printf("NO\n");
}

F - Abbreviation

思路： 超级好的一题。。结合了字符串和DP。

设第i个和第j个字符串后有$f[i][j]$个连续字符串相等。然后f数组可以预处理出来。然后比较暴力的枚举起始字符串i和长度j。将这段进行压缩，然后对于每个i和j枚举出有多少个串能够这样压缩，用这个更新答案。

总结一下，其实也不能说是DP。只是利用了一下预处理优化了一下暴力。

代码：

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

int n, ans, len, f[305][305];
string str[305];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) cin>>str[i], len+=str[i].size();
    len+=n-1; ans=len;
    for(int i=n; i>=1; i--)
        for(int j=n; j>=1; j--)
            if(str[i]==str[j]) f[i][j]=f[i+1][j+1]+1;

    for(int i=1; i<=n; i++)
    {
        int sum=0;
        for(int j=0; j+i<=n; j++)
        {
            int cnt=1;
            sum+=str[i+j].size();
            for(int pos=i+j+1; pos<=n; pos++)
                if(f[i][pos]>j) cnt++, pos+=j;

            int temp=len-sum*cnt+cnt;
            if(cnt>1 && ans>temp) ans=temp;
        }
    }
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述：

给定n个闭合的整数区间$[ai，bi]$和n个整数$c1，…，cn$。你需要求出集合$Z$最小的元素数量，使集合$Z$对于每一个区间$[ai，bi]$中都有$c$个整数。

输入：

第一行$n (n<=50000)$，表示有n个区间 接下来n行，每行包含$ai, bi, ci$三个整数，其中$0 <= ai <= bi <= 50000$

输出：

输出集合$Z$可能的最小元素数量。

思路：

首先这题有一种贪心的做法，以前用过这种做法，所以我们重点在差分约束上。

这是一道比较基础的差分约束。同样建边是重点，对于每个区间，$bi$之前元素个数$-ai$之前元素个数要$>=ci$，所以我们在$ai，bi$间连一条长度为$ci$的单向边。同样，由于每个点上最多只能放零或一个元素，所以要从每个点$i$向前一个点$i-1$连一条长度为-1的边，从$i$向$i+1$连一条长度为0的边。

建完图以后，由于是求最小值，按照套路用SPFA跑一遍最长路。由于题目保证了有解，所以不需要加特判，输出dis[maxn]就好。

代码：

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

int n, cnt, maxn, head[MAXN*4], dis[MAXN];
bool vis[MAXN];

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

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

void spfa()
{
    queue<int> q;
    memset(dis, -0x3f, sizeof(dis));
    dis[0]=0; vis[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b+1, c);
        maxn=max(maxn, b+1);
    }
    for(int i=0; i<maxn; i++) addedge(i, i+1, 0), addedge(i+1, i, -1);
    spfa();
    printf("%d\n", dis[maxn]);
}