Dylan's Blog
0%

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

Posted on Edited on In

问题描述：

给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段） 请你写一个程序依次完成这m个操作。

输入：

第一行包含2个整数n和m，分别表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜色 下面n-1行每行包含两个整数x和y，表示x和y之间有一条无向边。 下面m行每行描述一个操作： “C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c； “Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出：

对于每个询问操作，输出一行答案。

思路：

数据结构题。。。思维含量不高，要注意很多细节

首先对于树上路径的操作和询问一般不难想到用树剖。然后就考虑如果维护一个序列的颜色段数量，以及修改操作。这种序列问题一般用线段树维护，线段树节点储存：左端及右端颜色，区间颜色段总数，lazytag。up函数也稍微修改一下。这样就解决了在序列上的问题。

接着考虑树剖，对于树上区间的合并要注意特殊处理链的左右端点问题，要分别记录两条链的端点颜色，在合并时要分清是那一条链。

代码：

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
#define ls (root<<1)
#define rs (root<<1|1)
#define mid (l+r>>1)
#define MAXN 100005
using namespace std;

int n, m, ans, cnt, head[MAXN], w[MAXN];
int sum[MAXN*4], lcol[MAXN*4], rcol[MAXN*4], tag[MAXN*4];
int ind, Lcol, Rcol, val[MAXN], id[MAXN], f[MAXN], size[MAXN], dep[MAXN], son[MAXN], top[MAXN];

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 up(int root)
{
    sum[root]=sum[ls]+sum[rs];
    if(rcol[ls]==lcol[rs]) sum[root]--;
    lcol[root]=lcol[ls];
    rcol[root]=rcol[rs];
}

void down(int root, int l, int r)
{
    if(!tag[root]) return;
    sum[rs]=sum[ls]=1;
    lcol[ls]=rcol[ls]=tag[root];
    lcol[rs]=rcol[rs]=tag[root];
    tag[ls]=tag[rs]=tag[root];
    tag[root]=0;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        sum[root]=1;
        lcol[root]=rcol[root]=val[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    up(root);
}

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

void query(int root, int l, int r, int x, int y)
{
    if (l>y || r<x) return;
    if(l==x) Lcol=lcol[root];
    if(r==y) Rcol=rcol[root];
    if(x<=l && y>=r)
    {
        ans+=sum[root];
        return;
    }
    down(root, l, r);
    query(ls, l, mid, x, y);
    query(rs, mid+1, r, x, y);
    if(mid>=x && mid+1<=y && rcol[ls]==lcol[rs]) ans--;
}

void dfs1(int x, int fa)
{
    int maxson=-1; f[x]=fa; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        size[x]+=size[to];
        if(size[to]>maxson) son[x]=to, maxson=size[to];
    }
}

void dfs2(int x, int topf)
{
    id[x]=++ind; val[ind]=w[x]; 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!=f[x] && to!=son[x]) dfs2(to, to);
    }
}

void update1(int x, int y, int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y);
        update(1, 1, n, id[top[x]], id[x], k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y);
    update(1, 1, n, id[x], id[y], k);
}

int query1(int x, int y)
{
    int last1=0, last2=0; ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y), swap(last1, last2);
        query(1, 1, n, id[top[x]], id[x]);
        if(Rcol==last1) ans--;
        last1=Lcol;
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y), swap(last1, last2);
    query(1, 1, n, id[x], id[y]);
    if(Lcol==last1) ans--;
    if(Rcol==last2) ans--;
    return ans;
}

int main()
{
    int x, y, a, b, c; char opt;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%d%d", &opt, &a, &b);
        if(opt=='C') {scanf("%d", &c); update1(a, b, c);}
        if(opt=='Q') printf("%d\n", query1(a, b));
    }
}

Posted on Edited on In

6月19日 Codeforces Round #489 题目链接：http://codeforces.com/contest/992

A - Nastya and an Array

过水，不多说。

B - Nastya Studies Informatics

思路： 思路比较暴力，一开始以为不是正解，复杂度似乎是$O(\sqrt{n}log(n))$。

首先想到的便是暴力枚举，枚举a，b则可以通过计算得到($b=xy/a$)，然后判断$a，b$是否再范围内并且$gcd(a,b)$是否等于x。

然后便发现可以优化，可以将l，r，y同除x(注意取整)。如果x，y互素，则一定为0。然后就可以从1枚举到$\sqrt{y/x}$，判断a，b是否互素。

代码：

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 LL long long
using namespace std;

LL l, r, x, y, s, ans;

bool check(LL a, LL b)
{
    if(a>=l && a<=r && b>=l && b<=r) return true;
    else return false;
}

int main()
{
    cin>>l>>r>>x>>y;
    if(y%x!=0) 
    {
        printf("0\n");
        return 0;
    }
    l=(l+x-1)/x; r=r/x; y/=x;
    for(int i=1; i<=sqrt(y); i++)
    {
        if(y%i!=0) continue;
        int j=y/i; 
        if(check(i, j) && __gcd(i, j)==1)
        {
            if(i*i==y) ans++;
            else ans+=2;
        }
    }
    cout<<ans<<endl;
}

C - Nastya and a Wardrobe

思路： 结果还是数学题，我们可以考虑所有情况，k个月时可能的衣服数量是从$n*2^k$到$(n-1)*2^k+1$。

因为它们是等概率分布。所以答案是$n*2^k+(n-1)*2^k+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
#include <bits/stdc++.h>
#define LL long long
#define p 1000000007
using namespace std;

LL n, k;

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        x=(x*x)%p; y>>=1;
    }
    return sum%p;
}

int main()
{
    cin>>n>>k;
    if(n==0) cout<<0;
    else cout<<((n%p*ksm(2, k))%p+((n-1)%p*ksm(2, k))%p+1)%p;
}

D - Nastya and a Game

思路： 就是暴力啊。。比赛时想到了$O(n*n)$的暴力，其实稍微改一下就能A了。$O(n*n)$的暴力是这样的：先枚举L，记录下从L开始的乘积以及总和，只要符合要求就更新答案。

但是这样就会出现一些问题，首先是乘积会炸longlong，但是由于数据是构造好了的，只要乘积大于了10^18是一定不符合要求的，这时候就可以break了。、

这样的复杂度是不符合要求的，如果序列全是1，复杂度还是$O(n*n)$的。但是我们考虑因为1是不会影响乘积的，如果我们把序列中的1去掉，同样的暴力方法，最多枚举64个数字(64个数字全是2)就一定会break。这样的话，最坏复杂度就是$O(64*n)$。

最后，判断符合要求时要考虑序列中删去的1，写个check()函数就好了。

代码：

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
#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
using namespace std;

LL n, k, a[200005], nxt[200005], ans;

bool check(LL sum, LL pro, LL len)
{
    LL temp=pro-sum*k;
    if(temp%k) return false;
    if(temp/k>=0 && temp/k<=len) return true;
    else return false;
}

int main()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=n, pos=n+1; i>=1; i--)
    {
        nxt[i]=pos;
        if(a[i]>1) pos=i;
    }
    for(int i=1; i<=n; i++)
    {
        LL pro=1, sum=0;
        for(int j=i; j<=n; j=nxt[j])
        {
            if(pro>=INF/a[j]) break;
            pro*=a[j]; sum+=a[j];
            if(check(sum, pro, nxt[j]-j-1)) ans++;
            sum+=nxt[j]-j-1;
        }
    }
    cout<<ans<<endl;
}

E - Nastya and King-Shamans

思路： 超级神奇的数据结构题，在一个半月后终于A了。。前缀和处理应该不难想到，由于涉及修改操作，所以我们用树状数组维护前缀和。所以我们对于每一个询问要找到一个位置$x$，使得$sum[x-1]*2=sum[x]$（$sum$为前缀和）。

我们查找位置$x$可以利用分治的思想。对于任意一个区间$[l,r]$($lsum[r]$，不难发现这个区间内一定不会存在$x$。于是我们可以将整个区间$[0,n]$不断分治，直到找到位置$x$。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 1e18
#define MAXN 200005
using namespace std;

int n, q;
LL t[MAXN], a[MAXN];

void add(int x, LL y) {for(; x<=n; x+=(x&-x)) t[x]+=y;}

LL query(int x) {LL y=0; for(; x; x-=(x&-x)) y+=t[x]; return y;}

int find(int l, int r)
{
    int pos=-1, mid=(l+r)>>1;
    if(l+1==r) return query(l)*2==query(r)? r:-1;
    if(query(l)*2<=query(mid)) pos=max(pos, find(l, mid));
    if(pos!=-1) return pos;
    if(query(mid)*2<=query(r)) pos=max(pos, find(mid, r));
    return pos;
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld", &a[i]);
        add(i, a[i]);
    }
    for(int i=1; i<=q; i++)
    {
        int p;LL x;
        scanf("%d %lld", &p, &x);
        add(p, x-a[p]); a[p]=x;
        printf("%d\n", find(0, n));
    }
}

Posted on Edited on In

6月16日 AtCoder Beginner Contest 题目链接：https://abc100.contest.atcoder.jp/

A - Happy Birthday! & B - Ringo’s Favorite Numbers

比较水。。。 B题一定要弄清楚题意！！！注意特判！！！

C - *3 or /2

思路： 因为题目希望操作次数尽量多，所以我们可以贪心，每次只让一个数除2，其余乘3。那么这样，总操作次数便是每个数能够除以2的次数之和。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;

LL n, ans, a[10005];

int main()
{
    scanf("%lld", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        while(a[i]%2==0)
        {
            a[i]/=2;
            ans++;
        }
    }
    printf("%d\n", ans);
}

D - Patisserie ABC

思路： 这道题的做法稍稍有一点暴力。首先可以枚举三个值的正负情况，然后就可以计算每一个蛋糕对于三个值的贡献之和。排一个序，取前m个蛋糕的贡献之和用来更新答案。

代码；

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

int n, m, act[5], q[1005];
LL ans, b[1005], a[1005][5];

bool CMP(LL x, LL y) {return x>y;}

void dfs(int x)
{
    if(x==3)
    {
        LL temp=0; memset(b, 0, sizeof(b));
        for(int i=0; i<3; i++)
        {
            if(act[i]==1) for(int j=1; j<=n; j++) b[j]+=a[j][i];
            else for(int j=1; j<=n; j++) b[j]-=a[j][i];
        }
        sort(b+1, b+n+1, CMP);
        for(int i=1; i<=m; i++) temp+=b[i];
        if(temp>ans) ans=temp;
        return;
    }
    for(int i=1; i<=2; i++)
    {
        act[x]=i;
        dfs(x+1);
    }
}

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