P9831 [ICPC 2020 Shanghai R] Gitignore

题目描述

你的 git 项目（你不需要熟悉 git 来解决这个问题）中有一些文件应该被忽略同步。你需要计算 .gitignore 文件中所需的最小行数。

形式上，你的项目是一个文件夹。一个文件夹可以包含文件和子文件夹。没有空文件夹（即没有任何文件或子文件夹的文件夹）。最初，git 软件会同步项目中的所有文件。然而，你可以在设置中指定一些文件和文件夹（即 .gitignore）来排除它们的同步。在 .gitignore 中的每一行，你可以指定一个文件或一个文件夹中的所有文件。你不能忽略整个项目文件夹（即 .gitignore 中的空行）。

你将得到项目中所有文件的路径，以及它们是否应该被忽略。你的任务是计算 .gitignore 的最小行数。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量。对于每个测试用例，首先给出两个非负整数 $n$ 和 $m$。接下来是 $n$ 行非空的文件路径，这些文件路径应该被忽略，接着是 $m$ 行非空的文件路径，这些文件路径不应该被忽略。

路径是仅包含小写英文字母和斜杠（/）的字符串。斜杠用于分隔文件夹、子文件夹和文件名。例如，a/b/c/d 表示项目文件夹中的文件夹 a，文件夹 a 中的文件夹 b，b 中的文件夹 c，以及 c 中的文件 d。所有路径都是有效的，具体来说：

• 路径非空且总是表示一个文件（即路径不以斜杠结尾）。
• 路径不以斜杠开头。
• 文件夹名和文件名非空（即没有连续的斜杠）。
• 文件路径总是唯一的（即一个测试用例中的所有路径都是不同的）。
• 在一个文件夹中，没有子文件夹和文件共享相同的名称。例如，不会在一个测试用例中出现两个文件 a/b/a 和 a/b/a/d。然而，文件 a/b/a 和 a/b/b 是允许的。

$1\le n+m\le 100$ 且整个输入中文件路径的字符总数不超过 $1,000$（即整个输入文件中文件路径字符串的长度之和不超过 $1,000$）。

输出格式

$T$ 行非负整数，表示每个测试用例的 .gitignore 的最小行数。

输入输出样例 #1

输入 #1

2
3 0
data/train
data/test
model
3 1
data/train
data/test
model
data/sample

输出 #1

2
3

说明/提示

在第一个示例测试用例中，.gitignore 文件包含 2 行：一个文件夹行 data/ 和一个文件名 model。

在第二个示例测试用例中，.gitignore 文件包含 3 行文件：data/train、data/test 和 model。

题面翻译由 ChatGPT-4o 提供。

C++实现

#include <bits/stdc++.h>
using namespace std;
int T;
int n,m;
const int maxn = 105;
string s[maxn];
map<string,int> mp,vis;
int main(){
    cin>>T;
    while(T --> 0){
        mp.clear();vis.clear();
        cin>>n>>m;
        for(int i(1);i <= n;++i){
            cin>>s[i];//can be ignored
        }
        for(int i(1);i <= m;++i){
            string str,tmp = "";
            cin>>str; register int len = str.length();
            for(int j(0);j < len;++j){
                if(str[j] == '/'){
                    mp[tmp] = 1;
                }
                tmp += str[j];
            }
        }
        int ans = 0;
        for(int i(1);i <= n;++i){
            bool f = 1; string tmp = "";
            register int len = s[i].length();
            for(int j(0);j < len;++j){
                if(s[i][j] == '/'){
                    if(mp[tmp]) f = 1;
                    else{
                        if(vis[tmp]) f = 0;
                        vis[tmp] = 1;
                        break;
                    }
                }
                tmp += s[i][j];
            }
            ans += int(f);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容