Dylan's Blog
0%

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

Posted on Edited on In

问题描述：

FJ的奶牛们找到了一张详细的城市地图，上面标注了城市中所有$L(2 <= L <= 1000)$座标志性建筑物（建筑物按1..L顺次编号），以及连接这些建筑物的$P(2 <= P <= 5000)$条单向道路。

FJ会开车将奶牛们送到某个她们指定的建筑物旁边，等奶牛们完成她们的整个旅行并回到出发点后，将她们接回农场。对于编号为i的标志性建筑物，奶牛们清楚地知道参观它能给自己带来的乐趣值$F_i (1 <= F_i <= 1000)$。 奶牛们同样仔细地研究过城市中的道路。她们知道第i条道路两端的建筑物$ L1_i$和$L2_i$ 以及她们从道路的一头走到另一头所需要的时间$T_i(1 <= T_i <= 1000)$

奶牛们希望她们在一整天中平均每单位时间内获得的乐趣值最大。当然咯，奶牛们不会愿意把同一个建筑物参观两遍，也就是说，虽然她们可以两次经过同一个建筑物，但她们的乐趣值只会增加一次。 请你写个程序，帮奶牛们计算一下她们能得到的最大平均乐趣值。

输入：

第一行两个整数L, P（见上文定义） 接下来L行，每行一个数$F_i $ 接下来P行每行三个数：$ L1_i$，$L2_i$，$T_i$

输出：

一个两位小数，最大的单位时间平均乐趣。

思路：

比较简单的一道分数规划吧。二分答案，然后按照套路重新建图。新图上每条边的权值为$边权*mid-端点点权$，然后判断图中是否存在负环。

判断负环有一个特别巧妙的方法，就是跑一遍SPFA，记录松弛操作次数。如果操作次数大于了点的个数，那么就一定存在负环。

代码：

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 <queue>
#include <cmath>
#include <cstring>
#include <queue>
#define MAXN 1005
#define MAXE 5005
#define INF 2e9
#define eps 1e-4
using namespace std;

int n, m, cnt, f[MAXN], u[MAXE], v[MAXE], w[MAXE], head[MAXN], num[MAXN];
bool vis[MAXN];
double dis[MAXN];

struct Edge {int to, next; double dis;} edge[MAXE];

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

void init(double mid)
{
    cnt=0;
    memset(head, 0, sizeof(head));
    memset(num, 0, sizeof(num));
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<=n; i++) dis[i]=INF;
    for(int i=1; i<=m; i++) addedge(u[i], v[i], w[i]*mid-f[u[i]]);
}

bool spfa()
{
    queue<int> q;
    q.push(1); vis[1]=1; dis[1]=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;
                num[to]=num[x]+1;
                if(num[to]>=n) return 0;
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
    return 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &f[i]);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &u[i], &v[i], &w[i]);
    double l=0, r=500000, mid;
    while(fabs(r-l)>eps)
    {
        mid=(l+r)/2;
        init(mid);
        if(spfa()) r=mid;
        else l=mid;
    }
    printf("%.2lf\n", mid);
}

Posted on Edited on In

问题描述：

Byteotia城市有n个 towns，m条双向roads。每条road连接两个不同的 towns，没有重复的road且所有towns连通。

输入：

输入n<=100000 m<=500000及m条边

输出：

输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。

思路：

这道题与无向图的联通性有关，所以可以利用点双联通分量的相关知识。

首先考虑如果点i不为割点，那么答案就是$(n-1)*2$。如果它为割点，那么就把这张图分为了若干块，然后利用乘法原理我们就可以根据每个联通块的大小计算出答案。

然后就考虑如何计算删去某个点后的各个联通块大小。在执行tarjan过程中会产生一棵搜索树，于是我们可以利用这点，用类似于树形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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define LL long long
#define MAXE 500005
#define MAXN 100005
using namespace std;

int n, m, cnt, id, head[MAXN], low[MAXN], dfn[MAXN], size[MAXN];
LL ans[MAXN];

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

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

void tarjan(int x)
{
    int tag=0, sum=0; bool flag=false;
    low[x]=dfn[x]=++id; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(dfn[to]) low[x]=min(low[x], dfn[to]);
        else
        {
            tarjan(to);
            size[x]+=size[to];
            low[x]=min(low[x], low[to]);
            if(low[to]>=dfn[x])
            {
                tag++;
                if(x!=1 || tag>1) flag=true;
                ans[x]+=(LL)size[to]*(n-size[to]);
                sum+=size[to];
            }
        }
    }
    if(flag) ans[x]+=(LL)(n-sum-1)*(sum+1)+n-1;
    else ans[x]=(n-1)*2;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    tarjan(1);
    for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}

Posted on Edited on In

问题描述：

你将要游览一个有N个岛屿的公园。从每一个岛i出发，只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制： • 可以自行挑选一个岛开始游览。 • 任何一个岛都不能游览一次以上。 • 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。

由S到D可以有以下方法： 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离 渡船：你可以选择这种方法，仅当没有任何桥或以前使用过的渡船的组合可以由S走到D（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）

输入：

第一行包含N个整数，即公园内岛屿的数目（2<=N<=1000000） 随后的N行每一行用来表示一个岛，第i 行由两个以单空格分隔的整数，表示由岛i筑的桥，第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li （1<=Li<=100000000）

输出：

输出可能的最大步行距离

思路：

由于每个点都有一条出边，所以图是一个基环树森林的形态，题目就是求每棵基环树直径之和。

回顾一下树的直径，有树形DP和两边BFS的解法。推广到基环树，同样可以用树形DP求解。首先应该分类讨论，有两种情况：一种是直径在某一棵子树上，另一种是直径经过环，连接两棵子树的最长链。第一种情况不难处理，依然是树形DP，在DP的过程中还可以求出最长链。第二种情况就稍微难一点，首先我们需要找环，这我们可以用拓扑排序，为了节省码量，我们可以拓扑排序的过程中进行DP。找出环后，我们应该如何处理？

不难想到，我们可以把每棵子树的最长链投影到环上的点上（子树根节点）作为点权，设为$f_i$。然后我们就要在环上找两个点$i,j$，使得$f_i+dis(i,j)+f_j$最大。这是一个DP的模型，我们先破环为链，然后前缀和维护两点距离，设节点$i$到节点1的距离为$g_i$。然后我们可以枚举$i$,然后求$max(f_j-g_j)$，这个我们就可以用单调队列维护，这样我们就可以在$O(n)$内求出$max(f_i+f_j+g_i-g_j)$。

代码：

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

int n, id, l=1, r, cnt, head[MAXN], belong[MAXN], deg[MAXN], q[MAXN*2];
LL ans, dia[MAXN], len[MAXN], f[MAXN*2], g[MAXN*2];
bool vis[MAXN];

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

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

void dfs(int x, int id)
{
    belong[x]=id;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!belong[to]) dfs(to, id);
    }
}

void topsort()
{
    for(int i=1; i<=n; i++) if(deg[i]==1) q[++r]=i;
    while(l<=r)
    {
        int x=q[l++];
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            deg[to]--;
            dia[belong[x]]=max(dia[belong[x]], len[to]+len[x]+edge[i].dis);
            len[to]=max(len[to], len[x]+edge[i].dis);
            if(deg[to]==1) q[++r]=to;
        }
    }
}

void dp(int x)
{
    int y=x, tot=0;
    while(1)
    {
        bool flag=false;
        deg[y]=1; f[++tot]=len[y];
        for(int i=head[y]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            g[tot+1]=g[tot]+edge[i].dis;
            flag=true; y=to;
        }
        if(!flag) break;
    }
    if(tot==2)
    {
        int temp=0;
        for(int i=head[y]; i; i=edge[i].next)
            if(edge[i].to==x) temp=max(temp, edge[i].dis);
        dia[belong[x]]=max(dia[belong[x]], len[x]+len[y]+temp);
    }
    for(int i=head[y]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==x) g[tot+1]=g[tot]+edge[i].dis;
    }
    for(int i=1; i<=tot; i++)
    {
        f[i+tot]=f[i];
        g[i+tot]=g[tot+1]+g[i];
    }
    l=r=1; q[1]=1;
    for(int i=2; i<2*tot; i++)
    {
        while(l<=r && i-q[l]>=tot) l++;
        dia[belong[x]]=max(dia[belong[x]], f[i]+f[q[l]]+g[i]-g[q[l]]);
        while(l<=r && f[q[r]]+g[i]-g[q[r]]<=f[i]) r--;
        q[++r]=i;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(i, x, y);
        addedge(x, i, y);
    }
    for(int i=1; i<=n; i++) if(!belong[i]) dfs(i, ++id);
    topsort();
    for(int i=1; i<=n; i++)
    {
        if(deg[i]<=1 || vis[belong[i]]) continue;
        vis[belong[i]]=true;
        dp(i);
        ans+=dia[belong[i]];
    }
    printf("%lld\n", ans);
}