1011 World Cup Betting(20)

题目

在这里插入图片描述 Sample Input:

1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1

Sample Output:

T T W 39.31

题解

#include <iostream>
using namespace std;

int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    double a, b, c, sum = 1;
    while(~scanf("%lf %lf %lf", &a, &b, &c)){
         double t = max(a, max(b, c));
         if (t == a) printf("W ");
         else if (t == b) printf("T ");
         else if (t == c) printf("L ");
         sum *= t;
    }
    sum = (sum * 0.65 - 1) * 2;
    printf("%.2f", sum);
    return 0;
}

1012 The Best Rank（25）推荐：1星

题目

在这里插入图片描述 Sample Input:

5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999

Sample Output:

1 C
1 M
1 E
1 A
3 A
N/A

分析

常考模拟题。
推荐：1星

要点

多条件对比的时候，优先考虑数组。
exists用来记录数值和ID的映射关系。
flag用来决定排序的类别（这道题的亮点）。
将Exist放到排序后还可用于记录位置。

题解

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int id, best;
    int score[4], rank[4];
}stu[2005];

int exist[1000000], flag = -1;
bool cmp1(node a, node b) { return a.score[flag] > b.score[flag];}

int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int  n, m, id;
    scanf("%d %d", &n, &m);
    for(int i = 0; i< n; i++){
        scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
        stu[i].score[0] = (stu[i].score[1]+stu[i].score[2] +stu[i].score[3])/3.0;
    }
    for (flag=0; flag<=3; flag++){
        sort(stu, stu+n, cmp1);
        stu[0].rank[flag] = 1;
        for(int i = 1; i < n; i++){
            stu[i].rank[flag] = i + 1;
            if (stu[i].score[flag] == stu[i-1].score[flag])
                stu[i].rank[flag] = stu[i-1].rank[flag];
        }
    }
    for(int i = 0;i < n; i++){
        exist[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minn = stu[i].rank[0];
        for(int j = 1; j <= 3; j++){
            if(stu[i].rank[j] < minn){
                minn = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    char c[5] = {'A', 'C', 'M', 'E'};
    for(int i = 0; i < m; i++){
        scanf("%d", &id);
        int temp = exist[id];
        if(temp){
            int best = stu[temp-1].best;
            printf("%d %c\n", stu[temp-1].rank[best], c[best]);
        }else{
            printf("N/A\n");
        }
    }
    return 0;
}

1013 Battle Over Cities (25分) 推荐：经典

题目

在这里插入图片描述 Sample Input:

Sample Output:

1
0
0

分析

dfs经典题目，搜索类题目，要点在于

求解最大连通块，输出为联通域个数 - 1
推荐：经典
理解题意很重要，N个城市，M条铁路，K个被检查的城市。

题解

矩阵

#include <iostream>
#include <algorithm>
using namespace std;
int v[1010][1010];
bool visit[1010];
int n;

void dfs(int b){
    visit[b] = true;
    for(int i = 1;i <= n; i++){
        if(visit[i] == false && v[b][i]==1){
            dfs(i);
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("data.txt","r", stdin);
    #endif
    int m, k, a, b;
    scanf("%d%d %d",&n, &m, &k);
    for(int i = 0 ; i < m ; i++){
        scanf("%d%d", &a,&b);
        v[a][b] = v[b][a] = 1;
    }
    for(int i = 0;i < k;i++){
        fill(visit, visit+1010, false);
        int cnt = 0;
        scanf("%d", &a);
        visit[a] = true;
        for (int j = 1; j <= n; j++){
            if (visit[j]==false){
                dfs(i);
                cnt++;
            }
        }
        printf("%d\n", cnt-1);
    }
    return 0;
}

向量图

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> e[1010];
bool visit[1010] = {false};
void dfs(int node){
    if (visit[node]) return;
    visit[node] = true;
    for (int i = 0; i < e[node].size(); i++){
        dfs(e[node][i]);
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n,m,k,a,b,c;
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++){
        scanf("%d %d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i = 0; i < k; i++){
        scanf("%d", &c);
        fill(visit, visit+1010, false);
        visit[c] = true;
        int number = 0;
        for(int j = 1; j <= n; j++){
            if(visit[j]) continue;
            number++;
            dfs(j);
        }
        printf("%d\n", number-1);
    }
    return 0;
}

1014 Waiting in line(30) 推荐：2星

题目

在这里插入图片描述 Sample Input:

2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

Sample Output:

08:07
08:06
08:10
17:00
Sorry

分析

非常经典的模拟题，后面还有更难的，但是不实际，这道会了就够。
对于模拟题最重要的几点

数据的结构。
条件判断（模拟题通常会有很多限制，找到他们，写出来）

技巧就是先把输入输出写完，中间的过程留待后面再写。

推荐：2星

要点

poptime ：出队时间，其黄线内满了之后，最快什么时候可以再进去一个
endtime：队列中所有事务处理完时间
排队：那肯定是要用到队列的嘛
数字意义：实际上时间的长度：(17 - 8) * 60 = 540
注意：写完如果出现问题，先检查所有判断语句

知识点

vector 初始化并赋初值： vector sorry(k+1, false)

题解

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct node{
    int poptime, endtime;
    queue<int> q; //FIF0
};
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt","r",stdin);
#endif // ONLINE_JUDGE
    int n, m, k, q, index = 1; 
    scanf("%d%d%d%d", &n,&m,&k,&q);
    vector<int> time(k+1), result(k+1);
    for (int i = 1; i <= k; i++)
        scanf("%d", &time[i]);
    vector<node> window(n+1);
    vector<bool> sorry(k+1, false);
    for (int i = 1; i <= m; i++){ //初始化队列
        for (int j = 1; j <= n; j++){
            if (index<=k){
                window[j].q.push(time[index]);
                if(window[j].endtime >= 540) //结束条件
                    sorry[index] = true;
                window[j].endtime += time[index];
                if(i == 1)
                    window[j].poptime = window[j].endtime;
                result[index] = window[j].endtime;
                index++;
            }
        }
    }
    while(index <= k){
        int tempmin = window[1].poptime, tempwindow = 1; //找到下个可以进的窗口
        for(int i=2;i<=n;i++){
            if(window[i].poptime < tempmin){
                tempwindow = i;
                tempmin = window[i].poptime;
            }
        }
        window[tempwindow].q.pop();
        window[tempwindow].q.push(time[index]);
        window[tempwindow].poptime += window[tempwindow].q.front(); //更新下一个队列
        if (window[tempwindow].endtime >= 540) //当前时间已经大于结束时间则设置为true
            sorry[index] = true;
        window[tempwindow].endtime += time[index];//更新时间
        result[index] = window[tempwindow].endtime;//结束时间为..
        index++;
    }
    for(int i = 1; i <= q; i++){
        int query, minute;
        scanf("%d", &query);
        minute = result[query];
        if(sorry[query] == true){
            printf("Sorry\n");
        }else{
            printf("%02d:%02d\n", (minute + 480)/60, (minute + 480) % 60);
        }
    }
    return 0;
}

1015 Reversible Primes (20分) 推荐：2星

题目

在这里插入图片描述 Sample Input:

Sample Output:

Yes
Yes
No

分析

推荐：两星
很经典的一道小题：涉及到 进制转换，素数判断, 阶乘
素数判断尤其要注意：小于等于符合，不然会有漏判 i*i<=num , 还有1和0的特判
也可以使用数组来做进制的转换

题解

#include <iostream>
#include <cstdio>
#include <vector>
bool isFrime(int n){ // 素数判断
    if (n < 2) return false;
    for(int i =2 ; i * i <= n; i++){
        if (n % i == 0) return false;
    }
    return true;
}
int reverse(int num, int radix){ //进制转换
    int rnum = 0;
    while(num != 0){
        rnum = num % radix + rnum*radix;
        num /= radix;
    }
    return rnum;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n, d;
    while(~scanf("%d", &n)){
        if (n < 0) break;
        scanf("%d", &d);
        if (isFrime(n) && isFrime(reverse(n,d)))
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

1016 Phone Bills (25分) 推荐指数：2星

题目

在这里插入图片描述 Sample Input:

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
CYJJ 01:01:05:59 on-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line

Sample Output:

CYJJ 01
01:05:59 01:07:00 61 $12.10
Total amount: $12.10
CYLL 01
01:06:01 01:08:03 122 $24.40
28:15:41 28:16:05 24 $3.85
Total amount: $28.25
aaa 01
02:00:01 04:23:59 4318 $638.80
Total amount: $638.80

分析

推荐指数：2星
这道题审题是很重要的一部分，题目比较长，里面的条件比较繁琐，充分锻炼到审题的能力。
首先我们要模拟题的输入输出是很固定的，可以先完成输入输出

要点

审题，边读题，边将输入输出编写完成
rate[24] 存放着 24小时中每1分钟的花费值（乘上60就是1天总的耗时）
要注意到数据要求是成对出现（最近的两个），所以需要一次的步长应该为2（i+=2）
单位：cents/minute , 美分/分，转换为美元需要除以100
使用map是由原因的，题目中要求说输出必须是字母序（递增），所以使用map要比使用unorder_map好
对数组要注意赋初始 int rate[25] = {0}

知识点

队列
字典
排序
数值转换与计算
传递数组参数，在参数前面加*： int *array
利用 for (auto it : m ) 来快速遍历字典， it.first 输出key， it.second输出value

题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
struct node{ //数据较为复杂的这些大部分都用到结构体
    string name;
    int status, month, time, day, hour, minute;
};
bool cmp(node a, node b){
    return a.name != b.name ? a.name < b.name : a.time < b.time;
}
double billFromZero(node call, int *rate){
    double total = rate[call.hour] * call.minute + rate[24]*60*call.day;
    for(int i = 0; i < call.hour;i++)
        total += rate[i]*60;
    return total / 100.0;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt","r", stdin);
#endif // ONLINE_JUDGE
    int rate[25] = {0}, n;
    for ( int i = 0; i < 24 ;i++){
        scanf("%d", &rate[i]);
        rate[24] += rate[i]; //一整天的所有花费
    }
    scanf("%d", &n);
    vector<node> data(n);
    for(int i = 0; i < n; i++){
        cin >> data[i].name;
        scanf("%d:%d:%d:%d", &data[i].month, &data[i].day, &data[i].hour, &data[i].minute);
        string temp;
        cin >> temp;
        data[i].status = (temp == "on-line") ? 1:0;
        data[i].time = data[i].day * 24 * 60 + data[i].hour * 60 + data[i].minute;
    }
    sort(data.begin(), data.end(), cmp);
    map<string, vector<node>> custom;
    for(int i=1; i<n; i++){ /// 注意，这里是i++，i+2的话是不行，想想看为什么
        if(data[i].name == data[i-1].name && data[i-1].status==1 && data[i].status==0){
            custom[data[i-1].name].push_back(data[i-1]);
            custom[data[i].name].push_back(data[i]);
        }
    }
    for (auto it:custom){
        vector<node> temp = it.second;
        cout << it.first;
        printf(" %02d\n", temp[0].month);
        double total = 0.0;
        for (int i = 1; i< temp.size(); i+=2){
            double t = billFromZero(temp[i], rate) - billFromZero(temp[i-1], rate); ///直接将节点用来计算，求解时间段的数据
            printf("%02d:%02d:%02d ", temp[i-1].day, temp[i-1].hour, temp[i-1].minute);
            printf("%02d:%02d:%02d ", temp[i].day, temp[i].hour, temp[i].minute);
            printf("%d $%.2f\n", temp[i].time - temp[i - 1].time, t);
            total += t;
        }
        printf("Total amount: $%.2f\n", total); //注意空格要匹配
    }
    return 0;
}

1017 Queueing at Bank (25分)

题目

在这里插入图片描述 Sample Input:

7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10

Sample Output:

8.2

分析

模拟题, 之前那道排队的简化版
注意：重点在于模拟和情景的想象

要点

数据中有除法时，要注意除零错误

题解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
    int come, time;
}tempcustomer;

bool cmp1(node a, node b){
    return a.come < b.come;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n, k;
    scanf("%d%d", &n, &k);
    vector<node> custom;
    for(int i = 0; i < n; i++){
        int hh, mm, ss, time;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &time);
        int cometime = hh * 3600 + mm * 60 + ss;
        if(cometime > 61200) continue;
        tempcustomer = {cometime, time * 60};
        custom.push_back(tempcustomer);
    }
    sort(custom.begin(), custom.end(), cmp1); //这客户到来时间进行排序
    vector<int> window(k, 28800); //28800 = 8*3600, 即8点开始
    double result = 0.0;
    for(int i = 0; i < custom.size(); i++){
        int tempindex = 0, minfinish = window[0]; //找到当前最近窗口
        for(int j = 1; j < k; j++){
            if(minfinish > window[j]){
                minfinish = window[j];
                tempindex = j;
            }
        }
        if(window[tempindex] <= custom[i].come){
            window[tempindex] = custom[i].come + custom[i].time;
        }else{
            result += (window[tempindex]-custom[i].come); //
            window[tempindex] += custom[i].time;
        }
    }
    if(custom.size()==0)
        printf("0.0");
    else
        printf("%.1f", result/60.0/custom.size());
    return 0;
}

1018 Public Bike Management (30分) 推荐指数：2星

题目

在这里插入图片描述 Sample Input:

Sample Output:

3 0->2->3 0

分析

推荐指数：2星
多重最短路径问题，三个条件:路径最短-》最少移动的车辆-》最少带回去的车辆。
很经典的题目，这道题会了，则其他同类型的题也能触类旁通。
难点在于dfs中的条件判断，需要理清思路，minSent和minBack记录的是状态。只有输送车辆相同时，才依据最后的送回车辆。

要点

使用pre、path、tempPath来记录需要记录的前置点
need大于back，则需要把back置零
每个点都只有两个值，要带多少过去，要带多少走

知识点

题解

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 99999999; //设置默认值
int cmax, n, sp, m;
int minNeed = inf, minBack = inf;
int e[510][510], dis[510], weight[510]; //
bool visit[510];
vector<int> pre[510], path, temppath;
void dfs(int v) { //深度搜搜，从后往前寻找
    temppath.push_back(v);
    if(v == 0) { //递归边界，如果不是从0开始，则需要传入s(起始点)
        int need = 0, back = 0; //需要送过去的，需要返回的
        for(int i = temppath.size() - 1; i >= 0; i--) { //计算权重
            int id = temppath[i];
            if(weight[id] > 0) {
                back += weight[id];
            } else {
                if(back > (0 - weight[id])) { /// 0 - weight[id] -》取正
                    back += weight[id]; /// 需要带回去的数量匀一点给这个站点
                } else {
                    need += ((0 - weight[id]) - back); ///这个站点要得太多，只能再另送
                    back = 0;
                }
            }
        }
        if(need < minNeed) {  //选择需要送最少，返回的最少的路径
            minNeed = need;
            minBack = back;
            path = temppath;
        } else if(need == minNeed && back < minBack) {
            minBack = back;
            path = temppath;
        }
        temppath.pop_back(); //遍历完成，弹出重填
        return;
    }
    for(int i=0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back(); //弹出最后
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    fill(e[0], e[0] + 510 * 510, inf);     //填充数据
    fill(dis, dis + 510, inf);             //填充数据
    scanf("%d%d%d%d", &cmax, &n, &sp, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &weight[i]);
        weight[i] = weight[i] - cmax / 2; //权重需要进行转换， 理解了sent from 即最后需要送到目标城市的数量
    }
    for(int i = 0; i < m; i++) { //对路径赋值
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
    }
    dis[0] = 0;
    for(int i = 0; i <= n; i++) {
        int u = -1, minn = inf; //开始DJI
        for(int j = 0; j <= n; j++) {
            if(visit[j] == false && dis[j] < minn) { //找到距离最近的城市
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true; //设置为已拜访
        for(int v = 0; v <= n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[v] > dis[u] + e[u][v]) { //发现新的最短距离
                    dis[v] = dis[u] + e[u][v]; //使用最短距离
                    pre[v].clear();
                    pre[v].push_back(u); //
                }else if(dis[v] == dis[u] + e[u][v]) { //相同最短路径
                    pre[v].push_back(u);
                }
            }
        }
    }
    //上面简直是Dji的万能模板
    dfs(sp);
    printf("%d 0", minNeed);
    for(int i = path.size() - 2; i >= 0; i--)
        printf("->%d", path[i]);
    printf(" %d", minBack);
    return 0;
}

1019 General Palindromic Number (20分)

题目

在这里插入图片描述
Sample Input 1:

27 2

Sample Output 1:

Yes
1 1 0 1 1

Sample Input 2:

121 5

Sample Output 2:

No
4 4 1

题解

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int data[1000];
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    ll n, b;
    cin >> n >>b;
    int index = 0;
    while(n!=0){
        data[index] = n % b;
        n /= b;
        index++;
    }
    bool flag = true;
    for (int i = 0; i < index/2; i++){
        if( data[i] != data[index-i-1]){
            flag = false;
            break;
        }
    }
    if (flag) printf("Yes\n");
    else printf("No\n");
    for(int i= index-1; i >= 0; i--){
        if (i != index-1) printf(" ");
        printf("%d", data[i]);
    }
    return 0;
}

1020 Tree Traversals (25分) 推荐指数：2星

题目

在这里插入图片描述 Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

分析

推荐指数：2星
涉及到树的遍历：后序、中序、前序、层序遍历。
树的常见解法：

前序+中序-》后序
后序+中序-》前序
由上面两种再推出层序遍历
这道题涉及到上诉的2,3。

要点

判断条件： left>right
2index + 1 和 2index + 2 排序深度和左右节点（常考），满二叉树或者完全二叉树可以直接将index赋值

题解

中序+后序->前序，前序->层序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
vector<int> post, in; //用来存后序和中序向量
vector<node> ans; //存储Node节点的答案
void pre(int root, int start, int end, int index) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++; //找到中序根节点所在位置, <=也行，反正肯定有一个
    ans.push_back({index, post[root]}); //获取包含层序顺序的结果，等同于前序遍历，后面会在做一次排序
    // (左子树根节点，左子树起始位置，结束位置，层序下标1)
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    // (右子树根节点，右子树起始位置，结束位置，层序下标2)
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n;
    scanf("%d", &n);
    post.resize(n); //使用vector.resize(n)来重置大小
    in.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n - 1, 0, n - 1, 0); //由后序和中序来得出前序
    sort(ans.begin(), ans.end(), cmp); //排序得到层序
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i].value;
    }
    return 0;
}

原文链接：https://blog.csdn.net/Ashe_1994/article/details/116868058

目录

1011 World Cup Betting(20)

题目

题解

1012 The Best Rank（25）推荐：1星

题目

分析

要点

题解

1013 Battle Over Cities (25分) 推荐：经典

题目

分析

题解

1014 Waiting in line(30) 推荐：2星

题目

分析

要点

知识点

题解

1015 Reversible Primes (20分) 推荐：2星

题目

分析

题解

1016 Phone Bills (25分) 推荐指数：2星

题目

分析

要点

知识点

题解

1017 Queueing at Bank (25分)

题目

分析

要点

题解

1018 Public Bike Management (30分) 推荐指数：2星

题目

分析

要点

知识点

题解

1019 General Palindromic Number (20分)

题目

题解

1020 Tree Traversals (25分) 推荐指数：2星

题目

分析

要点

题解