nflsoi 7.25 题解

搂鱼114514

722人浏览 · 2025-07-31 22:19:47

搂鱼114514 · 2025-07-31 22:19:47 发布

C.#16047数列 / AT_abc265_d Iroha and Haiku

题意

给定一个长度为 $N$ 的数列 $A=(A0,…,AN−1)A=(A_0,\ldots,A_{N-1})$ 。
请判断是否存在整数四元组 $(x, y, z, w)$ ，满足以下所有条件：

$\leq x < y < z < w \leq N$
$Ax+Ax+1+…+Ay−1=PA_x + A_{x+1} + \ldots + A_{y-1} = P$
$Ay+Ay+1+…+Az−1=QA_y + A_{y+1} + \ldots + A_{z-1} = Q$
$Az+Az+1+…+Aw−1=RA_z + A_{z+1} + \ldots + A_{w-1} = R$

$\leq N \leq 2 \times 10^5$ ， $\leq A_i \leq 10^9$ ， $\leq P, Q, R \leq 10^{15}$ ，输入中的所有数值均为整数。

思路

像先用单调指针找到 $x, y$ ，然后向后推着做，无奈只有 92pts，原因是可能存在很多对 $(x, y)$ ， $y$ 的不固定会影响后面找 $z$ 。遂换更暴力优美的做法。

考虑到前缀和各自不同，因此考虑所有的前缀和 $s_i$ 扔进 set 里面，枚举一个存在的前缀和 $s_0$ ，并判断 $s_0+p$ ， $s_0+p+q$ ， $s_0+p+q+r$ 是否存在即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,p,q,r;
ll i,x,sum;
set<ll>S;
int main()
{
	S.insert(0);
	scanf("%lld%lld%lld%lld",&n,&p,&q,&r);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		sum+=x;
		S.insert(sum);
	}
	for(auto x:S)
	{
		if(S.find(x+p)!=S.end()&&S.find(x+p+q)!=S.end()&&S.find(x+p+q+r)!=S.end())
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

E.#1909 种橙子 / 洛谷 P7306 Strah

题意

Mirko 最害怕的是寻找合适的土地来种植草莓。他的土地可以用一个 $\times M$ 的矩阵来表示。土地中有些田地适合种植草莓，而有些不适合，因为那里杂草丛生。

Mirko 正在寻找一块合适矩形。当土地中有一块矩形区域包含的所有田地均适合种植草莓，则该矩形被称为合适矩形。

Mirko 还对所有田地的潜力值感兴趣。一块田地的潜力值定义为包含该田地的合适矩形的个数。

求 Mirko 所有田地的潜力值之和。

$\le N,M \le 2000$ 。

思路

考虑枚举 $i$ 为底，枚举 $j$ 列为右端，计算每个 $j$ 新增的贡献。

维护每个点可以无障碍向上延伸的长度 $up_{i,j}$ 。每一行 $i$ ，用单调栈维护单调递增的 $u p$ 、加入新决策点 $j$ ，形成形似阶梯状从而计算贡献：
在这里插入图片描述
不会算重吗？这题就是要算重！因为要计算包含每个格子的矩形的个数总和。

不过使用单调栈的做法似乎接近 $O(n^3)$ ，因为题目没有出完全递增的 $u p$ 来卡我。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2003;
ll n,m;
ll up[N][N];
char c[N][N];
ll stk[N],top;
ll sum(ll x)
{
	return x*(x+1)/2;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			if(c[i][j]=='.')up[i][j]=up[i-1][j]+1;
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)//以i行为底 
	{
		stk[top=1]=0;
		for(int j=1;j<=m;j++)//计算j列上贡献 
		{
			while(top>1&&up[i][stk[top]]>=up[i][j])top--;
			stk[++top]=j;
			for(int k=top;k>=2;k--)
			ans+=(sum(j-stk[k-1])-sum(j-stk[k]))*sum(up[i][stk[k]]);
		}
	}
	printf("%lld",ans);
	return 0;
}

F.#16866 LIS 升级 / AT_arc159_d LIS 2

题意

有一个数列 $X$ ，初始时 $X$ 为空。
高桥君依次进行了 $i=1,2,…,Ni=1,2,\ldots,N$ 的如下操作：

将 $li,li+1,…,ril_i,l_i+1,\ldots,r_i$ 按顺序依次添加到 $X$ 的末尾。

请你求出操作结束后， $X$ 的狭义单调递增子序列的最大长度。

$1≤N≤2×1051\leq N\leq 2\times 10^5$ ， $1≤li≤ri≤1091\leq l_i\leq r_i\leq 10^9$ 。

思路

很经典的题目。设 $f_i$ 表示，以第 $i$ 次操作的 $r_i$ 为结尾的最长子序列长度。那么：
$fi=max⁡{fj+ri−li+1(rj<li),fj+ri−rj(li≤rj<ri)}f_i=\max\{f_j+r_i-l_i+1(r_j<l_i),f_j+r_i-r_j(l_i\le r_j< r_i)\}$

区间求最大值考虑用线段树维护， $max⁡\max$ 的左右边，我们分别在 $1,l_i)$ 查询最大 $f_j$ 、在 $l_i,r_i)$ 上查询最大 $f_j-r_j$ ，然后在决策点 $r_i$ 维护新的 $f_i$ 和 $f_i-r_i$ 。

因为 $l, r$ 的值域很大，所以要离散化。具体细节见代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=4e5+9,inf=3e14;
struct SegT
{
	struct node
	{
		ll ma;
	}T[N<<2];
	void pushup(ll u)
	{
		T[u].ma=max(T[ls].ma,T[rs].ma);
	}
	void build(ll u,ll l,ll r)
	{
		T[u].ma=-inf;
		if(l==r)return;
		ll mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void modify(ll u,ll l,ll r,ll x,ll k)
	{
		if(l==r)
		{
			T[u].ma=k;
			return;
		}
		ll mid=(l+r)>>1;
		if(x<=mid)modify(ls,l,mid,x,k);
		if(x>mid)modify(rs,mid+1,r,x,k);
		pushup(u);
	}
	ll query(ll u,ll l,ll r,ll ql,ll qr)
	{
		if(ql>qr||qr<l||r<ql)return -inf;
		if(ql<=l&&r<=qr)return T[u].ma;
		ll mid=(l+r)>>1,ret=-inf;
		if(ql<=mid)ret=max(ret,query(ls,l,mid,ql,qr));
		if(qr>mid)ret=max(ret,query(rs,mid+1,r,ql,qr));
		return ret;
	}
}A,B;
ll n;
ll l[N],r[N],L[N],R[N],len[N];
ll aa[N],nn,nnn;
ll f[N]; 
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&l[i],&r[i]);
		aa[++nn]=l[i];
		aa[++nn]=r[i];
		len[i]=r[i]-l[i]+1;
	}
	sort(aa+1,aa+nn+1);
	nnn=unique(aa+1,aa+nn+1)-aa;
	A.build(1,1,nnn);
	B.build(1,1,nnn);
	for(int i=1;i<=n;i++)
	{
		L[i]=lower_bound(aa+1,aa+nnn+1,l[i])-aa;
		R[i]=lower_bound(aa+1,aa+nnn+1,r[i])-aa;
	}
	for(int i=1;i<=n;i++)
	{
		f[i]=max(len[i],max(A.query(1,1,nnn,1,L[i]-1)+len[i],B.query(1,1,nnn,L[i]+1,R[i]-1)+r[i]));
		A.modify(1,1,nnn,R[i],f[i]);
		B.modify(1,1,nnn,R[i],f[i]-r[i]); 
	}
	ll ans=-inf;
	for(int i=1;i<=n;i++)
	ans=max(ans,f[i]);
	printf("%lld",ans);
	return 0;
}

G.#4256 序列

H.#3322 Wifi 发射器 / 洛谷 P5969 POI2016 Nadajniki

有缘再补。

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

【电商剪辑如何人效提升效率？分镜素材库智能匹配替代人工繁琐剪辑】

2048 AI社区

小白实操 OpenClaw2.7.9，5 分钟完成本地 AI 环境部署指南

2048 AI社区

AI框架的资源管理：多模型适配、负载均衡、故障隔离

本文探讨了AI应用在多模型场景下的运维挑战及解决方案。核心问题是单点接入模型服务存在的高风险，以及多模型管理带来的复杂性。文章提出两大设计思路：通过统一接口抽象层屏蔽厂商差异，业务代码仅需调用资源SN；采用均衡组模式实现负载均衡和故障隔离，确保服务高可用。具体实现包括：资源项与均衡组两种组织形式、失败计数隔离机制、维度一致的Embedding资源管理、统一VDB接口等。最终目标是建立生产级稳定的A