Dylan's Blog
0%

Posted on Edited on In

问题描述

你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼（或总计2K个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 2K 个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。

因而，你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

输入

第一行包含整数n和k。 其中n（2≤n≤100000）表示办公楼的数目，k（1≤k≤n/2）表示可利用的网络电缆的数目。

接下来的n行每行仅包含一个整数（0≤s≤1000000000）,表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出

输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

思路

第一眼看题，想着用网络流去做QWQ。

想了一下后，突然想起一道题BZOJ2151 种树。当时做这道题时觉得这道题的思路十分巧妙。然后这道题也可以用一模一样的思路去做。

每次贪心选取最大值，答案加上这个最大值，最大值左右两边当然不能再选，于是就标记为访问过。

但是这个贪心显然是不完善的。当最大值左右两边之和大于它本身时，就会产生错误。于是就有一种神奇的操作：将左右两边之和减去最大值，作为新的节点，覆盖掉原来的最大值，并删去左右两个节点。

原因是要么选最大值，要么选它的左右之和，选最大值时答案加上这个最大值，不再去选新的节点，选左右之和时答案还是加上最大值，只不过后面还要加上新节点的值。也就是当我们再次选取的新节点时，也就相当于选取当时最大值的左右之和，而没有选最大值。

细节

  1. 要注意链头和链尾要特殊处理；
  2. 要注意删除操作的顺序;
  3. 访问过的节点dis要标记为INF.

代码

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

struct Sec
{
    LL dis, pos;
    bool operator < (const Sec &x) const
    {
        return dis>x.dis;
    }
} sec[MAXN];

LL n, k, ans, x[MAXN], dis[MAXN], pre[MAXN], nxt[MAXN];

priority_queue<Sec> q;

int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=1; i<=n; i++) scanf("%lld", &x[i]);
    for(int i=2; i<=n; i++)
    {
        dis[i]=x[i]-x[i-1];
        q.push((Sec) {dis[i], i});
        pre[i]=i-1; nxt[i]=i+1;
    }
    pre[2]=0; nxt[n]=0;
    for(int i=1; i<=k; i++)
    {
        while(dis[q.top().pos]==INF) q.pop();
        LL pos=q.top().pos; q.pop();
        ans+=dis[pos];
        if(!nxt[pos]) //处理链尾
        {
            dis[pre[pos]]=INF;
            nxt[pre[pos]]=0;
            continue;
        }
        if(!pre[pos]) //处理链头
        {
            dis[nxt[pos]]=INF;
            pre[nxt[pos]]=0;
            continue;
        }
        dis[pos]=dis[pre[pos]]+dis[nxt[pos]]-dis[pos];
        dis[pre[pos]]=dis[nxt[pos]]=INF;
        pre[pos]=pre[pre[pos]];
        nxt[pos]=nxt[nxt[pos]];
        pre[nxt[pos]]=nxt[pre[pos]]=pos;
        q.push((Sec){dis[pos], pos});
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述

你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入

第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种： install x：表示安装软件包x uninstall x：表示卸载软件包x 你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）

输出

输出文件包括q行。

输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

数据范围

对于全部数据：n<=100000, q<=100000。

思路

我们可以看出这些软件的依赖关系是一棵树。设未安装的节点权值为0，安装的权值为1。

然后install操作就是让x节点到根节点路径上权值为0的节点变为1，并输出权值为0节点个数。uninstall操作就是让x子树权值为1的节点变为0，并输出权值为1节点个数。

然后这就是一个很裸的树剖啦QVQ 线段树上的操作就是将整个区间变为0或1。

但是要注意常数问题！以install操作为例，如果先计算x到根节点权值之和，然后进行修改，再求一遍到根节点之和。这样的常数巨大，在BZOJ上会TLE。QWQ

所以我们可以优化一下,先保存一下整棵树权值之和(就是sum[1])，然后修改，输出整棵树前后权值之差。这样常数就小了不少。

细节

  1. 所有点的编号都要+1，不然树剖时会产生与0号节点有关的bug。
  2. lazytag要注意，初始赋为-1，下传标记时新tag要覆盖掉原tag。
  3. 要注意常数，TLE了一次QWQ

代码

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
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
#define ls (l+r<<1)
#define rs (l+r<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, x, q, cnt, head[MAXN], tag[MAXN*4], sum[MAXN*4];
int Index, son[MAXN], f[MAXN], dep[MAXN], size[MAXN], id[MAXN], top[MAXN];
char opt[100];
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 dfs1(int x, int fa, int deep)
{
    dep[x]=deep; f[x]=fa; size[x]=1;
    int maxson=-1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x, deep+1);
        size[x]+=size[to];
        if(size[to]>maxson) maxson=size[to], son[x]=to;
    }
}

void dfs2(int x, int topf)
{
    id[x]= ++Index; 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==son[x] || to==f[x]) continue;
        dfs2(to, to);
    }
}

void down(int root, int l, int r)
{
    if(tag[root]==-1) return;
    sum[ls]=(mid-l+1)*tag[root];
    sum[rs]=(r-mid)*tag[root];
    tag[ls]=tag[root];
    tag[rs]=tag[root];
    tag[root]=-1;
}

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

void act(int x, int y)
{
    while(top[x]!=1)
    {
        update(1, 1, n, id[top[x]], id[x], y);
        x=f[top[x]];
    }
    update(1, 1, n, id[1], id[x], y);
}

int main()
{
    memset(tag, -1, sizeof(-1));
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        addedge(i, x+1); 
        addedge(x+1, i);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    scanf("%d", &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%s%d", opt, &x); x++;
        int temp=sum[1];
        if(opt[0]=='i')
        {
            act(x, 1);
            printf("%dn", sum[1]-temp);
        }
        if(opt[0]=='u')
        {
            update(1, 1, n, id[x], id[x]+size[x]-1, 0);
            printf("%dn", temp-sum[1]);
        }
    }
}