瞎写写
0%

CSP记录2019-12

Posted on

记录一下刷csp第一题和第二题的一些题目和答案

CSP201503-2数字排序

问题描述

　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。

输入格式

输入的第一行包含一个整数n，表示给定数字的个数。
第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。

输出格式

　　输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。

样例输入

12
5 2 3 3 1 3 4 2 5 2 3 5

样例输出

3 4
2 3
5 3
1 1
4 1

评测用例规模与约定

　　1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。

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
#include <iostream>
#include <map>
#include <queue>
using namespace std;

struct Node{
    int num, count;
    bool operator < (const Node& a) const{
        if(count == a.count)
            return num > a.num;
        else
            return count < a.count;
    }
};

int main(){
    priority_queue<Node> q;
    map<int, int> m;
    int n, v;

    cin >> n;
    while (n--){
        cin >> v;
        m[v]++;
    }

    Node an;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); it++){
        an.num = it->first;
        an.count = it->second;
        q.push(an);
    }

    while (!q.empty()){
        an = q.top();
        q.pop();
        cout << an.num << " " << an.count << endl;
    }

    return 0;
}

CSP201509-3模板生成系统

问题描述

　　成成最近在搭建一个网站，其中一些页面的部分内容来自数据库中不同的数据记录，但是页面的基本结构是相同的。例如，对于展示用户信息的页面，当用户为 Tom 时，网页的源代码是
pic

　　而当用户为 Jerry 时，网页的源代码是
pic

　　这样的例子在包含动态内容的网站中还有很多。为了简化生成网页的工作，成成觉得他需要引入一套模板生成系统。
　　模板是包含特殊标记的文本。成成用到的模板只包含一种特殊标记，格式为 {{ VAR }}，其中 VAR 是一个变量。该标记在模板生成时会被变量 VAR 的值所替代。例如，如果变量 name = “Tom”，则{{ name }} 会生成 Tom。具体的规则如下：
　　·变量名由大小写字母、数字和下划线 (_) 构成，且第一个字符不是数字，长度不超过 16 个字符。
　　·变量名是大小写敏感的，Name 和 name 是两个不同的变量。
　　·变量的值是字符串。
　　·如果标记中的变量没有定义，则生成空串，相当于把标记从模板中删除。
　　·模板不递归生成。也就是说，如果变量的值中包含形如{{ VAR }}的内容，不再做进一步的替换。

输入格式

输入的第一行包含两个整数 m, n，分别表示模板的行数和模板生成时给出的变量个数。
接下来 m 行，每行是一个字符串，表示模板。
接下来 n 行，每行表示一个变量和它的值，中间用一个空格分隔。值是字符串，用双引号 (“) 括起来，内容可包含除双引号以外的任意可打印 ASCII 字符（ASCII 码范围 32, 33, 35-126）。

输出格式

输出包含若干行，表示模板生成的结果。

样例输入

11 2

1
2
3
4
5
6
7
8
9
10
11
12
13
<!DOCTYPE html>
<html>
<head>
<title>User {% raw %}{{ name }}{% endraw %}</title>
</head>
<body>
<h1>{% raw %}{{ name }}{% endraw %}</h1>
<p>Email: <a href="mailto:{% raw %}{{ email }}{% endraw %}">{% raw %}{{ email }}{% endraw %}</a></p>
<p>Address: {% raw %}{{ address }}{% endraw %}}</p>
</body>
</html>
name "David Beckham"
email "david@beckham.com"

样例输出

1
2
3
4
5
6
7
8
9
10
11
<!DOCTYPE html>
<html>
<head>
<title>User David Beckham</title>
</head>
<body>
<h1>David Beckham</h1>
<p>Email: <a href="mailto:david@beckham.com">david@beckham.com</a></p>
<p>Address: </p>
</body>
</html>

评测用例规模与约定

0 ≤ m ≤ 100
0 ≤ n ≤ 100
输入的模板每行长度不超过 80 个字符（不包含换行符）。
输入保证模板中所有以大括号开始的子串都是合法的标记，开始是两个左大括号和一个空格，然后是变量名，结尾是一个空格和两个右大括号。
输入中所有变量的值字符串长度不超过 100 个字符（不包括双引号）。
保证输入的所有变量的名字各不相同。 

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

/***
这道题的反思：
 1.句子中用getline的时候不要忘了，前面还有一个换行符，直接用的话会读到一个空数据，可以使用getchar解决
 2.这道题中涉及到一行中多次替换，标准答案中使用了在for中又加了个for(;;)来达到循环整行的目的
 3.map中的count方法很好用，结合条件运算符更好用
***/

#include <iostream>
#include <map>
#include <queue>
using namespace std;

struct Node{
    int num, count;
    bool operator < (const Node& a) const{
        if(count == a.count)
            return num > a.num;
        else
            return count < a.count;
    }
};

int main(){
    priority_queue<Node> q;
    map<int, int> m;
    int n, v;

    cin >> n;
    while (n--){
        cin >> v;
        m[v]++;
    }

    Node an;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); it++){
        an.num = it->first;
        an.count = it->second;
        q.push(an);
    }

    while (!q.empty()){
        an = q.top();
        q.pop();
        cout << an.num << " " << an.count << endl;
    }

    return 0;
}

CSP201809-2卖菜

问题描述

在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。
第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。
给定第一天各个商店的菜价，请计算第二天每个商店的菜价。

输入格式

输入的第一行包含一个整数n，表示商店的数量。
第二行包含n个整数，依次表示每个商店第一天的菜价。

输出格式

输出一行，包含n个正整数，依次表示每个商店第二天的菜价。

样例输入

8
4 1 3 1 6 5 17 9

样例输出

2 2 1 3 4 9 10 13

数据规模和约定

　　对于所有评测用例，2 ≤ n ≤ 1000，第一天每个商店的菜价为不超过10000的正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//🌟这个用了C++11新特性

#include<bits/stdc++.h>
#include <iostream>
#include <utility>
//#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0;//ans存储最终结果
    scanf("%d",&n);
    vector<pair<int,int>>v1(n),v2(n);//分别存储小H和小W的装车时间段
    for(int i=0;i<n;++i)
        scanf("%d%d",&v1[i].first,&v1[i].second);
    for(int i=0;i<n;++i)
        scanf("%d%d",&v2[i].first,&v2[i].second);
    for(pair<int,int>p1:v1)
        for(pair<int,int>p2:v2)
            if(p1.first<=p2.second&&p1.second>=p2.first)//判断有无重叠区间
                ans+=min(p1.second,p2.second)-max(p1.first,p2.first);//加上重叠区间
    printf("%d",ans);
    return 0;
}

CSP201812-2小明放学

题目背景

　　汉东省政法大学附属中学所在的光明区最近实施了名为“智慧光明”的智慧城市项目。具体到交通领域，通过“智慧光明”终端，可以看到光明区所有红绿灯此时此刻的状态。小明的学校也安装了“智慧光明”终端，小明想利用这个终端给出的信息，估算自己放学回到家的时间。

问题描述

　　一次放学的时候，小明已经规划好了自己回家的路线，并且能够预测经过各个路段的时间。同时，小明通过学校里安装的“智慧光明”终端，看到了出发时刻路上经过的所有红绿灯的指示状态。请帮忙计算小明此次回家所需要的时间。

输入格式

　　输入的第一行包含空格分隔的三个正整数 r、y、g，表示红绿灯的设置。这三个数均不超过 106。
输入的第二行包含一个正整数 n，表示小明总共经过的道路段数和路过的红绿灯数目。
接下来的 n 行，每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路，将会耗时 t 秒，此处 t 不超过 106；k=1、2、3 时，分别表示出发时刻，此处的红绿灯状态是红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。

输出格式

　　输出一个数字，表示此次小明放学回家所用的时间。

样例输入

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

样例输出

46

样例说明

　　小明先经过第一段路，用时 10 秒。第一盏红绿灯出发时是红灯，还剩 5 秒；小明到达路口时，这个红绿灯已经变为绿灯，不用等待直接通过。接下来经过第二段路，用时 11 秒。第二盏红绿灯出发时是黄灯，还剩两秒；小明到达路口时，这个红绿灯已经变为红灯，还剩 11 秒。接下来经过第三、第四段路，用时 9 秒。第三盏红绿灯出发时是绿灯，还剩 10 秒；小明到达路口时，这个红绿灯已经变为红灯，还剩两秒。接下来经过最后一段路，用时 3 秒。共计 10+11+11+9+2+3 = 46 秒。

评测用例规模与约定

　　有些测试点具有特殊的性质：
　　* 前 2 个测试点中不存在任何信号灯。
　　测试点的输入数据规模：
　　* 前 6 个测试点保证 n ≤ 103。
　　* 所有测试点保证 n ≤ 105。 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>

int main() {
    int r, y, g, n;
    int x, z;
    long long l = 0, tmp;
    int i;

    scanf("%d%d%d%d", &r, &y, &g, &n);
    for(i = 0; i < n; i++){
        scanf("%d%d", &x, &z);
        tmp = l % (r + y + g);
        if(x == 0){
            l = l + z;
        } else if(x == 1){
            if(tmp <= z){
                l = l + z - tmp;
            } else if(tmp > z){
                if(tmp > z + g){
                    l = l + g + y + r - tmp;
                }
            }
        } else if(x == 2){
            if(tmp <= z + r){
                l = l + z + r - tmp;
            } else if(tmp > z + r){
                if(tmp > z + r + g){
                    l = l + g + y + r - tmp;
                }
            }
        } else if(x == 3){
            if(tmp > z){
                if(tmp < z + y + r){
                    l = l + z + y + r - tmp;
                }
            }
        }
    }

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

///下面是一种满分解法
/***
#include <stdio.h>

int main(void)
{
    int r, y, g, n, k, t;
    long long ans = 0, tmp;
    scanf("%d%d%d%d", &r, &y, &g, &n);
    while(n--) {
        scanf("%d%d", &k, &t);

        if(k != 0) {
            if(k == 1)
                tmp = ans + (r - t);
            else if(k == 2)
                tmp = ans + r + g +y - t;
            else if(k == 3)
                tmp = ans + r + g - t;
            tmp %= r + g + y;

            if(tmp >= r + g)
                t = r + g + y + r - tmp;
            else if(tmp <= r)
                t = r - tmp;
            else
                t = 0;
        }
        ans += t;
    }

    printf("%lld", ans);

    return 0;
}
***/