[C++知识库]AtCoder Beginner Contest 234 (ABCDEF)

A - Weird Function

计算规定的函数值即可

ACcode

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll f(ll x){
	ll res = x * x + 2 * x + 3;
	return res;
}

int main(){
	
	ll t;
	cin >> t;
	ll res = f(f(f(t)+t)+f(f(t)));
	cout << res << endl;
	
	return 0;
}

B - Longest Segment

N 个点中，选两个点构成最长的线段。$O(N^2)$ 暴力计算即可。

ACcode

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 3e6 + 5;

double a[1005], b[1005];

double dis(int i, int j){
	double len = (a[i] - a[j]) * (a[i] - a[j]);
	len += (b[i] - b[j]) * (b[i] - b[j]);
	return len;
}

int main(){
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	
	double res = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			double tmp = dis(i, j);
			if(tmp > res) res = tmp;
		}
	}
	
	printf("%.10lf\n", sqrt(res));
	
	return 0;
}

C - Happy New Year!

本质就是计算 k 的二进制表示，注意把 ’1‘ 变成 ’2‘

ACcode

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
	
	ll k;
	cin >> k;
	
	string res = "";

	while(k){
		if(k&1) res = "2" + res;
		else res = "0" + res;
		k >>= 1;
	}	
	
	cout << res << endl;
	
	return 0;
}

D - Prefix K-th Max

依次输出序列前 $i$ 项$(k<=i<=n)$的第 $k$ 大。
用树状数组统计那个数字出现过，二分找第 k 大出现的数字。
ps：维护方法很多只要把前 k 大保留下来即可。

#include<bits/stdc++.h>
#include<queue>
#define ll long long
using namespace std;

const int maxn = 3e6 + 5;

int lowbit(int A){
	return A & (-A);
}

int a[maxn];
int t[maxn];
void add(int A){
	while(A < maxn){
		t[A]++;
		A += lowbit(A);
	}
}

int query(int A){
	int res = 0;
	while(A > 0){
		res += t[A];
		A -= lowbit(A);
	}
	return res;
}

int main(){
	
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	for(int i = 1; i < k; i++) add(a[i]);
	for(int i = k; i <= n; i++){
		add(a[i]);
		int pos = i - k + 1;
		int l = 1, r = n, res = -1;
		while(l <= r){
			int mid = l + r >> 1;
			if(query(mid) >= pos){
				res = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		cout << res << endl;
	}
	
	return 0;
}

E - Arithmetic Number

找到第一个大于等于 X 且满足要求的数字(每个数位等差)。
枚举第一位数是什么和公差是多少即可。时间复杂度：$O(9?19?17)$

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 3e6 + 5;

ll a[1005];
ll b[1005];

ll len, num = 0, res = 1e18;
void dfs(ll d, ll ai, ll now, ll step){
	if(step == len){
		if(now >= num && now < res) res = now; 
		return;
	}
	ll tmp = ai + d;
	if(tmp < 0 || tmp > 9) return;
	now = now * 10 + tmp;
	dfs(d, tmp, now, step+1);
}

int main(){
	
	string s;
	cin >> s;
	
	len = s.size();
	for(int i = 0; i < len; i++) a[i] = s[i] - '0';
	for(int i = 0; i < len; i++) num = num * 10 + a[i];
	
	for(int i = 1; i <= 9; i++){
		for(int j = -9; j <= 9; j++){
			dfs(j, i, i, 1);
		}
	}
	
	cout << res << endl;
		
	
	return 0;
}

F - Reordering

计算字符串 S 的全部非空子序列的全排列组成的字符串的种类。
定义：$d{p}_{i,j}$ 表示前 i 个字符构成长度为 j 的字符串的种类数
转移方程为：$d{p}_{i,j}=d{p}_{i?1,j?k}?C(j,k),i<=26,k<=第i种字符出现的次数$

#include<bits/stdc++.h>
#include<queue>
#define ll long long
using namespace std;

const int maxn = 5000 + 5;
const ll mod = 998244353;

ll f[maxn], inv[maxn];
ll dp[27][maxn];
int v[27];

ll qpow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b&1) res *= a;
		res %= mod;
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}

ll C(ll n, ll m){
	return f[n] * inv[m] % mod * inv[n-m] % mod;
}

int main(){
	
	f[0] = inv[0] = 1;
	for(int i = 1; i <= 5000; i++) f[i] = f[i-1] * i % mod;
	for(int i = 1; i <= 5000; i++) inv[i] = qpow(f[i], mod-2);
	
	string s;
	cin >> s;	
	
	int len = s.size();
	for(int i = 0; i < len; i++) v[s[i]-'a'+1]++;
	dp[0][0] = 1;
	for(int i = 1; i <= 26; i++){
		for(int j = 0; j <= len; j++){
			for(int k = 0; k <= min(j, v[i]); k++){
				dp[i][j] += dp[i-1][j-k] * C(j, k) % mod;
				dp[i][j] %= mod;
			}
		}
	}
	
	ll ans = 0;
	for(int i = 1; i <= len; i++) ans += dp[26][i], ans %= mod;
	cout << ans << endl;	
		
	return 0;
}