Acwing4261.孤独的照片

题目

原题链接

Farmer John 最近购入了 N 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。

然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。

输入格式
输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第 i 头奶牛是荷斯坦牛，该字符为 H。

输出格式
输出 Farmer John 会扔掉的孤独的照片数量。

数据范围
3 ≤ N ≤ 5×10^5

输入样例：

1
2
5
GHGHG

输出样例：

1
3

样例解释
这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。

所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。

分析

从题目数据范围我们可以发现，暴力枚举子串肯定是行不通的，时间复杂度应该是O（n）或者O（nlogn）。题目的关键是如何找到孤独的牛，从题意出发，通过维护两种牛的数量来判断的话是不太可行的。为此我们不妨思考下，孤独的牛有何特点？当它的左侧或右侧出现连续与它不同的牛时，它便是一头孤独的牛。所以我们只要找到某头牛左右两侧连续不同牛的数量，再利用乘法原理就可以计算出答案了。
为此，我们不难写出以下代码，这里为了防止溢出，开了long long。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n;
char oxs[N];
int main()
{
    cin >> n;
    cin >> oxs;
    LL res = 0;
    for(int i = 0;i < n;i++)
    {
        int l = i - 1;
        LL lcnt = 0;
        while(l >= 0 && oxs[l] != oxs[i])
        {
            lcnt++;
            l--;
        }
        int r = i + 1;
        LL rcnt = 0;
        while(r < n && oxs[r] != oxs[i])
        {
            rcnt++;
            r++;
        }
        res += lcnt * rcnt + max(0LL,lcnt - 1) + max(0LL,rcnt - 1);
    }
    cout << res << endl;
    return 0;
}

Acwing1240.完全二叉树的权值

题目

原题链接

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

</div>
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

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

注：根的深度是 1。

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

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

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

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

输入样例：

1
2
7
1 6 5 4 3 2 1

输出样例：

1
2

分析

模拟完全二叉树的每层并求和即可，只是这个过程恰好用到了双指针而已。需要注意的是，这里求和还可以用前缀和优化，常数上会小一些。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int tr[N];
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> tr[i];
    LL maxv = INT_MIN;
    int depth = 0;
    //遍历每一层
    for(int d = 1,i = 1;i <= n;d++,i *= 2)
    {
        LL val = 0;
        //每一层累加
        for(int j = i;j < i + (1 << d - 1) && j <= n;j++) val += tr[j];
        if(val > maxv)
        {
            maxv = val;
            depth = d;
        }
    }
    cout << depth << endl;
    return 0;
}

Acwing1096.地牢大师

题目

原题链接

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

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

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

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

请问，你有可能逃脱吗？

如果可以，需要多长时间？

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

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

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

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

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

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

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

输出格式
每组数据输出一个结果，每个结果占一行。

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

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

数据范围
1 ≤ L,R,C ≤ 100

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
3 4 5
S....
.###.
.##..
###.#

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

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

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

输出样例：

1
2
Escaped in 11 minute(s).
Trapped!

分析

本质上就是AcWing 1101. 献给阿尔吉侬的花束这题的三维扩展,
需要注意的就是坐标偏移量多了上下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
struct PIII
{
    int a,b,c;
};
int L,R,C;
char g[N][N][N];
int dist[N][N][N];
int dx[6] = {-1,1,0,0,0,0},dy[6] = {0,0,1,-1,0,0},dz[6] = {0,0,0,0,1,-1};
int bfs(PIII start,PIII end)
{
    queue<PIII> q;
    q.push(start);
    memset(dist,-1,sizeof dist);
    dist[start.a][start.b][start.c] = 0;
    while(q.size())
    {
        PIII t = q.front();q.pop();
        if(t.a == end.a && t.b == end.b && t.c == end.c) return dist[t.a][t.b][t.c];
        for(int i = 0;i < 6;i++)
        {
            int x = t.a + dx[i],y = t.b + dy[i],z = t.c + dz[i];
            //越界
            if(x < 0 || x >= L || y < 0 || y >= R || z < 0 || z >= C) continue;
            //障碍物
            if(g[x][y][z] == '#') continue;
            //计算过
            if(dist[x][y][z] != -1) continue;
            dist[x][y][z] = dist[t.a][t.b][t.c] + 1;
            q.push({x,y,z});
        }
    }
    return -1;
}
int main()
{
    while(cin >> L >> R >> C,L || R || C)
    {
        PIII start,end;
        for(int i = 0;i < L;i++)
        {
            for(int j = 0;j < R;j++)
            {
                for(int k = 0;k < C;k++)
                {
                    cin >> g[i][j][k];
                    if(g[i][j][k] == 'S') start = {i,j,k};
                    else if(g[i][j][k] == 'E') end = {i,j,k};
                }
            }
        }
        int res = bfs(start,end);
        if(res == -1) cout << "Trapped!" << endl;
        else printf("Escaped in %d minute(s).\n",res);
    }
    return 0;
}

Acwing1233. 全球变暖

题目

原题链接

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

1
2
3
4
5
6
7
.......
.##....
.##....
....##.
..####.
...###.
.......

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

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

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

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

1
2
3
4
5
6
7
.......
.......
.......
.......
....#..
.......
.......

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

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

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

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

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

数据范围
1 ≤ N ≤ 1000

输入样例1：

1
2
3
4
5
6
7
8
7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出样例1：

1
1

输入样例2：

1
2
3
4
5
6
7
8
9
10
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........

输出样例2：

1
1

分析

这题是Flood Fill的经典应用，
在找岛屿的过程中，记录下每个岛屿的总面积和临海面积，即可算出答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010;
int n;
char g[N][N];
bool st[N][N];
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
void bfs(int sx,int sy,int & total,int & bound)
{
    queue<PII> q;
    q.push({sx,sy});
    st[sx][sy] = true;
    while(q.size())
    {
        PII t = q.front();q.pop();
        total++;
        bool is_sea = false;
        for(int i = 0;i < 4;i++)
        {
            int x = t.x + dx[i],y = t.y + dy[i];
            //越界
            if(x < 0 || x >= n || y < 0 || y >= n) continue;
            //是海
            if(g[x][y] == '.')
            {
                is_sea = true;
                continue;
            }
            //访问过
            if(st[x][y]) continue;
            st[x][y] = true;
            q.push({x,y});
        }
        if(is_sea) bound++;
    }
}
int main()
{
    int res = 0;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> g[i];
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            //遍历每个连通块，统计岛的面积和靠近海的块数
            if(!st[i][j] && g[i][j] == '#')
            {
                int total = 0,bound = 0;
                bfs(i,j,total,bound);
                if(total == bound) res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

Acwing1207. 大臣的旅费

题目

原题链接

很久以前，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

输入样例：

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

输出样例：
1
135

分析

这题目本质上就是求一个树的直径，可以当作求树的直径的一种简单的模板背过，因为还有其它更优的方式。这个过程是：
先任取树上一点，找到距离该点的最远距离，假定为点u，再重复一次这个过程，找到距离点u的最远距离即为答案。
这里存图用的是数组模拟单链表的方式，这里单独把模板抽取出来，仅供参考。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,M = 2e5 + 10;
int n;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u,int p,int d)
{
    dist[u] = d;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j != p)
        {
            dfs(j,u,d + w[i]);
        }
    }
}
int main()
{
    //初始化h
    memset(h,-1,sizeof h);
    cin >> n;
    //求树的直径
    //任取一点，找到距它最远距离的点u
    for(int i = 0;i < n;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1,0);
    //再执行一次上面的操作，找到距离u最远的点，即为树的直径
    int maxv = INT_MIN,u = 0;
    for(int i = 1;i <= n;i++)
    {
        if(dist[i] > maxv)
        {
            maxv = dist[i];
            u = i;
        }
    }
    dfs(u,-1,0);
    maxv = INT_MIN;
    for(int i = 1;i <= n;i++) maxv = max(maxv,dist[i]);
    cout << 10 * maxv + (maxv + 1LL) * maxv / 2 << endl;

    return 0;
}

存图模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
...
const int N = 题目给的点数,M = 题目给的边数 / (单向边和点数相同，双向边为点数2倍);
int h[N],e[M],ne[M],w[M],idx;
//加边函数
void add(int a,int b,int c)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    ... //存图的其他信息，这里以边权举例
    w[idx] = c;
    ...
    h[a] = idx++;
}
int main()
{
    //初始化h
    memset(h,-1,sizeof h);

    //图的遍历(例如遍历点u的临边)
    for(int i = h[u];i != -1;i = ne[i])
    {
        //取出相邻点j
        int j = e[i];
        //取出其他信息
        int weight = w[i];
        ... //其他操作
    }
    ...
}

更多请查看: 我的Acwing主页