Problem - A - Codeforces

题意：你有 t 组数据，每组有两两不同的三个数 a,b,c，现在需要你求出他们的中位数。

思路：模拟即可

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		vector<int> a(3);
		for(int i = 0;i<3;i++)cin >> a[i];
		sort(a.begin(),a.end());
		cout << a[1] <<endl;
	}

Problem - B - Codeforces

题意：

现在对于任意一个单词，定义：它需要一个最小的大小为 x 的字母表，当且仅当这个单词只用到了英文字母中的前 x 个字符。

你现在需要对于 t 组长度为 n 的字符串 s，求出每一个单词的最小字母表。

思路：找最大的char，模拟即可

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		int l;
		string s;
		cin >> l >> s;
		int ans = -0x3f;
		for(auto ch : s){
			ans = max(ans,int(ch - 'a'));
		}
		cout << ans + 1 <<endl;
	}

Problem - C - Codeforces

题意：

若干个参赛者正在比拼。

每个人想要知道除自己以外的最厉害的人力量比自己弱多少，现在他们依次在向你询问。

思路：一个蛮坑的模拟题，注意到只需要讨论最大值和次大值即可，然后分类讨论最大值的数量

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		i64 n;
		cin >> n;
		vector<i64> a(n);
		map<i64,i64> mp;
		for(i64 i = 0;i<n;i++){
			cin >> a[i];
			mp[a[i]]++;
		}
		i64 max_val = *max_element(a.begin(),a.end());
		i64 second_max_val = -0x3f;
		for(i64 i = 0;i<n;i++){
			if(a[i]!=max_val){
				second_max_val = max(second_max_val , a[i]);
			}
		}
		if(i64(mp.size()) == 1){
			for(i64 i = 0;i<n;i++)cout <<"0 ";
		}
		else{
			if(i64(mp[max_val]) == 1){
				for(i64 i = 0;i<n;i++){
					if(a[i] == max_val){
						cout << max_val - second_max_val <<" ";
					}
					else cout << a[i] - max_val << " ";
				}
			}
			else{
				for(i64 i = 0;i<n;i++){
					cout << a[i] - max_val << " ";
				}
			}
		}
		cout << endl;
	}

Problem - D - Codeforces

题意：

一个含 n 个整数元素的序列 a[0…n−1]，如果有且只有一个连续子序列 a[l…r] 同时满足以下条件，那么我们称原序列是 valley 的。

• 0≤l≤r≤n−1 ,
• al​=al+1​=al+2​=⋯=ar​ ,
• l=0 或者 al−1​>al​ ,
• r=n−1 或者 ar​<ar+1​ 。

对于每次询问，判断给定的序列是否是一个 valley。

思路：注意到valley只有三种情况  左右升  左右降  左降右升。可以模拟跑一下各种情况，或者判断是不是只有一个解即可

// Code Start Here	
	int tt;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int cnt = 0;
		int beg = 0;
		while (beg < n) {
			int end = beg;
			while (end + 1 < n && a[end + 1] == a[end]) {
				end += 1;
			}
			if (beg == 0 || a[beg - 1] > a[beg]) {
				if (end == n - 1 || a[end + 1] > a[end]) {
					cnt += 1;
				}
			}
			beg = end + 1;
		}
		cout << (cnt == 1 ? "YES" : "NO") << '\n';
	}

Problem - E - Codeforces

题意：给定长度为 n 的 01 串，问至多将一个数字取反后逆序对的数量最大是多少。

思路：注意到数据范围是2e5思考如何优化计算方式，考虑到逆序对的定义是 i < j and ai > aj，而且每次只修改一个字符，思考到可以计算一下在当前位置的逆序对数量，对0 / 1分情况讨论，对另一半取反然后取最大值即可，逆序对数量可以用类似前缀和的方式快速计算

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<int> a(n+1),s(n+1,0);
		for(int i = 1;i<=n;i++){
			cin >> a[i];
			s[i] = s[i-1] + a[i];
		}
		int cnt = 0;
		int ans = 0;
		for(int i = 1;i<=n;i++){
			if(a[i] == 1){
				//后面多少个0
				ans += (n-i) -(s[n] - s[i]);
			}
			else{
				//前面多少个1
				ans += s[i-1];
			}
		}
		ans /= 2;
		cnt = ans;
		for(int i = 1;i<=n;i++){
			if(a[i] == 1){
				int now = s[i-1];
				ans = max(ans,(cnt - ((n-i) -(s[n] - s[i])) + now));
			}
			else{
				int now = (n-i) -(s[n] - s[i]);
				ans = max(ans,(cnt - s[i-1] + now));
			}
		}
		cout << ans <<endl;
	}

Problem - F - Codeforces

题意：

有 n 个任务，你每一天都可以选择其中的一个任务完成或不选。当你完成了第 i 个任务，你将获得 ai​ 元。但是如果你今天完成了一个任务，那么你之后 k 天内都不能再完成这个任务。

给出两个数 c，d，要求求出满足在 d 天内可以收集至少 c 元的最大的 k。

思路：首先注意到不存在和无限的情况

1.当全部的和大于c，即d天内只跑一轮就能完成，无限

2.每天都跑最大的还是不能达到c，不存在

其他情况一定有答案，可以二分天数，或者贪心看跑一遍什么时候刚好大于即可，这里跑了一遍贪心

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		//n个数  c元  d天
		memset(s , 0 , sizeof s);
		int n , c , d;
		cin >> n >> c >> d;
		for(int i = 1;i<=n;i++){
			cin >> a[i];
		}
		sort(a + 1 , a + 1 + n , [&](const int & a,const int & b){return a > b;});
		for(int i = 1;i<=n;i++){
			s[i] = s[i-1] + a[i];
		}
		if(s[min(n , d)] >= c){
			cout <<"Infinity" << '\n';
			continue;
		}
		if(s[1] * d < c){
			cout <<"Impossible" << '\n';
			continue;
		}
		int ans = -1;
		for(int i =  d- 1;i>=0;i--){
			int Round = d / (i + 1);
			int Res = d % (i + 1);
			if(s[min(n , Res)] + Round * s[min(n , i + 1)] >= c){
				ans = i;
				break;
			}
		}
		cout << max(ans , 0LL) << endl;
	}

Problem - G - Codeforces

題意：给你一棵树和两个点 a,b，边有边权。你可以在任意时刻从当前所在的点跳到任意除了 b 以外的点。求有没有方案使得从 a 出发，到达 b 时边权 xor 和为 0。

思路：根据xor的性质，当两个数相等时，xor值为0，因此题目可以变形为：有没有一种方案，使得从a出发和从b出发到达一个非b , a的点时两个路径的xor权值相等。

马上想到对其中一条边跑一遍dfs，然后记录下来所有简单路径的xor值，然后再跑一遍另外一个点查询即可。

// Code Start Here	
	int t;
	cin >> t;
	while(t--){
		int n , a , b;
		cin >> n >> a >> b;
		vector<vector<pair<int,int>>> g(n + 1);
		for(int i = 1;i<=n-1;i++){
			int u , v , w;
			cin >> u >> v >> w;
			g[u].push_back({v , w});
			g[v].push_back({u , w});
		}
		set<int> st;
		bool flag = false;
		st.insert(0);
		auto dfs1 = [&](auto dfs1 , int x ,int father , int val)->void{
			for(pair<int,int> &now : g[x]){
				if(now.first == father || now.first == b)continue;
				st.insert(val^now.second);
				dfs1(dfs1 , now.first , x ,val^now.second);
			}
		};
		auto dfs2 = [&](auto dfs2 , int x ,int father , int val)->void{
			for(pair<int,int> &now : g[x]){
				if(now.first == father)continue;
				if(st.count(val ^ now.second)) flag = true;
				dfs2(dfs2,now.first , x , val ^ now.second);
			}
		};
		dfs1(dfs1 , a , 0 , 0);
		dfs2(dfs2 , b , 0 , 0);
		if(flag)cout <<"Yes" << '\n';
		else cout <<"No" << '\n';
		
	}