首页 > 代码库 > luoguP2267 琪琪的项链
luoguP2267 琪琪的项链
题目：http://www.luogu.org/problem/show?pid=2267
题解：这题略吊。
看了之后发现不能用组合数学直接得出公式，然后如果直接暴力也不知道如何去排除两个颜色序列相同的情况。
然后去膜拜题解
---------------------------------------------------------------------------------------------------
令f[i]表示结尾 i 必选的DIY方法的种数。所有珠子颜色不一样的话：f[i] = f[0] + f[1] + ... + f[i-1]
对于颜色不同的话，假设珠子i颜色为c，颜色c在i之前出现的位置为j，那么在式子：f[i] = f[0] + f[1] + ... + f[i-1] 中，我们多算了f[0] + f[1] + ... + f[j-1]。
所以对于此时的f[i] = f[j] + ... +f[i-1]，最后 ans = sum(f[i] , 1 <= i <= n)。
----------------------------------------------------------------------------------------------------
说到这里应该就很明显了，搞个前缀和就行了。
这种与颜色序列有关的题貌似记录一下该颜色上一次出现的位置是个不错的想法？@HH的项链 @采花
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<string> 7 #include<set> 8 #include<map> 9 #include<vector>10 #include<algorithm>11 #include<queue>12 #define for0(i,n) for(int i=0;i<=n;i++)13 #define for1(i,n) for(int i=1;i<=n;i++)14 #define for2(i,x,y) for(int i=(x);i<=(y);i++)15 #define for3(i,y,x) for(int i=(y);i>=(x);i--)16 #define maxn 500000+10017 using namespace std;18 inline int read()19 {20 int x=0,f=1;char ch=getchar();21 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}22 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}23 return x*f;24 } 25 int n,m,tot,f[maxn],g[maxn],a[maxn],b[maxn],c[maxn],pre[maxn],head[maxn];26 inline bool cmp(int x,int y){return a[x]<a[y];}27 int main()28 {29 freopen("input.txt","r",stdin);30 freopen("output.txt","w",stdout);31 n=read();m=read();32 for1(i,n)a[i]=read(),c[i]=i;33 sort(c+1,c+n+1,cmp);34 for1(i,n)35 {36 if(i==1||a[c[i]]!=a[c[i-1]])tot++;37 b[c[i]]=tot;38 }39 for1(i,n)40 {41 pre[i]=head[b[i]];head[b[i]]=i;42 }43 g[0]=f[0]=1;44 for1(i,n)45 {46 f[i]=g[i-1];if(pre[i])f[i]=(f[i]-g[pre[i]-1]+m)%m;47 g[i]=(g[i-1]+f[i])%m;48 }49 printf("%d\n",g[n]-1);50 return 0;51 }
luoguP2267 琪琪的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。