2019年软件计科国庆新生联和赛题解

2019-10-07 ACM 阅读量

种种原因~~主要是计科的锅~~，比赛计科前的题目过于儿戏，$rand$ 的题目都往上放，$TC$ 数据只挂输入没挂输出，由于没网，离线 $OJ$ 不能重测，不能删题，全场所有人白给一道题，不过还好没有人因为罚时比别人名次低(前几)。不管软件这次出题真的是面面俱到了，希望大家认真补题。

题目分析

题目分布：软件-ACM集训队 A B C D题，计科-ACM工作室 I J K L 题，计科 - TC工作室 E F G H题
题目难度：

签到题： $A,G,J$
防 $AK$ 题：$C,I,L$
其余题目均为一般题

补题链接

点这里

A. Apple 大法好

题解

显然，最大值是 $m,k$ 的最小值。而对于最小值而言，当 $m+k \leq n$ 时，此时最少的人数应该为 $0$ ，很多人没注意到这一点。当 $n \leq m+k $ 时，此时直接输出 $m+k - n$ 即可。

标程

时间复杂度:$O(1)$

#include<stdio.h>
int main() {
    int n;
    while(scanf("%d",&n) !=EOF) {
        int m,k;
        scanf("%d %d",&m,&k);
        int MAX;
        if(m < k)
            MAX = m;
        else
            MAX = k;
        int ans = n - (m + k);
        if(ans < 0)
            printf("%d %d\n",MAX,-ans);
        else
            printf("%d 0\n",MAX);
    }
}

B. wbt和wpm的博弈游戏

题解

~~仔细读题不难发现说了一堆废话~~
只需要判断 $n,m$ 的关系即可。注意输出的是$N0$ 不是 $NO$ 。

标程

时间复杂度:$O(1)$

#include<stdio.h>
const int N = 1010;
int a[N], b[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &b[i]);
    }
    if (n > m)
        printf("YES\n");
    else
        printf("N0\n");
    return 0;
}

C. 到底谁是510最懒的？

题解

两层 $for$ 循环,第一层枚举每个人，第二层枚举每个人之前有多少个比他懒的人直接输出即可。

标程

时间复杂度:$O(n^2)$

#include<stdio.h>
int main() {
    int n, a[1005], b = 0;
    scanf("%d", &n);
    for(int i = 0;i < n;i++)
        scanf("%d",&a[i]);
    for(int i = 0;i < n;i++) {
        for(int j = i - 1;j >= 0;j--)
            if(a[i] > a[j])
                b++;
        printf("%d ",b);
        b = 0;
    }
    return 0;
}

D. why挤公交

理论上的防 $AK$ 题。

题解

Alt
~~太刁民了~~

标程

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

#include <iostream>
using namespace std;
const int maxn = 1e4 + 10;
int aa[maxn], bb[maxn];
int main() {
    int a, n, m, x;
    scanf("%d %d %d %d",&a,&n,&m,&x);
    aa[1] = 0, aa[2] = 1, aa[3] = 2;
    for(int i = 4; i < n; i++) {
        aa[i] = aa[i - 1] + aa[i - 2] - 1;
        bb[i] = bb[i - 1] + bb[i - 2] + 1;
    }
    int b = (m - aa[n - 1] * a) / bb[n - 1];
    printf("%d\n",aa[x] * a + bb[x] * b);
}

感受算法的魅力

你们学完二分以后可以再回头看这个题目，这里提供一种二分的解法。

直接暴力枚举第二站的上下车人数 $x$ 然后每次都去循环判断，到第 $n$ 站是否满足题目中的 $m$，如果满足这个 $x$ 就是我们要找的。如果按照我们枚举的 $x$ 得到的答案比题目中最后一站的人多则缩小 $x$ 的范围，否则增大，这样最终我们会得到一个满足题意的 $x$ 然后直接输出所求即可。

标程2

时间复杂度:$O(n*log{n})$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
const int INF = 0x3f3f3f3f;
long long up[MAXN],down[MAXN],a[MAXN];
int n,m,x;

int judge(int mid) {
    up[1] = a[1],up[2] = mid;
    down[1] = 0,down[2] = mid;
    for(int j = 3; j <= n; j++) {
        up[j] = up[j-1] + up[j-2];
        down[j] = up[j-1];
        a[j] = a[j-1] + up[j] - down[j];
    }
    if(a[n-1] == m) {
        cout << a[x] << endl;
        return 2;
    } else if(a[n-1] > m) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> a[1] >> n >> m >> x;
    if(x == 1 || x == 2) {
        cout << a[1] << endl;
        return 0;
    }
    a[2] = a[1];
    int L = 0,R = INF;
    while(L <= R) {
        int mid = (L + R) >> 1;
        int ans = judge(mid);
        if(ans == 2) {
            return 0;
        } else if(ans == 0) {
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return 0;
}

E.一道快乐的水题

题解：

只需要看当前指针指着的字母离下一个字母顺时针旋转近还是逆时针旋转近，最后把每次拧的次数加起来就行了。

标程

#include <stdio.h>
#include <string.h>
char ss[1000];
int main() {
    scanf("%s", ss);
    int sum = 0;
    char index = 'a';
    for (int i = 0; i < strlen(ss); i++) {
        int num = index - ss[i];
        if (num < 0)
            num += 26;
        if (num > 13)
            num = 26 - num;
        sum += num;
        index = ss[i];
    }
    printf("%d\n", sum);
    return 0;
}

F.最简单的签到题

题解

~~暖心签到竟成了劝退打法？~~ 大水题，但是要注意“！”是中文的感叹号，复制粘贴输出就可以了。

标程

#include<stdio.h>
int main() {
    printf("Hello World ！\n");
    return 0;
}

G.来自步步的疑惑

题解

从给定的坐标中找出上下左右的最值，作为矩形的上下左右边界，就可以求出矩形左上角和右下角的坐标。

标程

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int flag = 1;
    while (flag) {
        flag = 0;
        int x, y, Left = 1e6 + 5, Right = -1e6 - 5, Up = -1e6 - 5, Down = 1e6 + 5;
        while (~scanf("%d %d", &x, &y)) {
            if (x == 0 && y == 0)
                break;
            flag = 1;
            Left = min(Left, x), Right = max(Right, x);
            Down = min(Down, y), Up = max(Up, y);
        }
        if (flag)
            printf("%d %d %d %d\n", Right, Up, Left, Down);
    }
    return 0;
}

H.dch与lgp学弟的刁难

题解

我们可以这么想数组的下标看作x轴，对应的值看作y轴，那么区间值就是以下标和对应值作为坐标的区间左右边界的距离。那么求区间值的最小值就是求左右边界坐标的直线距离，也就是不进行任何拆分时的值。（数据范围会炸int）

标程

#include <stdio.h>
#include <math.h>
long long arr[1000005];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
    for (int i = 1; i <= m; i++) {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        double ans = sqrt((y - x) * (y - x) + (arr[x] - arr[y]) * (arr[x] - arr[y]));
        printf("%.3lf\n", ans);
    }
    return 0;
}

I.三角形？矩形？

题解

由于是矩形，那么必须是两个全等的直角三角形才能构成矩形。按从大到小排序，判断是否三个边都相等，其次判断a[0]*a[0]+a[1]*a[1]==a[2]*a[2]即可判断能否构成直角三角形

标程

#include <stdio.h>
void Bubble_Sort(int a[], int len) {
    int temp;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}
int main() {
    int a[3], b[3], i, ans = 0;
    for (i = 0; i < 3; i++) {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < 3; i++) {
        scanf("%d", &b[i]);
    }
    Bubble_Sort(a, 3);
    Bubble_Sort(b, 3);
    for (i = 0; i < 3; i++) {
        if (a[i] == b[i])
            ans++;
    }
    if (ans == 3) {
        if (a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    } else {
        printf("No\n");
    }
    return 0;
}

~~当然可以用更高效的排序，或者直接枚举全部情况~~

J.国庆集训

题解

题意可能很难读懂（~~预计的水题导致没人出~~ 背锅），但是：
可以将时间看作一个区间寻找规律：

$[1,n]$：学姐0

$[n+1,m+n]$：学姐1

$[m+n+1,2n+1]$：学姐0

$[2n+2,m+2n+1]$：学姐1

$[m+2n+2,3n+2]$：学姐0

$[3n+3,m+3n+2]$：学姐1
……
不难发现，除了第一次长度为$m+n$以外其余区间的长度均为$n+1$

故分两种情况:

$t\leq m+n$时，$[1,n]$为学姐0，$[n+1,m+n]$为学姐1。
$t>m+n$时，对每一个周期$n+1$内，前$n-m+1$天是学姐0，后$m$天是第学姐1。

标程

#include <stdio.h>
int main() {
    int T, n, m, q, t;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &q);
        while (q--) {
            scanf("%d", &t);
            if (t > n + m) {
                t = t - (n + m);
                if (t % (n + 1) != 0)
                    t = t % (n + 1);
                else
                    t = n + 1;
                printf("%d\n", t > n - m + 1);
            } else
                printf("%d\n", t > n);
        }
    }
    return 0;
}

K.爱的魔力转圈圈

题解

首先：得知道相切的时候数量最小
其次：我们只需要算每一个R球最大能占r球圆心角360°的多少°，如图：

根据题目提示和上图不难知道，答案将
向上取整即可。

标程

#include <math.h>
#include <stdio.h>
const double pi = 3.141593;
double r, R;
int main(){
	while(~scanf("%lf%lf",&r,&R)){
		printf("%d\n", (int)ceil(pi / asin(R / (r + R))));			
	}
	return 0;
}

L.nuoyanli会打印图形

题解

对于打印图形的题，使用平面几何知识也是很简单的；

标程

#include <stdio.h>
int main() {
    int a, b;
    int n;
    while (~scanf("%d", &n)) {
        for (a = 0; a < (4 * n - 3); a++) {
            for (b = 0; b < (6 * n - 5); b++) {
                if ((a == (3 * n - 3 - b)) || (a == (b - 3 * n + 3)) || (a == (b + n - 1)) ||
                    (a == (7 * n - 7 - b)) || (a == n - 1) && (b % 2 == 0) ||
                    (a == 3 * n - 3) && (b % 2 == 0))
                    printf("*");
                else if ((a > (3 * n - 3)) && (a > (7 * n - 7 - b)) || (a < n - 1) && (a < (b - 3 * n + 3)))
                    continue;
                else if ((a > (3 * n - 3 - b)) && (a > (b - 3 * n + 3)) ||
                         (a > (b - 3 * n + 3)) && (a <= (3 * n - 1)) || (a < (7 * n - 7 - b)))
                    printf(" ");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

感谢 王启宇 为我们提供详细的题解：https://blog.csdn.net/nuoyanli/article/details/102456178，至于for一行一行暴力找规律的代码就不贴出来了。