头像

以梦为马

HPU




离线:24天前



以梦为马
4个月前

题目

某单位给每个员工发工资(精确到元)。为了保证避免临时兑换零钱,且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数,请编程完成。

思想

贪心

C++代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){
    int n, gz;
    int b[8] = {0, 100,50, 20, 10, 5, 2, 1};
    int s[8] = {0, 0, 0, 0, 0, 0, 0, 0};
    cin >> n;
    for(int i = 1; i <= n; i ++){
        memset(s, 0, sizeof s);//清空s数组
        cin >> gz;
        for(int j = 1; j <= 7; j ++){
            int a = gz / b[j];
            s[j] += a;
            gz -= a * b[j];  
        }

        for(int i = 1; i <= 7; i ++){
            cout << b[i] << "---" << s[i] << endl;
        }
        cout << endl;
    }

    return 0;
}

样例输入

4
1200 11 25 30

样例输出

100---12
50---0
20---0
10---0
5---0
2---0
1---0

100---0
50---0
20---0
10---1
5---0
2---0
1---1

100---0
50---0
20---1
10---0
5---1
2---0
1---0

100---0
50---0
20---1
10---1
5---0
2---0
1---0



分享 数塔

以梦为马
4个月前

数塔

C ++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 50;

int a[N][N][4];
int n;

void number_tower(int n){
    //a[i][j][1]保存数塔值,a[i][j][2]记录最大路径值,a[i][j][3]记录路径
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= i; j ++){
            scanf("%d", &a[i][j][1]);//读入塔值
            a[i][j][2] = a[i][j][1];//最初路径最大值为其本身
            a[i][j][3] = 0;//路径初始化
        }
    }

    //计算数塔最大值并记录最大路径
    for(int i = n - 1; i >= 1; i --){
        for(int j = 1; j <= i; j ++){
            if(a[i + 1][j][2] > a[i + 1][j + 1][2]){
                a[i][j][2] = a[i][j][2] + a[i + 1][j][2];
                a[i][j][3] = 0;//从左下方上来
            }
            else{
                a[i][j][2] = a[i][j][2] + a[i + 1][j + 1][2];
                a[i][j][3] = 1;//从右下上来
            }
        }
    }

    //输出最大路径值
    printf("max = %d\n", a[1][1][2]);

    //输出最大路径
    int j = 1;
    for(int i = 1; i <= n - 1; i ++){
        printf("%d -> ", a[i][j][1]);
        j = j + a[i][j][3];
    }
    printf("%d\n", a[n][j][1]);
}

int main(){
    printf("please input the number of rows:\n");
    scanf("%d", &n);
    number_tower(n);
    return 0;
}

输入:

5
9 12 15 10 6 8 2 18 9 5 19 7 10 4 16

输出

please input the number of rows:
max = 59
9 -> 12 -> 10 -> 18 -> 10


分享 汉诺塔

以梦为马
4个月前

汉诺塔

C ++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

//将n个盘子由a柱经过c柱移动到b柱
void hanoi(int n, char a, char b, char c){
    if(n){
        hanoi(n - 1, a, c, b);//将a柱上面n-1个盘子经过c柱移动到b柱
        printf("plate %d from %c to %c\n", n, a, b);//将第n个盘子由a柱移动到c柱
        hanoi(n - 1, c, b, a);//将b柱上面n-1个盘子经过a柱移动到c柱
    }
}

int main(){
    int n;
    printf("please input the number of plates:\n");
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');//将n个盘子从a柱经过c柱移动到b柱
    return 0;
}

实验结果

输入: 1
please input the number of plates:
plate 1 from A to B
输入: 2
please input the number of plates:
plate 1 from A to C
plate 2 from A to B
plate 1 from C to B
输入: 3
please input the number of plates:
plate 1 from A to B
plate 2 from A to C
plate 1 from B to C
plate 3 from A to B
plate 1 from C to A
plate 2 from C to B
plate 1 from A to B
输入: 4
please input the number of plates:
plate 1 from A to C
plate 2 from A to B
plate 1 from C to B
plate 3 from A to C
plate 1 from B to A
plate 2 from B to C
plate 1 from A to C
plate 4 from A to B
plate 1 from C to B
plate 2 from C to A
plate 1 from B to A
plate 3 from C to B
plate 1 from A to C
plate 2 from A to B
plate 1 from C to B


分享 编译原理

以梦为马
5个月前
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

bool DFA(string s){//识别无符号数 
    int len = s.length();//串长 
    // 判断最后一位是否合法
    if(s[len - 1] < '0' || s[len - 1] > '9') return false; 
    if(s[len -1] == 'e' || s[len- 1] == 'E') return false;  
    if(s[len- 1] == '.' || s[len - 1] == '+' || s[len - 1] == '-') return false;

    int i = 0;
    if(s[0] < '0' || s[0] > '9') return false;//判断首位是否为数字
    for(; i < len; i ++){
        if(s[i] <= '9' && s[i] >= '0'){
            i ++;
        }
        else if(s[i] == '.'){//当前位为'.' 
            char c = s[i + 1];
            if(c >= '0' || c <= '9') i ++;
            else return false;
        }
        else if(s[i] == 'E' || s[i] == 'e'){//当前位为'E'或'e' 
            char c = s[i + 1];//预判下一位 
            if(c >= '0' || c <= '9') i ++;
            else if (c == '+' || c == '-') i ++;
            else return false;

        }
        else if(s[i] =='+' || s[i] == '-') i ++;//当前位为'+'或'-' 
        else return false;
    }
    if(i == len) return true;
}

int main(){
    cout << "input '*' to stop ! " << endl; 
    while(1){
        string str;
        cin >> str;
        if(str == "*") return 0;

        if(DFA(str)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}


分享 进制转换

以梦为马
5个月前

十进制转为二进制

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1000;
int n, num;
int a[N];

int main(){
    cin >> n;
    do{  //不用while循环,可以有效处理n == 0的情况
        a[num ++] = n % 2;
        n /= 2;
    }while(n != 0);

    for(int i = num - 1; i >= 0; i --){
        cout << a[i];
    }

    return 0;
}

十进制转为十六进制

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1000;
int n, num;
int a[N];
char h[17] = {'0', '1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};//十六进制

int main(){
    cin >> n;
    do{  //不用while循环,可以有效处理n == 0的情况
        a[num ++] = n % 16;
        n /= 16;
    }while(n != 0);

    for(int i = num - 1; i >= 0; i --){
        int n = a[i];
        cout << h[n];
    }

    return 0;
}



以梦为马
7个月前

题目描述

你现在被困在一个三维地牢中,需要找到最快脱离的出路!

地牢由若干个单位立方体组成,其中部分不含岩石障碍可以直接通过,部分包含岩石障碍无法通过。

向北,向南,向东,向西,向上或向下移动一个单元距离均需要一分钟。

你不能沿对角线移动,迷宫边界都是坚硬的岩石,你不能走出边界范围。

请问,你有可能逃脱吗?

如果可以,需要多长时间?

输入格式

输入包含多组测试数据。

每组数据第一行包含三个整数 L,R,C 分别表示地牢层数,以及每一层地牢的行数和列数。

接下来是 L 个 R 行 C 列的字符矩阵,用来表示每一层地牢的具体状况。

每个字符用来描述一个地牢单元的具体状况。

其中, 充满岩石障碍的单元格用”#”表示,不含障碍的空单元格用”.”表示,你的起始位置用”S”表示,终点用”E”表示。

每一个字符矩阵后面都会包含一个空行。

当输入一行为”0 0 0”时,表示输入终止。

输出格式

每组数据输出一个结果,每个结果占一行。

如果能够逃脱地牢,则输出”Escaped in x minute(s).”,其中X为逃脱所需最短时间。

如果不能逃脱地牢,则输出”Trapped!”。

数据范围

1≤L,R,C≤100

输入样例:

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

输出样例:

Escaped in 11 minute(s).
Trapped!

C++代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>

using namespace std;
const int N = 110;

int l, r, c;
char g[N][N][N];//地图
int dis[N][N][N];//到起点的距离
int dx[] = {0, 0, 0, 0, 1, -1};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {1, -1, 0, 0, 0, 0};

struct node{//结点
    int x, y, z;
};

int bfs(node &start, node &end){
    queue<node> q;
    q.push(start);
    memset(dis, -1, sizeof dis);
    dis[start.x][start.y][start.z] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 6;  i ++){
            int x = dx[i] + t.x, y = dy[i] + t.y, z = dz[i] + t.z;
            if(x < 0 || x >= l || y < 0 || y >= r || z < 0 || z >= c) continue;//越界
            if(g[x][y][z] == '#') continue;//碰壁
            if(dis[x][y][z] != -1) continue;//已遍历过
            dis[x][y][z] = dis[t.x][t.y][t.z] + 1;
            if(x == end.x && y == end.y && z == end.z) return dis[x][y][z];
            q.push({x, y, z});
        }
    }
    return -1;
}

int main(){
//  freopen("abc.txt", "r", stdin);
    node st, ed;
    while(cin >> l >> r >> c, l || r || c){
        for(int i = 0; i < l; i ++){
            for(int j = 0; j < r; j ++){
                for(int k = 0; k < c; k ++){
                //  scanf("%c", &g[i][j][k]);
                    cin >> g[i][j][k];
                    if(g[i][j][k] == 'S') st = {i, j, k};//起点
                    else if(g[i][j][k] == 'E') ed = {i, j, k};//终点
                }
            }
        }
        int t = bfs(st, ed);
        if(t == -1) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n", t);
    }

    return 0;
}



以梦为马
7个月前

题目描述

你有一张某海域 N×N 像素的照片,”.”表示海洋、”#”表示陆地,如下所示:

.......
.##....
.##....
....##.
..####.
…###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿,例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

例如上图中的海域未来会变成如下样子:

.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数N。

以下 N 行 N 列,包含一个由字符”#”和”.”构成的 N×N 字符矩阵,代表一张海域照片,”#”表示陆地,”.”表示海洋。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

数据范围

1≤N≤1000

输入样例1:

7
.......
.##....
.##....
....##.
..####.
…###.
.......

输出样例1:

1

输入样例2:

9
.........
.##.##…
.#####…
.##.##…
.........
.##.#....
.#.###…
.#..#....
.........

输出样例2:

1

C ++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;

int n;
char g[N][N];//地图
bool st[N][N];//是否被遍历过
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

//sx, sy表示初始坐标,lan和bound分别表示当前岛屿陆地和边界的数量
void bfs(int sx, int sy, int &land, int &bound){//flood fill算法
    queue<PII> q;//q表示陆地的集合
    q.push({sx, sy});//将初始位置加入队列
    st[sx][sy] = true;//初始位置已被遍历
    while(q.size()){
        auto t = q.front();
        q.pop();
        land ++;//陆地数量增1
        bool is_bound = false;
        for(int i = 0; i < 4; i ++){
            int x = dx[i] + t.x, y = dy[i] + t.y;
            if(x < 0 || x >= n || y < 0 || y >= n) continue;//越界
            if(st[x][y]) continue;//已被遍历过
            if(g[x][y] == '.'){//边界
                is_bound = true;
                continue;
            }
            q.push({x, y});//将当前点加入队列
            st[x][y] = true;//当前点已被遍历过

        }
        if(is_bound) bound ++;//边界的数量增1

    } 
}

int main(){
//  freopen("abc.txt", "r", stdin);
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);

    int cnt = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(!st[i][j] && g[i][j] == '#'){//当前点为陆地且未被遍历
                int land = 0, bound = 0;
                bfs(i, j, land, bound);
                if(land == bound) cnt ++;//边界数量和陆地数量相等,即岛屿被淹没
            }
        }
    }

    cout << cnt << endl;

    return 0;
}




以梦为马
7个月前

题目描述

小明要做一个跑步训练。

初始时,小明充满体力,体力值计为 10000。如果小明跑步,每分钟损耗

600 的体力。如果小明休息,每分钟增加 300 的体力。体力的损耗和增加都是

均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循

环。如果某个时刻小明的体力到达 0,他就停止锻炼。

请问小明在多久后停止锻炼。为了使答案为整数,请以秒为单位输出答案。

答案中只填写数,不填写单位。

【答案提交】

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个

整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int main(){
    int energy = 10000;
    int cnt = 0;
    int res = 0;
    bool ispao = true;
    while(true){
        if(energy < 600 && ispao == true) break;//轮到跑且能量不够跑完一分钟
        if(ispao){//跑一分钟
            ispao = false;
            energy -= 600;
        }
        else{//休息一分钟
            ispao = true;
            energy += 300;
        }
        cnt ++;//跑或者休息一分钟的次数
    }

    res = cnt * 60 + energy / 10;//以秒为单位

    cout << res << endl;

    return 0;
}



以梦为马
8个月前

题目描述

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数,使其乘积最大。

请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 1000000009 的余数。

注意,如果 X<0, 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数,即:0−((0−x)%1000000009)
输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

输出一个整数,表示答案。

数据范围

1≤K≤N≤105,
−105≤Ai≤105

输入样例1:

5 3
-100000
-10000
2
100000
10000

输出样例1:

999100009

输入样例2:

5 3
-100000
-100000
-2
-100000
-100000

输出样例2:

-999999829

主要考点

贪心

主要思路

step 1. 对Ai~An排序

step 2. 分类讨论:
    1) k == n, 直接算

    2) k < n , 再分类
        1) k为偶数, 结果必然为负,分类讨论:
            a. 负数有偶数个, 则 res >= 0
            b. 负数有奇数个, 则选偶数个奇数, 则 res >= 0

        2) k为奇数, 分类讨论:
            a. 所有数均为负数, res < 0
            b. 至少存在一个非负数,先选择最大的那个,然后再从k - 1个中选(k - 1 为偶数,回到上一种情况),res >= 0

C ++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1000000009;

int n, k;
int a[N];

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++) cin >> a[i];

    sort(a, a + n);

    int res = 1, sign = 1;
    int l = 0, r = n - 1; 

    if(k % 2){  // k为奇数的情况
        res = a[r];
        r --, k --;
        if(res < 0) sign = -1;  //判断最大值的符号, sign = -1, 表示最终结果为负
    }

    while(k){
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r - 1] * a[r];
        if(x * sign > y * sign){
            res = x % mod * res % mod;
            l += 2;
        }
        else{
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }

    printf("%d\n", res);

    return 0;
}




以梦为马
8个月前

题目描述

几个人一起出去吃饭是常有的事。

但在结帐的时候,常常会出现一些争执。

现在有 n 个人出去吃饭,他们总共消费了 S 元。

其中第 i 个人带了 ai 元。

幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出多少钱呢?

为了公平起见,我们希望在总付钱量恰好为 S 的前提下,最后每个人付的钱的标准差最小。

这里我们约定,每个人支付的钱数可以是任意非负实数,即可以不是 1 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍:标准差是多个数与它们平均数差值的平方平均数,一般用于刻画这些数之间的“偏差有多大”。

形式化地说,设第 i 个人付的钱为 bi 元,那么标准差为 :

输入格式

第一行包含两个整数 n、S;

第二行包含 n 个非负整数 a1, …, an。

输出格式

输出最小的标准差,四舍五入保留 4 位小数。

数据范围

1≤n≤5×105,
0≤ai,S≤109

输入样例1:

5 2333
666 666 666 666 666

输出样例1:

0.0000

输入样例2:

10 30
2 1 4 7 4 8 3 6 4 7

输出样例2:

0.7928

主要考点

贪心

核心思想

从小到大排序, 钱不够平均值则掏出当前剩余的所有钱, 不够的部分后面均摊,
当前钱够的话则掏平均值的钱即可.

C ++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 5e5 + 10;

int n, s;
int a[N];

int main(){
    cin >> n >> s;
    for(int i = 0; i < n; i ++) cin >> a[i];

    sort(a, a + n);  //以防后面的前不够平均数但已无能补偿的情况

    double ave = 1.0 * s / n, cur_ave = ave, sum = 0;
    for(int i = 0; i < n; i ++){
        if(a[i] <= cur_ave){
            sum += (a[i] - ave) * (a[i] - ave);
            s -= a[i];
            cur_ave = 1.0 * s / (n - i - 1);
        }
        else{
            sum += (cur_ave - ave) * (cur_ave - ave);
        }
    }

    printf("%.4lf\n", sqrt(sum / n));

    return 0;
}