2024/9/26

Redamancy_Lydic / 2024-09-26 / 原文

[ABC351G] Hash on Tree

首先暴力的 $DP$ 很简单。

然后尝试每次操作在链上修改，看看能不能卡过去。结果写了我 30min 还是被数据卡了。

于是只能去写正解的 $DDP$。

先是 131 行的树剖，又是 62 行的线段树维护矩乘。然后在纸上推了推矩乘，胡了个转移方程（我绝对不会说我推错了后去看了题解）。

然后调了 76min 调过了。

[ABC130D] Enough Array

因为下午还有模拟赛，所以果断放弃难题去水 ABC。

一个简单的二分前缀和查找区间个数。

小学不等式一推过掉（我爱水题）。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=2e5+10;
const int inf=-1e9-7;
int n,k;
int sum[maxn],a[maxn],ans;
signed main()
{
#ifdef Lydic
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
// #else
// 	freopen("defense.in","r",stdin);
// 	freopen("defense.out","w",stdout);
#endif
    cin>>n>>k;
	for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		int pos=lower_bound(sum+i,sum+n+1,sum[i-1]+k)-sum;
		ans+=(n-pos+1);
	}
	cout<<ans;
    return 0;
}

[ABC127D] Integer Cards

首先贪心选择最小值更新。

发现直接更新的话复杂度巨大。

于是加上小技巧，把操作离线后排个序再更新保证每个元素的更新次数。

然后就过了。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=2e5+10;
const int inf=-1e9-7;
int n,m;
struct no
{
	int b,c;
	inline friend bool operator < (no x,no y)
	{
		return x.c>y.c;
	}
}a[maxn];
priority_queue<int,vector<int>,greater<int> > q;
signed main()
{
#ifdef Lydic
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
// #else
// 	freopen("defense.in","r",stdin);
// 	freopen("defense.out","w",stdout);
#endif
    cin>>n>>m;
	for(int i=1;i<=n;i++)q.push(read());
	for(int i=1;i<=m;i++)a[i]={read(),read()};
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++)
	{
		while(a[i].b)
		{
			int u=q.top();
			if(u>=a[i].c)break;
			q.pop();
			u=a[i].c;
			q.push(u);
			a[i].b--;
		}
	}
	int ans=0;
	while(!q.empty())ans+=q.top(),q.pop();
	cout<<ans;
    return 0;
}

[ABC122C] GeT AC

这不一眼前缀和？

写完以后发现样例假了。

但是简单思考发现只有当 AC 两个字符分别在 $l-1$ 和 $l$ 的位置上的时候才会出错。

于是加上特判，轻松过掉。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=2e5+10;
const int inf=-1e9-7;
int n,Q;
char s[maxn];
int sum[maxn];
signed main()
{
#ifdef Lydic
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
// #else
// 	freopen("defense.in","r",stdin);
// 	freopen("defense.out","w",stdout);
#endif
    cin>>n>>Q;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='C'&&s[i-1]=='A')sum[i]=sum[i-2]+1;
		else sum[i]=sum[i-1];
	}
	while(Q--)
	{
		int l=read(),r=read();
		int ans=sum[r]-sum[l-1];
		if(s[l-1]=='A'&&s[l]=='C')ans--;
		printf("%lld\n",ans);
	}
    return 0;
}