QLUACM迎新赛解题报告(水题部分)

彻底打自闭了。没明白封榜是什么意思,考场上弃疗1h,结果被从rank2生爆到rank4。。。。可是最后三道题我是真的想不出来怎么做。。。

本次题解更新是水题部分。


M 签到题(时间空间什么的不重要了)

输出check in即可。

(想起了热身赛那天的寻找欧皇23333)

(有同学过了接近半个小时才发现有签到题,结果时长白白多加半个小时,充分证明了做题前先对题目难度稍微把握一下是很重要的)

(说实话我也差点没看见)

B Alice and Bob(2s,128MB)

题目大意:有n堆糖果,数量可能不同,Alice和bob轮流拿糖果直到全部拿完。
保证总是Alice先拿糖果,而且这两个人绝顶聪明,最后谁的糖果多谁获胜。
Alice获胜输出A Bob获胜输出B 平局输出again

思路:两个人拿糖果自然是哪一堆最多就拿哪个,这样是对自己最有利的。所以这题考场上我直接采用了贪心思想,所以先对所有的糖果堆从大到小排个序,然后Alice拿第一大,Bob拿第二大,Alice拿第三大……如此循环往复,可以看出Alice永远拿奇数堆,Bob永远拿偶数堆,然后统计一下这俩人最后能拿到的总糖数对比一下就是结果了。

(第一次交的时候数组没看见大小就开小了,非常SB地罚了一次时)

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define maxn 100005
using namespace std;
int n;
int a[maxn];
int top;
bool cmp(const int &a, const int &b) {
    return a > b;
}
int alice, bob;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1,cmp);
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1)
            alice += a[i];
        else
            bob += a[i];
    }
    if (alice > bob)
        cout << "A";
    else if (alice < bob)
        cout << "B";
    else
        cout << "again";
//    system("pause");
    return 0;

}

C 黑白黑(1s,128MB)

题目大意:两个人同时伸出一只手,手心为白,手背为黑。
如果有两人为黑一人为白,或者两人为白一人为黑,则单独伸出手心或者手背的那个人就输了。
现在有A、B、C三个人玩这个游戏,输入他们出的是手心还是手背
输出是谁赢,平局输出aha。

咱表示一开始没看到有签到题,这个是我第一道A掉的题。只需要输入三个整数a,b,c,然后先判断三者是否相等(也就是判平局),然后两两判断是否相等,如果相等那就是第三个人输掉。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a, b, c;
int main() {
    cin >> a >> b >> c;
    if (a == b && b == c)
        cout << "aha";
    else if (a == b)
        cout << "C";
    else if (b == c)
        cout << "A";
    else if (a == c)
        cout << "B";
//    system("pause");
    return 0;

}

D GPA(2s,128MB)

题目大意:输入七门课程的成绩和学分,根据平均绩点公式求GPA。
平均绩点:(课程学分1*绩点+课程学分2*绩点+~~~+课程学分n*绩点)/(课程学分1+课程学分2+~~~+课程学分n)

如果不想开一大堆变量建议用数组做。数组全开float类型就ok,剩下的没难度,照做即可。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
float chengji[10];
float jidian[10];
float xuefen[10];
float sumxuefen;
int main() {
    for (int i = 1; i <= 7; i++) {
        cin >> chengji[i];
        if (chengji[i] >= 91)
            jidian[i] = 4.0;
        else if (chengji[i] >= 86 && chengji[i] <= 90)
            jidian[i] = 3.5;
        else if (chengji[i] >= 81 && chengji[i] <= 85)
            jidian[i] = 3.0;
        else if (chengji[i] >= 76 && chengji[i] <= 80)
            jidian[i] = 2.5;
        else if (chengji[i] >= 71 && chengji[i] <= 75)
            jidian[i] = 2.0;
        else if (chengji[i] >= 66 && chengji[i] <= 70)
            jidian[i] = 1.5;
        else if (chengji[i] >= 60 && chengji[i] <= 65)
            jidian[i] = 1.0;
        else
            jidian[i] = 0;
    }
    for (int i = 1; i <= 7; i++) {
        cin >> xuefen[i];
        sumxuefen += xuefen[i];
    }
    float gpa = 0;
    for (int i = 1; i <= 7; i++) {
        gpa += xuefen[i] * jidian[i];
    }
    printf("%.2f", gpa / sumxuefen);
    //system("pause");
    return 0;

}

E are you ok?(2s,128MB)

题目大意:告诉你仓库里所有货物的名字和库存,如果库存全部为0,输出are you ok?
如果还有库存,就把有库存的物品按“物品名 x 数量”的格式输出。

开一个int数组记录货物存量,开一个string数组记录货品名称,读入的时候判断有没有非0数据,如果全都是0则直接输出are you ok?,如果有非0数据就扫一遍所有货物,如果当前货物仍然有库存就按格式输出即可。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#define maxn 2333
using namespace std;
int n;
int rem[maxn];
string s[maxn];
bool fail = true;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> rem[i];
        if (rem[i] > 0)
            fail = false;
    }
    if (fail) {
        cout << "are you ok?";
    }
    else {
        for (int i = 1; i <= n; i++) {
            if (rem[i] != 0)
                cout << s[i] << " x " << rem[i] << endl;
        }
    }
//    system("pause");
    return 0;

}

G 数数(2s,128MB)

题目大意:给你一个纯数字字符串,同一个重复数字不会出现超过9次,按照下面的格式输出:
有多少个连续相同数字则压缩为“数量+数字”这种形式。
比如说114514,就简化为2114151114(好吧这并不是压缩)
什么意思呢?最前边两个连着的1,写成21,然后单个的4,写成14,按这样的规律来。

这个题其实很简单,就是我想多了然后还写丑了。一开始拿到这个题脑子里首先想到用栈,先把第一位的数字压进栈,扫到第二位时判断栈里面的数字和它是不是一样,如果不是就输出栈大小和栈顶元素(就是数量+数字),然后清空栈,新元素入栈。如果是一样的数字就把它入栈。最后扫完一遍再执行一次输出栈的操作。这个操作看起来是没什么问题的,但是确实是不太好实现。

后来我发现我纯粹是想多了。这可是新生赛,怎么可能会考这么麻烦的玩意呢?后来我还想到用两重循环,第二重找到第一个不一样的就输出并且把第一重的循环变量改掉,但是这的确是个非常非常sb的想法,甚至说应该是错的。

然后我就在纸上推了一下,仔细一想就通了。设定一个当前字符的“指针”,其实用变量模拟指针就可以,没必要真的用指针。这个指针会在当前扫到不一样字符的时候进行更新。顺便路上记录一下当前字符个数是多少就好。最后再把剩下的那一点输出。这个思路和栈那个是几乎完全一样的,但是非常好操作。听我BB了这么多,实际上代码量真的不多。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define maxn 2333
using namespace std;
string s;
int main() {
    cin >> s;
    int l = s.length();
    int i;
    char prev = s[0];
    int nowcnt = 1;
    for (i = 1; i < l; i++) {
        if (s[i] != prev) {
            cout << nowcnt << prev;
            prev = s[i];
            nowcnt = 1;
        }
        else {
            nowcnt++;
        }
    }
    cout << nowcnt << prev;
    //system("pause");
    return 0;

}

H 老虎机(2s,128MB)

(好奇怪啊这些题怎么都单点2s)

题目大意:有一台有n个滚轮的老虎机,每个滚轮的数的取值范围是1~ai。
告诉你所有的ai,用这台老虎机转出来的数认作字符串,问字典序最小的是哪个。
字典序:两个字符串S和T,从前往后比较,
如果存在一个位置,在该位置两个字符串的字符不同,则比较小的那个所在的字符串字典序更小。
特殊的,220的字典序比22的大,因为22是220的一个前缀  
同时,老虎机上显示的数不包含前导0。

根据字典序比较特点,自然是我要让同一位上这个数越小越好。所以答案无非就是一堆1和0。等等,为什么还会有0?

想一下,现在这个老虎机有3位,每个滚轮取值范围1到10,那么请问是111大还是1101大?自然是111比较大, 因为第三位上1101是0,它比1小。

实际上不难想到,这些滚轮无外乎取值就是1,10,100。(滚轮取值最大到100)

但是最后一位只能取1。由于特例限制,比如说有11和110,这里第二位取了10但是要比11大,因为11是110的前缀。

这就好办了。读入的时候判断这些滚轮的取值范围,只要不是最后一位,取不到10的一律变1,取10到99的一律变10,取100的直接变100。这样一定能保证字典序最小。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define maxn 100005
using namespace std;
int t;
int n;
int a[maxn];
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (i != n) {
                if (a[i] < 10)
                    a[i] = 1;
                else if (a[i] >= 10 && a[i] < 100)
                    a[i] = 10;
                else if (a[i] >= 100)
                    a[i] = 100;
            }
            else {
                a[i] = 1;
            }

        }
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
//    system("pause");
    return 0;

}

I 五环(1s,128MB)

(这题再给2s那真的过分了啊)

题目大意:奥运五环上五个环颜色代表的意义:
Blue = Europe
Yellow = Asia
Black = Africa
Green = Oceania
Red = America

现在输入一个这里边的单词,输出与之相对应的单词。

这题不用讲。如果这个都不会可以考虑退队了。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define maxn 100005
using namespace std;
string s;
int main() {
    cin >> s;
    if (s == "Blue")
        cout << "Europe";
    else if (s == "Europe")
        cout << "Blue";
    else if (s == "Yellow")
        cout << "Asia";
    else if (s == "Asia")
        cout << "Yellow";
    else if (s == "Black")
        cout << "Africa";
    else if (s == "Africa")
        cout << "Black";
    else if (s == "Green")
        cout << "Oceania";
    else if (s == "Oceania")
        cout << "Green";
    else if (s == "Red")
        cout << "America";
    else if (s == "America")
        cout << "Red";
    //system("pause");
    return 0;

}

J 开挂的小洋(2s,128MB)

题目大意:小洋买了外挂去打地鼠,一秒钟内最多可以打两只。
现在告诉你游戏时长和地鼠出现的时间顺序,问小洋能打多少只。
就比如说2 3 3 3这个时间序列,2s时只有一只地鼠,所以只能打一只。
3s时有3只,但是小洋最多只能打两只,所以最终答案是1+2=3。

冷静分析后发现这个题里面游戏时长是用不到的,因为题目保证了所有地鼠都会在游戏时长之内出现,那我要这个时长有什么用。。。

开一个数组记录在第i秒打了多少只地鼠,对地鼠出现的序列排序后扫一遍整个序列,如果在第i秒打了不够两只说明还能打,就更新这个数组和ans,如果不能再打了就跳过。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define maxn 100005
using namespace std;
int n;
int m;
int a[maxn];
int num;
int cnt[maxn];
int sum;
int ans;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> num;
        if (cnt[num] < 2) {
            cnt[num]++;
            ans++;
        }
    }
    cout << ans;
    //system("pause");
    return 0;

}    

K 数字匹配(2s,128MB)

题目大意:给两个长度都是n的数列a和b,a和b中每个元素都应该进行匹配。
互相匹配的元素表现为相乘,然后还要把所有相乘的积进行相加。
例如:数组a:1 5 3  数组 b:2 3 4 
如果a中第一个元素跟b中第三个元素匹配,第二个元素跟b中第二个元素匹配,第三个元素跟b中第一个元素匹配,
匹配完后相乘得到 1*4、5*3、3*2,求和得到结果1*4+5*3+3*2=25。 
如果a中第一个元素跟b中第二个元素匹配,第二个元素跟b中第三个元素匹配,第三个元素跟b中第一个元素匹配,
匹配完后相乘得到 1*3、5*4、3*2,求和得到结果1*3+5*4+3*2=29。 
给出n和两个数组,分别计算求和的最大结果与最小结果。  

听起来挺麻烦,其实排个序就ojbk。道理很简单,也是基于一个贪心。如果是大乘大,小乘小,这样出来的结果一定是最大的。如果反过来,大乘小,小乘大,这样出来的结果就是最小的。

数组a要存两遍(其实数组b存两遍也行,我当时是两个都存了,其实是多余的),然后这两个数组一个升序排序一个降序排序。再对数组b进行升序或者降序排序。

然后乘一下,累加就完事了~

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#define maxm 2333
using namespace std;
int n;
int a1[maxm], b1[maxm];
int a2[maxm], b2[maxm];
int maxn, minn;

bool cmp(const int &a, const int &b) {
    return a > b;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a1[i];
        a2[i] = a1[i];
    }
    sort(a1 + 1, a1 + n + 1);
    sort(a2 + 1, a2 + n + 1,cmp);
    for (int i = 1; i <= n; i++) {
        cin >> b1[i];
        b2[i] = b1[i];
    }
    sort(b1 + 1, b1 + n + 1);
    sort(b2 + 1, b2 + n + 1,cmp);

    for (int i = 1; i <= n; i++) {
        maxn += a1[i] * b1[i];
    }
    for (int i = 1; i <= n; i++) {
        minn += a1[i] * b2[i];
    }
    cout << maxn << " " << minn;
//    system("pause");
    return 0;

}

剩下三道难题没能做出来,等补完题再去写题解吧,还得去请教一下集训队大佬们。。。。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。