[数据结构与算法]寒假训练1（2020ICPC上海站）

ZZULI 寒假训练

题目

G

（签到 思维题）
题目大意: 求斐波那契数列中 i : 1~n , j : i+1~n 中 fi*fj 为偶数的个数
思路：两数相乘为偶数 则一个数为偶数即可 斐波那契数列中3的倍数为偶数 则只需要求n中为3的倍数的个数 计算匹配数减去重复匹配的数量即可
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int main()
{
	ll n;cin>>n;
	ll k=n/3;
	ll ans = k*(n-1) - ((k-1)*k/2);
	cout<<ans<<endl;
}

M

题目大意：给出n个文件的路径，你需要删除的，再给出m个文件的路径，你不能删除的，如果一个文件夹中的所有文件都可以删除那么就一次性删除即可，问最少删除次数
思路：map 存一下字符串 ，先处理文件标记首先为0，如果不可以删除标记为1，对于已标记为0的字符串，将其标记为2，如果后面再次出现那么整个路径都需要删除 则ans–
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n, m;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int ans = n;
		map<string, int> mp;
		string s, ss[105];
		for (int i = 1; i <= n + m; i++)
		{
			cin >> ss[i];
			s.clear();
			for (int j = 0; j < ss[i].size(); j++)
			{
				if (ss[i][j] == '/')
				{
					if (i > n) mp[s] = 1; //前n个文件需要删除 后面不能删除
					else mp[s] = 0;//所有m路径记为1 其他均为0
				}
				else s += ss[i][j];
			}
		}
		for (int i = 1; i <= n; i++)
		{
			s.clear();
			for (int j = 0; j < ss[i].size(); j++)
			{
				if (ss[i][j] == '/')
				{
					if (mp[s] == 0) mp[s] = 2;//说明可以删去 先标记为2 后面出现再减
					else if (mp[s] == 1) continue;//不能删去
					else //标记为2 需要删去
					{
						ans--;
						break;
					}
				}
				else s += ss[i][j];
			}
		}
		cout << ans << endl;
	}
}