5、算法练习专栏——牛客练习——天梯备赛04

A：解方程

链接

题目描述

对于方程 2018 * x ^ 4 + 21 * x + 5 * x ^ 3 + 5 * x ^ 2 + 14 = Y，
告诉你Y的值，你能找出方程在0~100之间的解吗？

输入描述:

1
2
3
第一行输入一个正整数T（表示样例个数）
接下来T组样例
每组样例一行，输入一个实数Y

输出描述:

1
2
一行输出一个样例对应的结果，
输出方程在0~100之间的解，保留小数点后4位小数；如果不存在，输出 -1

示例1

输入

复制

1
2
3
2
1
20180421

输出

复制

1
2
-1
9.9993

代码

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
int a[N];
int nums[N];
int n, b, k;
int ans = 1;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> b;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < b) a[i] = -1;
        else if (a[i] > b) a[i] = 1;
        else k = i;
    }
    int sum = 0;
    for (int i = k - 1; i >= 1; i--) {
        sum += a[i];
        nums[n - sum]++;
        if (!sum) ans++;
    }
    
    sum = 0;
    for (int i = k + 1; i <= n; i++) {
        sum += a[i];
        ans += nums[n + sum];
        if (!sum) ans ++;
    }
    
    cout << ans;
    return 0;
}

B：[CQOI2009]中位数图

链接

题目描述

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入描述:

1
第一行为两个正整数n和b ，第二行为1~n 的排列。

输出描述:

1
输出一个整数，即中位数为b的连续子序列个数。

示例1

输入

复制

1
2
7 4
5 7 2 4 3 1 6

输出

复制

1
4

备注:

1
2
3
4
5
对于30%的数据中，满足 n≤100

对于60%的数据中，满足 n≤1000

对于100%的数据中，满足 n≤100000,1≤b≤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
#include <iostream>
#include <algorithm>

using namespace std;
const double eps = 1e-5;
int T;
double Y;

int main()
{
    cin >> T;
    while (T--) {
        scanf("%lf", &Y);
        double l = 0, r = 100;
        while (r - l >= eps) {
            double mid = (l + r) / 2; // 注意不可以使用 >>
            if (2018 * mid * mid * mid * mid + 21 * mid + 5 * mid * mid * mid + 5 * mid * mid + 14 > Y) r = mid;
            else l = mid;
        }
        if (l == 0 || r == 100) printf("-1\n");
        else printf("%.4f\n", l);
    }

    return 0;
}

C：[NOIP2007]奖学金

链接

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理，不能得分。

输入描述:

1
2
3
第1行为一个正整数n，表示该校参加评选的学生人数。
第2到n+1行，每行有3个用空格隔开的数字，每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。
所给的数据都是正确的，不必检验。

输出描述:

1
共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。

示例1

输入

复制

1
2
3
4
5
6
7
6 
90 67 80 
87 66 91 
78 89 91 
88 99 77 
67 89 64 
78 89 98

输出

复制

1
2
3
4
5
6 265
4 264
3 258
2 244
1 237

示例2

输入

复制

1
2
3
4
5
6
7
8
9
8 
80 89 89 
88 98 78 
90 67 80 
87 66 91 
78 89 91 
88 99 77 
67 89 64 
78 89 98

输出

复制

1
2
3
4
5
8 265
2 264
6 264
1 258
5 258

备注:

1
2
50%的数据满足: 各学生的总成绩各不相同
100%的数据满足: 6 ≤ n ≤ 300

代码

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 <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 310;
int n;

struct Node {
    int sum;
    int a;
    int b;
    int c;
    int num;
}Grades[N];

bool cmp(Node A, Node B) {
    if (A.sum != B.sum) return A.sum > B.sum;
    if (A.a != B.a) return A.a > B.a;
    else return A.num < B.num;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        Grades[i] = {a + b + c, a, b, c, i + 1};
    }
    sort(Grades, Grades + n, cmp);
    
    for (int i = 0; i < 5; i++) {
        cout << Grades[i].num << " " << Grades[i].sum << '\n';
    }
    return 0;
}

D：前缀统计

链接

题目描述

给定N个字符串S1,S2…SNS_1,S_2 \dots S_NS1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1∼SNS_1 \sim S_NS1∼SN中有多少个字符串是T的前缀。输入字符串的总长度不超过10610^6106，仅包含小写字母。

输入描述:

1
第一行两个整数N，M。接下来N行每行一个字符串Si。接下来M行每行一个字符串表示询问。

输出描述:

1
对于每个询问，输出一个整数表示答案

示例1

输入

复制

1
2
3
4
5
6
3 2
ab
bc
abc
abc
efg

输出

复制

1
2
2
0

代码

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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int son[N][26], cnt[N];
int n, m, idx;

void insert(string s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string s){
    int p = 0, res = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!son[p][u]) break;
        res += cnt[p];
        p = son[p][u];
        
    }
    res += cnt[p];
    return res;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    
    while(m--) {
        string s;
        cin >> s;
        cout << query(s) << '\n';
    } 

    return 0;
}

题目E：小红的数字拆解

链接

题目描述

小红拿到了一个偶数，她希望你将其切割成尽可能多的偶数。你能帮帮她吗？

输入描述:

1
2
一个偶数xxx。
1≤x≤101051\leq x \leq 10^{10^5}1≤x≤10105

输出描述:

1
输出若干行，从小到大输出每个偶数。

​ 示例1

输入

复制

1
1024

输出

复制

1
2
3
2
4
10

说明

1
拆分成"10"+"2"+"4"三个偶数。

​ 示例2

输入

复制

1
999999999999999999999999990

输出

复制

1
999999999999999999999999990

​ 示例3

输入

复制

1
202020

输出

复制

1
2
3
4
5
6
0
0
0
2
2
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, k;
string s;
string a[N];
bool cmp(string x,string y) {
    if (x.length() != y.length()) return x.length() < y.length();
    else return x < y;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> s;
    int len = s.length();
    if ((s[len - 1] - '0') % 2 == 0) {
        for (int i = 0; i < len;) {
            string ss;
            while ((s[i++] - '0') % 2 == 1) {
                ss += s[i - 1];
            }            
            ss += s[i - 1];
            a[k++] = ss;
        }
    }  
    sort(a, a + k, cmp);
    for (int i = 0; i < k; i++) cout << a[i] << '\n';
    return 0;
}