时间戳

首页 > 技术文章 > AtCoder Beginner Contest 158 题解报告

AtCoder Beginner Contest 158 题解报告

prjruckyone 2020-03-08 19:28 原文

A:Station and Bus

题目大意:

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

考察点:

水题

Code:

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + 10;

typedef long long LL;
typedef pair<int,int>PII;

int main(void) {
	string str;
	cin >> str;
	int a = 0,b = 0;
	for(int i = 0; i < str.length(); i ++) {
		if(str[i] == 'A') a ++;
		else b ++;
	}
	if(a == 3 || b == 3) {
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
	}
	return 0;
}

B:Count Balls

题目大意:

有一串蓝气球,一串红气球,然后个给你一个总数,需要按照先蓝后红的顺序进行排列,
最后问你蓝气球会有多少个？

考察点:

水题

Code:

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + 10;

typedef long long LL;
typedef pair<int,int>PII;

LL n,a,b;

int main(void) {
	cin >> n >> a >> b;
	LL res = a + b;
	if(a == 0) cout << 0 << endl;
	else if(n % res == 0) {
		cout << n / res * a << endl;
	} else {
		LL value = n / res * a;
		LL mod = n % res;
		if(mod >= a) cout << value + a << endl;
		else cout << value + mod << endl;
	}
	return 0;
}

C:Tax Increase

题目大意:

有两个已知的数 a、b,问是否有这样的一个数 x 满足 x * 0.08 = a 
并且 x * 0.1 = b;存在这样的数就输出这个数,不存在就输出 -1.

考察点:

二分、暴力

析题得侃：

我们可以假设某个数是成立的,然后带进去看是否符合我们得到的答案。
由于这个数据范围较小,也可以逐个枚举进行尝试。

Code:

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + 10;

typedef long long LL;
typedef pair<int,int>PII;

int a,b;

bool Check(int x) {
	int c = x * 0.08,d = x * 0.1;
	if(c >= a && d >= b) return true;
	else return false;
} 

int main(void) {
	cin >> a >> b;
	int l = 1,r = maxn;
	while(l < r) {
		int mid = l + r >> 1;
		if(Check(mid)) r = mid;
		else l = mid + 1;
	}
	int x = r * 0.08,y = r * 0.1;
	if(x == a && b == y) {
		cout << r << endl;
	} else {
		cout << -1 << endl;
	}
	return 0;
}

D:String Formation

题目大意:

题目会先给我们一个字符串,然后会有三种操作:
1、反转该字符串
2、在字符串的开始位置增加一个字符
3、在字符串的末尾位置增加一个字符
最后输出该字符串。

考察点:

思维、字符串、双端队列

析题得侃:

我们发现反转后的字符串如果要添加的话只需要将向开始位置添加转换为
向末尾添加即可,同理,向末尾添加也是同样的道理,所以我们不需要每次
都进行反转,这样做的话有可能还是会超时的。
字符串的拼接会浪费大量的时间,要不用更加高级的数据结构进行维护,要不
对字符串进行插入,不然是会超时的,超时的。

超时代码:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

string a;

int t,op,f;

char c;

int main(void) {
	cin >> a;
	scanf("%d",&t);
	int ans = 1;
	while(t --) {
		scanf("%d",&op);
		if(op == 1) {
			ans ++;
		} else {
			scanf("%d",&f);
			getchar();
			scanf("%c",&c);
			if(ans % 2 == 1) {
				if(f == 1) {
					a = c + a;
				} else {
					a += c;
				}
			} else {
				if(f != 1) {
					a = c + a;
				} else {
					a += c;
				}
			}
		}
	}
	if(ans % 2 == 1)
		for(int i = 0; i < a.length(); i ++) {
			printf("%c",a[i]);
		}
	else {
		for(int i = 0; i < a.length() / 2; i ++) {
			swap(a[i],a[a.length() - i - 1]);
		}
		for(int i = 0; i < a.length(); i ++) {
			printf("%c",a[i]);
		}
	}
	return 0;
}

AC代码:

#include <deque>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

string a;

int t,op,f;

char c;

deque<char>de;

int main(void) {
	cin >> a;
	for(int i = 0; i < a.length(); i ++) {
		de.push_back(a[i]);
		// 掌握 双端队列插入时的特点 
	}
	scanf("%d",&t);
	int ans = 1;
	while(t --) {
		scanf("%d",&op);
		if(op == 1) {
			ans ++;
		} else {
			scanf("%d",&f);
			getchar();
			scanf("%c",&c);
                        //根据反转次数决定向那个方向进行插入
			if(ans % 2 == 1) {
				if(f == 1) {
					de.push_front(c);
				} else {
					de.push_back(c);
				}
			} else {
				if(f != 1) {
					de.push_front(c);
				} else {
					de.push_back(c);
				}
			}
		}
	}
	if(ans % 2 == 1)
		for(int i = 0; i < de.size(); i ++) {
			printf("%c",de[i]);
		}
	else {
		for(int i = de.size() - 1; i >= 0; i --) {
			printf("%c",de[i]);
		}
	}
	return 0;
}

E:Divisible Substring

题目大意:

给一串数字字符,求这串字符中的子串有多少 % p == 0.(P 是质数)

参考博客:

1、https://www.cnblogs.com/zdragon1104/p/12441877.html
2、https://blog.csdn.net/Huah_2018/article/details/104731106

考察点:

思维、字符串、前缀和

析题得侃:

怎么表示一个子串的整数形式呢？
可以这样来表示:    S[L --- R] * 10 ^(R - L)
假设 R - L = x, 我们可以知道 (10^x mod p) != 0 (p != 2 && p != 5 的情况下)
S[L --- R] * 10^(R - L) = S[L] * 10^(R - L) - S[R] * 10^(R -L)
在还没有 % p 的时候 , 我们知道如果 p != 2 && p != 5 的时候 10 ^ (R - L) != 0
所以只能 s[L] - S[R] = 0,所有 S[L] = S[R] 的时候才满足这个子串 % p = 0;
所以我们只需要寻找所有子串中相等的即可。

p = 2 || p = 5 的时候我们可以单独处理,如果说当前字符 % p == 0,说明前面的都可以(将
当前字符作为个位),直接累加即可。

p 为其他数时,我们进行逆序处理(因为字符串中最右端是最低位,所以先从低位开始进行统计)

Code:

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 10;

char a[maxn]; 

map<int,int>maps;

int n,p;

LL res = 0;

int main(void) {
	scanf("%d%d",&n,&p);
	scanf("%s",a + 1);
	if(10 % p == 0) {
		for(int i = 1; i <= n; i ++) {
			if((a[i] - '0') % p == 0) {
				res += i;
			}
		}
	} else {
		LL ans = 0,t = 1;
		for(int i = n; i ; i -- ){
                        // 第一次要先将 0 加进去,每次都将新的余数加进去
			maps[ans] ++;
			ans = (ans + (a[i] - '0') * t)  % p;
                        // 与进位类似
			t = t * 10 % p; 
			res += maps[ans];
		}
	}
	cout << res << endl;
	return 0;
}

F:Removing Robots

能力有限,琢磨 ing.

后记:

本人深知自己写的还有很多不足的地方,望各位大佬多多指教。

推荐阅读