Atcoder Beginner Contest 242

由于我8点半才下课，我只好晚半个小时再打，这次还行，排名3042

五道题，秒了前三道，第四道不会，第五道想出正解，结果一直不对，比完后看了一下大佬的代码恍然大悟，但是比赛早已结束.....

A: T-shirt

题意:

All participants who ranked A-th or higher get a T-shirt.

Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt

我就不翻译了，很简单。

Code

#include<iostream>
#include<cstdio>
using namespace std;
int a, b, c, x;
int main(){
	cin >> a >> b >> c >> x;
	double ans;
	if(x <= a){
		ans = 1.0;
	}
	else if(x > b){
		ans = 0;
	}
	else{
		ans = 1.0 * c / (b - a);
	}
	printf("%.7lf", ans);
	return 0; 
}

B:Minimize Ordering

题意:给一个字符串升序排序

啊这。。。。。。

我觉得应该放在A

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
string s;
int main(){
	cin >> s;
	sort(s.begin(), s.end());
	cout << s;
	return 0; 
}

C:1111gal password

题意：询问有多少个N位正整数，每一位上为1~9，且相邻两位相差不超过一

总算遇到递推了，恰好前几天做了好多USACO的DP题。

思路很简单，dp[i][j]为i长度以j结尾的方法数，状态转移方程：

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] + dp[i - 1][j]

That's all

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long dp[1000005][10] = {0};
const int mod = 998244353;
int main(){
	cin >> n;
	for(int i = 1; i <= 9; i++)
		dp[1][i] = 1;
	for(int i = 2; i <= n; i++){
		dp[i][1] = dp[i - 1][1] + dp[i - 1][2];
		dp[i][1] %= mod;
		for(int j = 2; j <= 8; j++)
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] + dp[i - 1][j], dp[i][j] %= mod;
		dp[i][9] = dp[i - 1][9] + dp[i - 1][8];
		dp[i][9] %= mod;
	}
	long long ans = 0;
	for(int i = 1; i <= 9; i++)
		ans += dp[n][i], ans %= mod;
	cout << ans;
	return 0; 
}

D:ABC Transform

看了一眼数据范围10^18，就没心思读题了……

E： (∀x∀)

题意：给一个n长度的字符串s，求有多少个字符串t，其长度为s，且为回文串，同时字典序小于等于s

我第一次想到了第五题的做法！！！ 虽然没做对

首先判断奇偶

我们可以依次处理1~n/2，每次算出这一位之前都不变，这一位比原来小的情况数，

最后判断一下1~n /2都相同时的回文串是否比原来小

我是这样写的：

if(a[n / 2] <= a[n / 2 + 1])
   ans++;
ans %= mod;

WA了6个点QWQ。。。。

实际要考虑后面的请况，应该这么写：

string s1 = s;
for(int i = 0; i < n / 2; i++)
	s1[n - i - 1] = s1[i];
if(s1 <= s)
	ans = (ans + 1) % mod;

考后代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
string s;
int t, n;
const int mod = 998244353;
#define ll long long
ll p26[1000005];
int a[1000005] = {0};
string s1;
int main(){
	//freopen("p.in", "r", stdin);
	cin >> t;
	p26[0] = 1;
	for(int i = 1; i <= 500005; i++)
		p26[i] = 1ll * p26[i - 1] * 26, p26[i] %= mod;
	for(int abc = 1; abc <= t; abc++){
	//	memset(a, 0, sizeof a);
		scanf("%d", &n);
		ll ans = 0;
		string s;
		cin >> s;
		s1 = s;
		for(int i = 1; i <= n; i++){
			a[i] = s[i - 1] - 'A' + 1;
		}
		if(n % 2 == 0){
			for(int i = 1; i <= n / 2; i++){
				ans += 1ll * (a[i] - 1) * p26[n / 2 - i];
				ans %= mod;
			}
			for(int i = 0; i < n / 2; i++)
				s1[n - i - 1] = s1[i];
			if(s1 <= s)
				ans = (ans + 1) % mod;
		}
		else{
			for(int i = 1; i <= n / 2 + 1; i++){
				ans += 1ll * (a[i] - 1) * p26[n / 2 - i + 1];
				ans %= mod;
			}
			for(int i = 0; i < n / 2; i++)
				s1[n - i - 1] = s1[i];
			if(s1 <= s)
				ans = (ans + 1) % mod;
		}
		printf("%lld\n", ans);
	}
	return 0; 
}

总结：都还好，注意细节！！！

今天我们学贪心，还是很有难度的……

That's all