建网站的小软件,北京的网站建设公司,seoyoon,网站建站华为云Problem - A - Codeforces
题意#xff1a;你有 t 组数据#xff0c;每组有两两不同的三个数 a,b,c#xff0c;现在需要你求出他们的中位数。
思路#xff1a;模拟即可
// Code Start Here int t;cin t;while(t--){vectorint a(3);for(int i 0;i3…Problem - A - Codeforces
题意你有 t 组数据每组有两两不同的三个数 a,b,c现在需要你求出他们的中位数。
思路模拟即可
// Code Start Here int t;cin t;while(t--){vectorint a(3);for(int i 0;i3;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;vectori64 a(n);mapi64,i64 mp;for(i64 i 0;in;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;in;i){if(a[i]!max_val){second_max_val max(second_max_val , a[i]);}}if(i64(mp.size()) 1){for(i64 i 0;in;i)cout 0 ;}else{if(i64(mp[max_val]) 1){for(i64 i 0;in;i){if(a[i] max_val){cout max_val - second_max_val ;}else cout a[i] - max_val ;}}else{for(i64 i 0;in;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 ,alal1al2⋯ar ,l0 或者 al−1al ,rn−1 或者 arar1 。
对于每次询问判断给定的序列是否是一个 valley。
思路注意到valley只有三种情况 左右升 左右降 左降右升。可以模拟跑一下各种情况或者判断是不是只有一个解即可
// Code Start Here int tt;cin tt;while (tt--) {int n;cin n;vectorint 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;vectorint a(n1),s(n1,0);for(int i 1;in;i){cin a[i];s[i] s[i-1] a[i];}int cnt 0;int ans 0;for(int i 1;in;i){if(a[i] 1){//后面多少个0ans (n-i) -(s[n] - s[i]);}else{//前面多少个1ans s[i-1];}}ans / 2;cnt ans;for(int i 1;in;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 天内都不能再完成这个任务。
给出两个数 cd要求求出满足在 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;in;i){cin a[i];}sort(a 1 , a 1 n , [](const int a,const int b){return a b;});for(int i 1;in;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;i0;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;vectorvectorpairint,int g(n 1);for(int i 1;in-1;i){int u , v , w;cin u v w;g[u].push_back({v , w});g[v].push_back({u , w});}setint st;bool flag false;st.insert(0);auto dfs1 [](auto dfs1 , int x ,int father , int val)-void{for(pairint,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(pairint,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;}
