Codeforces Round 913 (Div. 3) A~E

2023-12-06 19:04
文章标签 codeforces round div 913

本文主要是介绍Codeforces Round 913 (Div. 3) A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

A. Rook 

问题分析: 

B. YetnotherrokenKeoard

问题分析:  

C. Removal of Unattractive Pairs

问题分析:  

D. Jumping Through Segments

问题分析:  

E. Good Triples

问题分析:  

A. Rook 

问题分析: 

给一个棋子将其同行同列的位置输出

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{string a;cin>>a;char x=a[0];int num=a[1]-'0';for(int i=1;i<=8;i++){if(i!=num)cout<<x<<i<<endl;}for(int i=0;i<=7;i++){if('a'+i!=x){cout<<(char)('a'+i)<<num<<endl;}}}return 0;
}

B. YetnotherrokenKeoard

 

问题分析:  

一个字符串，当当前字符为'b'时，删除新字符串最右边的 小写字符，当当前字符为'B'时删除新字符串最右边的大写字符，没有则不删除，除去'b'和'B'的其他字符添加到新字符串当中，然后输出。

可以通过栈来存储新字符串当中的大小写字符的位置，然后遇到相应的'b' or 'B',将栈顶的位置标记，最后按照标记输出原字符串的字符即可

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{string a;cin>>a;stack<int>lowi,upi;vct<bool>st(a.LEN);for(int i=0;i<a.LEN;i++){if(a[i]=='b'){st[i]=1;if(lowi.empty())continue;else st[lowi.top()]=1,lowi.pop();}else if(a[i]=='B'){st[i]=1;if(upi.empty())continue;else st[upi.top()]=1,upi.pop();}else {if(islower(a[i])){lowi.push(i);}else {upi.push(i);}}}for(int i=0;i<a.LEN;i++){if(!st[i])cout<<a[i];}cout<<"\n";
}return 0;
}

C. Removal of Unattractive Pairs

 

问题分析:  

 给定字符串，如果相邻两个字符不同，可以删除这两个字符，求出最终可以剩下几个字符

我们统计每个字符的数量，为了保证最后剩下的字符个数最少，我们贪心地用个数次大的字符与个数最大的字符相抵消，因为需要维护数量的降序排序，我们选择使用大根堆来维护，我们每次弹出堆顶的两个元素，将他们互相抵消，也就是都减一，如果大于零就再放回堆当中，最终堆内会只剩下一个数，也就是最短的字符串长度

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOS
use{int n;cin>>n;string a;cin>>a;vct<int>cnt(26);for(int i=0;i<a.LEN;i++){cnt[a[i]-'a']++;}priority_queue<int>q;for(int i=0;i<26;i++){if(cnt[i]!=0)q.push(cnt[i]);}while(q.size()>1){int x=q.top();q.pop();int y=q.top();q.pop();x--;y--;if(x>0)q.push(x);if(y>0)q.push(y);}if(q.empty())cout<<"0"<<endl;else cout<<q.top()<<endl;
}return 0;
}

D. Jumping Through Segments

 

问题分析:  

 n个线段，每次可以选择走0~k格，第i次一定要落在第i个线段内部，要求在满足条件的情况下使得k最小.

对于k来说，k的大小对于结果的影响是单调的，故可以用二分答案,我们只需要确定第i步走出的范围能够与第i个线段有交集即可

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOSuse{int n;cin >> n;int ans;vct<int> l(n + 1);vct<int> r(n + 1);for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];int L = 0, R = 1e9;int mid;auto check = [&](int mid) -> bool {int dis1 = 0, dis2 = 0;for (int i = 1; i <= n; i++) {dis1 -= mid, dis2 += mid;if (dis1 > r[i] || dis2 < l[i]) return false;mmax(dis1, l[i]), mmin(dis2, r[i]);}return true;};while (L <= R) {mid = (L + R) >> 1;if (check(mid)) {R = mid - 1;ans = mid;} else L = mid + 1;}cout << ans << endl;}return 0;
}

E. Good Triples

 

问题分析:  

给定整数n，求出有多少个三元组满足题目条件，且若三元组的元素相同但排序不同，则 算是不同的三元组。

我们通过样例以及向下推导可知:

故满足[(n+2)\times (n+1)\div2 ]的公式，且为n各位数字得到结果的乘积

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N =1e5+7;
signed main()
{IOSuse{string a;cin>>a;int ans=1;for(int i=0;i<a.LEN;i++){ans*=(a[i]-'0'+2)*(a[i]-'0'+1)/2;}cout<<ans<<endl;}return 0;
}

 

这篇关于Codeforces Round 913 (Div. 3) A~E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/462951。

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
Codeforces 482B 线段树

Codeforces 482B 线段树

求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2