https://codeforces.com/gym/101669/problem/E
猜了一下结论然而过了，有点惊喜。。。
首先把12种基调状态压缩预处理一下，然后高位前缀和维护一下超集，vis[mask]=true表示当前有的音调状态是存在某一种基调中的
然后我们知道给出的是环，所以我们把他拓展到2倍，然后找dp[i]-dp[i-n]就是截取这一段的最小值求出来就行了，求最小值就是i向后移动，然后mask更新，如果vis[mask]不行了，就说明[l,i]这一段不能再同一首歌中，所以l就要向右移动直到[l,i]可以在同一首歌中。
然后有个问题,如果dp[i-n]=dp[i-n+1]，说明从a[i-n+1]到a[n]的开头是由dp[i-n]拓展过来的还是必须单独开一段，所以要+1，因为我每次都是直到某一个不行才换新的一段。其实这里我没想清楚，也证明不出，因为舍弃掉a[i-n]时，从a[i-n+1]开始可能可以向右到更右边，dp[i]可能会更小一些，但我怀疑这12种基调会完美地解决这个问题，就是舍掉一个向右走，还是一样会换新的一段，然后就过了233
用scanf超时了了一发，换了fread只要400ms，看wxh的博客发现他用cin取消同步读string，我试了一下我的变成了1000ms还是过了
wxh的做法更对一些，不用考虑12种基调的具体情况。只需要枚举开头是12种情况的哪一种，然后尽可能左右扩大以后，跑剩下的部分，复杂度变成了O（12*n）但是非常正确
#include<bits/stdc++.h> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int rd(int &x){ char c=nc(),f=1; for(;(c<'0'||c>'9')&&c!=EOF;c=nc()) if(c=='-') f=-1; if(c==EOF) return EOF; for(x=0;c>='0'&&c<='9';c=nc()) x=x*10+c-'0'; x*=f; return 1; } inline int blank(char ch){ return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; } inline int rd(char *s){ char c=nc(); while(blank(c)) c=nc(); if(c==EOF) return EOF; for (;!blank(c)&&c!=EOF;c=nc())*s++=c; *s=0; return 1; } const int maxl=2e7+10; int n,ans; int a[maxl],dp[maxl]; bool vis[maxl]; char s[100]; int tx[12]={0,2,4,5,7,9,11,12}; int num[12]; inline void prework() { //scanf("%d",&n); rd(n); int l; for(int i=1;i<=n;i++) { //scanf("%s",s); rd(s); l=strlen(s); if(s[0]=='D') a[i]= (l==2)?0:1; if(s[0]=='R') a[i]= (l==2)?2:3; if(s[0]=='M') a[i]=4; if(s[0]=='F') a[i]= (l==2)?5:6; if(s[0]=='S' && s[1]=='o') a[i]= (l==3)?7:8; if(s[0]=='L') a[i]= (l==2)?9:10; if(s[0]=='S' && s[1]=='i') a[i]=11; } for(int i=n+1;i<=2*n;i++) a[i]=a[i-n]; int mask,d; for(int i=0;i<12;i++) { mask=1<<i; for(int j=1;j<=7;j++) { d=(i+tx[j])%12; mask|=1<<d; } vis[mask]=true; } for(int j=0;j<12;j++) for(int i=0;i<(1<<12);i++) if(!(i&(1<<j))) vis[i]|=vis[i|(1<<j)]; } inline void mainwork() { int mask=0,l=1; for(register int i=1;i<=2*n;++i) { if(num[a[i]]==0) mask|=1<<a[i]; num[a[i]]++; while(!vis[mask] || l<=i-n) { num[a[l]]--; if(!num[a[l]]) mask^=1<<a[l]; l++; } dp[i]=dp[l-1]+1; } ans=dp[n]; for(register int i=n+1;i<=2*n;++i) { if(dp[i-n]==dp[i-n+1]) ans=min(ans,dp[i]-dp[i-n]+1); else ans=min(ans,dp[i]-dp[i-n]); } } inline void print() { printf("%d",ans); } int main() { prework(); mainwork(); print(); return 0; }
