Gitignore

题意：
给n个需要忽视的目录，m个需要保护的目录，求Gitignore的最小行数(有多少文件路径没被忽视--本应该被忽视的)

思路：

比赛的时候写了个神仙代码
正解应该就是模拟，标记被保护了的路径名父级目录(a/b/c就只标记a、b)，因为输入保证不会同时出现:。接着枚举应该忽略的文件路径，如果某个父级目录或子级目录没有被保护，那么这个父级目录后面的子目录都要被忽视。

Code:

#include <bits/stdc++.h>
using namespace std;
vector<string>v1,v2;
map<string,bool>vis,pro;
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n,m,t,ans;
    string s;
    cin>>t;
    while(t--) {
        cin>>n>>m;
        v1.clear(), v2.clear(), vis.clear(), pro.clear();
        for(int i=1;i<=n;++i) cin>>s,v1.push_back(s);
        for(int i=1;i<=m;++i) cin>>s,v2.push_back(s);
        for(int i=0;i<m;++i) {
            s="";
            for(char &ch : v2[i]) {
                if(ch=='/') pro[s]=true;
                s+=ch;
            }
        }
        ans=n;
        for(int i=0;i<n;++i) {
            s="";
            for(char &ch : v1[i]) {
                if(ch=='/'&&!pro[s]) {
                    if(vis[s]) --ans;
                    else vis[s]=true;
                    break;
                }
                s+=ch;
            }
        }
        cout<<ans<<endl;
    }
}

比赛时候的思路

每个文件名看成一个点，'/'看成是边，那么每个点都加上路径、文件名这两个属性就能唯一确定一个点。(比赛的时候居然忘记加的属性是深度、文件名，太菜了、、

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7;
#define sc(x) scanf("%lld", &(x))
struct node {
    string name,path;
    bool operator<(const node &a)const{
        if(path!=a.path) return path<a.path;
        return name<a.name;
    }
}to[N];
int tot = 0;
map<node, int> head;
int Next[N];
map<node, bool>  cnt,vis;
void deal(string s, bool op) {
    vector<node> div;
    div.push_back(node{"QAQ",""});
    string now = "",path="";
    for (int i = 0, n = s.length(); i < n; ++i) {
        if (s[i] == '/')
            div.push_back(node{now,path}),path=path+"/"+now, now = "";
        else
            now += s[i];
    }
    div.push_back({now,path});
    for (int i = 1, sz = div.size(); i < sz; ++i) {
        vis[div[i]] = op;
        to[++tot] = div[i];
        Next[tot] = head[div[i - 1]];
        head[div[i - 1]] = tot;
    }
}
int ans;
void dfs(node u) {
    for (int i = head[u]; i; i = Next[i]) {
        if (vis[to[i]]) {
            dfs(to[i]);
            vis[to[i]]=false;
            cnt[to[i]]=true;
        }
        else if (!cnt[to[i]]) {
            ans += 1;
            cnt[to[i]] = true;
        }
    }
}
void init() {
    tot = 0;
    head.clear();
    vis.clear();
    cnt.clear();
    ans = 0;
}
signed main() {
    int T;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) {
        string s;
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            cin >> s;
            deal(s, false);
        }
        for (int i = 0; i < m; ++i) {
            cin >> s;
            deal(s, true);
        }
        dfs(node{"QAQ",""});
        cout << ans << endl;
        init();
    }
}