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#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 bool mmax(T &u, T v) { return u pii;const int N =1e5+7;signed main(){IOSuse{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#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 bool mmax(T &u, T v) { return u pii;const int N =1e5+7;signed main(){IOSuse{string a;cin>>a;stacklowi,upi;vctst(a.LEN);for(int i=0;i

C. Removal of Unattractive Pairs

问题分析:

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

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

#include#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 bool mmax(T &u, T v) { return u pii;const int N =1e5+7;signed main(){IOSuse{int n;cin>>n;string a;cin>>a;vctcnt(26);for(int i=0;iq;for(int i=0;i1){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格，第次一定要落在第个线段内部，要求在满足条件的情况下使得k最小.

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

#include#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 bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }template 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"<<endlusing namespace std;typedef pairpii;const int N =1e5+7;signed main(){ IOS use{ int n; cin >> n; int ans; vct l(n + 1); vct r(n + 1); for (int i = 1; i > 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  r[i] || dis2 < l[i]) return false; mmax(dis1, l[i]), mmin(dis2, r[i]); } return true; }; while (L > 1; if (check(mid)) { R = mid - 1; ans = mid; } else L = mid + 1; } cout << ans << endl; } return 0;}

E. Good Triples

问题分析:

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

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

故满足的公式，且为n各位数字得到结果的乘积

#include#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 bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }template 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"<<endlusing namespace std;typedef pairpii;const int N =1e5+7;signed main(){IOSuse{ string a;cin>>a; int ans=1; for(int i=0;i