nflsoi 8.12 题解

N个人站成一列，每个人都戴着一顶帽子，颜色为红、黄、绿的一种。第i个人前面有ai个人戴着和他颜色相同的帽子。求出N个人帽子颜色的所有组合方案。答案对1097取模。

搂鱼114514

1006人浏览 · 2025-08-12 17:09:34

搂鱼114514 · 2025-08-12 17:09:34 发布

C.#4939 戴帽子 / AT_sumitb2019_e Colorful Hats 2

题意

~~最有含金量的 C。~~

$N$ 个人站成一列，每个人都戴着一顶帽子，颜色为红、黄、绿的一种。第 $i$ 个人前面有 $a_i$ 个人戴着和他颜色相同的帽子。求出 $N$ 个人帽子颜色的所有组合方案。答案对 $10^9+7$ 取模。

$1≤N≤10^5$ ， $0≤a_i<N$ 。

思路

一开始我还想着这题有一些组合数的规律，阶乘优化组合数都写好了，但是发现无用。

我们发现其实戴什么颜色的帽子并不重要。我们只需要知道，对于当前 $i$ 他可以戴多少种帽子，即有多少种帽子的人数和 $a_i$ 相等。

~~啊就没了？~~ 记得给选定帽子的 $c n t$ 加 $1$ 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9,mod=1e9+7;
ll n,cnt[5];//统计每种颜色人数 
int main()
{
	scanf("%lld",&n);
	ll cur=0,ans=1;
	for(int i=1;i<=n;i++)
	{
		ll x,able=0;
		scanf("%lld",&x);
		for(int j=1;j<4;j++)
		if(x==cnt[j])cur=j,able++;
	//	cout<<able<<" ";
		ans=ans*able%mod;
		cnt[cur]++;
	}
	printf("%lld",ans);
	return 0;
}

D.#11234 极大递增子序列 / TopCoder 7753 Increasing Subsequences

题意

数字序列 $a$ 的子序列是指通过删除 $a$ 中零个或多个元素得到的结果。递增子序列是指子序列中每个元素（除第一个外）都严格大于前一个元素。如果恢复 a 中被删除的任意一个元素都无法使递增子序列变得更长，则称该递增子序列是极大的。

例如，若 $a={1,3,2,6,4,5}$ ，则 ${1,3,4}$ 是一个递增子序列，但不是极大的递增子序列。而 ${1,2,4,5}$ 、 ${1,3,4,5}$ 、 ${1,2,6}$ 和 ${1,3,6}$ 都是极大的递增子序列。

给定一个数字序列的 $a$ ，输出其中包含的极大递增子序列的数量。

$n\le 50$ 。

思路

感觉这题巨简单啊，这 $n$ 也太小了，~~不过怎么有人暴搜做~~。都不用数据结构优化。

考虑计算以 $a_i$ 为结尾的极大递增子序列的个数 $f_i$ ，就是个递推而已。前面什么数可以转移过来呢？如果 $j<i,a_j<a_i$ 而且 $(j, i)$ 没有比 $a_j$ 大的数，此时以 $a_j$ 为结尾的极大递增子序列只有塞一个 $a_i$ 在后面才能成为更长的。

由此我们得到了转移条件。然后获取答案就是看存在哪些数 $a_i$ ，使得 $(i, n]$ 没有比 $a_i$ 大的数，就可以作为极大递增子序列的结尾。

时间复杂度 $O(n^2)$ ，除非给个加强版 $n > 5000$ 才要优化。记得初始化 $f_0=1$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=56;
ll n,a[N];
ll aa[N],nn;
ll f[N],cnt[N];
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		aa[i]=a[i];
	}
	sort(aa+1,aa+n+1);
	nn=unique(aa+1,aa+n+1)-aa-1;
	for(int i=1;i<=n;i++)
	a[i]=lower_bound(aa+1,aa+nn+1,a[i])-aa;//可以不用离散化
	a[0]=-1;//方便f[1]转移
	f[0]=1;
	cnt[0]=0;
	for(int i=1;i<=n;i++)
	{
		ll ma=-114514;
		for(int j=i-1;j>=0;j--)
		{
			if(a[j]>ma&&a[j]<a[i])
			{
				f[i]+=f[j];
				ma=a[j];
			}
		}
	//	cout<<f[i]<<" ";
	}
	ll ans=0;
	for(int i=n;i>=1;i--)
	{
		bool flag=1;
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<a[j])
			{
				flag=0;
				break;
			}
		}
		if(flag)ans+=f[i];
	}
	printf("%lld",ans);
	return 0;
}

E.#15595 守卫树 / AT_abc207_f Tree Patrolling

题意

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1$ 到 $N$ 。第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$ ，且为双向边。

你作为这棵树的主人，打算在若干个顶点（可以为 $0$ 个）上选择放置高桥君，让他来守卫这棵树。被放置在顶点 $x$ 的高桥君会守卫顶点 $x$ 以及所有与 $x$ 直接通过边相连的顶点。

选择放置高桥君的顶点的方式共有 $2^N$ 种。在这些方式中，有多少种方式使得被至少一位高桥君守卫的顶点恰好有 $K$ 个？

请对于 $K=0,1,\ldots,N$ ，分别输出答案，并对 $10^9+7$ 取模。

$\leq N \leq 2000$ ， $\leq u_i < v_i \leq N$ ，给定的图为一棵树。

思路

这题感觉非常有价值，让我再次见识到了这种经典的、考验设状态和推式子能力的树形 dp，好久没有那么顺利写出来这种题过了，估计是今天状态好。

上来先 $f_{i,j,op}$ 表示 $i$ 子树内 $j$ 个被覆盖，其中 $i$ 是否被覆盖（ $o p = 0/1$ ）。不过发现转移的时候不好判断儿子是否存在守卫、使得可以覆盖 $i$ ，因此多加一维：

设 $f_{i,j,op1,op2}$ 表示 $i$ 子树内 $j$ 个被覆盖，其中 $i$ 是否被覆盖 $o p 1 = 0/1$ ， $i$ 是否放置警卫 $o p 2 = 0/1$ 。

对于边 $(u, v)$ 合并子树 $u$ 和 $v$ ，照例枚举 $u$ 子树覆盖数 $x\in[0,siz_u],y\in[0,siz_v]$ ，然后后置合并 $s i z$ 优化，时间复杂度预计 $O(n^2)$ 。于是考虑如何转移到 $f_{u,x+y,op1,op2}$ 。

如果 $u$ 无覆盖，这要求每个 $v$ 都不放置守卫，根据乘法原理合并：
$f_{u,x+y,0,0}\leftarrow f_{u,x,0,0}\times (f_{v,y,0,0}+f_{v,y,1,0})$

如果 $u$ 覆盖了，且 $u$ 处没有守卫？首先 $u$ 可以从没有被覆盖，然后和一个 $v$ 处放置守卫的状态（ $f_{v,y,1,1}$ ）合并：
$f_{u,x+y,1,0}\leftarrow f_{u,x-1,0,0}\times f_{v,y,1,1}$

（减 $1$ 是因为合并后多覆盖了个 $u$ ）

$u$ 也可以已经被前面的某些儿子覆盖了，然后可以合并无差别合并 $v$ 的所有状态——因为 $u$ 没有守卫，所以不会对 $v$ 是否被覆盖造成影响：
$f_{u,x+y,1,0}\leftarrow f_{u,x,1,0}\times(f_{v,y,0,0}+f_{v,y,1,0}+f_{v,y,1,1})$

如果 $u$ 放置了守卫（ $u$ 必然被覆盖），对于没有被覆盖的 $v$ ，可以将其覆盖，于是可以合并：
$f_{u,x+y,1,1}\leftarrow f_{u,x,1,1}\times f_{v,y-1,0,0}$

如果 $v$ 已经被覆盖，也不会对 $v$ 造成影响，直接合并即可：
$f_{u,x+y,1,1}\leftarrow f_{u,x,1,1}\times (f_{v,y,1,0}+f_{v,y,1,1})$

为了防止合并影响状态 $x + y$ ，可以选择倒序枚举 $x, y$ ，也可以开一个辅助数组 $t e m$ 。不过记得合并回去哦！

答案就是 $f_{1,k,0,0}+f_{1,k,1,0}+f_{1,k,1,1}$ 。记得初始化 $f_{i,j,0,0}=f_{i,j,1,1}=1$ ，这是可以开始就决定的，至于 $i$ 被其他节点覆盖则无法开始就决定，故不管。记得勤取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4056,mod=1e9+7;
ll n;
struct edge
{
	ll to,next;
}e[N<<1];
ll idx,head[N];
void addedge(ll u,ll v)
{
	idx++;
	e[idx].to=v;
	e[idx].next=head[u];
	head[u]=idx;
}
ll siz[N],f[N][N][2][2];
void dfs(ll u,ll fa)
{
	siz[u]=1;
	f[u][0][0][0]=1;
	f[u][1][1][1]=1;
	ll tem[N][2][2];
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int x=0;x<=siz[u]+siz[v];x++)
		tem[x][0][0]=tem[x][1][0]=tem[x][1][1]=0;
		for(int x=0;x<=siz[u];x++)
		{
			for(int y=0;y<=siz[v];y++)
			{
				//0 0
				tem[x+y][0][0]=(tem[x+y][0][0]+f[u][x][0][0]*(f[v][y][1][0]
															+f[v][y][0][0])%mod)%mod;//u没人管 
				//1 0
				tem[x+y][1][0]=(tem[x+y][1][0]+f[u][x][1][0]*((f[v][y][0][0]
																+f[v][y][1][0])%mod
																+f[v][y][1][1])%mod)%mod;//u不驻前面覆盖 
				if(x>=1)
				tem[x+y][1][0]=(tem[x+y][1][0]+f[u][x-1][0][0]*f[v][y][1][1]%mod)%mod;//u不驻前无覆盖 
				//1 1
				tem[x+y][1][1]=(tem[x+y][1][1]+f[u][x][1][1]*((f[v][y][1][0]
																+f[v][y][1][1])%mod
																+f[v][y-1][0][0])%mod)%mod;//u驻v覆盖 
			
			}
		}
		siz[u]+=siz[v];
		for(int x=0;x<=siz[u];x++)
		{
			f[u][x][0][0]=tem[x][0][0];
			f[u][x][1][0]=tem[x][1][0];
			f[u][x][1][1]=tem[x][1][1];
		}
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<n;i++)
	{
		ll u,v;
		scanf("%lld%lld",&u,&v);
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,0);
	for(int k=0;k<=n;k++)
	printf("%lld\n",((f[1][k][0][0]+f[1][k][1][0])%mod+f[1][k][1][1])%mod);
	return 0;
}

F.#6506 计算 / BZOJ2506 calc

题意

给一个长度为 $n$ 的非负整数序列 $a_1,a_2,...,a_n$ 。现有 $m$ 个询问，每次询问给出 $l, r, p, k$ ，问满足 $i\in[l,r]$ 且 $a_i\bmod p=k$ 的 $i$ 的个数。

$1\le n,m\le 10^5$ ， $\forall a_i\le 10^4$ ，每个询问 $1\le p\le 10^4$ ， $0\le k<p$ 。

思路

机房大佬一眼看出这是根号分治呢……

这是因为，分出小除数和大除数之后，小除数可以用一些小技巧存答案（空间不会爆），大除数可以枚举值域内每一个 $x\bmod p=k$ 的 $x$ ， $x$ 可以表示为 $k+pt,t\in\mathbb{Z}$ ，直接跳效率同样高！取大小除数分界 $\sqrt{10000}=100$ ，这样维持了“根号平衡”，小除数处理方法就可以采用适用于较小数的简易算法。

记 $cnt_{p,k}$ 表示 $\bmod p=k$ 的数的个数，易知加入一个 $a_i$ 时，对于每个除数 $j$ ， $cnt_{j,a_i\bmod j}$ 个数加 $1$ 。

对于给出的询问，我们发现直接枚举 $[l, r]$ 非常费时间，而且还要枚举询问，除非您对 $n$ 个数分块做到 $O(m\sqrt{n})$ ，一点操作空间都没有了；而且处理左右块之间的 $c n t$ 甚至开不下……

于是考虑扫描线。因为询问的个数符合前缀的性质，于是把询问拆成 $1\sim l-1$ 的个数和 $1\sim r$ 的个数。就可以 $a_{1\sim n}$ 直接 $O (n)$ 扫过去。然后根据上面的方法，分大小除数处理答案即可。

~~话说 nflsoj 可不可以加快评测速度？光是等待提交都等死我了，成为我无法调完 G 题的祸根，也可能只是我的考试策略问题……~~

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3e5+9,B=102;
ll n,m;
ll a[N];
struct term
{
	ll id,x,p,y,val;
};
ll cnt[B][B],buc[N],ans[N];
vector<term>P[N];
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	ll tot=0;
	for(int i=1;i<=m;i++)
	{
		ll l,r,p,y;
		scanf("%lld%lld%lld%lld",&l,&r,&p,&y);
		P[l-1].push_back((term){i,l-1,p,y,-1});
		P[r].push_back((term){i,r,p,y,1});
	}
	ll pos=1;
	for(int i=1;i<=n;i++)
	{
		buc[a[i]]++;
		for(int j=1;j<=100;j++)
		cnt[j][a[i]%j]++;
		for(auto x:P[i])
		{
			if(x.p<=100)ans[x.id]+=x.val*cnt[x.p][x.y];
			else
			{
				for(int j=x.y;j<=10000;j+=x.p)
				ans[x.id]+=x.val*buc[j];
			}
		}
	}
	for(int i=1;i<=m;i++)
	printf("%lld\n",ans[i]);
	return 0;
}

G.#4571 旅行家 / 洛谷 P7924 旅行家

题意

题目传送门，建议前往洛谷仔细阅读题意、样例和配图。

思路

B 组的同学说这是诈骗题，因为这是他们的 T1，不过确实诈骗，我缺的是时间——这是我们的 T7。

例如下图，出现两个边双联通分量。我们可以在一个“旅游季”走多次不同的路径，把这些 edcc 上的点全都遍历完。（这里一定要好好理解题意）

于是图上会出现很多 edcc，缩点会缩成一棵树。
在这里插入图片描述
比如从 $1$ 走到 $15$ ，会经过红、浅蓝、橙、米黄 $4$ 个 edcc，这些 edcc 上的所有点权之和，就是询问 $x = 1, y = 15$ 的贡献；又如从 $9$ 走到 $14$ ，会经过橙、深蓝、褐 $3$ 个 edcc。

因为是所有询问路径的交集，于是我们想要标记这些走过的连通块，我们可以使用树上差分，标记每个 edcc（缩点建树）的经过次数，如果次数 $> 0$ ，整个 edcc 的点权和就对答案贡献。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+9,M=2e6+9;
int n,m,Q;
int a[N];
struct bian
{
	int u,v;
}b[M];
struct edge
{
	int to,next;
}e[M<<1];
int idx=1,head[N];
void addedge(int u,int v)
{
	idx++;
	e[idx].to=v;
	e[idx].next=head[u];
	head[u]=idx;
}
int dfn[N],low[N],ti;
int stk[N],top;
int edcno[N],edccnt,edcsum[N];
void tarjan(int u,int from)
{
	dfn[u]=low[u]=++ti;
	stk[top++]=u;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		else if(i!=(from^1))low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		edccnt++;
		while(1)
		{
			int tem=stk[--top];
			edcno[tem]=edccnt;
			edcsum[edccnt]+=a[tem];
			if(u==tem)break;
		}
	}
}
vector<int>G[N];
int dep[N],f[N][20];
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=19;i++)
	f[u][i]=f[f[u][i-1]][i-1];
	for(auto v:G[u])
	{
		if(v==fa)continue;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)
	if(dep[x]-(1<<i)>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int cf[N],ans;
void cal(int u,int fa)
{
	for(auto v:G[u])
	{
		if(v==fa)continue;
		cal(v,u);
		cf[u]+=cf[v];
	}
	if(cf[u]>0)ans+=edcsum[u];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
		b[i]=(bian){u,v};
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i,0);
	for(int i=1;i<=m;i++)
	{
		int eu=edcno[b[i].u],ev=edcno[b[i].v];
		if(eu==ev)continue;
		G[eu].push_back(ev);
		G[ev].push_back(eu);
	}
	dfs(1,0);
	scanf("%d",&Q);
	while(Q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int eu=edcno[x],ev=edcno[y];
		int LCA=lca(eu,ev);
		cf[eu]++;
		cf[ev]++;
		cf[LCA]--;
		cf[f[LCA][0]]--;
	}
	cal(1,0);
	printf("%d",ans);
	return 0;
}

2048 AI社区

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

更多推荐

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

2048 AI社区

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

2048 AI社区

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

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