最大波动 (100)

小明正在研究一只股票的波动程度,他获取了连续 n 天的每日股票收盘价格。小明想知道在这 n 天中,股票收盘价格的最大波动值,即某一天与前一天的收盘价格之差的绝对值的最大值。

输入格式:

  • 第一行:一个整数 n,表示连续天数。
  • 第二行:n 个正整数,依次表示每天的收盘价格。

输出格式:

  • 一个整数,表示这只股票在 n 天中的最大波动值。

数据范围:

  • 对于所有评测用例,2≤n≤1000。
  • 股票每一天的价格为 1 到 10000 之间的整数。

输入样例:

6
2 5 5 7 3 5

输出样例:

4

样例解释: 第四天和第五天之间的波动最大,波动值为 |3−7|=4。

代码实现

#include <iostream>
using namespace std;

int n, p, u, ans = 0;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> p;
    while(--n) {
        cin >> u;
        ans = max(ans, abs(p - u));
        p = u;
    }
    cout << ans;
    return 0;
} 

火车购票 (100)

假设一节车厢有 20 排、每一排 5 个座位。

输入格式:

  • 第一行:一个整数 n,表示购票指令的数量。
  • 第二行:n 个整数,每个整数 p 在 1 到 5 之间,表示要购入的票数,相邻的两个数之间使用一个空格分隔。

输出格式:

  • n 行,每行对应一条指令的处理结果。
    • 输出 p 张车票的编号,按从小到大排序。

数据范围:

  • 对于所有评测用例,1≤n≤100,所有购票数量之和不超过 100。

输入样例:

4
2 5 4 2

输出样例:

1 2
6 7 8 9 10
11 12 13 14
3 4

样例解释:

  • 购 2 张票,得到座位 1、2。
  • 购 5 张票,得到座位 6 至 10。
  • 购 4 张票,得到座位 11 至 14。
  • 购 2 张票,得到座位 3、4。

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 50;

int n;
bool g[N][N];
bool check(int i, int p) {
    int cnt = 0;
    for(int j = 0; j < 5; ++j)
        if(!g[i][j]) ++cnt;
    return p <= cnt;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while(n--) {
        int p, i = 0, j = 0;
        bool f = 0;
        cin >> p;
        while(i < 20 && !check(i, p)) ++i;
        if(i >= 20) {
            for(int i = 0; i < 20; ++i) {
                for(int j = 0; j < 5; ++j) {
                    if(!g[i][j]) {
                        g[i][j] = 1;
                        cout << i * 5 + j + 1 << ' ';
                        --p;
                        if(!p) {
                            f = 1;
                            break;
                        }
                    }
                }
                if(f) break;
            }
        }
        while(p) {
            if(!g[i][j]) {
                cout << i * 5 + j + 1 << ' ';
                g[i][j] = 1;
                --p;
            }
            ++j;
        }
        cout << '\n';
    }
    return 0;
} 

炉石传说 (100)

《炉石传说:魔兽英雄传》(Hearthstone: Heroes of Warcraft,简称炉石传说)是暴雪娱乐开发的一款集换式卡牌游戏(如下图所示)。

游戏在一个战斗棋盘上进行,由两名玩家轮流进行操作,本题所使用的炉石传说游戏的简化规则如下:

hearthstone.jpg

  1. 玩家控制角色,每个角色有生命值和攻击力。角色分为英雄和随从。
  2. 英雄生命值为30,攻击力为0,当英雄死亡时,游戏结束,另一方获胜。
  3. 玩家可召唤随从,战场有7个位置,随从死亡会被移除。
  4. 游戏中轮流进行操作,每回合可召唤随从、随从攻击、结束回合。
  5. 随从攻击时,双方造成等同于攻击力的伤害,生命值可能为负数。

输入格式

  • 第一行:整数n,表示操作的个数。
  • 接下来n行,每行描述一个操作,格式如下:
    • <action> <arg1> <arg2> ...

三种操作:

  • summon <position> <attack> <health>:召唤随从。
  • attack <attacker> <defender>:随从攻击。
  • end:结束回合。

输出格式

  • 第1行:整数,表示n次操作后游戏的胜负结果,1表示先手玩家获胜,-1表示后手玩家获胜,0表示游戏尚未结束。
  • 第2行:整数,表示T时刻先手玩家的英雄生命值。
  • 第3行:若干个整数,表示T时刻先手玩家在战场上存活的随从个数及其生命值(从左到右)。
  • 第4行和第5行:与第2行和第3行类似,表示后手玩家。

数据范围

  • 操作个数:0≤n≤1000
  • 随从生命值:1≤生命值≤100,攻击力:0≤攻击力≤100

保证所有操作均合法。

数据约定

  • 前2
  • 前4
  • 前6

输入样例

8
summon 1 3 6
summon 2 4 2
end
summon 1 4 5
summon 1 2 1
attack 1 2
end
attack 1 1

输出样例

0
30
1 2
30
1 2

题目分析

大模拟 String

代码实现

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int n;
bool player;
string line;
typedef struct {
    int h, a;
}fl;
vector <fl> fls[2];
void summon(int p, int a, int h) {
    fl tar = {h,a};
    if(p > fls[player].size()) fls[player].push_back(tar);
    else {
        vector <fl> temp;
        int i = 0;
        for(; i < p; ++i) temp.push_back(fls[player][i]);
        temp.push_back(tar);
        for(; i < fls[player].size(); ++i) temp.push_back(fls[player][i]);
        fls[player] = temp;
    }
}
void attack(int a, int b) {
    fls[player][a].h -= fls[!player][b].a;
    fls[!player][b].h -= fls[player][a].a;
    if(a && fls[player][a].h <= 0) fls[player].erase(fls[player].begin() + a);
    if(b && fls[!player][b].h <= 0) fls[!player].erase(fls[!player].begin() + b);
}
void getStatus(int p) {
    cout << fls[p][0].h << '\n' << fls[p].size() - 1 << ' ';
    for(int i = 1; i < fls[p].size(); ++i) cout << fls[p][i].h << ' '; 
    cout << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fls[0].push_back({30,0});
    fls[1].push_back({30,0});
    cin >> n;
    cin.ignore();
    while(n--) {
        if(fls[0][0].h <= 0 || fls[1][0].h <= 0) continue;
        getline(cin, line);
        stringstream sstr(line);
        sstr >> line;
        if(line == "summon") {
            int p, a, h;
            sstr >> p >> a >> h;
            summon(p, a, h);
        }
        else if(line == "attack") {
            int a, d;
            sstr >> a >> d;
            attack(a, d);
        }
        else if (line == "end")
            player = !player;
    }
    if(fls[1][0].h <= 0) cout << 1 << '\n';
    else if (fls[0][0].h <= 0) cout << -1 << '\n';
    else cout << 0 << '\n';
    getStatus(0);
    getStatus(1);
    return 0;
} 

交通规划 (100)

G国国王来中国参观后,决定改造现有铁路成高速铁路系统。为了满足条件并节约成本,希望找到最少改造的铁路长度。使得任何两个城市间都可以通过高速铁路到达,而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。

输入格式

  • 第一行:两个整数 n 和 m,表示城市数量和城市间铁路数量。
  • 接下来 m 行,每行三个整数 a, b, c,表示城市 a 和城市 b 之间有一条长度为 c 的铁路。

输出格式

  • 一行整数,表示在满足条件的情况下最少要改造的铁路长度。

数据范围

  • 2
  • 5
  • 8
  • 10

输入保证每个城市都可以通过铁路达到首都。可能存在不止一条铁路连接两个城市。

输入样例

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

输出样例

11

提示

在输入样例中,可以将城市2到城市3的铁路改造成高速铁路,长度为5,使得每个城市到首都的最短路径长度保持不变,总共改造长度为5+2+3=10。改造其他铁路都会增加总改造长度。

题目分析

最短路径树 Dijkstra SPFA

代码实现

Dijkstra

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 1e4 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m, h[N], e[M], w[M], ne[M], dist[N], idx;
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra() {
    priority_queue <PII, vector <PII>, greater <PII>> heap;
    heap.push({0,1});
    dist[1] = 0;
    while(heap.size()) {
        PII p = heap.top(); heap.pop();
        if(st[p.y]) continue;
        st[p.y] = 1;
        for(int i = h[p.y]; ~i; i = ne[i]) {
            int u = e[i];
            if(dist[u] > dist[p.y] + w[i]) {
                dist[u] = dist[p.y] + w[i];
                heap.push({dist[u],u});
            }
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dijkstra();
    int ans = 0;
    for(int u = 2; u <= n; ++u) {
        int minEdge = INF;
        for(int i = h[u]; ~i; i = ne[i]) {
            int p = e[i];
            if(dist[u] == dist[p] + w[i]) {
                minEdge = min(minEdge, w[i]);
            }
        }
        ans += minEdge;
    }
    cout << ans;
    return 0;
} 

SPFA

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m, idx, h[N], e[M], ne[M], w[M], dist[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa() {
    queue <int> que;
    que.push(1);
    dist[1] = 0;
    st[1] = 1;
    while(que.size()) {
        int p = que.front(); que.pop();
        st[p] = 0;
        for(int i = h[p]; ~i; i = ne[i]) {
            int u = e[i];
            if(dist[u] > dist[p] + w[i]) {
                dist[u] = dist[p] + w[i];
                if(!st[u]) {
                    st[u] = 1;
                    que.push(u);
                }
            }
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    spfa();
    int ans = 0;
    for(int u = 2; u <= n; ++u) {
        int minEdge = INF;
        for(int i = h[u]; ~i; i = ne[i]) {
            int p = e[i];
            if(dist[u] == dist[p] + w[i]) 
                minEdge = min(minEdge, w[i]);
        }
        ans += minEdge;
    }
    cout << ans;
    return 0;
} 

祭坛

在遥远的 Dgeak 大陆,生活着一种叫做 Dar-dzo-nye 的怪物。

每当这种怪物降临,人们必须整夜对抗怪物而不能安睡。

为了乞求这种怪物不再降临,人们决定建造祭坛。

Dgeak 大陆可以看成一个用平面直角坐标系表示的巨大平面。

在这个平面上,有 n 个 Swaryea 水晶柱,每个水晶柱可以用一个点表示。

如果 4 个水晶柱依次相连可以构成一个四边形,满足其两条对角线分别平行于 x 轴和 y 轴,并且对角线的交点位于四边形内部(不包括边界),那么这 4 个水晶柱就可以建立一个结界。

其中,对角线的交点称作这个结界的中心。

例如下左图中,水晶柱 ABCD 可以建立一个结界,其中心为 O。

p1.png p2.png

为了起到抵御 Dar-dzo-nye 的最佳效果,人们会把祭坛修建在最多层结界的保护中。

其中不同层的结界必须有共同的中心,这些结界的边界不能有任何公共点,并且中心处也不能有水晶柱。

这里共同中心的结界数量叫做结界的层数。

为了达成这个目的,人们要先利用现有的水晶柱建立若干个结界,然后在某些结界的中心建立祭坛。

例如上右图中,黑色的点表示水晶柱(注意 P 和 O 点不是水晶柱)。

祭坛的一个最佳位置为 O 点,可以建立在 3 层结界中,其结界的具体方案见下左图。

当然,建立祭坛的最佳位置不一定是唯一,在上右图中,O 点左侧 1 单位的点 P 也可以建立一个在 3 个结界中的祭坛,见下右图。

p3.png p4.png

现在人们想知道:

  1. 祭坛最佳选址地点所在的结界层数;
  2. 祭坛最佳的选址地点共有多少个。

输入格式: 输入的第一行包含两个正整数 n,q,表示水晶柱的个数和问题的种类。保证 q=1 或 2,其意义见输出格式。

接下来 n 行,每行包含两个非负整数 x,y,表示每个水晶柱的坐标。保证相同的坐标不会重复出现。

输出格式: 若 q=1,输出一行一个整数,表示祭坛最多可以位于多少个结界的中心;若 q=2,输出一行一个整数,表示结界数最多的方案有多少种。

数据范围: 对于所有的数据,保证存在至少一种方案,使得祭坛建造在至少一层结界中,即不存在无论如何祭坛都无法建造在结界中的情况。

数据分为 8 类,各类之间互相没有交集,分别有以下特点:

  1. 占数据的 1
  2. 占数据的 1
  3. 占数据的 1
  4. 占数据的 1
  5. 占数据的 1
  6. 占数据的 1
  7. 占数据的 2
  8. 占数据的 2

此外,每类数据中,q=1 与 q=2 各占恰好一半。

输入样例1:

26 1
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5

输出样例1:

3

输入样例2:

26 2
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5

输出样例2:

2

样例解释: 样例即为题目描述中的例子,两个样例数据相同,分别询问最多的结界数量和达到最多结界数量的方案数。

其中图片的左下角为原点,右和上分别是 x 轴和 y 轴的正方向,一个格子的长度为单位长度。

以图中的 O 点建立祭坛,祭坛最多可以位于 3 个结界的中心。不存在更多结界的方案,因此样例1的答案为3。

在O点左侧1单位的点(4,5)也可以建立一个在3个结界中的祭坛,因此样例2的答案为2。

题目分析

离散化 线段树


0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status