Yxa's Place
0%

qdu第一届程序设计竞赛部分题解

发表于 更新于 分类于 ，
本文字数： 1.7k 阅读时长 ≈ 2 分钟

年前计科acm那边办的比赛，和两位dalao一起去参加了。因为各种经验不足+各种思路想歪导致只做了5题拿了银。不过过程还是很有趣的。于是来补补题～

没做的同学可以来这里补题or看看,题目总体还是很简单的。

E（模拟 细节） lgz学长哄女友

当时wa了半天差点自闭的题。当时一开始没认真看题导致wa了几下才看出来。后来我写了一发类似于尺取的东西在粗心wa了一发（这锅是我的）之后就过了（记得里面各种iterator满天飞）。总体不难但是要注意细节。

F（思维 - -） ak爷走格子

贼毒，一开始各种理解错。认真看了题之后思路逐渐打开但不知怎么的奇怪的偏离了正解的方向（真的有毒）。然后我就想出来一种更毒但是是错的解法然后写了快一个小时间接导致没拿金。现在看看其实挺简单的。

首先，假设先处理出每一步xy坐标的delta，因为不一定机器人会走完完整的一串指令。可能走着走着走到一半到终点就停了，所以我们要枚举这个停下来时的这个点。

然后我们其实就是让下面两个公式同时成立：

delta_x[len] * k + delta_x[i] == ex

delta_y[len] * k + delta_y[i] == ey

len为字符串长度，k是之前进行了几轮完整的字符串命令，delta_x/y[len]也就是经过一轮完整的命令之后x/y的偏差值。ex，ey是终点坐标。

接下来就是枚举delta_x/y[i]了。注意特例（贼坑）。首先k不能是负的。其次在求k的时候，如果假设delta_x[len] = 0,说明x的k可以是任意数字，那么就让这个k等于y求出来的k。如果delta_y[len]也是0，说明这串指令绕了个圈，那么让k=0就行了。相当于比较delta_x[i] == ex && delta_y[i] == ey

实际上就是当时想多了然后被特例坑到然后越改越错，加了很多乱七八糟的判断条件……其实当时应该已经注意到正解不可能这么麻烦，最后我们就自闭了……

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
#include <iostream>
#include <cstdio>
#include <cstring>
int dx[120],dy[120];
char str[120];
int main()
{
    int ex,ey;
    while(~scanf("%d%d",&ex,&ey)) {
        scanf("%s",str);
        int len = strlen(str);
        memset(dx,0,sizeof dx);
        memset(dy,0,sizeof dy);
        if(ex == 0 && ey == 0) {printf("Yes\n"); goto fin;}
        for(int i = 0; i < len; ++i) {
            if(str[i] == 'U') dy[i+1] = dy[i] + 1,dx[i+1] = dx[i];
            if(str[i] == 'D') dy[i+1] = dy[i] - 1,dx[i+1] = dx[i];
            if(str[i] == 'L') dx[i+1] = dx[i] - 1,dy[i+1] = dy[i];
            if(str[i] == 'R') dx[i+1] = dx[i] + 1,dy[i+1] = dy[i];
        }
        int k;
        for(int i = 1; i <= len; ++i) {
            if(dx[len]) k = (ex - dx[i]) / dx[len];
            else if(dy[len]) k = (ey - dy[i]) / dy[len];
            else k = 0;
            if(k < 0) continue;//k = 0; 
            if(k * dx[len] + dx[i] == ex && k * dy[len] + dy[i] == ey) 
            {
                printf("Yes\n"); goto fin;
            }
        }
        printf("No\n");
        fin: continue;
    }
    return 0;
}

G（暴力 方法） 小Z的初中数学题

本来以为是数学题没想到是暴力，早知道就先写这个了。

首先这个式子有5个未知数，怎么暴力呢？先把式子分成两部分，一部分是前两个个未知数，一部分三个未知数。先去枚举前两个未知数求出第一部分所有可能的值并存起来，然后再枚举后三个未知数求出后半部分的解之后看看前半部分和它是相反数的值有多少……可以选择把前半部分的所有值排序然后二分范围(nlogn)，也可以开两个大数组分别处理正数和负数，直接记录值i出现了多少次(n)。

因为每个未知数最大50，所以数组最大就是（50^4）×4 = 25，000，000，大概95MB。整体时间复杂度O(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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
const int maxn = 7000000;
int pos[maxn*2],neg[maxn*2];
int abs(int n) {
    if(n>=0) return n;
    return -n;
}
int main() {
    int T; scanf("%d",&T);
    while(T--) {
        int ans = 0;
        int x[5];
        memset(pos,0,sizeof(pos));
        memset(neg,0,sizeof(neg));
        for(int i = 0; i < 5; ++i) scanf("%d",&x[i]);
        for(int i = -50; i <= 50; ++i) {
        if(i == 0) continue;
        for(int j = -50; j <= 50; ++j) {
            if(j == 0) continue;
            int tmp = i*i*i*x[0]+j*j*j*x[1];
            if(tmp > 0) pos[tmp]++;
            else neg[-tmp]++; 
        }
    }
        for(int i = -50; i <= 50; ++i) {
            if(i == 0) continue;
            for(int j = -50; j <= 50; ++j) {
                if(j == 0) continue;
                for(int k = -50; k <= 50; ++k) {
                    if(k == 0) continue;
                    int tmp = i*i*i*x[2]+j*j*j*x[3]+k*k*k*x[4];
                    if(abs(tmp) >= maxn*2)
                        if(tmp > 0) break;
                        else continue;
                    if(tmp > 0) ans+=neg[tmp];
                    else ans+=pos[-tmp];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

H（思维）+1学姐在线嘤嘤嘤

题目还行，颁奖第一次见到Z+1，感受到了区域赛金牌选手的气场23333

应该算是全场最难的思维题：

给你2×n-2个字符串，它们分别是长度为n的字符串的前缀或者后缀，让你去判断它们是前缀还是后缀。其中长度为1～n-1的字符串各有两个（虽然没说这两个会不会相同，但按照出题人题解里的口气大概没有）但输入顺序随机。答案保证唯一且一定有解。

其实如果细想会发现这题有很多细节，但是实际上它们与正解并无关联。首先原字符串肯定可以由一个长度为n-1和1的两个字符串拼凑而成，它们前后位置又可以互换，每种长度两个字符串，这样原字符串就有8种可能。因为答案唯一所以一定有一个原字符串使得所有的字符串都是它的前缀或后缀…

思路借鉴black_hole6

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 <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
std::vector<std::string> v,a,b,q,h;
bool isq(const std::string &a,const std::string &b) {
    for(int i = 0,j = 0; i < b.length() && j < a.length(); ++i,++j)
    if(b[i] != a[j]) return 0;
    return 1;
}
bool ish(const std::string &a,const std::string &b) {
    for(int i = b.length() - 1,j = a.length() - 1; i >= 0 && j >= 0; --i,--j)
    if(b[i] != a[j]) return 0;
    return 1;
}
bool used[300];
int main()
{
    int n; std::cin>>n;
    for(int i = 1; i <= 2 * n - 2; ++i) {
        std::string s; std::cin>>s;
        v.push_back(s);
        if(s.length() == 1) a.push_back(s);
        if(s.length() == n - 1) b.push_back(s);
    }
    int ans = -1;
    std::string total_s[] =
    {a[0]+b[0],a[0]+b[1],a[1]+b[0],a[1]+b[1],b[0]+a[0],b[0]+a[1],b[1]+a[0],b[1]+a[1]};
    for(int i = 0; i < 8; ++i)
    {
        memset(used,0,sizeof(used));
        for(int j = 0; j < v.size(); ++j) {
            if(isq(v[j],total_s[i])) used[j] = 1;
            else if(!ish(v[j],total_s[i])) goto con;
        }
        break;
        con:continue;
    }
    for(int i = 0; i < 2 * n - 2; ++i)
    if(used[i]) putchar('P');
    else putchar('S');
    return 0;
}

I（思维） 不吃草的灰太郎

这个题小学奥数（早知道就先做了哭）。首先狼和草因为都不能与羊共存但彼此能共存所以可看做是一类物品。假设数据是1 1 1 1，那么先运羊，在运狼，再把羊运回来同时运走草，最后运回羊。

如果狼+草or羊的数量其中有一方 < d,那么可以一直运着它再运一点另一方分别一点一点把另外一方运过去。如果有一方==d，那么只能分两次运另一方了，方法同1 1 1 1的情况。因为运两次，所以另一方的数量要<=2*d

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
int main()
{
    int a,b,c,d;
    while(~scanf("%d%d%d%d",&a,&b,&c,&d)) {
        if(a+c<d||b<d||a+c==d&&b<=2*d||b==d&&a+c<=2*d) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

J(博弈)

博弈狗屁不会

总结

怎么说呢，因为打比赛经验不够导致实力发挥不出来。各种wa+疯狂调试弄得人只想自闭。所以还要继续努力啊～