打卡信奥刷题（2739）用C++实现信奥题 P3560 [POI 2013] LAN-Colorful Chain

题目P3560要求统计满足特定条件的子串数量。给定一个长度为n的序列和m个条件（每个条件包含颜色c_i及其出现次数l_i），需要找出所有满足以下条件的连续子串：1)子串中每个c_i恰好出现l_i次；2)子串不包含条件中未出现的其他颜色。输入包含序列长度n、条件数m，序列元素以及各条件的颜色和出现次数。输出满足条件的子串总数。

rogeliu

761人浏览 · 2026-01-24 11:42:12

rogeliu · 2026-01-24 11:42:12 发布

P3560 [POI 2013] LAN-Colorful Chain

题目描述

Little Bytie loves to play with colorful chains.

He already has quite an impressive collection, and some of them he likes more than the others.

Each chain consists of a certain number of colorful links.

Byteasar has noticed that Bytie’s sense of aesthetics is very precise.

It turns out that Bytie finds a contiguous fragment of a chain nice if it contains exactly $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ links of color $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ links of color $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ links of color $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ , and moreover it contains no links of other colors.

A chain’s appeal is its number of (contiguous) fragments that are nice.

By trial and error, Byteasar has determined the values $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ and $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ .

Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

给定一个长度为 $n$ 的序列 ${a\}$ 和 $m$ 个条件（每个条件中包含键 $c_i$ 和值 $l_i$ ），要求找出满足下列条件的子串的数量并输出：

对于 $m$ 个条件中存在的 $c_i$ （ $1≤i≤n1\le i\le n$ ），子串中包含恰好 $l_i$ 个 $c_i$ ；
对于 $m$ 个条件中不存在的键值，子串中不包含它。

输入格式

The first line of the standard input gives two integers, $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ and $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ( $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ), separated by a single space.

These are the length of the chain and the length of a nice fragment’s description.

The second line gives $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ integers, $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ( $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ), separated by single spaces.

The third line gives $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ integers, $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ( $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ , $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ for $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ), also separated by single spaces.

The sequences $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ and $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ define a nice fragment of a chain - it has to contain exactly $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ links of color $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ .

The fourth line gives $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ integers, $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ( $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ ), separated by single spaces, that are the colors of successive links of the chain.

In tests worth 50% of total points the constraint $外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传$ holds in addition.

先输入 $n$ 和 $m$ ，再输入 $m$ 个条件的 $l_i$ ，然后输入 $m$ 个条件的 $c_i$ ，最后输入 $a_i$ 。

输出格式

Your program is to print a single integer, the number of nice contiguous fragments in the chain, to the first and only line of the standard output.

输出一行一个整数，表示满足条件的子串数量。

输入输出样例 #1

输入 #1

7 3
2 1 1
1 2 3
4 2 1 3 1 2 5

输出 #1

说明/提示

数据范围：

对于 $100%100\%$ 的数据， $1≤m≤n≤1061\leq m\leq n \leq 10^6$ ， $1≤ai,li,ci≤n1\leq a_i,l_i,c_i\leq n$ 。

C++实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const unsigned long long mod=23333333333333333,bas=131;
unsigned long long hsh[1000009];
int cnt[1000009],num[1000009];
unsigned long long goal,noww;
int n,m,rd,l=1,r,ans,maxx;
int main ()
{
	scanf("%d%d",&n,&m);
	hsh[0]=1;
	for(int i=1;i<=n;i++)
		hsh[i]=hsh[i-1]*bas%mod;
	for(int i=1;i<=m;i++)
		scanf("%d",&cnt[i]),maxx+=cnt[i];//记录目标串的长度
	for(int i=1;i<=m;i++)
		scanf("%d",&rd),goal+=hsh[rd]*cnt[i];//构建目标串
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]);
	for(int i=1;i<=n;i++)
	{
		noww+=hsh[num[i]];//修改当前串
		if(++r-l+1>maxx) noww-=hsh[num[l++]];//移动左右端点
		if(noww==goal) ans++;
	}
	printf("%d",ans);
	return 0;
}