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

题目分析

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

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

抱歉：第一次比赛出现很多问题，有些题面和数据补题赛已经修好QAQ

补题链接:

https://nuoyanli.com/contest/19/problems

A.最简单的签到题

题目链接：

https://nuoyanli.com/contest/19/problem/A

题意

要求输出“Hello World ！”。

解题

大水题，但是要注意“！”是中文的感叹号，复制粘贴输出就可以了。

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

B.爱的魔力转圈圈

题目链接

https://nuoyanli.com/contest/19/problem/B

题解

• 首先：得知道相切的时候数量最小
• 其次：我们只需要算每一个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;
}

C.why挤公交

理论上的防 $AK$ 题。

题目链接：

https://nuoyanli.com/contest/19/problem/C

题解

太刁民了

标程

时间复杂度:$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;
}

D.一道快乐的水题

题目链接：

https://nuoyanli.com/contest/19/problem/D

题意：

要求输出最少拧几次。

解题思路：

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

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

E.nuoyanli会打印图形

题目链接

https://nuoyanli.com/contest/19/problem/E

题解

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

完整代码：

#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一行一行暴力找规律的代码就不贴出来了。

F.来自步步的疑惑

题目链接：

https://nuoyanli.com/contest/19/problem/F

题意：简单

解题：

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

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

G.wbt和wpm的博弈游戏

题目链接：

https://nuoyanli.com/contest/19/problem/G

题解

仔细读题不难发现说了一堆废话
只需要判断 $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;
}

H.到底谁是510最懒的？

题目链接：

https://nuoyanli.com/contest/19/problem/H

题解

两层 $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;
}

I.国庆集训

题目链接：

https://nuoyanli.com/contest/19/problem/I

题解

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

• $[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$

故分两种情况:

1. $t\leq m+n$时，$[1,n]$为学姐0，$[n+1,m+n]$为学姐1。
2. $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;
}

J.三角形 ？矩形？

题目链接

https://nuoyanli.com/contest/19/problem/A

题解

由于是矩形，那么必须是两个全等的直角三角形才能构成矩形。按从大到小排序，判断是否三个边都相等，其次判断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;
}

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

K.Apple 大法好

题目链接：

https://nuoyanli.com/contest/19/problem/K

题解

显然，最大值是 $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);
    }
}

L.dch与lgp学弟的刁难

题目链接：

https://nuoyanli.com/contest/19/problem/L

题意：

题中给出了区间值的计算函数并说明大区间值可以拆分成小区间值的和，不同的拆分方法可以得到不同的值，要求求出最小值。

解题：

我们可以这么想数组的下标看作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;
}