Dylan's Blog
0%

Posted on Edited on In

问题描述：

机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3…N。这N个任务被分成若干批，每批包含相邻的若干任务。

从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。

输入：

第一行两个整数，N,S。 接下来N行每行两个整数，Ti,Fi。

输出：

一个整数，为所求的答案。

思路：

首先$O(n^3)$的DP不难想到，这里就不多说了。然后$O(n^2)$的做法比较巧妙，我们可以提前计算出这个启动时间对后面状态造成对影响，然后用前缀和预处理一下$sumc$，$sumt$。所以状态转移方程为:

如果我们将上面对式子进行变形，就可以发现它是可以使用斜率优化的： 其中$f[j]$是纵坐标，$sumc[j]$是横坐标，斜率是$s+sumt[i]$。然后我们就要单调队列维护这些点构成的凸壳，使得两点之间的斜率是递增的。对于$i$的最优决策就是就是在凸壳上的某个点$j$，它左边的斜率小于$s+sumt[i]$，右边的斜率大于$s+sumt[i]$，然后我们就可以用这个j来更新$f[i]$。

最后有一点要注意的就是题目中的$T$能是负数，所以我们不能够像一般的斜率优化根据斜率的单调性pop掉队头元素。而是要改为二分来求出最优的决策点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
#include <bits/stdc++.h>
#define LL long long
#define MAXN 300005
using namespace std;

int n, s, head, tail;
LL sumc[MAXN], sumt[MAXN], q[MAXN], f[MAXN];

int find(int k)
{
    int l=tail, r=head, ans; 
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]])) l=mid+1;
        else r=mid;
    }
    return q[l];
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<=n; i++)
    {
        int t, c;
        scanf("%d%d", &t, &c);
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    head=tail=1; q[head]=0;
    for(int i=1; i<=n; i++)
    {
        int j=find(s+sumt[i]);
        f[i]=f[j]-(s+sumt[i])*sumc[j]+sumt[i]*sumc[i]+s*sumc[n];
        while(tail<head && (f[q[head]]-f[q[head-1]])*(sumc[i]-sumc[q[head]])>=(f[i]-f[q[head]])*(sumc[q[head]]-sumc[q[head-1]])) head--;
        q[++head]=i;
    }
    printf("%lld\n", f[n]);
}

Posted on Edited on In

7月13日 Codeforces Round #496 题目链接：http://codeforces.com/contest/1005

A - Tanya and Stairways & B - Delete from the Left

过水，不多说。。。

C - Summarize to the Power of Two

思路： $O(nlogn^2)$的比较暴力的做法，估计不是正解，水过去的QWQ

就是对于一个数$a[i]$，我们可以枚举所有的2的次幂，找到数组$a$在中是否有另一个数$a[j]$，使得它们和为2的次幂，这个可以用map维护。但是要注意一个细节就是a[i]本身是2的次幂，这个要特判一下。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define MAXN 120005
using namespace std;

int n, a[MAXN], ans;
map<int, int> mmp;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        mmp[a[i]]++;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=30; j++)
            if(mmp.count((1<<j)-a[i]) && ((1<<j)!=a[i]*2 || mmp[a[i]]>1))
                {ans++; break;}
    printf("%d\n", n-ans);
}

D - D - Polycarp and Div 3

思路： 首先有一个引理：就是如果有一串长度大于3的数字它们和能被3整除，那么一定有一个连续字串的和也能被3整除。

这个比较显然，证明就不多说了。我们进行DP，根据上面的引理，每个$f[i]$会只从它前面的$f[i-1],f[i-2],f[i-3]$转移而来，所以就直接$O(n)$扫一遍就好了。(DP如何转移就看代码好了，比较简单)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;

int n, cnt=1, ans, num[MAXN], f[MAXN][2];

int main()
{
    while(scanf("%1d", &num[cnt])!=EOF) cnt++;
    for(int i=1; i<cnt; i++) num[i]+=num[i-1];
    for(int i=1; i<cnt; i++)
        for(int j=max(i-3, 0); j<i; j++)
        {
            if((num[i]-num[j])%3==0) f[i][1]=max(f[i][1], f[j][1]+1);
            else f[i][1]=max(f[i][1], f[j][1]);
        }
    printf("%d\n", f[cnt-1][1]);
}

E1 - Median on Segments (Permutations Edition)

思路： 这题我的思路和题解的也不太一样。（其实是当时想一口气做出两个来，结果发现这个思路E2有BUG）

首先我们对于序列中数的大小是不关心的，只关系它与k的关系。所以可以把比k小的看成-1，比k大的看成1，然后维护前缀和，记为num[i]。我们同样记录k的位置pos，那么答案就是在pos两边有多少对i，j使得$num[i]=num[j]$或$num[i]=num[j]+1$。所以我们cnt数组记录在pos前$num[i]$的数量，对于pos后的$num[i]$就将$cnt[num[i]]$和$cnt[num[i]-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
#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, k, pos=MAXN, a[MAXN], num[MAXN], cnt[MAXN*2];
LL ans;

int main()
{
    scanf("%d%d", &n, &k);
    cnt[n]=1;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i]==k) pos=i;
        if(a[i]<k) num[i]=-1;
        if(a[i]==k) num[i]=0;
        if(a[i]>k) num[i]=1;
        num[i]+=num[i-1];
        if(i<pos) cnt[num[i]+n]++;
    }
    for(int i=pos; i<=n; i++) ans+=cnt[n+num[i]], ans+=cnt[n+num[i]-1];
    printf("%lld\n", ans);
}

E2 - Median on Segments (General Case Edition)

思路： 这道题自然是没有想到的QWQ…..膜了下题解

由于直接求中位数为m的序列是不好求的，所以我们可以变一下，求中位数大于m的序列。那么答案就是做一个容斥，为中位数大于m的序列—中位数大于m+1的序列。

那么求中位数大于m的序列的做法和上一题我的做法有些相似。$num$是前缀和，$cnt$数组记录数量，由于长度为偶数时中位数是中间较小的那个，所以操作的顺序是不一样的。

代码：

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>
#define MAXN 200005
#define LL long long
using namespace std;

int n, m, a[MAXN];
LL num, cnt[MAXN*2];

LL solve(int m)
{
    LL ans=0, add=0;
    memset(cnt, 0, sizeof(cnt));
    num=n; cnt[num]=1;
    for(int i=1; i<=n; i++)
    {
        if(a[i]<m) num--, add-=cnt[num];
        else add+=cnt[num], num++;
        ans+=add;
        cnt[num]++;
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    printf("%lld\n", solve(m)-solve(m+1));
}

F - Berland and the Shortest Paths

思路： 用BFS一遍处理出每个点深度，用个vector记录每个点连向父亲的边(可能有多个父亲)。因为每个点vector中存的边可以随便取，所以用dfs乱搞一下计算出答案。

代码：

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

int n, m, k, ans, cnt=1, head[MAXN], dep[MAXN], temp[MAXN];
bool vis[MAXN];

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

vector<int> pre[MAXN], path[MAXN];
queue<int> q;

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

void bfs()
{
    memset(dep, 0x3f, sizeof(dep));
    q.push(1); dep[1]=0;
    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(dep[to]>dep[x]+1)
            {
                dep[to]=dep[x]+1;
                q.push(to);
            }
            if(dep[to]==dep[x]+1) pre[to].push_back(i);
        }
    }
}

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=0; i<m; i++) path[ans].push_back(temp[i]);
        ans++;
        return;
    }
    for(int i=0; i<pre[x].size(); i++)
    {
        temp[pre[x][i]/2-1]=1;
        dfs(x+1);
        if(ans==k) return;
        temp[pre[x][i]/2-1]=0;
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    bfs();
    dfs(2);
    printf("%d\n", ans);
    for(int i=0; i<ans; i++)
    {
        for(int j=0; j<m; j++) printf("%d", path[i][j]);
        printf("\n");
    }
}

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