AtCoder Beginner Contest 353（A~E)

本文主要是介绍AtCoder Beginner Contest 353（A~E)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

A Buildings

1.基本思路：

• 模拟

2.代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n;void solve(){cin>>n;int pre;for(int i=1;i<=n;i++){int x; cin>>x;if(i==1) pre=x;else if(x>pre){cout<<i;return;}}cout<<-1;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

B - AtCoder Amusement Park

1.基本思路：

• 模拟，理解题意就ok了

2.代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,k,a[N];
int cnt=1;void solve(){cin>>n>>k;int now=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]+now<=k) now+=a[i];else{now=a[i];++cnt;}}cout<<cnt;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

C - Sigma Problem

1.基本思路：

• 思维
• 发现规律，两数之和小于1e8直接相加即可，两数之和大于1e8需要减去一个1e8,再累加到答案
• 我们发现数组的顺序不影响答案，排序一下
• 然后二分找到第一个与当前第i个数相加大于1e8的位置，该位置之前的数与当前数字相加均小于1e8，这里前缀和与处理一下。
• 该位置及之后的位置，相加均大于1e8，需要减去（i-pos）个1e8。

2.代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 3e5+10, INF = 0x3f3f3f3f;
const int mod = 1e8;
int n,a[N],sum[N];
int ans=0;void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n); 
//	for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];for(int i=2;i<=n;i++){int x=mod-a[i];int pos=lower_bound(a+1,a+1+i,x)-a;if(pos>i) pos--;
//		cout<<x<<' '<<pos<<endl;ans+=sum[pos-1]+(i-1)*a[i];ans+=sum[i-1]-sum[pos-1]-(i-pos)*mod;}cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

D - Another Sigma Problem

1.基本思路：

• 思维题
• 第i个数需要加上（i-1）次，因为受前面数的影响
• 而当数与后面的数字连接显然跟后面数字的位数有关
• 所以累加当前数字乘以10的位数次方，位数是后面每个数字的位数

2.代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 2e5+10, INF = 0x3f3f3f3f;
const int mod = 998244353;
int n,a[N],ans;
int dp[N][12]; //dp[i][j]表示第i个数之前(包含i)长度为j的数的个数 
int cnt[N]; int qpow(int a,int b){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];int k=a[i],len=0;while(k){len++;k/=10;}cnt[len]++;dp[i][len]++;}for(int i=1;i<=n;i++){for(int j=1;j<=10;j++){dp[i][j]+=dp[i-1][j];}}
//	for(int i=1;i<=n;i++) cout<<cnt[i]<<' '; cout<<endl;for(int i=1;i<=n;i++){ans=(ans+a[i]*(i-1)%mod)%mod;for(int j=1;j<=10;j++){ //长度为j int num=cnt[j]-dp[i][j]; //i之后长度为j的数的个数 
//			cout<<"***"<<cnt[j]<<' '<<dp[i][j]<<' '<<num<<endl;ans=(ans+a[i]%mod*qpow(10,j)%mod*num%mod)%mod;}} cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

E - Yet Another Sigma Problem

1.基本思路：

• 字典树Trie的模板题
• 字典树每个字母出现的次数对答案的贡献是C(n,2)

2.代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N =3e5+10, INF = 0x3f3f3f3f;
const int mod = 998244353;
int n,ans;
int ch[N][26],idx; 
map<int,int> mp;void insert(string s){int p=0;for(int i=0;i<s.size();i++){int j=s[i]-'a';if(!ch[p][j]) ch[p][j]=++idx;mp[ch[p][j]]++;p=ch[p][j];}
}void solve(){cin>>n;for(int i=1;i<=n;i++){string s; cin>>s;insert(s);}for(auto i:mp) ans+=i.se*(i.se-1)/2;cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

这篇关于AtCoder Beginner Contest 353（A~E)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---