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