[关闭]
@ysner 2018-05-26T06:38:30.000000Z 字数 1507 阅读 1823

刷漆

DP


题面

你的花园里有一个由块排成一条直线的木板组成的栅栏,木板从左到右依次标号

块木板中,有块木板前面放着一桶油漆。油漆有不同的颜色,每种颜色可以由一个大写字母表示()。而你要求用他的油漆刷子给栅栏刷上油漆。

已知 Czy 会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后,他开始随机地沿着栅栏走,他不会走出栅栏的范围。随机地走表示会沿着他选择的方向一直走,然后随机在任何时候改变方向。沿着栅栏走只有两个方向,向前和向后。
你发现刷油漆的过程总是符合下列规则:

已知木板可以被多次刷上油漆,每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候,才能停下来(当然他也可以继续刷到他想停下来为止)。

你看着在栅栏前来回舞动,突然想知道停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时,两种油漆方案被视为是不同的。

解析

完美诠释了越长的题目越简单
首先头尾连续的无油漆桶段不影响答案,去掉不考虑。
然后对于任意两个连续的油漆桶中的段落(假设坐标分别为,)可以有种油漆方案,则所有段落的方案数乘积即为所求。
注意不算两个相同颜色油漆桶之间的情况。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int mod=1e9+9;
  14. ll n,m;
  15. struct node{int a;char b;bool operator < (const node &o) const{ return a<o.a;}}p[500005];
  16. ll ans=1,las,now;
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void wri(re int x)
  27. {
  28. if(x<0) putchar('-'),x=-x;
  29. if(x>9) wri(x/10);
  30. putchar(x%10+'0');
  31. }
  32. int main()
  33. {
  34. freopen("paint.in","r",stdin);
  35. freopen("paint.out","w",stdout);
  36. n=gi();m=gi();
  37. fp(i,1,m)
  38. {
  39. char gun;cin>>p[i].b;
  40. p[i].a=gi();
  41. }
  42. sort(p+1,p+1+m);
  43. fp(i,2,m) {if(p[i].b!=p[i-1].b) (ans*=(p[i].a-p[i-1].a))%=mod;}
  44. printf("%lld\n",ans);
  45. fclose(stdin);
  46. fclose(stdout);
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注