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
",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
",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
",(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:down
memset(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("
l:%d
",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
",i,j,x,0,f[i][j][x][0]);
if(x+j-k<=n) De && printf("f[%d][%d][%d][%d]=%d
",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
",1,l+1,x,0,f[1][l+1][x][0]);
De && printf("f[%d][%d][%d][%d]=%d
",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
",ans,Solve2(n));
De=0;
ans=std::min(ans,Solve2(n));
printf("%d
",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
",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;
}