数位之和 (100)

给定一个十进制整数 n,要求计算并输出 n 的各位数字之和。

输入格式: 输入一个整数 n。

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

数据范围: 1 ≤ n ≤ 10^9

输入样例:

20151220

输出样例:

13

样例解释: 对于输入整数 20151220,各位数字之和为 2+0+1+5+1+2+2+0=13。

题目描述

String 模拟

代码实现

#include <iostream>
using namespace std;

int n, ans, t = 1;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while(t <= n) {
        ans += n / t
        t *= 10;
    }
    cout << ans;
    return 0;
} 

消除类游戏 (100)

消除类游戏是一种深受大众欢迎的游戏,棋盘上的每一行或每一列,连续三个或更多相同颜色的棋子将被消除。现在给定一个 n 行 m 列的棋盘,每个方格有一个有颜色的棋子。请模拟一次消除后的棋盘情况。

输入格式: 第一行包含两个整数 n, m,表示棋盘的行数和列数。 接下来 n 行,每行 m 个整数,表示每个方格中棋子的颜色编号。

输出格式: 输出 n 行,每行 m 个整数,表示经过一次消除后的棋盘。如果一个方格中的棋子被消除,则输出 0,否则输出棋子的颜色编号。

数据范围: 1 ≤ n, m ≤ 30

输入样例1:

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

输出样例1:

2 2 3 0 2
3 4 5 0 4
2 3 2 0 3
0 0 0 4 4

样例1解释: 第4列的1和第4行的2可被消除,其他方格中的棋子保留。

输入样例2:

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

输出样例2:

2 2 3 0 2
3 0 0 0 0
2 3 2 0 3
2 2 0 0 0

样例2解释: 所有的1以及最后一行的3可被同时消除,其他方格中的棋子保留。

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
#define x first 
#define y second 
using namespace std;
using PII = pair <int ,int>;
const int N = 50;

int n, m, g[N][N];
bool st[N][N];
PII dir[4] = {{1,0},{-1,0},{0,-1},{0,1}};
bool check_row(int i, int j) {
    int l = j, r = j;
    do --l; while(l >= 1 && g[i][l] == g[i][j]);
    do ++r; while(r <= m && g[i][r] == g[i][j]);
    --r, ++l;
    return r - l + 1 >= 3;
}
bool check_list(int i, int j) {
    int l = i, r = i;
    do --l; while(l >= 1 && g[l][j] == g[i][j]);
    do ++r; while(r <= n && g[r][j] == g[i][j]);
    --r, ++l;
    return r - l + 1 >= 3;
}
void check(int i, int j) {
    st[i][j] = (check_row(i,j) || check_list(i,j));
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> g[i][j];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            check(i,j);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j)
            if(st[i][j]) cout << "0 ";
            else cout << g[i][j] << ' ';
        cout << '\n';
    }
    return 0;
} 

画图 (90)

题目描述:

用 ASCII 字符来画图是一件有趣的事情,并形成了一门被称为 ASCII Art 的艺术。

例如,下图是用 ASCII 字符画出来的 CSPRO 字样。

..____.____..____..____...___..
./.___/.___||.._.\|.._.\./._.\.
|.|...\___.\|.|_).|.|_).|.|.|.|
|.|___.___).|..__/|.._.<|.|_|.|
.\____|____/|_|...|_|.\_ ___/.

本题要求编程实现一个用 ASCII 字符来画图的程序,支持以下两种操作:

  1. 画线:给出两个端点的坐标,画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符 - 来画,竖直线段用字符 | 来画。如果一条水平线段和一条竖直线段在某个位置相交,则相交位置用字符 + 代替。

  2. 填充:给出填充的起始位置坐标和需要填充的字符,从起始位置开始,用该字符填充相邻位置,直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 个方向,如下图所示,字符 @ 只和 4 个字符 * 相邻。

    .*.
    *@*
    .*.

输入格式:

第 1 行有三个整数 m, nqmn 分别表示画布的宽度和高度,以字符为单位。q 表示画图操作的个数。

第 2 行至第 q+1 行,每行是以下两种形式之一:

  • 0 x1 y1 x2 y2:表示画线段的操作,(x1,y1)(x2,y2) 分别是线段的两端,满足要么 x1=x2y1≠y2,要么 y1=y2x1≠x2
  • 1 x y c:表示填充操作,(x,y) 是起始位置,保证不会落在任何已有的线段上;c 为填充字符,是大小写字母。

画布的左下角是坐标为 (0,0) 的位置,向右为 x 坐标增大的方向,向上为 y 坐标增大的方向。

q 个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .(小数点)。

输出格式:

输出有 n 行,每行 m 个字符,表示依次执行这 q 个操作后得到的画图结果。

数据范围:

  • 2 ≤ m, n ≤ 100
  • 0 ≤ q ≤ 100
  • 0 ≤ x < m(x 表示输入数据中所有位置的 x 坐标)
  • 0 ≤ y < n(y 表示输入数据中所有位置的 y 坐标)

输入样例1:

4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A

输出样例1:

AAAA
A--A

输入样例2:

16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C

输出样例2:

................
...+--------+...
...|CCCCCCCC|...
...|CC+-----+...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC+-----+...
...|CCCCCCCC|...
...+--------+...
................

题目分析

BFS 模拟

代码实现

#include <iostream>
#include <queue>
#include <cstring>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 110;

int n, m, q, op, x1, x2, y1, y2, x, y;
char g[N][N], ch;
PII dir[4] = {{-1,0},{1,0},{0,1},{0,-1}};
bool check(int i, int j) {
    char& ch = g[i][j];
    return ch == '+' || ch == '-' || ch == '|';
}
void bfs() {
    bool st[N][N];
    memset(st, 0, sizeof st);
    queue <PII> que;
    que.push({x,y});
    st[x][y] = 1;
    g[x][y] = ch;
    while(que.size()) {
        PII t = que.front(); que.pop();
        for(int k = 0; k < 4; ++k) {
            int I = t.x + dir[k].x, J = t.y + dir[k].y;
            if(I >= 0 && I < n && J >= 0 && J < m && !check(I,J) && !st[I][J]) {
                st[I][J] = 1;
                g[I][J] = ch;
                que.push({I,J});
            }
        }
    }
}
void drawline() {
    if(x1 == x2) {
        int t = max(y1, y2);
        y1 = min(y1, y2);
        y2 = t;
        for(int i = y1; i <= y2; ++i) {
            char& ch = g[x1][i];
            if(ch == '-') ch = '+';
            else ch = '|';
        }
    }
    if(y1 == y2) {
        int t = max(x1, x2);
        x1 = min(x1, x2);
        x2 = t;
        for(int i = x1; i <= x2; ++i) {
            char& ch = g[i][y1];
            if(ch == '|') ch = '+';
            else ch = '-';
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            g[i][j] = '.';
    while(q--) {
        cin >> op;
        if(op) {
            cin >> x >> y >> ch;
            bfs();
        }
        else {
            cin >> x1 >> y1 >> x2 >> y2;
            drawline();
        }
    }
    for(int i = m - 1; i >= 0; --i) {
        for(int j = 0; j < n; ++j)
            cout << g[j][i];
        cout << '\n';
    }
} 

送货 (100)

为了增加公司收入,F公司新开设了物流业务。

由于 F 公司在业界的良好口碑,物流业务一开通即受到了消费者的欢迎,物流业务马上遍及了城市的每条街道。

然而,F 公司现在只安排了小明一个人负责所有街道的服务。

任务虽然繁重,但是小明有足够的信心,他拿到了城市的地图,准备研究最好的方案。

城市中有 n 个交叉路口,m 条街道连接在这些交叉路口之间,每条街道的首尾都正好连接着一个交叉路口。

除开街道的首尾端点,街道不会在其他位置与其他街道相交。

每个交叉路口都至少连接着一条街道,有的交叉路口可能只连接着一条或两条街道。

小明希望设计一个方案,从编号为 1 的交叉路口出发,每次必须沿街道去往街道另一端的路口,再从新的路口出发去往下一个路口,直到所有的街道都经过了正好一次。

输入格式

输入的第一行包含两个整数 n,m ,表示交叉路口的数量和街道的数量,交叉路口从 1 到 n 标号。

接下来 m 行,每行两个整数 a,b(a≠b) ,表示和标号为 a 的交叉路口和标号为 b 的交叉路口之间有一条街道,街道是双向的,小明可以从任意一端走向另一端。

两个路口之间最多有一条街道。

输出格式

如果小明可以经过每条街道正好一次,则输出一行包含 m+1 个整数 p1,p2,p3,…,pm+1 ,表示小明经过的路口的顺序,相邻两个整数之间用一个空格分隔。

如果有多种方案满足条件,则输出字典序最小的一种方案,即首先保证 p1 最小,p1 最小的前提下再保证 p2 最小,依此类推。

如果不存在方案使得小明经过每条街道正好一次,则输出一个整数 −1。

数据范围

前 3 前 5 所有评测用例满足:1≤n≤10000,n−1≤m≤100000 。

输入样例1:

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

输出样例1:

1 2 4 1 3 4

输入样例2:

4 6
1 2
1 3
1 4
2 4
3 4
2 3

输出样例2:

-1

题目分析

欧拉路径 DFS

代码实现

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

int n, m, h[N], e[M], ne[M], idx, ans[M], cnt, din[N], dout[N];
bool used[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int p) {
    vector <PII> edges;
    for(int i = h[p]; ~i; i = ne[i])
        if(!used[i]) edges.push_back({e[i],i});
    sort(edges.begin(), edges.end());
    for(PII& edge : edges) {
        if(used[edge.y]) continue;
        used[edge.y] = used[edge.y ^ 1] = 1;
        dfs(edge.x);
    }
    ans[++cnt] = p;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
        ++din[a], ++din[b];
        ++dout[a], ++dout[b];
    }
    int ct = 0;
    for(int i = 1; i <= n; ++i)
        if(din[i] & 1) ++ct;
    if(ct && ct != 2 || (ct == 2 && !(din[1] & 1))) {
        cout << "-1";
        return 0;
    }
    dfs(1);
    if(cnt - 1 != m) cout << "-1";
    else for(int i = cnt; i ; --i) cout << ans[i] << ' ';
    return 0;
} 

矩阵 (0)

创造一个世界只需要定义一个初状态和状态转移规则。

宏观世界的物体运动规律始终跟物体当前的状态有关,也就是说只要知道物体足够多的状态信息,例如位置、速度等,我们就能知道物体之后任意时刻的状态。

现在小 M 创造了一个简化的世界。

这个世界中,时间是离散的,物理规律是线性的:世界的初始状态可以用一个 m 维向量 b(0) 表示,状态的转移方式用 m×m 的矩阵 A 表示。

若已知这个世界当前的状态是 b,那么下一时刻就等于 b 左乘状态转移矩阵 A,即 Ab。

这个世界中,物体的状态也是离散的,也就是说可以用整数表示。

再进一步,整数都可以用二进制编码拆分为有限位 0 和 1。

因此,这里的矩阵 A 和向量 b 的每个元素都是 0 或 1,矩阵乘法中的加法运算视为异或运算(xor),乘法运算视为与运算(and)。

具体地,设矩阵 A 第 i 行第 j 列的元素为 ai,j,向量 b 的第 i 个元素为 bi。

那么乘法 Ab 所得的第 k 个元素为

(ak,1 and b1) xor (ak,2 and b2) xor ⋯ xor (ak,m and bm)
矩阵和矩阵的乘法也有类似的表达。

小 M 发现,这样的矩阵运算也有乘法结合律,例如有 A(Ab)=(AA)b=A2b。

为了保证自己创造的世界维度不轻易下降,小 M 保证了矩阵 A 可逆,也就是说存在一个矩阵 A−1,使得对任意向量 d,都有 A−1Ad=d。

小 M 想了解自己创造的世界是否合理,他希望知道这个世界在不同时刻的状态。

具体地,小 M 有 n 组询问,每组询问会给出一个非负整数 k,小 M 希望你帮他求出 Akb。

**输入格式**

输入第一行包含一个整数 m,表示矩阵和向量的规模。

接下来 m 行,每行包含一个长度为 m 的 01 串,表示矩阵 A。

接下来一行,包含一个长度为 m 的 01 串,表示初始向量 b(0)。(b(0) 是列向量,这里表示它的转置)

注意:01 串两个相邻的数字之间均没有空格。

接下来一行,包含一个正整数 n,表示询问的个数。

最后 n 行,每行包含一个非负整数 k,表示询问 Akb(0)。

注意:k 可能为 0,此时是求 A^0 b(0) = b(0)。

**输出格式**

输出 n 行,每行包含一个 01 串,表示对应询问中 Akb(0) 的结果。

注意:01 串两个相邻的数字之间不要输出空格。

**数据范围**

本题使用 10 个评测用例来测试你的程序。

对于评测用例 1,m=10,n=100,k≤103。

对于评测用例 2,m=10,n=100,k≤104。

对于评测用例 3,m=30,n=100,k≤105。

对于评测用例 4,m=180,n=100,k≤105。

对于评测用例 5,m=10,n=100,k≤109。

对于评测用例 6,m=30,n=100,k≤109。

对于评测用例 7,m=180,n=100,k≤109。

对于评测用例 8,m=600,n=100,k≤109。

对于评测用例 9,m=800,n=100,k≤109。

对于评测用例 10,m=1000,n=100,k≤109。

**输入样例:**

```plaintext
3
110
011
111
101
10
0
2
3
14
1
1325
6
124124
151
12312

输出样例:

101
010
111
101
110
010
100
101
001
100

1 条评论

Frances Meeks · 2023年12月29日 上午2:06

I have been surfing online greater than three hours today, but I by no means discovered any interesting article like yours.
It’s lovely value enough for me. In my opinion, if all site owners and bloggers
made just right content material as you probably did, the web will likely be
a lot more useful than ever before.

发表回复

Avatar placeholder

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

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

站点状态:Status