A - Thermometer
高桥测量了自己的体温，发现体温为 X°C。

体温分为以下几种：

高于或等于 38.0°C："高烧"。
高于或等于 37.5°C 且低于 38.0°C："发烧"。
低于 37.5°C："正常"。

根据输出部分以整数形式给出答案。

思路：模拟即可

// Code Start Here	
	double x;
	cin >> x;
	if(x >= 38){
		cout <<"1"<<endl;
	}
	else if(x < 38 && x >= 37.5){
		cout <<"2" <<endl;
	}
	else{
		cout <<"3" <<endl;
	}
	return 0;	

B - Ticket Gate Log

题意：

高桥汇总了检票口的使用记录。但是，他不小心删除了一些进出站记录。他正试图恢复被删除的记录。

给你一个由 i 和 o 组成的字符串 S 。我们希望在 S 中的任意位置插入 0 个或更多字符，以使得到的字符串满足以下条件：

- 它的长度是偶数，每个奇数（第 1、第 3、……）字符都是 i ，而每个偶数（第 2、第 4、……）字符都是 o 。

求需要插入的最少字符数。在此问题的限制条件下，可以证明通过插入适当数量的字符， S 可以满足条件。
 

思路：

注意到为了满足题意要求，第一个必须是i，最后一个必须是o，连续的i之间需要插入o，连续的o之间需要插入i，模拟即可

// Code Start Here	
	string s;
	cin >> s;
	stack<char> st;
	int ans = 0;
	if(s[0] != 'i')ans++;
	if(s[(int)(s.size() - 1)]!='o')ans++;
	for(int i = 0;i<(int)(s.size());i++){
		st.push(s[i]);
	}
	while(!st.empty()){
		char op = st.top();
		st.pop();
		int cnt = 1;
		while(!st.empty() && st.top() == op){
			st.pop();
			cnt++;
		}
		ans += cnt-1;
	}
	cout << ans << endl;
	return 0;	

C - Variety Split Easy

题意：

本问题是问题 F 的简化版。

给你一个长度为 N 的整数序列：A = (A1, A2, …, AN)。

当把序列 A 在任意位置分割成两个非空（连续）子数组时，求这两个子数组中不同整数计数之和的最大值。

更具体地说，求满足 1 ≤ i ≤ N-1 的整数 i，使得子数组 (A1, A2, …, Ai) 中不同整数的计数与子数组 (A(i+1), A(i+2), …, AN) 中不同整数的计数之和达到最大值。

思路：模拟，当右边没有数的时候，减

	// Code Start Here	
	int n;
	cin >> n;
	vector<int> a(n+1);
	vector<int> vis(n+1, 0);
	set<int> l, r;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		vis[a[i]]++;
	}
	vis[a[1]]--;
	for(int i = 2; i <= n; i++){
		r.insert(a[i]);
	}
	l.insert(a[1]);
	int ans = int(l.size()) + int(r.size()); 
	for(int i = 2; i <= n-1; i++){
		vis[a[i]]--;
		if(vis[a[i]] == 0){
			r.erase(a[i]);
		}
		l.insert(a[i]);
		ans = max(ans, int(l.size()) + int(r.size()));
	}
	cout << ans << endl;
	return 0;	

D - Cubes

题意：

给你一个正整数 N。判断是否存在一对正整数 (x, y)，使得 x³ - y³ = N。  
如果存在这样的 (x, y)，请打印出其中一对。  

思路：我们首先注意到y + 1<= x，从而有

3y^2 + 3y + 1 ≤ x^3 - y^3 = N ，可以在sqrt N内破解，但是时间复杂度1e18还是会TLE

不妨设 x - y = d 。对于 (x, y) 与 x^3 - y^3 = N，我们有 x^3 - y^3 = (x - y) · (x^2 + xy + y^2) = d · (x^2 + xy + y^2) 。

再根据放缩，有 x^2 + xy + y^2 ≥ x^2 - 2xy + y^2 = d^2

所以有 d^3 ≤ d · (x^2 + xy + y^2) = x^3 - y^3 = N 。

去检查d即可

// Code Start Here	
	int n;
	cin >> n;
	for(int d = 1;d* d *d <= n ; d++){
		if((n - d*d*d) % (3 *d) != 0)continue;
		int m = (n - d *d *d)/(3 * d);
		int dd = d * d + 4 * m;
		int t = (int)(floor(sqrt((double)(dd))));
		if(t *t !=dd)continue;
		if((-d + t) % 2 != 0)continue;
		int y = (-d + t)/2;
		if(y <= 0){
			continue;
		}
		int x = y + d;
		cout << x <<" "<< y <<endl;
		return 0;
	}
	cout << -1 << endl;

E - Path Decomposition of a Tree

题意：

问题陈述

给你一棵有 NK 个顶点的树。顶点编号为 1, 2, …, NK，对于每个 i（i = 1, 2, …, NK-1）有一条边双向连接顶点 u_i 和 v_i。

请判断这棵树是否可以分解成长度为 K 的 N 条路径。更确切地说，确定是否存在满足以下条件的 N x K 矩阵 P：

- P(1,1), P(1,2), …, P(1,K), P(2,1), …, P(N,K) 是 1, 2, …, NK 的排列。
- 对于每个 i = 1, 2, …, N 和 j = 1, 2, …, K-1，都有一条边连接顶点 P(i,j) 和 P(i,j+1)。

思路：题意要求把NK个点分解成N条路径，每条路径包含K个顶点（K-1条边），且所有路径顶点两两不交。

根据树的性质，树只有NK-1条边，所以我们不用求完所有边，只需要求完所有顶点。

我们可以自底而上进行DFS，看该节点向下延伸的未配对的链长，看他向下传递的候选链和从子节点得到的。对于每个节点 v，我们设候选链表示从 v 向下延伸、尚未完成一条长为 K 的路径的部分（计作链中顶点个数）。叶节点没有候选链，我们规定如果 K==1 则返回 0（表示自己构成一条完整路径），否则返回 1（表示以叶节点开始的待延长链，其长度为 1）

对于内部节点 v，我们从各子节点收集非 0 的候选链（值范围均在 1~K–1 内）。注意：若子节点返回 0，表示该子树已经“完成”了一个路径，不需要继续传上候选链。

由于 v 只能属于一条路径，v 最多只能“接”一条候选链继续向上延长；不过如果恰好有两个候选链，并且它们之和正好等于 K–1，则 v 可以用自己将这两个链“对接”，凑成一条完整的路径（这时 v 就被“消耗”，不向上传递候选链）。

若 v 收到的候选链数为 0，则 v 自己启动一条新链，返回值为 1；

若正好收到 1 条候选链 d，则返回 d+1（如果 d+1 恰好等于 K，则返回 0，表示完成了一条路径）；

若收到 2 条候选链且两者之和等于 K–1，即两条可以合成一条，则返回 0；其他情况均视为无法构造合法分解，返回 –1。

// Code Start Here	
	cin >> n >> k;
	for(int i = 1;i<= n *k - 1 ;i++){
		int u , v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto dfs = [&](auto dfs , int v ,int p)->int{
		vector<int> now;
		for (int u : g[v]) {
			if(u == p) continue;
			int d = dfs(dfs,u, v);
			if(d == -1) return -1;
			if(d > 0) { 
				now.push_back(d);
			}
		}
		if(now.empty()){
			if(k == 1)return 0;
			else return 1;
		}
		if(now.size() == 1) {
			int re = now[0] + 1;
			if(re == k)return 0;
			else return re;
		}
		if(now.size() == 2) {
			if(now[0] + now[1] == k - 1) return 0;
			else return -1;
		}
		return -1;
	};
	int res = dfs(dfs , 1 , -1);
	if(res == 0)cout <<"Yes\n";
	else cout <<"No\n";