# AtCoder Beginner Contest 234(AtCoder Beginner Contest 234)-其他

## 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

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!

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

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

$$dp[i][j]:$$ $$i$$表示$$26$$个字母中前$$i$$个字母，$$j$$表示字符串子串长度为$$j$$
$$vis[i]:$$ 表示字符串$$S$$中每个字母的个数

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;
}



————————

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)