随便想的两道算法题+题解

在初中的时候，感觉打OI最有意思的事情之一就是出题。因为自己出的题目可以套一些奇奇怪怪的设定来整活，还可以名正言顺地迫害小伙伴。不过呢出的都不是什么正经题目。

现在几年过去了，感觉已经好久没有出过题目了，正好社团的友谊赛给了我一个契机来认真出两道题，个人认为这两题的难度，思维量，码量也都说的过去，就出一篇题解。

A.萌娘评鉴指南

题目大意就是给主角找对象啦(* /ω＼*)

概括

给定nn个集合，这nn个集合组成一个序列，给定3种操作，一共进行qq次：

  1. 给编号l~r的集合每个集合添加一个数cc
  2. 给编号l~r的集合每个集合进行反转 （去掉有的数字，添加原先没有的数字）
  3. 询问编号l~r的集合中，有数字cc的集合数量是奇数还是偶数。

数据范围： n,m≤2×105,c≤15n,m \leq 2\times10^5, c\leq15.

思路：

位运算：

其实看到c的范围就可以找到这题的突破口。因为对于集合里的每个数，都只有“有”和“没有”两种状态，所以完全可以利用位运算，来把每个集合转化为二进制的数字，这样集合就可以以int的形式存储了。

例： 1,2,4 -> 1011 -> 11

使用位运算，我们又可以重新翻译一下这道题目：

给定n个整数，进行q次以下可能的操作：

  1. 给编号l~r的数每个数都 按位或 1<<c
  2. 给编号l~r的数每个数都进行 取反
  3. 查询l~r的数的异或和 按位与 1<<c的结果。

熟悉位运算的应该能非常容易作出这种转化，不熟悉的也会发现这几种操作可以和原先所说的完全对应起来。

线段树：

因为询问的是异或的结果，而异或是满足结合律的，结合数据范围，我们必须要想到一种能够在lognlogn复杂度内进行操作的方法。

那么很明显就是用 线段树。 线段树维护的内容是区间内的异或和。

那么问题来了，怎么样完成1操作和2操作呢？

对于线段树而言，肯定是要建lazytag的，通过合理地设置lazytag，我们就可以合理建出满足要求的线段树 （车轱辘话时间）

显然，lazytag中包含以下两个内容： 区间要取或的值 和 区间是否取反。但是有一个问题：区间进行取反之后，区间要取或的值就变了！思考一下可以发现，要取或的值，取反之后，再取与就可以了。

所以实际上我们的lazytag要存储3个内容：

  1. 区间要取或的值
  2. 区间是否取反
  3. 区间要取与的值

此外，还有n个细节需要注意：

  1. 区间长度为偶数，异或和不需要取反，长度为奇数要取反
  2. 如果区间长度为偶数，那么取或操作应该改为取反后取与（因为某一位如果有偶数个1，那么异或和就是0）
  3. 是否取反的标记，应该使用 异或 操作,因为取反两次就相当于没有取反，如果用了赋值会出错。

代码：

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
#include<iostream>
using namespace std;

int n, m, k;
int a[500100];

struct tag{
    int val, v_and = (1<<23)-1, v_or = 0;
    bool rev = 0;
}t[2000100];

inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}

void pushup(int p){
    t[p].val = t[ls(p)].val ^ t[rs(p)].val;
}

inline void lazy(int p,int l, int r, int vand, int vor, bool isrev){
    if(isrev){
        int temp = t[p].v_and;
        t[p].v_and = (~t[p].v_or);
        t[p].v_or = (~temp);
        if(((r-l+1)%2)==1)t[p].val= (~t[p].val);
    }
    if((r-l+1)%2 == 0){
        t[p].val &= vand;
        t[p].val &= (~vor);       
    }
    else{
        t[p].val &= vand;
        t[p].val |= vor;
    }
    
    t[p].rev ^= isrev; 
    t[p].v_and &= vand;
    t[p].v_and |= vor;
    t[p].v_or |= vor;
    t[p].v_or &= vand;
}

void pushdown(int p, int l, int r){
    int mid = (l+r)>>1;
    lazy(ls(p),l,mid,t[p].v_and,t[p].v_or,t[p].rev);
    lazy(rs(p),mid+1,r,t[p].v_and,t[p].v_or,t[p].rev);
    t[p].v_and = (1<<23)-1;
    t[p].v_or = 0;
    t[p].rev = 0;
}

void build(int p, int l, int r){
    if(l==r){t[p].val=a[l];return;}
    int mid = (l+r)>>1;
    build(ls(p), l, mid);
    build(rs(p), mid+1, r);
    pushup(p);
}

void update(int nl, int nr, int l, int r, int p, int vand, int vor, bool isrev){
    if(nl <= l && nr >=r){pushdown(p,l,r);lazy(p,l,r,vand,vor,isrev);return;}
    pushdown(p,l,r);
    int mid = (l+r)>>1;
    if(nl<=mid)update(nl, nr, l, mid, ls(p), vand, vor, isrev);
    if(nr >mid)update(nl, nr, mid+1, r, rs(p), vand, vor, isrev);
    pushup(p);
}

int query(int nl, int nr, int l, int r, int p){
    if(nl <= l && nr>=r){pushdown(p,l,r);return t[p].val;}
    int res = 0;
    pushdown(p, l, r);
    int mid = (l+r)>>1;
    if(nl<=mid)res^=query(nl, nr, l, mid, ls(p));
    if(nr> mid)res^=query(nl, nr, mid+1,r,rs(p));
    return res;
}

int main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++){
        int ci;
        cin>>ci;
        while(ci--){
            int u;
            cin>>u;
            a[i] += (1<<u);
        }
    }
    build(1,1,n);
    for(int i = 0;i<m;i++){
        int op;
        cin>>op;
        if(op == 1){
            int l,r,c;
            cin>>l>>r>>c;
            update(l,r,1,n,1,((1<<23)-1), (1<<c), 0);
        }
        if(op == 2){
            int l ,r;
            cin>>l>>r;
            update(l,r,1,n,1,((1<<23)-1), 0, 1);
        }
        if(op == 3){
            int l, r, c;
            cin>>l>>r>>c;
            cout<<((query(l, r, 1, n, 1) & (1<<c))?"Yes":"No" )<< endl;
        }
    }
    return 0;
}

B.新建文件夹

在出这道题之前，我开玩笑地说“题目已经在出了（新建文件夹）”，于是干脆就把这题叫作新建文件夹好了，题目大意也跟我出题的过程有关，只能说当时的精神状态极为良好（笑）

概括：

以深度优先的顺序访问一棵树的每个节点，直到访问到目标的叶子节点结束。询问访问节点数量的期望。

思路：

这题可以说跟上一题相比非常简单了。

我们可以发现，从根节点到目标叶子节点的这一条链，是一定会被访问到的。也就是说访问到这些节点的概率为1。

那么其它的节点呢？我们会发现，对于链上的每一个节点，他们的兄弟节点被访问的概率都是相等的，它们要么被访问到，要么没有被访问到，概率为12\frac{1}{2}。
对于这些节点的所有子孙节点，他们都是一定会被访问到的。因为只有把这些节点全部走完才可能返回上一级，所以他们的概率也是12\frac{1}{2}。

那么答案就出来了：从根节点到目标叶子节点的这一条链节点的数量+其它节点数量/2.

总码量奇短无比。

代码：

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<iostream>
using namespace std;
int n,target,len;
int fa[3000010];
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        int c;
        cin>>c;
        for(int j = 0;j<c;j++){
            int x;
            cin>>x;
            fa[x] = i;
        }
    }
    cin>>target;
    while (target != 0)
    {
        len++;
        target = fa[target];
    }
    cout<<len + (n-len)/2<<((n-len)%2?".500000":".000000")<<endl;
    return 0;
}
技术向
#OI #题解 #算法
随便想的两道算法题+题解
http://example.com/2024/02/28/随便想的两道算法题+题解/
作者
Blauter
发布于
2024年2月28日
许可协议