Dylan's Blog
0%

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

Posted on Edited on In

问题描述：

小Z把这N只袜子从1到N编号，然后从编号L到R中抽两只袜子。你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。他可能会询问多个(L,R)以方便自己选择。

输入：

第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。 接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。 再接下来M行，每行两个正整数L，R表示一个询问。

输出：

包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。

思路：

这道题可以说是莫队的模板了。首先考虑如何计算概率，在给定的区间内抽到两只颜色相同的袜子的概率是$ans=(Σ(sum(color[i])^2)−(R−L+1))/((R−L+1)∗(R−L))$。

然后就使用莫队，先将问题离排序，离线操作，写一个update函数进行转移。详细内容可以看代码啦。

最后输出答案时应输出最简分数，记得要分子分母同除GCD。

代码：

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

int n, m, l=1, r, size, col[MAXN], belong[MAXN];
LL ans, sum[MAXN];

struct Q {int l, r, id; LL x, y;} q[MAXN];

bool CMP1(Q x, Q y) 
{
    if(belong[x.l]==belong[y.l]) return x.r<y.r; 
    else return x.l<y.l;
}

bool CMP2(Q x, Q y) {return x.id<y.id;}

void update(int pos, int opt)
{
    ans-=sum[col[pos]]*sum[col[pos]];
    sum[col[pos]]+=opt;
    ans+=sum[col[pos]]*sum[col[pos]];
}

int main()
{
    scanf("%d%d", &n, &m);
    size=sqrt(n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &col[i]);
        belong[i]=i/size+1;
    }
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id=i;
    }
    sort(q+1, q+m+1, CMP1);
    for(int i=1; i<=m; i++)
    {
        while(l<q[i].l) update(l++, -1);
        while(l>q[i].l) update(--l, 1);
        while(r<q[i].r) update(++r, 1);
        while(r>q[i].r) update(r--, -1);
        if(q[i].l==q[i].r)
        {
            q[i].x=0; q[i].y=1;
            continue;
        }
        q[i].x=ans-q[i].r+q[i].l-1;
        q[i].y=(LL)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        LL t=__gcd(q[i].x, q[i].y); 
        q[i].x/=t; q[i].y/=t;
    }
    sort(q+1, q+m+1, CMP2);
    for(int i=1; i<=m; i++) printf("%lld/%lld\n", q[i].x, q[i].y);
}