2020ICPC上海站M-Gitignore 题解

题目大意

给你n个需要删除的文件和m个不能删除的文件，分别告诉你这些文件的路径，当某个文件夹中没有不能删除的文件时，你可以删除这一整个文件夹，问最少需要删除几次。

解题思路

我们打了南京，铁了，难受啊。。

寒假要好好学了，不然牌都拿不到就退役了。。

当时这场打完之后我们复现了一场，然后这题没写出来。

打这一场的他们说就是一个搜索。

后面看了下别人的代码，这个应该就是一个思维题。

不过这个思路特别妙。

把有不能删的文件夹标记一下，如果遇到了不能删的文件夹就继续往下走。

如果碰到了能删的，就直接删了这个文件夹，并标记一下。

如果碰到了删过的文件夹，就ans–。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

map<string, int> M;
vector<string> v;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		M.clear(); v.clear();
		int n, m; cin >> n >> m;
		string s;
		rep(i, 1, n) {
			cin >> s;
			v.push_back(s);
		}
		rep(i, 1, m) {
			cin >> s;
			int l = s.length();
			string t;
			rep(j, 0, l - 1) {
				t += s[j];
				if (s[j] == '/')	M[t] = 1;
			}
		}
		int ans = n;
		for (auto x : v) {
			int l = x.length();
			string t;
			rep(i, 0, l - 1) {
				t += x[i];
				if (x[i] == '/') {
					if (M[t] != 1) {
						if (M[t] != 2) M[t] = 2;
						else {
							ans--; break;
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}