算法 C7 部分题解

形式化的来说，大写字母是指 ASCII 码在 $[65, 90]$ 之间的字符（A-Z）；小写字母是指 ASCII 码在 $[97, 122]$ 之间的字符（a-z）；空格是 ASCII 码为 $32$ 的字符（）；连字符是 ASCII 码为 $45$ 的字符（-）；单词是指由空格分割的字符串。

输出描述

输出一个正整数，表示有多少个植物是仙人掌。

输入样例

Cactie
Symmetree
Violet
Dogtus
StareChew of LeadBear Tree
Picactusso
Call-A-Lily
Cactus Cactus

输出样例

题解

这道题考验的是字符串读取以及字符串处理。

首先可以使用cin>>s读入字符串，cin的值可以直接判断是否读到输入末尾，循环条件就可以写while(cin >> s){}。cin会在遇到空格、换行符时停止，所以我们每次读入的是一个单词。可以通过读取char c = getchar()读取后面的空白字符是什么，通过是否为换行符判断是否读到末尾。

因为一个名字里面若不同的单词都满足条件，也只能计算一次，这里使用了一个flag记录这个名字前面是否已经满足条件了，如果为true则放弃这次读的单词。不过要严格处理读到换行符的逻辑。

之后是匹配三种可能的“仙人掌”。因为我用的string存的单词，前两种情况可以使用substr切分前三个字符和最后三个字符并用==与要求进行比较。第三种情况直接使用自带的find函数查找即可。判断这三种情况的时候需要事先判断s长度是否到了3或者6。

代码

#include <bits/stdc++.h>
using namespace std;

string s;

int main(){
    int flag = 0;
    int sum = 0;
    while(cin >> s){
        char c = getchar();
        if(flag == 1){
            if(c=='\n'){flag = 0; continue;}
            else continue;
        }
        int l = s.length();
        for(int i = 0; i < l ; i++)if(isupper(s[i])) s[i] = tolower(s[i]);
        if(s.length() < 3) continue;
        if(s.substr(0,3) == "cac"){
            sum++;
            flag = 1;
            if(c=='\n')flag = 0; continue;
        }
        if(s.substr(s.length() - 3) == "tus"){
            sum++;
            flag = 1;
            if(c=='\n')flag = 0; continue;
        }
        if(s.length() < 6) continue;
        if(s.find("cactus") != string::npos){
            sum++;
            flag = 1;
            if(c=='\n')flag = 0; continue;
        }
    }
    cout << sum;
    return 0;
}

E 冰之勇者

题目

题目背景

在幻想乡的大陆上，有一个传说，集齐 $9$ 种冰块的勇者可以召唤神龙

题目描述

幻想乡的大陆由 $n$ 座城市和 $m$ 条城市间的双向道路组成，并保证所有城市连通。第 $i$ 座城市都有一块种类为 $w_i$ 的冰块（$1 \le w_i \le 9$）。

冰之勇者琪露诺会从一个城市出发，然后沿道路去往不同的城市，每到一个城市，她都会收集城市中的冰块（包含初始城市的冰块）。现在她想知道她从哪些城市出发可以集齐 $9$ 种冰块（即收集到种类 $1$ 到 $9$ 的所有冰块）。

你只需要告诉她有多少个这样的城市即可。

输入格式

第一行两个整数 $n, m$ ($1 \le n, m \le 2 \times 10^5$)。第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 座城市的冰块种类 $w_i$。接下来 $m$ 行，每行两个整数 $u, v$，表示城市 $u$ 和 $v$ 之间有一条道路。

输出格式

输出一个整数，表示满足条件的起始城市数量。

样例输入

样例输出

题解

这道题可以使用BFS进行扫描。用数组vis记录每个点是否被扫描到过。

循环每一个点：对每个没访问的点进行BFS，每一次BFS用哈希数组记录1-9出没出现过，每次BFS结束后检验，如果1-9都出现过则加到总和里面。

很容易证明，一次BFS扫描到的点属于一个连通分量，再去数这个连通分量里面是否都有1-9即可。

总时间复杂度O(m+n)。

代码

#include <iostream>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
const int N = 200005;
const int M = 400005;
const int INF  = 0x3f3f3f3f;
struct Edge{
    int to, w, next
;}e[M];

int cnt_E = 0;
int head[N];
void init(int n){
    memset(head, -1, sizeof(head));
}

void addEdge(int x, int y, int w){
    e[cnt_E].to = y;
    e[cnt_E].w = w;
    e[cnt_E].next = head[x];
    head[x] = cnt_E++;
}

int w[N]; // 点类型
int n,m;

int qq[10]; // 哈希
int vis[N]; 
int ans = 0;

void bfs(int s){
    int all = 0;
    queue<int> q;
    vis[s] = 0;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        qq[w[u]]++; vis[u] = 1; all++;
        q.pop();
        for(int i = head[u]; i!=-1; i=e[i].next){
            int v= e[i].to;
            if(vis[v] == 0){
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    for(int i = 1; i<=9;i++){
        if(qq[i] == 0) return ;
    }
    ans += all;
}

int main(){
    scanf("%d%d",&n, &m);
    for(int i = 1; i<= n;i++){
        scanf("%d", &w[i]);
    }
    init(n);
    for(int i = 1; i<= m;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        addEdge(a,b,1);
        addEdge(b,a,1);
    }
    for(int i = 1; i<= n;i++){
        if(vis[i]) continue;
        memset(qq, 0, sizeof(qq));
        bfs(i);
    }
    printf("%d",ans);
    return 0;
}

G 墨鱼和最短路

题目

题目描述

有一只墨鱼想请你教 ta 无向图的最短路算法!

具体来说，给定一个 $n$ 个点 $m$ 条边的无向图和一个正整数 $K$，这只墨鱼会进行 $q$ 次询问，对于每次询问它想知道对于两个点 $s$ 和 $t$，在满足经过的中间节点（即路径上所有除了 $s$ 和 $t$ 的其它节点）的编号均不大于 $K$ 的条件下的最短路径长度，或判断不存在这样的路径。

输入格式

第一行一个正整数 $t$ ($1 \le t \le 10$)，表示数据组数。

对于每组数据，第一行三个正整数 $n, m, K$ ($1 \le n \le 100, \ 1 \le m \le 10^5, \ 1 \le K \le n$)，含义同题目描述。

接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, \ 1 \le w_i \le 10^5$)，表示第 $i$ 条边 $(u_i, v_i)$ 的权值为 $w_i$。

接下来一行一个正整数 $q$ ($1 \le q \le 5 \times 10^4$)，含义同题目描述。

接下来 $q$ 行，每行两个正整数 $x_i, y_i$ ($1 \le x_i, y_i \le n$)，表示第 $i$ 次询问的两个参数。

保证给定的图中没有自环，但可能有重边。

输出格式

对于每组数据，输出 $q$ 行，其中第 $i$ 行：

如果第 $i$ 次询问的两点间存在满足条件的路径，则输出一个非负整数表示最短路径长度。
否则，输出 QAQ。

输入样例

输出样例

QAQ
1
4
4

题解

这道题纯纯Floyd板子题。要求的“编号均不大于 $K$ ”即Floyd的DP矩阵遍历的第K次，所以把遍历次数改成k就可以了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 109;
const long long INF = 0x3f3f3f3f3f3f3f3f;

long long d[N][N];
int t, n, m, k, q;

void init(int n){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i==j){
                d[i][j] = 0;
            }else{
                d[i][j] = INF;
            }
        }
    }
}

void floyd(int n, int kk){
    for(int k = 1; k<=kk; k++){
        for(int i = 1; i <= n;i++){
            for(int j = 1; j <= n; j++){
                if(d[i][k] == INF || d[k][j] == INF) continue;
                if(d[i][k] + d[k][j] < d[i][j]){
                    d[i][j]  = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        init(n);
        for(int i =1;i<=m;i++){
            int ui, vi, wi;
            cin >> ui >> vi >> wi;
            if(wi < d[ui][vi]){
                d[ui][vi] = wi;
            }
            if(wi < d[vi][ui]){
                d[vi][ui] = wi;
            }
        }
        floyd(n, k);
        cin >> q;
        while(q--){
            int x, y;
            cin >> x >> y;
            if(d[x][y] != INF) cout << d[x][y] << '\n';
            else cout << "QAQ\n";
        }
    }
    return 0;
}

不想学习…

C 前缀数组

题目

题解

代码

E 冰之勇者

题目

题解

代码

G 墨鱼和最短路

题目

题解

代码

添加新评论