Codeforces Round 913 (Div. 3)
Codeforces Round 913 (Div. 3)
文章目录
- Codeforces Round 913 (Div. 3)
- A. Rook
- B. YetnotherrokenKeoard
- C. Removal of Unattractive Pairs
- D. Jumping Through Segments
- E. Good Triples
A. Rook
模拟,字符串
已经给了你位置,只要按照每一行每一列的顺序输出即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void slove(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
for(int i=1;i<=8;i++){
if('a'+i-1==s[0])continue;
cout<<(char)('a'+i-1)<<s[1]<<endl;
}
for(int i=8;i>=1;i--){
if(i==s[1]-'0')continue;
cout<<s[0]<<i<<endl;
}
}
}
int main(){
slove();
}
B. YetnotherrokenKeoard
思维,模拟
记录每一个B前面的大小写比较麻烦,所以直接倒过来记录。
当出现b/B,就将计数器++,当出现大小写,就将计数器–,并标记。
然后正序输出所有未标记的即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool cmp(int a,int b){
return a>b;
}
void slove(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int bcnt=0;
int Bcnt=0;
int len=s.size();
vector<int> flag(len+1);
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='b'){
bcnt++;
continue;
}
if(s[i]=='B'){
Bcnt++;
continue;
}
if(islower(s[i]) and bcnt>0){
bcnt--;
flag[i]=1;
}
if(isupper(s[i])and Bcnt>0){
Bcnt--;
flag[i]=1;
}
}
for(int i=0;i<len;i++){
if(s[i]=='B' or s[i]=='b' or flag[i]==1)continue;
cout<<s[i];
}
cout<<endl;
}
}
int main(){
slove();
}
C. Removal of Unattractive Pairs
思维,贪心
不需要模拟,这道题的答案只与最大的相同字母有关。
如果有一个字母出现了大于n/2次,那么最终剩下的一定是这个字母。
假设出现了m次,那么答案就是2*m-n
如果小于n/2次,那么它一定会被消除,无论在什么位置。
最终剩下的元素个数只与奇偶性有关
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void slove(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
map<char,int> m;
for(int i=0;i<s.size();i++){
m[s[i]]++;
}
int x=n/2;
int maxn=0;
priority_queue<int,vector<int>,less<int>> q;
for(auto it=m.begin();it!=m.end();it++){
maxn=max(maxn,it->second);
q.push(it->second);
}
if(maxn>n-maxn){
cout<<2*maxn-n<<endl;
}
else{
if(n&1)cout<<1<<endl;
else cout<<0<<endl;
}
}
}
int main(){
slove();
}
D. Jumping Through Segments
二分答案
一道二分答案,但是是区间形式。
以往传统的二分答案,最终的解都是实数
但是这一次,我们二分的是可行性
即每次跳的区间范围是否合法。
比较少见
设start=0,end=0
第一次跳的长度最长是k,且可以前后跳
所以理论上能跳到 [start-k,end+k]
但是我们需要在 [ l [ i ] , r [ i ] ] [\ l[i],r[i]\ ] [ l[i],r[i] ]之内
所以跳一次之后的start应该取 max(l[i],start-k)
跳一次之后的end应该取 min(r[i],end+k)
那么什么情况下会不满足呢?
我们注意到,每一次跳,start的结果必然>=l[i]
每一次跳,end的结果必然<=r[i]
所以当 start>end 的时候,这个区间是不存在的。
那么什么时候start 会大于end呢?
当k超级小的时候, 如k=1 ,l[i]=2,r[i]=4
那么跳一次之后,start=2,end=1
所以我们就要将mid取大,也就是l=mid
反之,就将mid尽可能取小即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+7;
void slove(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<ll> l(n+1),r(n+1);
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
auto check=[&](ll mid){
ll start=0,end=0;
for(int i=1;i<=n;i++){
start=max(l[i],start-mid);
end=min(r[i],end+mid);
if(end<start)return 0;
}
return 1;
};
ll L=0; ll R=1e9+7;
while(L<R){
ll mid=(L+R)>>1;
if(check(mid)==1){
R=mid;
}
else L=mid+1;
}
cout<<L<<endl;
}
}
int main(){
slove();
}
E. Good Triples
思维,数论
算是一道开拓思维的题。
需要将 n划分为三个数 a,b,c
并且 位数之和等于n
破题点就是:位数之和什么情况下会改变?
当a+b+c 会进位的时候, 9+1–>10 ,位数之和就减少了9
很好理解,因为a,b,c都是十进制,当你缝9进1
如果是2进制,那就是每进一次就少1
如果3进制,每进一次位就少2
以此类推
所以我们要想三位数不进位,那么就将每一位数分成3份,放到 相应的位上。
例如99,将个位的9,分成3份到abc的个位上
将十位的9分成三份到abc的十位上
这样绝对不会进位。
由于每个位数之间的划分三份都是独立的,所以答案乘起来即可。
现在就要考虑如何将一个数a( 0<=a<=9) 划分成三份。
可以dp,也可以排列组合。
由于可以选0,且0最多可以选两次。
那么一共就是a+2个数,选出两个数后,第三个数是确定的
所以答案 C a + 2 2 = ( a + 2 ) ( a + 1 ) / 2 C_{a+2}^2=(a+2)(a+1)/2 Ca+22=(a+2)(a+1)/2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+7;
void slove(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
ll ans=1;
while(n){
int cnt=n%10;
n/=10;
ans*=(cnt+2)*(cnt+1)>>1ll;
}
cout<<ans<<endl;
}
}
int main(){
slove();
}
edef long long ll;
const int N=1e7+7;
void slove(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
ll ans=1;
while(n){
int cnt=n%10;
n/=10;
ans*=(cnt+2)*(cnt+1)>>1ll;
}
cout<<ans<<endl;
}
}
int main(){
slove();
}
推荐阅读
-
CodeForces Round 933 | Div3-内容详情:
-
Codeforces Round 932 (Div. 2)----->A. Entertainment in MAC
-
Codeforces Round #322 (Div. 2) A、B、C
-
Codeforces Round 932 (Div. 2) ABCD-D. Exam in MAC
-
Codeforces Round #835 (Div. 4) A-G Complete Problem Solving-G、
-
Codeforces Round #834 (Div. 3) A-G
-
Codeforces Round 913 (Div. 3)
-
Codeforces Round 928 (Div. 4) (A-E)
-
Educational Codeforces Round 121 (Rated for Div. 2)——A - Equidistant Letters
-
Codeforces Round #633 (Div. 2)D Edge Weight Assignment(构造、树的权值异或)