AtCoder Beginner Contest 234(AtCoder Beginner Contest 234)

AtCoder Beginner Contest 234

  • A – Weird Function

思路:模拟

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll t;
ll f(ll x){
	return x*x+2*x+3;
}
int main(){
	cin>>t;
	cout<<f(f(f(t)+t)+f(f(t)))<<endl;
	return 0;
}
  • B – Longest Segment

思路:注意误差小于\(10^{-6}\)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n;
struct node{
	int x,y;
}a[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	double ans=-1;
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int dx=(a[i].x-a[j].x)*(a[i].x-a[j].x);
			int dy=(a[i].y-a[j].y)*(a[i].y-a[j].y);
			ans=max(ans,sqrt(dx+dy));
		}
	}
	cout<<fixed<<setprecision(7);
	cout<<ans;	
	return 0;
}
  • C – Happy New Year!

思路:本质就是输入\(k\),输出\(k\)的二进制表示,并把\(1\)用\(2\)表示

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
ll n,a[N];
int main(){
	cin>>n;
	int tt=0;
	while(n>0){
		a[tt++]=n%2;
		n/=2;
	}
	for(int i=tt-1;i>=0;i--){
		if(a[i]==1) cout<<"2";
		else cout<<"0";
	}
	return 0;
}
  • D – Prefix K-th Max

思路:把数放入一个小根堆维护即可

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
priority_queue<int,vector<int>,greater<int> > q;
int n,k,x;
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>x;
		q.push(x);
	}
	cout<<q.top()<<endl;
	for(int i=k+1;i<=n;i++){
		cin>>x;
		q.push(x);
		q.pop();
		cout<<q.top()<<endl;
	}

	return 0;
}
  • E – Arithmetic Number

题目大意:给定一个数\(x\),找出一个不小于\(x\)的数\(y\),\(y\)满足每个数位之间成等差关系,输出最小\(y\)

思路:\(dfs\)爆搜,注意剪枝,\(x<100\)直接输出原数即可

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353;
typedef long long ll;
ll vis[N],x,tt;
void dfs(ll sum,int d,int cnt,int tmp){
    if(cnt>18) return ;
    vis[++tt]=sum;
    if(tmp+d<0||tmp+d>9) return ;
    dfs(sum*10+d+tmp,d,cnt+1,tmp+d);
}
int main(){
    cin>>x;
    if(x<100) cout<<x<<endl;
    else{
        for(int i=1;i<=9;i++){
            for(int j=0;j<=9;j++){
                dfs(i*10+j,j-i,2,j);
            }
        }
        sort(vis+1,vis+1+tt);
        for(int i=1;i<=tt;i++){
            if(vis[i]>=x) {
                cout<<vis[i]<<endl;
                break;
            }
        }
    }
	return 0;
}

  • F – Reordering

题目大意:给定一个字符串\(S\),求有该字符串的非空子串的排列数

思路:方法一:\(dp\) + 线性求逆元求组合数

\(dp[i][j]:\) \(i\)表示\(26\)个字母中前\(i\)个字母,\(j\)表示字符串子串长度为\(j\)
\(vis[i]:\) 表示字符串\(S\)中每个字母的个数
列出转移方程:\(dp[i+1][j]=\sum_{k=0}^{min(j,vis[i])} dp[i][j-k]*(j,k)\)
结果即:\(ans=\sum_{i=1}^{S.size()}dp[26][i]\)

求组合数\((j,k)\)时,要线性预处理逆元(用快速幂求会超时)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353;
typedef long long ll;
ll fac[N],dp[30][N],inv[N],finv[N];
string str;
int vis[30];
void init(){
    fac[0]=fac[1]=1,inv[1]=1,finv[0]=finv[1]=1;
    for(int i=2;i<=5050;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-mod/i*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll C(ll n,ll m){
    return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
    init();
    cin>>str;
    int len=str.size();
    dp[0][0]=1;
    for(int i=0;i<len;i++){
        int tt=str[i]-'a';
        vis[tt]++;
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<=len;j++){
            for(int k=0;k<=min(j,vis[i]);k++){
                dp[i+1][j]+=dp[i][j-k]*C(j,k);
                dp[i+1][j]%=mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=len;i++){
        ans+=dp[26][i];
        ans%=mod;
    }
	cout<<ans<<endl;
	return 0;
}

方法二:生成函数 + \(NTT\)(待更

————————

AtCoder Beginner Contest 234

  • A – Weird Function

Idea: simulation

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll t;
ll f(ll x){
	return x*x+2*x+3;
}
int main(){
	cin>>t;
	cout<<f(f(f(t)+t)+f(f(t)))<<endl;
	return 0;
}
  • B – Longest Segment

Idea: note that the error is less than \ (10 ^ {-6} \)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n;
struct node{
	int x,y;
}a[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	double ans=-1;
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int dx=(a[i].x-a[j].x)*(a[i].x-a[j].x);
			int dy=(a[i].y-a[j].y)*(a[i].y-a[j].y);
			ans=max(ans,sqrt(dx+dy));
		}
	}
	cout<<fixed<<setprecision(7);
	cout<<ans;	
	return 0;
}
  • C – Happy New Year!

Idea: the essence is to input \ (K \) and output the binary representation of \ (K \), and represent \ (1 \) with \ (2 \)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
ll n,a[N];
int main(){
	cin>>n;
	int tt=0;
	while(n>0){
		a[tt++]=n%2;
		n/=2;
	}
	for(int i=tt-1;i>=0;i--){
		if(a[i]==1) cout<<"2";
		else cout<<"0";
	}
	return 0;
}
  • D – Prefix K-th Max

Idea: put the number into a small root heap for maintenance

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
priority_queue<int,vector<int>,greater<int> > q;
int n,k,x;
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>x;
		q.push(x);
	}
	cout<<q.top()<<endl;
	for(int i=k+1;i<=n;i++){
		cin>>x;
		q.push(x);
		q.pop();
		cout<<q.top()<<endl;
	}

	return 0;
}
  • E – Arithmetic Number

Main idea of the topic: given a number \ (x \), find a number \ (Y \) not less than \ (x \), \ (Y \) satisfies the equal difference relationship between each digit, and outputs the minimum \ (Y \)

Idea: \ (DFS \) pop search, pay attention to pruning, and \ (X & lt; 100 \) directly output the original number

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353;
typedef long long ll;
ll vis[N],x,tt;
void dfs(ll sum,int d,int cnt,int tmp){
    if(cnt>18) return ;
    vis[++tt]=sum;
    if(tmp+d<0||tmp+d>9) return ;
    dfs(sum*10+d+tmp,d,cnt+1,tmp+d);
}
int main(){
    cin>>x;
    if(x<100) cout<<x<<endl;
    else{
        for(int i=1;i<=9;i++){
            for(int j=0;j<=9;j++){
                dfs(i*10+j,j-i,2,j);
            }
        }
        sort(vis+1,vis+1+tt);
        for(int i=1;i<=tt;i++){
            if(vis[i]>=x) {
                cout<<vis[i]<<endl;
                break;
            }
        }
    }
	return 0;
}

  • F – Reordering

Given a string \ (s \), find the number of permutations of non empty substrings with the string

Idea: Method 1: \ (DP \) + linear inverse element to find the combination number

\(DP [i] [J]: \) \ (I \) indicates the first \ (I \) of the \ (26 \) letters, \ (J \) indicates that the length of the string substring is \ (J \)
\(VIS [i]: \) represents the number of each letter in the string \ (s \)
List the transfer equation: \ (DP [i + 1] [J] = \ sum {k = 0} ^ {min (J, VIS [i])} DP [i] [J-K] * (J, K) \)
The result is: \ (ANS = \ sum {I = 1} ^ {s.size()}dp [26] [i] \)

When finding the combination number \ ((J, K) \), it is necessary to linearly preprocess the inverse element (the fast power will timeout)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353;
typedef long long ll;
ll fac[N],dp[30][N],inv[N],finv[N];
string str;
int vis[30];
void init(){
    fac[0]=fac[1]=1,inv[1]=1,finv[0]=finv[1]=1;
    for(int i=2;i<=5050;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-mod/i*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll C(ll n,ll m){
    return fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
    init();
    cin>>str;
    int len=str.size();
    dp[0][0]=1;
    for(int i=0;i<len;i++){
        int tt=str[i]-'a';
        vis[tt]++;
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<=len;j++){
            for(int k=0;k<=min(j,vis[i]);k++){
                dp[i+1][j]+=dp[i][j-k]*C(j,k);
                dp[i+1][j]%=mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=len;i++){
        ans+=dp[26][i];
        ans%=mod;
    }
	cout<<ans<<endl;
	return 0;
}

Method 2: generate function + \ (NTT \) (to be changed)