(AtCoder Beginner Contest 330) 题解

一、前言

有一次做出 $6$ 道题，~~痴心妄想~~ 梦想能够稳定 $6$ 题。

二、题解

言归正传，开始讲题。

第 A 题 Buildings

很简单的一道题，按照模拟即可。——有趣的东西：我为什么吃罚时？因为 $y d$ 翻译出锅了。（把"左边数第一个"翻译成"左边的一个"）

代码：

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
	int n; cin>>n;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		if (i!=1&&a[i]>a[1]){
			cout<<i; return 0;
		}
	}cout<<-1;
}

第 B 题 AtCoder Amusement Park

也是一道语法题。可以设定 $s u m$ 为当前排队人数。如果剩余座位不够，就清空，然后在加上人数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int sum=0,cnt=0;
int main(){
	int n,x,k; cin>>n>>k;
	while (n--){
		cin>>x; //cout<<sum<<"\n";
		if (sum+x>k) sum=0,cnt++;
		sum+=x;
	}cout<<cnt+1;
}

第 C 题 Sigma Problem

题目说 不要对答案取余！

我们可以发现：答案是所有任意两个数加起来的和 - 需要取余的数对数 $×108 \times10^8$ 。

可以使用二分或双指针解决问题。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[300010],n;
signed main(){
	cin>>n; int sum=0;
	for (int i=1; i<=n; i++) cin>>a[i]; 
	sort(a+1,a+n+1);
	int r=n+1,ans=0;
	for (int l=1; l<=n; l++){
		if (l>=r) r++;
		while (l<r-1&&a[l]+a[r-1]>=100000000) r--;
		ans-=100000000*(n-r+1); ans+=a[l]*(l-1)+sum; sum+=a[l];
	}cout<<ans;
}

第 D 题 Another Sigma Problem

又一个求和问题（下面左边的加法表示拼接）。

$A+B=A\times log_{10}B+B$

可以使用前缀和解决问题。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int a[300010],n;
int ask(int x){
	int ans=1;
	while (x) x/=10,ans*=10;
	return ans;
}signed main(){
	cin>>n; int sum=0,ans=0,sumx=0;
	for (int i=1; i<=n; i++) cin>>a[i]; 
	for (int i=n; i>=1; i--){
		ans=(ans+sum+sumx*a[i]%mod)%mod;
		sum+=a[i]; sumx+=ask(a[i]);
		sum%=mod; sumx%=mod;
	}cout<<ans;
}

第 E 题 Yet Another Sigma Problem

又双叒叕是一道求和问题。

我们可以把一个长度为 $5$ 的共同最长前缀拆成 $5$ 个共同前缀（前缀的前缀还是前缀）。

如何求共同前缀的个数？可以使用 $M a p$ 记录前缀字符串。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
string s[300010];
map <string,int> mp;
signed main(){
	int n,ans=0; cin>>n;
	for (int i=1; i<=n; i++){
		cin>>s[i]; string now="";
		for (int j=0; j<s[i].size(); j++){
			now.push_back(s[i][j]);
			ans+=mp[now]; mp[now]++;
		}
	}cout<<ans;
}

TLE！怎么办？

智商不够，数据结构来凑！

$M a p$ 挂掉了，看来只有 $T r i e$ 了！（详见算法笔记）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
string s[300010];
int tr[300010][26],tot;
int num[300010];
signed main(){
	int n,ans=0; cin>>n;
	for (int i=1; i<=n; i++){
		cin>>s[i]; int id=0;
		for (int j=0; j<s[i].size(); j++){
			int to=s[i][j]-'a';
			if (!tr[id][to]){
				tr[id][to]=++tot;
			}id=tr[id][to];
			ans+=num[id]; num[id]++;
		}
	}cout<<ans;
}

第 G 题 Merchant Takahashi

题目说，有 $n$ 次活动，每次活动都在一个点上举行。参加活动会赚钱，移动到相邻的点会花路费。

可以使用 $D p$ ：

int dp[i];//dp[i]表示在i点最多能赚到多少钱

$dp_{i}=dp_{j}+w_{j}-|i-j|\times c$

很显然，超时。那么可以使用线段树进行优化。

代码：

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define ls(n) 2*n
#define rs(n) 2*n+1
#define int long long
int a[800010],b[800010],m;
struct Seg_tree{
	void change(int now){
		a[now]=max(a[ls(now)],a[rs(now)]);
		b[now]=max(b[ls(now)],b[rs(now)]);
	}void update(int now,int l,int r,int id,int val){
		if (l==r){
			a[now]=val+id*m,b[now]=val-id*m; 
			return ;
		} if (id<=mid) update(ls(now),l,mid,id,val);
		else update(rs(now),mid+1,r,id,val);
		change(now);
	}int query1(int now,int l,int r,int ql,int qr){
		if (ql<=l&&r<=qr) return a[now];
		if (qr<=mid) return query1(ls(now),l,mid,ql,qr);
		if (ql>mid) return query1(rs(now),mid+1,r,ql,qr);
		return max(query1(ls(now),l,mid,ql,mid),query1(rs(now),mid+1,r,mid+1,qr));
	}int query2(int now,int l,int r,int ql,int qr){
		if (ql<=l&&r<=qr) return b[now];
		if (qr<=mid) return query2(ls(now),l,mid,ql,qr);
		if (ql>mid) return query2(rs(now),mid+1,r,ql,qr);
		return max(query2(ls(now),l,mid,ql,mid),query2(rs(now),mid+1,r,mid+1,qr));
	}
}t; 
signed main(){
	int n,k,mx=0; cin>>n>>m>>k;
	for (int i=1; i<=n; i++) t.update(1,1,n,i,-(i-1)*m);
	for (int i=1; i<=k; i++){
		int id,k; cin>>id>>k;
		int l=max(1ll,id-k/m),r=min(n,id+k/m);
		int num=max(t.query1(1,1,n,1,id)-id*m,t.query2(1,1,n,id,n)+id*m)+k;
		t.update(1,1,n,id,num); mx=max(mx,num);
	}cout<<mx;
	return 0;
}