12.7 Test

2018.12.7 Test
- A 序列sequence(迭代加深搜索)
- B 轟炸bomb(Tarjan DP)
- C 字符串string(AC自動機狀壓DP)
- 考試代碼
  - A
  - C

2018.12.7 Test

題目為2018.1.4雅禮集訓。

時間：4.5h
期望得分：0+100+10
實際得分：0+100+10

A 序列sequence(迭代加深搜索)

顯然可以每次將最大的數轉到第一位，再轉到對應的位，所以答案不會超過\(2n-2\)。
這其實挺小的，考慮爆搜迭代加深。

注意到每次反轉最多只會影響一對數的連續關系（反轉位置\(p\)與\(p+1\)），所以借此可以求出當前至少還需多少步。利用這個剪枝就可以過了。。

復雜度\(O(能過)\)。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=27;int n,lim,OK,A[N];inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
void DFS(int step,int need)
{if(OK||step+need>lim) return;int p=n;while(A[p]==p) --p;if(!p) {OK=1; return;}
//  for(int p=2; p<=n; ++p)//這種玄學題還是倒著吧...?for(; p>=2; --p){int t=(p<n && std::abs(A[p]-A[p+1])==1)-(p<n && std::abs(A[1]-A[p+1])==1);std::reverse(A+1,A+1+p);DFS(step+1,need+t);std::reverse(A+1,A+1+p);if(OK) break;}
}int main()
{freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);A[0]=-233;for(int T=read(); T--; ){n=read(); int t=0;for(int i=1; i<=n; ++i) A[i]=read();for(int i=1; i<n; ++i) if(std::abs(A[i]-A[i+1])!=1) ++t;for(OK=0,lim=t; ; ++lim)if(DFS(0,t),OK) break;printf("%d\n",lim);}return 0;
}

B 轟炸bomb(Tarjan DP)

縮點，將每個連通分量縮點后的權值設成連通分量大小，那么就是求每個連通塊的最長鏈了。簡單DP一下。

另外可以\(O(1)\)將連通分量中的點的出邊接到根節點（連通分量代表點）的邊表后面去，訪問那些點就直接訪問根節點好了。這樣無需新建一張圖。

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e6+5;int Ans,Enum,ed[N],H[N],nxt[N<<1],to[N<<1],dfn[N],low[N],top,sk[N],bel[N],val[N],f[N];
bool vis[N],ins[N];
char IN[MAXIN],*SS=IN,*TT=IN;inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
inline void AE(int v,int u)
{if(!H[u]) ed[u]=Enum+1;to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
void Tarjan(int x)
{static int Index=0;low[x]=dfn[x]=++Index, sk[++top]=x, ins[x]=1;for(int i=H[x],v; i; i=nxt[i])if(!dfn[v=to[i]]) Tarjan(v), low[x]=std::min(low[x],low[v]);else if(ins[v]) low[x]=std::min(low[x],dfn[v]);if(dfn[x]==low[x]){do{int tmp=sk[top--];++val[x], bel[tmp]=x;if(x!=tmp) nxt[ed[x]]=H[tmp], ed[x]=ed[tmp];//, H[tmp]=0;ins[tmp]=0;}while(sk[top+1]!=x);}
}
void DFS(int x)
{int mx=0; vis[x]=1;for(int i=H[x],v; i; i=nxt[i])if((v=bel[to[i]])!=x){if(!vis[v]) DFS(v);mx=std::max(mx,f[v]);}f[x]=val[x]+mx;Ans=std::max(Ans,f[x]);
}int main()
{freopen("bomb.in","r",stdin);freopen("bomb.out","w",stdout);int n=read(),m=read();for(int i=1; i<=m; ++i) AE(read(),read());for(int i=1; i<=n; ++i) bel[i]=i;for(int i=1; i<=n; ++i)if(!dfn[i]) Tarjan(i);for(int i=1; i<=n; ++i)if(!vis[i]&&bel[i]==i) DFS(i);printf("%d\n",Ans);return 0;
}

C 字符串string(AC自動機狀壓DP)

原題：HDU 6086

考慮沒有反回文這一條件，那么將\(n\)個字符串都插入AC自動機，就可以在上面狀壓DP了（狀壓匹配了哪幾個字符串）。
具體就是，令\(f[i][j][k]\)表示當前為第\(i\)位，當前在AC自動機上的節點\(j\)，匹配字符串狀態為\(k\)，的方案數。轉移時，枚舉節點\(u\)，然后枚舉下一步放哪個字符\(c\)，然后會跳到一個節點\(v=son[u][c]\)。那么\(f[i][u][k]\)就可以轉移到\(f[i+1][v][k|s_v]\)，其中\(s_v\)為在\(v\)節點匹配的字符串集合。
（這樣當然對啊，雖然只是對\(n\)個串建AC自動機，但每次填一個字符一定會轉移到某個節點且仍保持某種匹配狀態）
最后答案就是\(\sum_{i=1}^{tot}f[m][i][2^n-1]\)，\(tot\)是AC自動機總結點數。

考慮反回文的情況。那么每個串在長\(2m\)的串中出現有四種情況：在前一半出現，在后一半出現，跨越中點且在前一半的部分多，跨越中點且在后一半的部分多。

對于第二種情況，把反串（reverse后再01取反）插入到AC自動機，同樣狀壓DP就好了。

對于第三種情況，我們需要判斷每個串\(s\)的每個長度至少為\(|s|\)一半的前綴\(s[1...i]\)判斷（注意\(i\)的范圍！），反轉它后是否能對應\(s[i+1...|s|]\)，也就是它是否可以跨越中點。
對每個節點再狀壓一個狀態\(s'_u\)，表示以該節點作為中間點（也就是前一半串的結束點）能匹配的字符串集合。最后計算答案時\(s_u\)與\(s'_u\)取個并再判斷是否等于\(2^n-1\)即可。
如果該串在當前匹配節點\(u\)處可以跨越中點，就加入到\(s'_u\)中去。

對于第四種情況，對反串同情況三一樣處理即可。

//15MS  1344K
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod 998244353
#define Add(x,v) (x+=v)>=mod&&(x-=mod)
typedef long long LL;
const int N=6*20*2+7;//6*100*2+7;struct AC_Automaton
{int tot,son[N][2],s1[N],s2[N],fail[N],q[N],f[2][N][(1<<6)+2];void Clear(){tot=0, memset(son,0,sizeof son), memset(fail,0,sizeof fail);memset(s1,0,sizeof s1), memset(s2,0,sizeof s2), memset(f,0,sizeof f);}inline bool Check(char *s,int p,int l){for(int i=p+1; i<l; ++i) if(/*p-i+p+1<0||*/s[i]==s[p-i+p+1]) return 0;return 1;}void Insert(char *s,int l,int id){int x=0;for(int i=0,c,mid=l-1>>1; i<l; ++i)//mid=(l-1)/2 !{if(!son[x][c=s[i]-48]) son[x][c]=++tot;x=son[x][c];if(i>=mid && Check(s,i,l)) s2[x]|=id;}s1[x]|=id;}void Build(){int h=0,t=0;if(son[0][0]) fail[son[0][0]]=0, q[t++]=son[0][0];if(son[0][1]) fail[son[0][1]]=0, q[t++]=son[0][1];while(h<t){int x=q[h++];s1[x]|=s1[fail[x]], s2[x]|=s2[fail[x]];for(int i=0; i<2; ++i)if(son[x][i]) fail[son[x][i]]=son[fail[x]][i], q[t++]=son[x][i];else son[x][i]=son[fail[x]][i];}}void Solve(int n,int m){
//      for(int i=0; i<=tot; ++i) s1[i]|=s1[fail[i]], s2[i]|=s2[fail[i]];int p=1,lim=(1<<n)-1; f[p][0][0]=1;for(int i=1; i<=m; ++i,p^=1)for(int u=0; u<=tot; ++u)for(int k=0,val; k<=lim; ++k){if(!(val=f[p][u][k])) continue;for(int l=0; l<2; ++l){int v=son[u][l],s=k|s1[v];Add(f[p^1][v][s],val);}f[p][u][k]=0;}LL ans=0;for(int u=0; u<=tot; ++u)for(int k=0; k<=lim; ++k)if((k|s2[u])==lim) ans+=f[p][u][k];printf("%d\n",(int)(ans%mod));}
}ac;inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}int main()
{freopen("string.in","r",stdin);freopen("string.out","w",stdout);static char tmp[105];int n=read(),m=read();for(int i=0,l; i<n; ++i){scanf("%s",tmp), l=strlen(tmp);ac.Insert(tmp,l,1<<i);std::reverse(tmp,tmp+l);for(int j=0; j<l; ++j) tmp[j]^=1;//就算是'0''1'，相鄰的一個奇數一個偶數也可以直接轉啊 ac.Insert(tmp,l,1<<i);}ac.Build(), ac.Solve(n,m);return 0;
}

考試代碼

A

自閉。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=27;int A[N];
char IN[MAXIN],*SS=IN,*TT=IN;inline int read()
{int now=0,f=1;register char c=gc();for(;!isdigit(c);c=='-'&&(f=-1),c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f;
}
int Solve1(int n)
{static int B[N];memcpy(B,A,sizeof A);int now=n,ans=0,lim=n; B[0]=-233;while(now!=1){while(B[lim]==now) --lim, --now;if(!lim) break;if(B[1]==now) std::reverse(B+1,B+1+lim), --lim, --now, ++ans;else{int p=1;for(int i=1; i<=lim; ++i) if(B[i]==now) {p=i; break;}std::reverse(B+1,B+1+p), ++ans;}}return ans;
}
bool De=1;
int Solve2(const int n)
{static int f[N][N][N][2];//0:up 1:downmemset(f,0x3f,sizeof f);for(int i=1; i<=n; ++i){f[i][i][A[i]][0]=f[i][i][A[i]][1]=0;for(int j=i+1; j<=n; ++j)if(A[j]==A[i]+j-i) f[i][j][A[i]][0]=0, f[i][j][A[i]][1]=0;else break;for(int j=i+1; j<=n; ++j)if(A[j]==A[i]-j+i) f[i][j][A[j]][1]=0, f[i][j][A[j]][0]=0;else break;}for(int l=1; l<n; ++l){De && printf("\nl:%d\n",l);for(int i=1; i+l<=n; ++i){int j=i+l;for(int x=1; x<=n; ++x){for(int k=i; k<j; ++k){if(x+k+1-i<=n) f[i][j][x][0]=std::min(f[i][j][x][0],f[i][k][x][0]+f[k+1][j][x+k+1-i][0]);if(x+j-k<=n) f[i][j][x][1]=std::min(f[i][j][x][1],f[i][k][x+j-k][1]+f[k+1][j][x][1]);if(x+k+1-i<=n) De && printf("f[%d][%d][%d][%d]=%d\n",i,j,x,0,f[i][j][x][0]);if(x+j-k<=n) De && printf("f[%d][%d][%d][%d]=%d\n",i,j,x,1,f[i][j][x][1]);}}}for(int x=1; x<=n; ++x){f[1][l+1][x][0]=std::min(f[1][l+1][x][0],f[1][l+1][x][1]+1),f[1][l+1][x][1]=std::min(f[1][l+1][x][1],f[1][l+1][x][0]+1);De && printf("f[%d][%d][%d][%d]=%d\n",1,l+1,x,0,f[1][l+1][x][0]);De && printf("f[%d][%d][%d][%d]=%d\n",1,l+1,x,1,f[1][l+1][x][1]);}}return std::min(f[1][n][1][0],f[1][n][1][1]+1);
}int main()
{freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);for(int T=read(); T--; ){int n=read();for(int i=1; i<=n; ++i) A[i]=read();int ans=Solve1(n);
//      De=1, printf("ans1:%d ans2:%d\n",ans,Solve2(n));De=0;ans=std::min(ans,Solve2(n));printf("%d\n",ans);}return 0;
}

C

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod 998244353
typedef long long LL;
const int N=1005;int len[8],s[8][105];inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
namespace Subtask1
{int n,m,L,mid,Ans,bit[N];void Recover(int m,int L){for(int i=1; i<=m; ++i) bit[L-i+1]=bit[i]^1;}bool Check(int *s,int l){for(int i=1; i+l-1<=L; ++i)for(int j=1; ; ++j)if(j<=l && s[j]!=bit[i+j-1]) break;else if(j==l) return 1;
//      puts("Failed:"); for(int i=1; i<=l; ++i) printf("%d ",s[i]); puts("");return 0;}void DFS(int x){if(x>m){Recover(m,L);
//          puts("Now:"); for(int i=1; i<=L; ++i) printf("%d ",bit[i]); puts("");for(int i=1; i<=n; ++i)if(!Check(s[i],len[i])) return ;++Ans;return;}bit[x]=0, DFS(x+1), bit[x]=1, DFS(x+1);}void Main(int n,int m){Subtask1::n=n, Subtask1::m=m, L=m<<1;DFS(1), printf("%d\n",Ans);}
}int main()
{freopen("string.in","r",stdin);freopen("string.out","w",stdout);static char tmp[105];int n=read(),m=read();for(int i=1; i<=n; ++i){scanf("%s",tmp+1), len[i]=strlen(tmp+1);for(int j=1; j<=len[i]; ++j) s[i][j]=tmp[j]-'0';}if(m<=17) return Subtask1::Main(n,m),0;return 0;
}

轉載于:https://www.cnblogs.com/SovietPower/p/10093811.html