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