头像

zbmacro




离线:1天前



zbmacro
28天前

题目描述

给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入格式
第一行包含整数 N,表示数组长度。

第二行包含 N 个不大于 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤10^5

样例

输入样例1:
6
7 1 5 3 6 4
输出样例1:
7
输入样例2:
5
1 2 3 4 5
输出样例2:
4
输入样例3:
5
7 6 4 3 1
输出样例3:
0
样例解释
样例1:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

样例3:在这种情况下, 不进行任何交易, 所以最大利润为 0。

#include <iostream>

using namespace std;

const int N = 100000;

int main(){
    int n, t, buy, tbuy, sell = 0;
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &t);
        if(i == 0) buy = -t;
        else{
            tbuy = buy;
            buy = max(buy, sell-t);
            sell = max(sell, tbuy+t);
        }
    }
    cout <<sell;
    return 0;
}



zbmacro
28天前

题目描述

实现一个单链表,链表初始为空,支持三种操作:

向链表头插入一个数;
删除第 k 个插入的数后面的数;
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式
第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

H x,表示向链表头插入一个数 x。
D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。
输出格式
共一行,将整个链表从头到尾输出。

数据范围
1≤M≤100000
所有操作保证合法。

样例

输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100000;
struct node{
    int n;
    node *next;
    node(int n): n(n), next(NULL){};
};

int main(){
    int m, k, x, n = 0;
    char c;
    node *sign[N+1], *head = NULL;
    scanf("%d", &m);

    for(int i = 1; i <= m; i++){
        getchar();
        scanf("%c %d", &c, &k);
        if(c == 'H'){
            node *p = new node(k);
            p->next = head;
            head = p;
            sign[++n] = p; 
        }else if(c == 'D'){
            if(k == 0) head = head->next;
            else sign[k]->next = sign[k]->next->next;
        }else{
            scanf("%d", &x);
            node *p = new node(x);
            p->next = sign[k]->next;
            sign[k]->next = p;
            sign[++n] = p; 
        }
    }

    while(head){
        printf("%d ", head->n);
        head = head->next;
    }
    return 0;
}



zbmacro
28天前

题目描述

很久以前,T王国空前繁荣。

为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。

为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。

同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣,他巡查于各大城市之间,体察民情。

所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。

他有一个钱袋,用于存放往来城市间的路费。

聪明的J发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。也就是说走1千米花费11,走2千米要花费23。

J大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?

输入格式
输入的第一行包含一个整数 n,表示包括首都在内的T王国的城市数。

城市从 1 开始依次编号,1 号城市为首都。

接下来 n−1 行,描述T国的高速路(T国的高速路一定是 n−1 条)。

每行三个整数 Pi,Qi,Di,表示城市 Pi 和城市 Qi 之间有一条双向高速路,长度为 Di 千米。

输出格式
输出一个整数,表示大臣J最多花费的路费是多少。

数据范围
1≤n≤10^5,
1≤Pi,Qi≤n,
1≤Di≤1000

样例

输入样例:
5 
1  2  2 
1  3  1 
2  4  5 
2  5  4 
输出样例:
135

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

struct node{
    int city, price;
    node(int city, int price): city(city), price(price){};
};
const int N = 100000;
int sign[N+1];
vector<vector<node*>> input(N+1, vector<node*>());

void dfs(int start, int father, int dist){
    sign[start] = dist;

    for(int i = 0; i < input[start].size(); i++)
        if(input[start][i]->city != father) dfs(input[start][i]->city, start, dist+input[start][i]->price);
}

int main(){
    int n, p, q, d, city = 1;
    scanf("%d", &n);

    if(n == 1) return 0;

    for(int i = 0; i < n; i++){
        scanf("%d%d%d", &p, &q, &d);
        input[p].push_back(new node(q, d));
        input[q].push_back(new node(p,d));
    }

    dfs(1, -1, 0);

    for(int i = 1; i <= n; i++)
        if(sign[i] > sign[city]) city = i;

    dfs(city, -1, 0);

    for(int i = 1; i <= n; i++)
        if(sign[i] > sign[city]) city = i;

    cout <<(21+(long long int)sign[city])*sign[city]/2;
    return 0;
}



zbmacro
28天前

题目描述

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

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

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

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

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

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

输入格式
第一行包含一个整数N。

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

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

输出格式
一个整数表示答案。

数据范围
1≤N≤1000

样例

输入样例1:
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1:
1
输入样例2:
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2:
1

#include <iostream>

using namespace std;

const int N = 1000;
char input[N+1][N+1];
int n, dx[4] = {0,0,-1,1}, dy[4] = {1,-1,0,0};
bool chen;

void dfs(int x, int y){
    input[x][y] = '*';
    bool ischen = false; // 当前岛屿是否会沉,true会  false不会
    for(int i = 0; i < 4; i++){
        int xx = x+dx[i], yy = y+dy[i];
        if(xx >= 0 && x < n && yy >= 0 && yy < n){
            if(input[xx][yy] == '.') ischen = true;
            if(input[xx][yy] == '#') dfs(xx, yy);
        }
    }
    if(chen && !ischen) chen = false;
}

int main(){
    int ans = 0;

    scanf("%d", &n);
    getchar();
    for(int i = 0; i < n; i++) scanf("%s", input[i]);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(input[i][j] == '#'){
                chen = true;
                dfs(i, j);
                ans += chen;
            }
    cout <<ans;
    return 0;
}



zbmacro
28天前

题目描述

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

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

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

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

请问,你有可能逃脱吗?

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

输入格式
输入包含多组测试数据。

每组数据第一行包含三个整数 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!

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

using namespace std;

const int N = 100;

int main(){
    int l, r, c, bfs[N*N*N+10][4], ind, tind, find, dl[3] = {1, -1}, dr[4] = {0,0,1,-1}, dc[4] = {1,-1,0,0};
    char input[N+10][N+10][N+10];

    while(true){
        scanf("%d%d%d", &l, &r, &c);
        if(!l && !r && !c) break;
        find = ind = tind = 0;

        for(int i = 0; i < l; i++){
            getchar();
            for(int j = 0; j < r; j++){
                scanf("%s", input[i][j]);
                for(int z = 0; z < c & !ind; z++){
                    if(input[i][j][z] == 'S'){
                        bfs[ind][0] = i;
                        bfs[ind][1] = j;
                        bfs[ind][2] = z;
                        bfs[ind++][3] = 0;
                        input[i][j][z] = '#';
                    }
                }
            }
        }

        while(tind < ind && !find){
            for(int i = 0; i < 4; i++){
                int ll = bfs[tind][0], rr = bfs[tind][1] + dr[i], cc = bfs[tind][2] + dc[i];

                if(rr >= 0 && rr < r && cc >=0 && cc < c && input[ll][rr][cc] != '#'){
                    if(input[ll][rr][cc] == 'E') find = bfs[tind][3]+1;
                    bfs[ind][0] = ll;
                    bfs[ind][1] = rr;
                    bfs[ind][2] = cc;
                    bfs[ind++][3] = bfs[tind][3]+1;
                    input[ll][rr][cc] = '#';
                }
            }
            for(int i = 0; i < 2; i++){
                int ll = bfs[tind][0] + dl[i], rr = bfs[tind][1], cc = bfs[tind][2];

                if(ll >= 0 && ll < l && input[ll][rr][cc] != '#'){
                    if(input[ll][rr][cc] == 'E') find = bfs[tind][3]+1;
                    bfs[ind][0] = ll;
                    bfs[ind][1] = rr;
                    bfs[ind][2] = cc;
                    bfs[ind++][3] = bfs[tind][3]+1;
                    input[ll][rr][cc] = '#';
                }
            }
            tind++;
        }

        if(find) printf("Escaped in %d minute(s).\n", find);
        else printf("Trapped!\n");
    }
    return 0;
}



zbmacro
28天前

题目描述

给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN,如下图所示:

现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?

如果有多个深度的权值和同为最大,请你输出其中最小的深度。

注:根的深度是 1。

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。

输出格式
输出一个整数代表答案。

数据范围
1≤N≤10^5,
−10^5≤Ai≤10^5

样例

输入样例:
7
1 6 5 4 3 2 1
输出样例:
2

#include <iostream>
#include <cstdio>
#include <climits>

const int N = 100000;
using namespace std;

int main(){
    int n, a, depth = 1, tmpdepth = 1, node = 2;
    long long int maxsum = INT_MIN,  tmpsum = 0;
    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        scanf("%d", &a);
        if(i == node){
            node *= 2;
            if(maxsum < tmpsum){
                maxsum = tmpsum;
                depth = tmpdepth;
            }
            tmpdepth++;
            tmpsum = a;
        }else tmpsum += a;
    }
    if(maxsum < tmpsum){
        maxsum = tmpsum;
        depth = tmpdepth;
    }

    cout <<depth;
    return 0;
}



zbmacro
28天前

题目描述

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。

请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下

1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时,表示输入结束。

输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围
1≤W,H≤20

样例

输入样例:
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0
输出样例:
45

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

using namespace std;

int main(){
    char input[30][30];
    int bfs[1000][2], w, h, ans, ind, tind, dx[4] = {0,0,-1,1}, dy[4] = {1,-1,0,0};

    while(true){
        ans = ind = tind = 0;
        scanf("%d%d", &w, &h);
        if(w == 0 && h == 0) break;

        for(int i = 0; i < h; i++){
            scanf("%s", input[i]);
            for(int j = 0; j < w && !ind; j++){
                if(input[i][j] == '@'){
                    bfs[ind][0] = i;
                    bfs[ind++][1] = j;
                    input[i][j] = '#';
                    ans++;
                }
            }
        }

        while(tind < ind){
            for(int i = 0; i < 4; i++){
                int xx = bfs[tind][0] + dx[i], yy = bfs[tind][1] + dy[i];
                if(xx >= 0 && xx < h && yy >= 0 && yy < w && input[xx][yy] == '.'){
                    bfs[ind][0] = xx;
                    bfs[ind++][1] = yy;
                    input[xx][yy] = '#';
                    ans++;
                }
            }
            tind++;
        }

        printf("%d\n", ans);
    }

    return 0;
}



zbmacro
28天前

题目描述

有 N 个瓶子,编号 1∼N,放在架子上。

比如有 5 个瓶子:

2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式
第一行包含一个整数 N,表示瓶子数量。

第二行包含 N 个整数,表示瓶子目前的排列状况。

输出格式
输出一个正整数,表示至少交换多少次,才能完成排序。

数据范围
1≤N≤10000,

样例

输入样例1:
5
3 1 2 5 4
输出样例1:
3
输入样例2:
5
5 4 3 2 1
输出样例2:
2

#include <iostream>

const int N = 10000;
using namespace std;

int main(){
    int n, input[N+1], sign[N+1], ans = 0;

    cin >>n;
    for(int i = 1; i <= n; i++){
        cin >>input[i];
        sign[input[i]] = i;
    }

    for(int i = 1; i <= n; i++){
        if(input[i] != i){
            int t = input[i];
            swap(input[sign[i]], input[i]);
            sign[t] = sign[i];
            ans++;
        }
    }
    cout <<ans;
    return 0;
}



zbmacro
28天前

题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置,字符 E 表示奶酪所在的位置,字符 # 表示墙壁,字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。

输入格式
第一行是一个正整数 T,表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R 和 C,表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容,每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。

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

数据范围
1<T≤10,
2≤R,C≤200

样例

输入样例:
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
输出样例:
5
1
oop!

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

using namespace std;

int main(){
    char input[210][210];
    bool sign[210][210];
    int t, r, c, n, tn, find = 0, bfs[40010][3], dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
    scanf("%d", &t);

    for(int i = 0; i < t; i++){
        memset(sign, 0, sizeof(sign));
        n = tn = find = 0;

        scanf("%d%d", &r, &c);
        getchar();
        for(int x = 0; x < r; x++){
            scanf("%s", &input[x]);
            for(int y = 0; y < c && !n; y++){
                if(input[x][y] == 'S'){
                    bfs[n][0] = x;
                    bfs[n][1] = y;
                    bfs[n++][2] = 0;
                    sign[x][y] = true;
                }
            }
        }

        while(tn < n){
            for(int j = 0; j < 4; j++){
                int xx = bfs[tn][0]+dx[j], yy = bfs[tn][1]+dy[j];
                if(xx >= 0 && xx < r && yy >= 0 && yy < c && input[xx][yy] != '#' && !sign[xx][yy]){
                    if(input[xx][yy] == 'E') find = bfs[tn][2]+1;
                    bfs[n][0] = xx;
                    bfs[n][1] = yy;
                    bfs[n++][2] = bfs[tn][2]+1;
                    sign[xx][yy] = true;
                }
            }
            tn++;
            if(find) break;
        }
        if(find) cout <<find <<endl;
        else cout <<"oop!" <<endl;
    }
    return 0;
}



zbmacro
28天前

题目描述

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N 行。

其中每一行的格式是:

ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是”热帖”。

具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是”热帖”。

给定日志,请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式
第一行包含三个整数 N,D,K。

以下 N 行每行一条日志,包含两个整数 ts 和 id。

输出格式
按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围
1≤K≤N≤10^5,
0≤ts,id≤10^5,
1≤D≤10000

样例

输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3

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

using namespace std;

const int N = 100000;
struct node{
    int ts, id;
    node(int ts, int id): ts(ts), id(id){};
};

static bool cmp(node *a, node *b){
    if(a->id == b->id) return a->ts < b->ts;
    return a->id < b->id;
}

int main(){
    int n, d, k, ts, id;
    node *input[N];
    scanf("%d%d%d", &n, &d, &k);

    for(int i = 0; i < n; i++){
        scanf("%d%d", &ts, &id);
        input[i] = new node(ts, id);
    }

    sort(input, input+n, cmp);

    int left = 0, right = 0, sum = 0;
    bool out = false;
    while(right < n){
        if(input[left]->id == input[right]->id){
            if(!out){
                while(input[right]->ts - input[left]->ts >= d){
                    sum--;
                    left++;
                }
                sum++;
            }
        }else{
            left = right;
            sum = 1;
            out = false;
        }
        if(!out && sum >= k){
            printf("%d\n", input[left]->id);
            out = true;
        }
        right++;
    }
    return 0;
}