Zth's Blog

记录学习路上的点滴

0%

2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛（正式赛）

发表于 分类于

2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛（正式赛）

E 找规律

代码

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
#include <iostream>
#include <cstdio>

int t;
int n, k, q;
int ans;

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d%d%d", &n, &k, &q);
        k ++;

        if(q % 2)
        {
            if(k + q - 1 <= n)
                ans = k + q - 1;
            else
            {
                k -= n - q + 1;

                int turns = k / n, lft = k % n;

                if(turns % 2)
                    ans = lft ? lft : 1;
                else
                    ans = lft ? n - lft + 1 : n;
            }
        }
        else
        {
            if(q - k + 1 >= 1)
                ans = q - k + 1;
            else
            {
                k -= q;

                int turns = k / n, lft = k % n;

                if(turns % 2)
                    ans = lft ? n - lft + 1 : n;
                else
                    ans = lft ? lft : 1;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

I 签到之一

代码

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 <iostream>
#include <cstdio>
#include <algorithm>

int n;
int a[112345];
bool one;
int z;
int ans;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);

        if(a[i] == 1) one = true;
        if(a[i] == 0) z ++;
    }

    std:: sort(a + 1, a + n + 1);
    n = std:: unique(a + 1, a + n + 1) - a - 1;

    if(z == 1)
        ans = 1;
    else if(z > 1)
        ans = 0;
    else if(one)
        ans = n - 1;
    else
        ans = n;

    printf("%d\n", ans);

    return 0;
}

J 签到之一

题解

代码其实有点假， 思路是正方体展开必然是第二行满的， 第一行第三行各一个， 然后就判断就可以了

但是实际上会出现别的情况， 但是我这么想然后写的过了。。。

代码

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
#include <iostream>
#include <cstdio>

int mp[4][5];
int a[7];
bool ans = true;

int main()
{
    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
            scanf("%d", &mp[i][j]);

    for(int j = 1; j <= 4; j ++)
        for(int i = 1; i <= 3; i ++)
        {
            if(i == 2) continue;

            if(mp[i][j] && !mp[2][j]) std:: swap(mp[i][j], mp[2][j]);
        }

    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
        {
            if(i == 2) continue;

            if(mp[i][j]) std:: swap(mp[i][1], mp[i][j]);
        }

    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
        {
            if(i + 1 <= 3 && i - 1 >= 1 && mp[i + 1][j] && mp[i - 1][j])
                a[mp[i + 1][j]] = mp[i - 1][j], a[mp[i - 1][j]] = mp[i + 1][j];

            if(j + 1 <= 4 && j - 1 >= 1 && mp[i][j + 1] && mp[i][j - 1])
                a[mp[i][j + 1]] = mp[i][j - 1], a[mp[i][j - 1]] = mp[i][j + 1];
        }

    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
            scanf("%d", &mp[i][j]);

    for(int j = 1; j <= 4; j ++)
        for(int i = 1; i <= 3; i ++)
        {
            if(i == 2) continue;

            if(mp[i][j] && !mp[2][j]) std:: swap(mp[i][j], mp[2][j]);
        }

    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
        {
            if(i == 2) continue;

            if(mp[i][j]) std:: swap(mp[i][1], mp[i][j]);
        }

    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 4; j ++)
        {
            if(i + 1 <= 3 && i - 1 >= 1 && mp[i + 1][j] && mp[i - 1][j])
            {
                if(a[mp[i + 1][j]] != mp[i - 1][j]) ans = false;
            }

            if(j + 1 <= 4 && j - 1 >= 1 && mp[i][j + 1] && mp[i][j - 1])
            {
                if(a[mp[i][j + 1]] != mp[i][j - 1]) ans = false;
            }
        }

    if(ans)
        printf("YES\n");
    else
        printf("NO\n");
}

下面是重现赛后补的题

A. SegmentTree

题意

给一个线段树的代码如下

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
#include <bits/stdc++.h>
#define mid	(l + r) / 2
#define ls	now * 2
#define rs	now * 2 + 1
using namespace std;
int n, q, l, r;
int flag = 0;
void build( int now, int l, int r, int *a )
{
	if ( l == r )
	{
		cin >> a[now]; return;
	}
	build( ls, l, mid, a );
	build( rs, mid + 1, r, a );
	a[now] = a[ls] + a[rs];
	return;
}


int query( int now, int l, int r, int L, int R, int *a )
{
	if ( a[ls] + a[rs] != a[now] )
		flag = 1;
	if ( L <= l && r <= R )
		return(a[now]);
	int sum = 0;
	if ( L <= mid )
		sum += query( ls, l, mid, L, R, a );
	if ( mid + 1 <= R )
		sum += query( rs, mid + 1, r, L, R, a );
	return(sum);
}


int main()
{
	cin >> n >> q;
	int a[4 * n];
	memset( a, 0, sizeof(a) );
	build( 1, 1, n, a );
	for (int i = 1 ; i <= q ; i++ )
	{
		cin >> l >> r;
		cout << query( 1, 1, n, l, r, a ) << endl;
	}
	return 0 ;
}

把这份代码提交到一个线段树的板题上， 板题一共有$T$组测试样例， 每组测试样例有$n$次询问， 给出$T$， 然后每组测试样例给出一个$n$， 随机生成$n$个询问$\{l, r\}$， 其中保证$\{l, r\}$是合法的， 问AC这道板题的概率是多少， 输出答案模$10^9 + 7$

数据范围

$1 \leq T \leq 10$

$1 \leq n, q \leq 10^5$

$1 \leq a_i \leq 1000$

题解

Hint1

首先看代码有什么错误， 但是我看了好几遍并没有看出来什么错误

仔细看看它有一个flag是没有用的， 错误就出在这里， 我们访问到每个节点时都会访问他的左右儿子， 但是叶子结点没有左右儿子

众所周知线段树要开四倍空间， 那访问了叶子结点的儿子(当然不存在)就会导致越界， 就不能AC了

Hint2

那我们就可以找到越界的那些询问， 然后随便组合数学一下就知道答案了， 那什么时候一个询问$\{l, r\}$一定会产生越界呢？

Hint3

首先越界一定是访问到了某些叶子结点， 由于$n$只有$10^5$， 我们可以模拟出建树的整个过程， 从而确定访问到哪些叶子结点会导致越界， 所以现在我们找到了所有会越界的叶子结点

然后我们就需要考虑另外一个问题了， 什么情况下对于一个询问$\{l, r\}$必然会访问到某个给定的叶子结点呢？

Hint4

一个叶子结点如果是它父亲的左儿子， 那么如果一个询问包含了这个结点和他的右兄弟， 那它就不可能被访问到， 所以询问必然是要以这个叶子结点为右端点， 就可以保证必然访问到它

一个叶子结点如果是它父亲的右儿子， 那么所有以这个结点为左端点的询问都会访问到这个叶子结点

总的规律就是一个询问如果要访问一个特定的结点， 那么首先它要完全包含这个结点的区间， 其次它不能完全包含这个结点的父亲的区间

然后就可以写代码了

代码

时间复杂度就是线段树建树的时间复杂度

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
#include <iostream>
#include <cstdio>

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

const int mod = 1e9 + 7;

int t;
int n, q;
int mx; // 越界的极限， 也就是4 * n
int tot, cnt, ls; // tot表示总的不同询问的数量， cnt表示会出错的询问的数量， ls表示当前出现了多少个越界的左端点
int ans = 1;

int Qpow(int x, int y)
{
    int res = 1;
    for( ; y; x = 1LL * x * x % mod, y >>= 1)
        if(y & 1)
            res = 1LL * res * x % mod;

    return res;
}

void Build(int l, int r, int rt)
{
    if(l == r)
    {
        if((rt << 1 | 1) >= mx)
        {
            int tmp = 0;

            if(rt % 2)
                tmp = n - l + 1, ls ++; // 加上以该结点为左端点的询问
            else
                tmp = l - ls; // 加上以该结点为右端点的询问， 有些询问被算了两次， 要减去一次， 因为建树是从左到右的， 所以ls是正确的

            cnt = (1LL * cnt + tmp + mod) % mod;
        }

        return;
    }

    int mid = (l + r) >> 1;

    Build(lson);
    Build(rson);
}

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        cnt = tot = ls = 0;

        scanf("%d%d", &n, &q);

        mx = n << 2;
        tot = (1LL + n) * n / 2 % mod;

        Build(1, n, 1);

        int res = (tot - cnt + mod) % mod;
        res = 1LL * res * Qpow(tot, mod - 2) % mod;
        res = Qpow(res, q); // 这组测试样例正确的概率

        ans = 1LL * ans * res % mod; // T组测试样例正确的概率
    }

    printf("%d\n", ans);

    return 0;
}

C. GCD

题意

给出三个数$l, r, k$， 从$[l, r]$中选出$k$个不同的数， 这些数的$gcd$为$d$， 求不同的$d$的个数

数据范围

$1 \leq l \leq r \leq 10^{12}, 2 \leq k \leq r - l + 1$

题解

想法

刚拿到这个题我想的是假设$gcd$为$d$， $[l, r]$中有$x$个数是$d$的倍数且有$x \geq k$， 他们分别是$d$的$b, b + 1, b + 2, …$倍， 那么怎么从中选出$k$个$b + y$让他们互质呢？

其实这根本不用考虑， 因为对于任意一个正整数$x$， $gcd(x, x + 1) = 1$， 证明很简单

假设$gcd(x, x + 1) = 2$， 那么需要$x, x + 1$至少都是$2$的倍数， 但是$2$的倍数两个连续两个数里只有一个， 相邻的两个数必不可能都是$2$的倍数

假设$gcd(x, x = 1) = 3$， 那么需要$x, x + 1$至少都是$3$的倍数， 但是$3$的倍数三个数里只有一个， 相邻两个数必不可能都是$3$的倍数

…..

就能证出来了， 他们俩最多只能都是$1$的倍数

正解

这里直接给出正解了

假设$gcd = d$， 那么$d$可行的充分条件为$\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l - 1}{d} \rfloor \geq k$

首先看到这个式子我们肯定要想为什么是$l - 1$而不是$l$， 因为如果是$l$的话， 如果$l$恰好是$d$的倍数， 那实际上只要满足$\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l}{d} \rfloor \geq k - 1$就可以了， 因为$l$是算的， 但是如果$l$不是$d$的倍数就是$\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l}{d} \rfloor \geq k$， 显然不如直接$\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l - 1}{d} \rfloor \geq k$方便， 不用特判， 避免了很多麻烦， 后续会发现如果用$l$的话就没法做了

我们显然不能直接枚举$d$， 但是看到条件的式子里都是整除且被除数都是不变的， 可以想到整除分块

对$r, l - 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
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
#include <iostream>
#include <cstdio>

long long ql, qr, k;
struct Seg
{
    long long d, l, r; // d是整除的结果， l， r是结果相同的端点
} ll[2123456], rr[2123456];
int cnt[2];
long long ans;

void Work(Seg* a, int b, long long n)
{
    long long l = 1;
    while(l <= n)
    {
        long long tmp = n / l;
        long long r = n / tmp;

        a[++ cnt[b]] = (Seg){tmp, l, r};

        l = r + 1;
    }
}

long long Insect(long long l1, long long r1, long long l2, long long r2) // 区间求交
{
    if(l1 > l2)
        l1 ^= l2, l2 ^= l1, l1 ^= l2, r1 ^= r2, r2 ^= r1, r1 ^= r2;

    if(l2 > r1)
        return 0;
    else if(r2 <= r1)
        return r2 - l2 + 1;
    else
        return r1 - l2 + 1;
}

int main()
{
    scanf("%lld%lld%lld", &ql, &qr, &k);

    Work(ll, 0, ql - 1);
    ll[++ cnt[0]] = (Seg){0, ql, qr};

    Work(rr, 1, qr);

    int j = cnt[1];
    for(int i = cnt[0]; i; i --)
    {
        long long lk = ll[i].d;

        while(j && rr[j].d < lk + k) j --; // 找到r符合条件的整除区间

        long long l1 = ll[i].l, r1 = ll[i].r, r2 = rr[j].r;

        if(j) ans += Insect(l1, r1, 1LL, r2);
    }

    printf("%lld\n", ans);

    return 0;
}