18-19学年码到成功ACM集训队招新

|

ACM集训队招新算法考核

作者：肖锐

简介

本次比赛设置赛题8道，其难度不一，时间长度为2.5小时，按照OI赛制选拔队员。

比赛结果

OI排名

比赛现场

A9-303

A9-301
赛后部分题目讲解
比赛题目部分讲解

题目以及题解

一览

题目 难度
A 老陈的口算题 简单
B 老陈的校验码 较简单
C 老陈的字符串 较难
D 老陈的七彩石 难
E 老陈的三角形 较难
F 老陈的海岸线 难
G 老陈的日记 较简单
H 老陈的集合 简单

第一题

题解

直接循环输入a、b、c后判断a+b是否等于c即可。

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
#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    int ans1 = 0,ans2 = 0;
    for(int i = 0;i < n;i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a + b == c)
        {
            ans1 ++;
        }
        else
        {
            ans2 ++;
        }
    }
    printf("%d %d",ans1,ans2);
    return 0;
}
 
/**************************************************************
    Problem: 4481
    Language: C++
    Result: 正确
    Time:3 ms
    Memory:1080 kb
****************************************************************/

第二题

题解

对于一级校验码，遍历一遍输入的字符串，统计0-9，A-F的数量。（注意F之后的字母不要算）
统计之后将每个数转化成十六进制后形成所要的校验码。
对于K>1的情形，重复上面操作即可。

第三题

题解

我们可以遍历存下A、C、M这三个字母在字符串中出现的位置。
对于每一个A的位置，在题目要求的长度范围内找到第一个C。（利用所得的所有C的位置）
之后计算这个C到要求长度范围内有几个M。
累加即可。
注意答案超过int范围。

第四题

题解

对于现在有的石头和需要的石头，我们可以相减一下得到还需要多少个或者多了多少个这种石头。

遇到需要补充的石头直接从离它最近的高等级石头开始砸起，计数即可。
（对于次数可以先预算一下。例如一块紫色石头能砸出多少个红色石头，要砸多少次之类，加快速度）

第五题

题解

计算三角形三边的长度。（两点间距离）
如果三边都是非整数那么肯定不能让三角形变成符合要求的三角形。
如果三边都是整数且不一样，那么就已经符合要求了。
如果有两边一样或者有两边不是整数，那么我们需要判断是整数的那条边是否是1。如果是，那么就无法得到符合要求的三角形；否则可以。（利用三角形两边之和大于第三边可以得到不存在）
如果有两边是整数，判断两边之中大者是不是1即可。（同上判断）

第六题

题解

利用bfs/dfs算法可以解决，重点在边长的计算。（不详述）

第七题

题解

本题两个问题：判断日期是否合法，判断日期大小
是否合法（yy/mm/dd）：
注意判断dd是否在对应月份的天数内。mm不能超过12。注意判断闰年，注意负数。
判断日期大小：
年份小的必定小，年份一样看月份，月份一样看日。
注意判断日期合法后才能判断大小。

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
#include <stdio.h>
 
int mon[1000000] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
    int n;
    scanf("%d", &n);
    int maxy = 9999999,maxm = 9999999,maxd = 9999999;
    int yy,mm,dd;
    int count = 0;
    for(int i = 0;i < n;i ++)
    {  
        scanf("%d/%d/%d",&yy,&mm,&dd);
 
        int flag = 0;
         
        if(yy % 400 == 0 || (yy % 100 != 0 && yy % 4 == 0)) 
        {
            flag = 1;
            mon[2] ++;
        }
 
        if(mm < 1 || mm > 12 || !(dd >= 1 && mon[mm] >= dd))
        {
            count ++;
            if(flag == 1)
            {
                mon[2] --;
            }
            continue;
        }
 
        if(flag == 1)
        {
            mon[2] --;
        }
         
        if(maxy > yy)
        {
            maxy = yy;
            maxm = mm;
            maxd = dd;
        }
        else if(maxy == yy && maxm > mm)
        {
            maxm = mm;
            maxd = dd;
        }
        else if(maxy == yy && maxm == mm && maxd > dd)
        {
            maxd = dd;
        }
    }
    printf("%d/%d/%d\n",maxy,maxm,maxd);
    printf("%d error(s)",count);
 
    return 0;
}
/**************************************************************
    Problem: 4487
    Language: C++
    Result: 正确
    Time:36 ms
    Memory:4984 kb
****************************************************************/

第八题

题解

可以使用一个数组将输入的所有数放在一个数组里后排序，每输出一个数检查是否是上一个输出的数就行了。
坑点：题目写着“均不超过1000”，但可能是一个很大的负数，所以这题要使用long long来存数据才能通过，否则最多92分。
如果使用C++，set会很便利。

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
#include <stdio.h>
#include <set>
/*
 *set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就像一个集合一样。
 *所有的操作的都是严格在logn时间之内完成，效率非常高。
 *set容器中的值都是唯一的，即不能再插入一个容器中已经有的值。
 */
using namespace std;
 
int main()
{
    set<long long> s; //创建一个空的set容器，里面元素的类型为long long
    int n, m;
    scanf("%d%d", &n, &m);
    long long t;
    for(int i = 0;i < n;i ++)
    {
        scanf("%lld", &t);
        s.insert(t); //把t插入到容器中，容器中没有这个值的话成功插入，否则插入失败。
    }
    for(int i = 0;i < m;i ++)
    {
        scanf("%lld", &t);
        s.insert(t);
    }
 
    set<long long>::iterator itr;
 
    //遍历set，因为set是有序，唯一的，所以直接输出就是答案
    for(itr = s.begin();itr != s.end();itr ++) 
    {
        printf("%lld ",*itr);
    }
 
    return 0;
}
 
/**************************************************************
    Problem: 4488
    Language: C++
    Result: 正确
    Time:3 ms
    Memory:1204 kb
****************************************************************/

总结

本次比赛举办得较好，有力得促进了各参赛者的编程水平以及提高其编程积极性。
感谢出题人以及队内管理人员的付出。
2018即将过去，迎来2019，在新一年里，集训队要争取更好成绩，push