A - Triple Four

题意：

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

请判断在 A 中是否有相同元素连续出现三次或三次以上的位置。

更正式地说，请判断是否存在一个整数 i 与 1≤i≤N−2 这样的 Ai=Ai+1=Ai+2 。

思路：按照题意模拟即可

// Code Start Here	
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0;i<n;i++)cin >> a[i];
	bool f = false;
	for(int i = 0;i<n-2;i++){
		if(a[i] == a[i+1] && a[i+1] == a[i+2])f = true;
	}
	cout << (f ? "Yes" : "No") << '\n';

B - Card Pile

题意：

有一叠 100 纸牌，每张都标有整数 0 。

处理 Q 个查询。每个查询都属于以下情况之一：

• 输入 1 ：将一张标有整数 x 的卡片放在堆栈顶部。
• 类型 2 ：取出堆栈顶端的卡片，并输出写在该卡片上的整数。在此问题的限制条件下，牌堆中总是至少有一张牌。

思路：一个栈  模拟即可

// Code Start Here	
	stack<int> st;
	for(int i = 0;i<100;i++)st.push(0);
	int q;
	cin >> q;
	while(q--){
		int op;
		cin >> op;
		if(op == 1){
			int x;
			cin >> x;
			st.push(x);
		}
		else{
			cout << st.top() <<endl;
			st.pop();
		}
	}
	return 0;	

C - Buy Balls

题意：

有 N 个黑球和 M 个白球。
每个球都有一个值。第 i 个黑球( 1≤i≤N )的值是 Bi​ ，第 j 个白球( 1≤j≤M )的值是 Wj。

选择 0 个或更多的球，使得所选黑球的数量至少等于所选白球的数量。在所有这样的选择中，求所选球的数值之和的最大值。

思路：为了使贡献值更大，我们将数组从大到小排序以后

我们考虑这几种情况：

1：黑球白球全大于0且黑球少于白球

2：白球少于黑球  或  白球开始变负

3：白球大于黑球  黑球开始变负

后两种情况保证两者相加 > 0即可

// Code Start Here	
	int n , m;
	cin >> n >> m;
	deque<int> b(n);
	deque<int> w(m);
	for(int i = 0;i<n;i++)cin >> b[i];
	for(int i = 0;i<m;i++)cin >> w[i];
	int ans = 0;
	sort(b.begin(),b.end(),greater<int>());
	sort(w.begin(),w.end(),greater<int>());
	while(!b.empty() && !w.empty() && b.front() >= 0 && w.front() >= 0){
		ans += b.front();
		ans += w.front();
		b.pop_front();
		w.pop_front();
	}
	if(b.empty()){
		cout << ans << endl;
		return 0;
	}
	if(w.empty() || w.front() < 0){
		while(!b.empty() && b.front() > 0){
			ans += b.front();
			b.pop_front();
		}
		cout << ans << endl;
		return 0;
	}
	sort(b.begin(),b.end(),greater<int>());
	sort(w.begin(),w.end(),greater<int>());
	while(!b.empty() && !w.empty() && (w.front() + b.front() > 0)){
		ans += (w.front() + b.front());
		w.pop_front();
		b.pop_front();
	}
	cout << ans << endl;

D - Minimum XOR Path

题意：

给你一个简单相连的无向图，图中有 N 个顶点，编号为 1 到 N ；有 M 条边，编号为 1 到 M 。边 i 连接顶点 ui 和 vi ，其标签为 wi​ 。

在从顶点 1 到顶点 N 的所有简单路径(不经过同一顶点多次的路径)中，求路径上边的标签的最小 XOR。

思路：观察到N < 20  无脑dfs即可

// Code Start Here	
	int n , m;
	cin >> n >> m;
	vector<vector<pair<int,int>>> g(n+1);
	vector<bool> vis(n+1,false);
	for(int i = 1;i<=m;i++){
		int u , v , w;
		cin >> u >> v >> w;
		g[u].push_back({v , w});
		g[v].push_back({u , w});
	}
	int ans = LLONG_MAX;
	auto dfs = [&](auto dfs,int u,int val)->void{
		if(u == n){
			ans = min(ans , val);
			return ;
		}
		else{
			for(auto [v , w] : g[u]){
				if(!vis[v]){
					vis[v] = true;
					dfs(dfs , v , val ^ w);
					vis[v] =false;
				}
			}
		}
	};
	vis[1] = true;
	dfs(dfs , 1 , 0);
	cout << ans << endl;

E - Min of Restricted Sum

题意：我们验证是否存在一个“好”序列，满足给定整数N、M及三个长度为M的序列：X、Y、Z。检查是否能构造一个满足对每个i，A[X_i]和A[Y_i]的XOR值等于Z_i的序列。

思路：

将每个约束视作等式Au​⊕Av​=z，注意到如果我们固定某个连通块内一个顶点的值（例如令它的“电势” d=0），那么对任意顶点 v 都有Av=t⊕dv。其中 dv是从根（取值0）出发沿唯一确定的路径（若无矛盾）得到的值，而 t 是该连通块的整体平移（即全体异或相同数值）。在搜索过程中若遇到已访问顶点，检查是否满足 dv=du⊕z，否则无解

由于 XOR 按位独立，我们可以对每一位单独决定 t 的该位。

对于某一位 j（权值 2^j），设连通块中有 cnt1个顶点在该位为 1，其余 cnt0个顶点在该位为 0。

如果令 tj=0，此位贡献为 cnt1⋅2^j；若令 tj=1，则贡献为 cnt0⋅2^j。
因此，我们对每一位选择较小者（若相等则取 0，以避免不必要的加成）最终，对连通块内每个顶点 v 令Av=t⊕dv

// Code Start Here	
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> g(n + 1);
	for(int i = 0; i < m; i++){
		int a, b;
		int z;
		cin >> a >> b >> z;
		if(a == b){
			if(z != 0){
				cout << -1 << "\n";
				return 0;
			}
			continue;
		}
		g[a].push_back({b, z});
		g[b].push_back({a, z});
	}
	vector<bool> vis(n + 1, false);
	vector<int> d(n + 1, 0);
	vector<int> ans(n + 1, 0);
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			vector<int> temp;
			queue<int> q;
			vis[i] = true;
			d[i] = 0;
			q.push(i);
			temp.push_back(i);
			while(!q.empty()){
				int now = q.front();
				q.pop();
				for(auto e : g[now]){
					int v = e.first;
					int w = e.second;
					int nd = d[now] ^ w;
					if(!vis[v]){
						vis[v] = true;
						d[v] = nd;
						q.push(v);
						temp.push_back(v);
					}
					else{
						if(d[v] != nd){
							cout << -1 << "\n";
							return 0;
						}
					}
				}
			}
			int t = 0;
			for(int bit = 0; bit < 32; bit++){
				int cnt1 = 0;
				for(int v : temp){
					if((d[v] >> bit) & 1LL)
						cnt1++;
				}
				int cnt0 = temp.size() - cnt1;
				if(cnt1 > cnt0)
					t |= (1ULL << bit);
			}
			for(int v : temp){
				ans[v] = t ^ d[v];
			}
		}
	}
	for(int i = 1; i <= n; i++){
		cout << ans[i] <<  " ";
	}
	cout << endl;
	return 0;