SDNU ACM-ICPC 2018 Training Weekly Contest(Freshman/11-11)【解题报告】

发表于 | 更新于 | 分类于

题目难度分析及考察内容：

easy：

1004(C语言)

1001(快速幂模板，周五晚刚讲的)

1005(简单字符串处理)

1006(模拟 + 细节)

medium：

1002(规律||直接做<数组开全局就能开的下了>)

1003(中等字符串处理)

1008(结构体排序<课上没讲吗?那就趁这个机会学一下>)

1007(题意理解)

hard：

1009(map + 题意)

发现的问题：

  1. 乱加getchar()。(王某)
  2. 数组不开全局，导致RE。(孙某)
  3. 8102年了，不知道递推，求fibonacci数列还用递归(第二题没做出来的xxxxxxx)
  4. 不跟榜，在一个题上从开场WA到结束。
  5. 对罚时还没概念，这个慢慢培养吧，身处弱校 + 自身菜鸡很多时候都靠罚时蹭个牌。。

说明：

这些题目一周内完全可以补完，下周一至周四尽量补完。

充分思考后再看思路，最后再看代码。AC过也最好看看，说不定就学到新知识了呢。

一定要保证最后能自己写出来并AC掉。

题解

1349.快速幂入门

快速幂模板题，签到

Code:无。

1356.Fibonacci

题意：给出一个序列，序列的定义为

$
\operatorname{F[i]}=\begin{cases}
7 & \text{i = 0 } \
\text 11 & \text{i = 1}\
F[n-1] + F[n-2] & \text{i $\geq$ 2 } \
\end{cases}
$

问F[n] % 3 是否等于 0

思路：

  1. 直接做(怎么还有人用递归？这种可以递推的别递归啊，看一下n的范围，递归这不明摆着过不了吗)

    可以直接做的原因是 $(a + b) \% m = ((a \% m) + (b \% m)) \% m$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000010;

int f[N], n;
void init()
{
    f[0] = 7, f[1] = 11;
    for(int i = 2; i < N; ++i)
        f[i] = (f[i - 1] + f[i - 2]) % 3;
}
int main()
{
    init();
    while(~scanf("%d", &n))
        puts(f[n] ? "no" : "yes");
    return 0;
}
  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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

//int f[111];
int main()
{
    /*
    f[0] = 7, f[1] = 11;
    for(int i = 2; i <= 20; ++i)
        f[i] = f[i - 1] + f[i - 2];

    for(int i = 0; i <= 20; ++i)
        cout << f[i] % 3 << ' ';
    cout << '\n';
    */
    int n;
    while(~scanf("%d", &n))
        puts((n - 2) % 4 ? "no" : "yes");
    return 0;
}

1357.Text Reverse

题意：将输入的每个字符进行翻转。

思路：直接做

代码：用string的reverse函数可以简单快速的实现

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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;

int t;
string a, s;
int main()
{
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        getline(cin, s);    //读取一行
        stringstream ss(s); //创建一个“字符串流”
        bool flag = 0;      //控制空格
        while(ss >> a)
        {
            if(flag)    cout << ' ';
            flag = 1;
            reverse(a.begin(), a.end());
            cout << a;
        }
        cout << '\n';
    }
    return 0;
}

1358.Buildings

题意：记录只有0和1构成的$N \times M$的矩阵中有多少个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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n, m, tem, res;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        res = 0;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n * m; ++i)
        {
            scanf("%d", &tem);
            res += tem;
        }
        printf("%d\n", res);
    }
    return 0;
}

1359.GPA

题意：自己翻译。

思路：直接做。

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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

bool flag;
int val[256];
char s[1111];
int cnt, len, sum;
void init()
{
    memset(val, -1, sizeof(val));
    val['A'] = 4; val['B'] = 3;
    val['C'] = 2; val['D'] = 1;
    val['F'] = 0;
}
int main()
{
    init();
    while(gets(s))
    {
        flag = 1;
        sum = cnt = 0;
        len = strlen(s);
        for(int i = 0; i < len; ++i)
        {
            if(s[i] == ' ') continue;
            if(val[s[i]] == -1)
            {
                flag = 0;
                break;
            }
            ++cnt;
            sum += val[s[i]];
        }
        if(!flag)
            puts("Unknown letter grade in input");
        else
            printf("%.2f\n", (double)sum / cnt);
    }
    return 0;
}

1361.Grasshopper And the String

题意：找出一个字符串的两个相邻的元音字母(‘A’, ‘E’, ‘I’, ‘O’, ‘U’ and ‘Y’)的最大位置。

思路：直接做。记得初始位置和结束位置特判。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

char s[111];
bool judge(char ch)
{
    if(ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U' || ch =='Y')
        return true;
    return false;
}
int main()
{
    while(~scanf("%s", s))
    {
        int len = strlen(s);
        int res = 0, tmp = -1;
        for(int i = 0; i < len; ++i)
        {
            if(judge(s[i]))
            {
                res = max(res, i - tmp);
                tmp = i;
            }
        }
        res = max(res, len - tmp);
        printf("%d\n", res);
    }
    return 0;
}

1362.Parade

题意：阅读理解题，这里不写了，自己细细品味。

思路：嗯。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;

int n, res, sum1, sum2, a[N], b[N];
int t1, t2, best;
int main()
{
    while(~scanf("%d", &n))
    {
        sum1 = sum2 = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &a[i], &b[i]);
            sum1 += a[i];
            sum2 += b[i];
        }

        res = 0;
        best = abs(sum1 - sum2);
        for(int i = 1; i <= n; ++i)
        {
            t1 = sum1 - a[i] + b[i];
            t2 = sum2 - b[i] + a[i];
            if(abs(t1 - t2) > best)
            {
                best = abs(t1 - t2);
                res = i;
            }
        }

        printf("%d\n", res);
    }
    return 0;
}

1363.Solving Order

题意：嗯。

思路：结构体排序。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n, m;
struct node
{
    int cnt;
    char color[11];
} a[11];
bool cmp(node u, node v)
{
    return u.cnt > v.cnt;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%s%d", &a[i].color, &a[i].cnt);
        sort(a + 1, a + n + 1, cmp);
        for(int i = 1; i <= n; ++i)
            printf("%s%c", a[i].color, i == n ? '\n' : ' ');
    }
    return 0;
}

1533.寻找复读机

题意：中文题面。

思路：map标记，直接找。

坑点：

1. 卡PE 
2. `找出所有可能是复读机的群友`(我们只能确定出明确不是复读机的群友，剩下的不确定的都可能是)。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int N = 1111;

string s[N];
int n, m, a[N];
map<int, bool> MP;
int main()
{
    while(cin >> n >> m)
    {
        for(int i = 1; i <= m; ++i)
            cin >> a[i] >> s[i];

        for(int i = 1; i <= n; ++i)
            MP[i] = 1;

        MP[a[1]] = 0;
        for(int i = 2; i <= m; ++i)
            if(s[i] != s[i - 1])
                MP[a[i]] = 0;

        bool flag = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(!MP[i])  continue;
            if(flag)    cout << ' ';
            flag = 1;   cout << i;
        }
        cout << '\n';
    }
    return 0;
}

END：

每当在书中读及那些卑微的努力，都觉得感动且受震撼。也许每个人在发出属于自己的光芒之前，都经历了无数的煎熬，漫长的黑夜，无尽的孤独，甚至不断的嘲讽和否定，但好在那些踮脚的少年，最后都得到了自己想要的一切。

Donate comment here
0%