A.这是一个简单的签到题

经典永流传，一个解义符的输出

1
2
3
4
5
6
#include<bits/stdc++.h>
using namespace std;
int main(void){
	printf("\\*CUIT!*\\");
	return 0;
}

B.叔叔送口罩

正如注释所说，答案为每个人没带口罩的概率乘1，然后求和输出即可。

$ans = \sum_{i = 1}^{100} \frac{100 - x_i}{100}$

时间复杂度： $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    scanf("%d", &n);
    double ans = 0;
    for(int i = 1;i <= n;i++){
        double now;
        scanf("%lf", &now);
        ans += now / 100.0;
    }
    printf("%.2lf\n", ans);
    return 0;
}

C. kl爱贴纸

法一：差分前缀和

我们可以开一个数组，每个元素代表一个线段。那么如果这个区间有贴纸，那么区间+1，最后看有多少个线段没有覆盖即可。于是转化为了区间加问题，可以用差分前缀和解决。需要注意的是，数据给的是端点，需要把端点转化为线段。

时间复杂度: $O(m + 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
#include<bits/stdc++.h>

using ll = long long;

const int maxn = 2e5+5;

int num[maxn];
int main(void){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1;i <= m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        num[x + 1] ++;
        num[x + y + 1] --;
    }
    
    int ans = 0;
    for(int i = 1;i <= n;i++){
        num[i] += num[i - 1];
        if(num[i] != 0) ans++;
    }
    
    printf("%d\n", ans);
    
    return 0;
}

法二：模拟区间合并

我们可以把所有重叠的贴纸看成一个大贴纸，这样就是很多个大贴纸在线上，所以可以用区间合并的方法来解决。可以直接用双指针模拟区间合并，也可以用set等等来模拟区间合并，我这里展示一下用双指针模拟区间合并。

时间复杂度: $mlog(m) + 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
42
43
44
45
46
47
48
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5+5;

struct node{
    int l, r;
}seg[maxn];

int cmp(node a, node b){
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}

int main(void){

    int n, m;
    scanf("%d%d", &n, &m);
    
    for(int i = 0;i < m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        seg[i].l = x;seg[i].r = x + y;
    }
    
    sort(seg, seg + m, cmp); // 把所有区间排序，先按左端点，再按右端点
    
    int ans = 0;
    int st = -1, ed = -1;// 当前大区间的起点与终点
    for(int i = 0;i < m;i++){
        if(seg[i].l > ed){ // 如果当前区间与之前的大区间没有相交，那么计算前一个区间的答案以及更新区间
            ans += ed - st; // 区间线段数与端点的关系
            st = seg[i].l;
            ed = seg[i].r;
        }else{
            // 如果当前区间与前一个区间相交，那么只用更新大区间的右端点
            ed = max(ed, seg[i].r);
        }
    }
    
    // 算最后一个区间的贡献
    ans += ed - st;
    
    printf("%d", ans);
    
    return 0;
}

D.我超,yuan

这个题，先说结论，答案是圆A横坐标的最简分数$\frac{a}{b}$与圆B横坐标的最简分数$\frac{c}{d}$的分子与分子与分子相加，分母与分母相加的和，也就是$\frac{a+c}{b+d}$。
由于已经给出了坐标与直径，那么我们可以知道半径和为$\frac{1}{2b^2}$ + $\frac{1}{2d^2}$。
圆心距是$\sqrt{(\frac{a}{b}-\frac{c}{d})^2+(\frac{1}{2b^2}-\frac{1}{2d^2})^2 }$。
如果相切，我们圆心距与半径和相减，我们可以简单化简公式为$(ad-bc)^2 = 1$。
那么根据这一步，我们知道了相切条件，并且由于$a,b,c,d$都是正数，所以说结果一定是$\ge 1$的，这也证明了任意两个圆不会相交。
那么我们现在假设$\frac{a}{b} < \frac{o}{p} < \frac{c}{d}$。

如果C与A,B相切，那么易得$(ap-bo)^2 = (cp-do)^2$。根据大小关系，我们可以直接打开平方，结果为
$bo-ap = cp-do$，再移项得$o(b+d) = p(a+c)$，最后化简为$\frac{o}{p} = \frac{a+c}{b+d}$。
得证。
并且我们可以根据裴祖定理得知$\frac{a+c}{b+d}$一定是最简分数

时间复杂度： $O(log(1e7))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
	if ( b > 0 )
		return gcd( b , a%b );
    else return a ;
}
int main(void){
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
    int g1 = gcd(a,b);
    int g2 = gcd(c,d);
    a /= g1,b /= g1;
    c /= g2,d /= g2;
    printf("%d %d\n",a+c,b+d);
    return 0;
}

E.DDL

先说结论：输出最大的奇数,如果没有奇数就是最大的偶数
我们回看题目会发现有三个规则：

  1. 同奇同偶会剩下 更大的数
  2. 一奇一偶会剩下 奇数
  3. 总数为奇数剩下 最后一个数
    我们采用反证法：即最大的奇数会被淘汰，他会在哪被淘汰了呢？
         回看规则1，作为最大的奇数，他肯定不会被淘汰
     回看规则2，作为一奇一偶的奇，也不会被淘汰
     回看规则3，他只会被留下6
    即：最大的奇数不会淘汰（即使最大的奇数有多个，剩下的那个数肯定也是这个大小） 如果没有奇数，更具规则2，最大的偶数会被留下

时间复杂度： $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main(void){
    int n;
    scanf("%d",&n);
    int ans2 = -1;
    int ans1 = -1;
	for( int i = 1 ; i <= n ; i++ ){
		scanf("%d",&a[i]);
		if( a[i] % 2 == 1 ){//奇数 
			ans1 = max( ans1 , a[i] );	
		}
		ans2 = max( ans2 , a[i] );
	}
	if( ans1 != -1 ) printf("%d\n",ans1);
	else printf("%d\n",ans2);
	return 0;
	
}

F.泥头车创创子

法一：二分

我们可以先把剩余木桶数算出来，然后把中位数的位置算出来，这样就知道了中位数左侧有多少个幸存的木桶，然后来二分答案，check即为判断当前数字左侧幸存木桶数量多少。

时间复杂度：$O(mlog(1e18))$

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
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 2e5+5;

ll n, m;
ll pos;
struct node{
    ll l, r;
}seg[maxn];

int check(ll mid){
    // 总的数量减去左侧烂木桶的数量即为当前及左侧剩余的数量，需要注意当前check的木桶已经烂掉了的情况
    ll num = mid;
    for(int i = 0;i < m;i++){
        if(seg[i].r < mid){
            num -= seg[i].r - seg[i].l + 1;
        }
        if(seg[i].l <= mid && mid <= seg[i].r){
            num -= mid - seg[i].l + 1;
        }
    }
    if(num < pos) return 0;
    return 1;
}

int main(void){
    scanf("%lld %lld", &n, &m);
    
    ll len = 0;
    for(int i = 0;i < m;i++){
        ll l, r;
        scanf("%lld %lld", &l, &r);
        seg[i].l = l; seg[i].r = r;
        len += r - l + 1;
    }

    if(len == n){
        printf("-1");
        return 0;
    }

    pos = (n - len + 1) / 2;

    ll l = 1, r = 1e18;
    while(l < r){
        ll mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld\n", l);
    return 0;
}

法二：模拟

我们先把中位数是第几个幸存的数字算出来，然后把区间排序，从左到右遍历一次，直接找即可。

时间复杂度： $O(mlog(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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>

using ll = long long;
using namespace std;

const int maxn = 2e5+5;
struct node{
    ll l, r;
}seg[maxn];

int cmp(node a, node b){
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}

int main(void){
    ll n, m;
    scanf("%lld %lld", &n, &m);

    ll len = 0;
    for(int i = 0;i < m;i++){
        ll x, y;
        scanf("%lld %lld", &x, &y);
        seg[i].l = x;seg[i].r = y;
        len += y - x + 1;
    }

    if(len == n){
        printf("-1\n");
        return 0;
    }

    // 为了方便处理，在两边各添加一个
    seg[m].l = 0, seg[m].r = 0;
    seg[m + 1].l = n + 1, seg[m + 1].r = n + 1;
    
    // 结构体排序	
    sort(seg, seg + m + 2, cmp);
    
    ll now = 0;
    ll pos = (n - len + 1) / 2;
    ll ans = -1;
    for(int i = 1;i < m + 2;i++){
        // 前一个区间右端点到当前区间左端点之间就是幸存的
        // 如果加上当前这部分超过了，那么就找到了
        if(now + (seg[i].l - seg[i-1].r - 1) >= pos){
            ans = seg[i-1].r + pos - now;
            break;
        }
        now += seg[i].l - seg[i-1].r - 1;
    }
    printf("%lld\n", ans);

    return 0;
}