折点计数 (100)

给定 n 个整数表示连续 n 天的销售量。

如果某天之前销售量增长,而后一天销售量减少,则称这一天为折点;反过来如果之前销售量减少而后一天销售量增长,也称这一天为折点。

其他天不是折点。

如下图所示,第 3 天和第 6 天是折点。

折点示例

给定 n 个整数 a1, a2, ..., an 表示销售量,请计算总共有多少个折点。

输入格式:

  • 第一行:一个整数 n
  • 第二行:n 个整数,用空格分隔,表示 a1, a2, ..., an

输出格式:

  • 一个整数,表示折点的数量。

数据范围:

  • 所有评测用例满足:1 ≤ n ≤ 1000,每天的销售量不超过 10000 的非负整数。

输入样例:

7
5 4 1 2 3 6 4

输出样例:

2

题目分析

模拟

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, p, u, cnt;
bool up;
int main () {
    cin >> n >> p >> u;
    up = p < u;
    for(int i = 2; i < n; ++i) {
        p = u;
        cin >> u;
        if(up && p > u) up = !up, ++cnt;
        else if(!up && p < u) up = !up, ++cnt;
    }
    cout << cnt;
    return 0;
} 

俄罗斯方块 (100)

俄罗斯方块是由俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。

游戏在一个 15 行 10 列的方格图上进行,方格图上的每个格子可能已经放置了方块,或者没有放置方块。

每一轮,都会有一个由 4 个小方块组成的板块从方格图的上方落下,玩家可以左右移动板块并放到合适的位置。当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时,板块停止移动。如果此时方格图的某一行全放满了方块,则该行被消除并得分。

在这个问题中,需要编写一个程序来模拟板块下落,无需处理玩家的操作和消行得分。

输入格式:

  • 输入的前 15 行:初始的方格图,每行包含 10 个数字,相邻的数字用空格分隔。数字为 0 表示方格中没有方块,数字为 1 表示初始时有方块。前 4 行的数字都是 0。
  • 输入的第 16 至第 19 行:新加入的板块的形状,每行包含 4 个数字,组成了板块图案。0 表示无方块,1 表示有方块。板块的图案中正好包含 4 个方块,且是四连通的。
  • 第 20 行:一个 1 到 7 之间的整数,表示板块图案最左边开始的时候在方格图的哪一列中。

输出格式:

  • 输出 15 行,每行 10 个数字,相邻的数字之间用一个空格分隔,表示板块下落后的方格图。

注意:

  • 无需处理最终的消行。

输入样例:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3

输出样例:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 0 0 0 0

题目分析

模拟

代码实现

#include <iostream>
#include <vector>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 15, M = 10, O = 20, F = 4;

int g[N][M];
vector <PII> nodes;
bool check(int d) {
    vector <PII> t = nodes;
    for(auto& no : t) {
        no.x += d;
        if(no.x >= N) return 0;
        if(g[no.x][no.y]) return 0;
    }
    return 1;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            cin >> g[i][j];
    for(int i = 0; i < F; ++i)
        for(int j = 0; j < F; ++j) {
            int val = 0;
            cin >> val;
            if(val) nodes.push_back({i,j}); 
        }
    int d;
    cin >> d;
    int dx = nodes[0].x, dy = nodes[0].y;
    for(PII& t : nodes) t.x -= dx, t.y += d - 1;
    d = 0;
    while(check(d)) ++d;
    for(PII& t : nodes) {
        t.x += d - 1;
        g[t.x][t.y] = 1;
    }
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < M; ++j)
            cout << g[i][j] << ' ';
        cout << '\n';
    }
    return 0;
} 

路径解析 (100)

在操作系统中,数据通常以文件的形式存储在文件系统中。

文件系统一般采用层次化的组织形式,由目录和文件构成,形成一棵树的形状。

文件有内容,用于存储数据。

目录是容器,可包含文件或其他目录。

为了指定文件系统中的某个文件,需要用路径来定位。

在类 Unix 系统中,路径由若干部分构成,每个部分是一个目录或者文件的名字,相邻两个部分之间用 / 符号分隔。

有一个特殊的目录被称为根目录,是整个文件系统形成的这棵树的根节点,用一个单独的 / 符号表示。

在操作系统中,有当前目录的概念,表示用户目前正在工作的目录。根据出发点可以把路径分为两类:

  • 绝对路径:以 / 符号开头,表示从根目录开始构建的路径。
  • 相对路径:不以 / 符号开头,表示从当前目录开始构建的路径。

例如,有一个文件系统的结构如下图所示。

在这个文件系统中,有根目录 / 和其他普通目录 d1、d2、d3、d4,以及文件 f1、f2、f3、f1、f4。

其中,两个 f1 是同名文件,但在不同的目录下。

对于 d4 目录下的 f1 文件,可以用绝对路径 /d2/d4/f1 来指定。

如果当前目录是 /d2/d3,这个文件也可以用相对路径 ../d4/f1 来指定,这里 .. 表示上一级目录(注意,根目录的上一级目录是它本身)。

还有 . 表示本目录,例如 /d1/./f1 指定的就是 /d1/f1。

注意,如果有多个连续的 / 出现,其效果等同于一个 /,例如 /d1///f1 指定的也是 /d1/f1。

本题会给出一些路径,要求对于每个路径,给出正规化以后的形式。

一个路径经过正规化操作后,其指定的文件不变,但是会变成一个不包含 . 和 .. 的绝对路径,且不包含连续多个 / 符号。

如果一个路径以 / 结尾,那么它代表的一定是一个目录,正规化操作要去掉结尾的 /。

若这个路径代表根目录,则正规化操作的结果是 /。

若路径为空字符串,则正规化操作的结果是当前目录。

输入格式:

  • 第一行:一个整数 P,表示需要进行正规化操作的路径个数。
  • 第二行:一个字符串,表示当前目录。
  • 以下 P 行,每行一个字符串,表示需要进行正规化操作的路径。

输出格式:

  • 共 P 行,每行一个字符串,表示经过正规化操作后的路径,顺序与输入对应。

数据范围:

  • 1 ≤ P ≤ 10。
  • 文件和目录的名字只包含大小写字母、数字和小数点 .、减号 - 以及下划线 _。
  • 不会有文件或目录的名字是 . 或 ..,它们具有题目描述中给出的特殊含义。
  • 输入的所有路径每个长度不超过 1000 个字符。
  • 输入的当前目录保证是一个经过正规化操作后的路径。

输入样例:

7
/d2/d3
/d2/d4/f1
../d4/f1
/d1/./f1
/d1///f1
/d1/
///
/d1/../../d2

输出样例:

/d2/d4/f1
/d2/d4/f1
/d1/f1
/d1/f1
/d1
/
/d2

题目分析

String 模拟

代码实现

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

int p;
string ss, s;
void getslice(vector <string>& a, string& s) {
    int p = 0;
    while(p < s.length()) {
        string t = "";
        while(p < s.length() && s[p] == '/') ++p;
        if(p >= s.length()) break;
        while(p < s.length() && s[p] != '/') t += s[p++];
        a.push_back(t);
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> p;
    cin.ignore();
    getline(cin, ss);
    while(p--) {
        getline(cin, s);
        vector <string> cur;
        if(*s.begin() != '/') getslice(cur, ss);
        getslice(cur,s);
        int p = 0;
        while(p < cur.size()) {
            if(cur[p] == ".") cur.erase(cur.begin() + p);
            else if (cur[p] == "..") {
                cur.erase(cur.begin() + p);
                if(p - 1 >= 0) cur.erase(cur.begin() + p - 1), --p;
            }
            else ++p;
        }
        if(!cur.size()) cout << '/';
        for(auto&  chs : cur) cout << '/' << chs;
        cout << '\n';
    }
    return 0;
} 

游戏(100)

小明在玩一个电脑游戏,游戏在一个 n×m 的方格图上进行,小明控制的角色开始的时候站在第一行第一列,目标是前往第 n 行第 m 列。

方格图上有一些方格是始终安全的,有一些在一段时间是危险的,如果小明控制的角色到达一个方格的时候方格是危险的,则小明输掉了游戏,如果小明的角色到达了第 n 行第 m 列,则小明过关。

第一行第一列和第 n 行第 m 列永远都是安全的。

每个单位时间,小明的角色必须向上下左右四个方向相邻的方格中的一个移动一格。

经过很多次尝试,小明掌握了方格图的安全和危险的规律:每一个方格出现危险的时间一定是连续的。

并且,小明还掌握了每个方格在哪段时间是危险的。

现在,小明想知道,自己最快经过几个时间单位可以达到第 n 行第 m 列过关。

输入格式:

  • 第一行:三个整数 n, m, t,表示方格图的行数 n、列数 m,以及方格图中有危险的方格数量。
  • 接下来 t 行,每行 4 个整数 r, c, a, b,表示第 r 行第 c 列的方格在第 a 个时刻到第 b 个时刻之间是危险的,包括 a 和 b。游戏开始时的时刻为 0。输入数据保证 r 和 c 不同时为1,而且当 r 为 n 时 c 不为 m。一个方格只有一段时间是危险的。

输出格式:

  • 一个整数,表示小明最快经过几个时间单位可以过关。

数据范围:

  • 前 3
  • 所有评测用例满足:0 < n, m ≤ 100,0 ≤ t < 9999,1 ≤ r ≤ n,1 ≤ c ≤ m,0 ≤ a ≤ b ≤ 100。

输入样例:

3 3 3
2 1 1 1
1 3 2 10
2 2 2 10

输出样例:

6

样例解释: 第 2 行第 1 列时刻 1 是危险的,因此第一步必须走到第 1 行第 2 列。

第二步可以走到第 1 行第 1 列,第三步走到第 2 行第 1 列,后面经过第 3 行第 1 列、第 3 行第 2 列到达第 3 行第 3 列。

题目分析

BFS 拆点

代码实现

#include <iostream>
#include <queue>
#define x first.first 
#define y first.second
#define z second
using namespace std;
using PIII = pair <pair <int,int>, int>;
const int N = 200;
const PIII dir[4] = {{{-1,0},0},{{1,0},0},{{0,-1},0},{{0,1},0}};

int n, m, t;
bool g[N][N][N];
bool check(PIII p) {
    if(p.x < 1 || p.y < 1 || p.x > n || p.y > m || g[p.x][p.y][p.z]) return 0;
    return 1;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> t;
    while(t--) {
        int r, c, a, b;
        cin >> r >> c >> a >> b;
        for(int i = a; i <= b; ++i)
            g[r][c][i] = 1;
    }
    queue <PIII> que;
    que.push({{1,1}, 0});
    while(que.size()) {
        PIII p = que.front(); que.pop();
        if(!check(p)) continue;
        g[p.x][p.y][p.z] = 1;
        for (int k = 0; k < 4; ++k) {
            PIII u = {{p.x + dir[k].x, p.y + dir[k].y},p.z + 1};
            if(check(u)) {
                if(u.x == n && u.y == m) {
                    cout << u.z;
                    return 0;
                }
                que.push(u);
            }
        }
    }
    cout << "-1";
    return 0;
} 

网络连接 (0)

输入格式:

  • 第一行:一个正整数 T,表示数据的组数,保证 T=5。接下来依次描述每组数据。
  • 每组数据的第一行:3 个正整数 n, m, p,表示设备的总数,可以建立的连线数量和拓扑结构的参数。
  • 第二行:一个长度为 n 的 01 字符串,依次表示这 n 台设备是否为用户设备;为 1 表示是,为 0 表示不是。相邻字符之间无空格隔开,保证不会出现除了 0 和 1 之外的字符。保证至少有 2 个设备是用户设备。
  • 接下来 m 行,每行包含 3 个非负整数 u, v, w,表示设备 u 和设备 v 可以消耗 w 的费用建立连线。其中 0 < u < v ≤ n,v–u ≤ p,w ≤ 106。

输出格式:

  • 对于每组数据,输出一行一个整数,表示能达到要求所需的最少费用。

数据范围: 每个测试点的每组数据分别都满足以下限制(其中 c 表示用户设备总数):

  • 1 ≤ n ≤ 500
  • 0 ≤ p ≤ 6
  • 2 ≤ c ≤ n
  • 1 ≤ m ≤ 9999
  • 0 < u < v ≤ n
  • v–u ≤ p
  • w ≤ 106

输入样例:

1
20 11 6
10000100001100000000
1 6 300
1 3 100
3 6 100
4 10 100
4 6 100
6 10 400
10 15 100
11 15 100
10 11 500
12 15 100
15 20 100

输出样例:

700

样例解释: 用户设备分别是 1、6、11、12。

最优的方案需要选择以下连线:设备 1 和 3,费用 100;设备 3 和 6,费用 100;设备 4 和 6,费用 100;设备 4 和 10,费用 100;设备 10 和 15,费用 100;设备 11 和 15,费用 100;设备 12 和 15,费用 100。

共计 700。

题目分析

联通性DP 集合的最小表示法


0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status