ATCODER ABC158 题解

A - Station and Bus

题意

给一个长度为三的字符串,如果字符串每个字母都相等,就输出 “No”，否则输出“Yes”;

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000+10;
int main(){
	char a[4];
	cin>>a;
	int ok1=0,ok2=0;
	for(int i=0;i<3;i++){
		if(a[i]=='A'){
			ok1=1;
		}
		if(a[i]=='B'){
			ok2=1;	
		}
	}
	if(ok1&&ok2){
		cout<<"Yes";
	}
	else cout<<"No";
	return 0;
}

B - Count Balls

题意

排气球，先排a个蓝气球，再排b个红气球，然后再a个蓝气球....
问前n个气球里有多少个蓝气球

思路

除一下再取个膜什么的就可以了，注意要开long long

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000+10;
int main(){
	long long n,a,b,ans=0;
	cin>>n>>a>>b;
	long long c=a+b;
	ans=(n/c)*a;
	if((n%c)<a){
		ans+=(n%c);	
	}
	else ans+=a;
	cout<<ans;
	return 0;
}

C - Tax Increase

题意

找到最小的正整数x，满足⌊x∗0.08⌋=A 且 ⌊x∗0.1⌋=B，若不存在，输出-1。

思路

数据范围比较小，所以直接暴力就好了
从10到1000枚举n，假设n是成立的,然后带进去看是否符合我们得到的答案

代码

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	for(int i=10;i<=1000;i++){
		if(floor(i*0.08)==a&&floor(i*0.1)==b){
			cout<<i;
			return 0;
		}
	}
	cout<<"-1";
	return 0;
}

D - String Formation

题意

给一个字符串S，进行Q次操作，有翻转字符串、字符串开头加一个字符、字符串结尾加一个字符三种操作，输出最终的字符串。

思路

因为每次只加一个字符，所以所谓翻转字符串，只是改变从开头/结尾加字符的相对位置就好了，比如本来是要求从开头插入，翻转后变成从实际上从字符串结尾插入，然后用STL的双端队列维护就行了。

双端队列:
头文件#include<deque>
调用 deque<char> que;
从队头插入 que.push_front(a);
从队尾插入 que.push_back(a);
从队头出队 que.pop_front(a);
从队尾出队 que.pop_back(a);
访问对头 que.front();
访问队尾 que.back();

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
const int maxn=300000+10;
char a[maxn];
deque<char> que;

int main(){
	int q;
	cin>>a>>q;
	int len=strlen(a);
	for(int i=0;i<len;i++){
		que.push_back(a[i]);	
	}
	int nowt=1;
	while(q--){
		int x;cin>>x;
		if(x==1){
			if(nowt==1){
				nowt=2;	
			}
			else nowt=1;
		}
		else if(x==2){
			int vis;char ch;
			cin>>vis>>ch;
			if(vis==1){
				if(nowt==1){
					que.push_front(ch);	
				}
				else{
					que.push_back(ch);	
				}
			}
			else{
				if(nowt==2){
					que.push_front(ch);	
				}
				else{
					que.push_back(ch);	
				}
			} 
		}
	}
	if(nowt==1){
		while(!que.empty()){
			cout<<que.front();
			que.pop_front();
		}
	} 
	else{
		while(!que.empty()){
			cout<<que.back();
			que.pop_back();
		}	
	}
}

E - Divisible Substring

题意

给一个长度为N的字符串S，以及一个质数P，求有多少个子串在十进制下对P取模为0。

思路

首先可以得知10xmod P≠0(P≠2 and P≠5)，那么对于S[l...r]子串，当且仅当S[l...N]≡S[r...N](mod P)成立时，满足要求。

证明如下：S[l...r]×10r−l=S[l...N]−S[r...N]，若S[l...N]−S[r...N]≡0(mod P)，由于10xmod P≠0，可以得出S[l...r] mod P=0，若 S[l...N]−S[r...N]≢0(mod P)，显然S[l...r] mod P≠0。

可以对P=2,P=5进行特判，然后倒着遍历字符串，每次加上之前余数和当前余数相同的个数。