清华计科考研2022复试机考

发表于 分类于

22年正式机考整体难度适中。T2是模板题，只要有模板则难度不大；T3比较讨巧，在处理时需要思考各种特殊情况。

  • T1: 签到
  • T2: 平衡树，01-trie，启发式合并
  • T3: 容斥

传送门

T1 字符串

输入一个长度为$n$的01串。输出其包含多少长度大于$m$的连续1子串。

对于长度为$x$的连续1子串，其包含长度大于$m$的连续1子串的个数为$1+2+3+…+(x-m+1)=\frac{(x-m+1)(x-m+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 <cstdio>
#include <algorithm>
using namespace std;
int n,m;
char s[100010];
long long ans;
long long calc(long long x)
{
    if(x<m) return 0;
    return 1ll*(x-m+1)*(x-m+2)/2;
}
int main()
{
    scanf("%d%d%s",&n,&m,s+1);
    int tmp=0;
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='0') ans+=calc(tmp),tmp=0;
        else ++tmp;
    }
    ans+=calc(tmp);
    printf("%lld\n",ans);
    return 0;
}

T2 飞船调度

维护$n$个集合，支持：插入元素，集合内所有元素增加$x$，查询中位数，删除中位数，合并两个集合，删除集合内$\le x$的元素。

题目要求非常简单，看着很像 set 就能解决的任务（乐），但是因为 set 不支持中位数相关操作，所以显然是一道平衡树模板题。

清华机考允许带纸质资料进场，直接套板子难度不大。

卡常？

使用一种叫做 01-trie 树的科技。将一个数拆解为二进制表达，从高位到低位，0走左儿子，1走右儿子，即可维护一个无符号整数的有序集合。等价于一颗权值线段树。

增加指令可以利用 lazy 标记的思想，通过对每个集合维护 offset 实现。需要注意的是，题意中插入元素的大小和增加的大小都为正数，但可能存在提升后插入较小元素，使得最终插入裸值$\lt 0$的情况，如增加$100$，之后插入$1$，插入的裸值会变成$-99 \lt 0$，超过 01-trie 的表示范围。故 offset 的初始值需要设定成一个较大的数。

合并指令需要使用启发式合并的思想：每次合并时都指定从小的集合合并到大的集合，反复从小的集合提取元素插入到大的集合。对$n$个元素来讲，这样做的最坏时间复杂度为$O(n \log n \log M)$（$\log M$为集合存储整数范围的对数，即 01-trie 深度），需要$n$次插入与$n$次合并，依题意，有最大$n=200000$，此时预计运算次数为$200000 \cdot \log 200000 \cdot 63 = 226800000$，存在卡常的风险。

如果用平衡树的话，复杂度可以降到$O(n \log^2 n)$，最坏情况快3.5倍。因为没有OJ测试数据，最终也无法知道那天是否卡常了。

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
// 01-trie
#include <cstdio>
#include <algorithm>
using namespace std;
struct Fleet
{
    struct Node
    {
        int cnt;
        Node *s[2];
        Node()
        {
            cnt=0;
            s[0]=s[1]=NULL;
        }
    };
    Node *root;
    long long offset;
    Fleet()
    {
        root=new Node();
        offset=-4000000000000ll;
    }
    void insert(long long x);
    void upgrade(long long x);
    void merge(Fleet &x);
    void remove(long long x,Node *pos,int i);
    long long query(bool remove);
};

void Fleet::insert(long long x)
{
    if(!x) return;
    x-=offset;
    ++root->cnt;
    Fleet::Node *pos=root;
    for(int i=62;~i;--i)
    {
        int dir=x>>i&1;
        if(!pos->s[dir]) pos->s[dir]=new Fleet::Node();
        ++pos->s[dir]->cnt;
        pos=pos->s[dir];
    }
}

void Fleet::upgrade(long long x) {offset+=x;}

void Fleet::merge(Fleet &x)
{
    if(x.root->cnt < root->cnt) swap(root,x.root);
    while(root->cnt) x.insert(query(true));
}

void Fleet::remove(long long x,Node *pos=NULL,int i=62)
{
    if(!pos) pos=root;
    if((x-offset)&(1ll<<i))
    {
        pos->s[0]=NULL;
        if(pos->s[1]) remove(x, pos->s[1], i-1);
    }
    else if(pos->s[0]) remove(x, pos->s[0], i-1);
    pos->cnt=0;
    if(pos->s[0]) pos->cnt+=pos->s[0]->cnt;
    if(pos->s[1]) pos->cnt+=pos->s[1]->cnt;
}

long long Fleet::query(bool remove)
{
    if(!root->cnt) return 0;
    int x=(root->cnt+1)/2;
    if(remove) --root->cnt;
    Fleet::Node *pos=root;
    long long ret=0;
    for(int i=62;~i;--i)
    {
        if(pos->s[0]&&pos->s[0]->cnt>=x)
        {
            if(remove) --pos->s[0]->cnt;
            pos=pos->s[0];
        }
        else
        {
            ret+=(1ll<<i);
            if(pos->s[0]) x-=pos->s[0]->cnt;
            if(remove) --pos->s[1]->cnt;
            pos=pos->s[1];
        }
    }
    return ret+offset;
}

int n,q;
Fleet f[400010];

int main()
{
    scanf("%d%d",&n,&q);
    int mode,x,y;
    while(q--)
    {
        scanf("%d%d",&mode,&x);
        if(mode!=4) scanf("%d",&y);
        if(mode==1) f[x].insert(y);
        else if(mode==2) f[x].upgrade(y);
        else if(mode==3) f[x].insert(f[y].query(true));
        else if(mode==4) printf("%lld\n",f[x].query(false));
        else if(mode==5) f[x].merge(f[y]);
        else f[x].remove(y);
    }
    return 0;
}

平衡树 + 启发式合并

1
//TODO

T3 圆上计数

在一个周长为$C$的圆形上有$N$个点，问以他们为顶点可以找出多少个三角形，使得圆心在三角形内部。

转化成求有多少三角形不满足要求。可以发现，所有不满足要求的三角形三个顶点都在一个半圆内。固定顺时针方向扫过半圆的最后一个点，则反推半圆，求半圆中的点的个数，从中任意取两点的方案个数即不满足要求的三角形个数。

本题中可能出现多个点位于同一个位置的情况，便可能出现两种特殊的三角形：一条线（两个顶点重合）和一个点（三个顶点重合）。在先前的计算中，某些情况没有统计到，如两个顶点重合在固定节点位置，以及三个顶点重合的情况，这些情况均需进行容斥处理。

最后，还有一种特殊情况：当总周长为偶数时，每个点和他正对面的点构成的直线从两个点的方向来看都会被计算，从而会被统计两次，容斥处理加回一次即可。

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
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100010
int n,c,s[MAXN];
long long ans;
int main()
{
    scanf("%d%d",&n,&c);
    int tmp;
    for(int i=1;i<=n;++i) scanf("%d",&tmp),++s[tmp+1];
    for(int i=1;i<=c;++i) s[i]+=s[i-1];
    ans=n*(n-1)*(n-2)/6;
    for(int i=1;i<=c;++i)
        if(s[i]-s[i-1])
        {
            int sum;
            if(i<=c/2) sum=s[i-1]+s[c]-s[i+(c/2)-1];
            else sum=s[i-1]-s[i-(c/2)-1];
            ans-=1ll*(s[i]-s[i-1])*sum*(sum-1)/2;
            ans-=1ll*(s[i]-s[i-1])*(s[i]-s[i-1]-1)/2*sum;
            ans-=1ll*(s[i]-s[i-1])*(s[i]-s[i-1]-1)*(s[i]-s[i-1]-2)/2;
            if(c%2==0&&i<=c/2)
            {
                ans+=1ll*(s[i]-s[i-1])*(s[i]-s[i-1]-1)/2*(s[i+(c/2)]-s[i+(c/2)-1]);
                ans+=1ll*(s[i]-s[i-1])*(s[i+(c/2)]-s[i+(c/2)-1])*(s[i+(c/2)]-s[i+(c/2)-1]-1)/2;
            }
            // printf("%d %d %lld\n",i-1,sum,ans);
        }
    printf("%lld\n",ans);
    return 0;
}