Blue Mary的战役地图
\(solution\)
暴力卡常
时间复杂度较高\(O(n^7)\)
优化后可过：
倒叙枚举边长，一旦找到就输出
AC Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=55;
int n;
int a[N][N],b[N][N];
bool dfs(int x,int y,int k)
{
for(int i=1;i<=n-k+1;i++)
{
for(int j=1;j<=n-k+1;j++)
{
if(b[i][j]==a[x][y])
{
int o=0;
for(int s=0;s<k;s++)
{
for(int w=0;w<k;w++)
{
if(a[x+s][y+w]!=b[i+s][j+w])
{
o=1;
break;
}
}
if(o==1)break;
}
if(o==0)return true;
}
}
}
return false;
}
int main()
{
// freopen("map.in","r",stdin);
// freopen("map.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=read();
int ans=0;
for(int k=n;k>=1;k--)
{
for(int i=1;i<=n-k+1;i++)
{
for(int j=1;j<=n-k+1;j++)
{
if(dfs(i,j,k))
{
ans=k;
printf("%d\n",ans);
return 0;
}
}
}
}
return 0;
}
无界单词
\(solution\)
对于总的无界单词的个数，我们考虑用dp来解决。
设计状态\(f_i\)表示长度为i的无界单词个数，由此可得转移方程为：\(f_i=2^{i}-\sum_{j=1}^{i/2}{f_{j}*2^{i-2*j}}\)
然后我们来考虑第k小的无界单词
kmp预处理+dp找在已经确定了len长的串后的无界单词个数
转移方程为：\(f_{i}=2^{i-len}-\sum_{j=1}^{i/2}{a_j}\)
分类讨论：
- \(len\leq j,a_j=f_{j}*2^{i-j*2}\)
- 否则\(len\leq i-j,a_j=f_j*2^{i-len-j}\)
- 否则，判断\(w_{1\cdots len-i+j}\)和\(w_{1\cdots len}\)是否相等，如果不相等\(w_j=1,k-=f[n]\)
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
inline ull read()
{
ull x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
ull t,n,k,qow[100];
ull nex[100],w[100],f[100];
void kmp(int len)
{
for(int i=2,j=0;i<=len;i++)
{
while(j>0&&w[j+1]!=w[i])j=nex[j];
if(w[j+1]==w[i])j++;
nex[i]=j;
}
}
ull init(int len)
{
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
{
if(i<=len)
{
f[i]=!nex[i];
continue;
}
f[i]=qow[i-len];
for(int j=1;j<=i/2;j++)
{
if(j>=len)f[i]-=f[j]*qow[i-j*2];
else if(len<=i-j)f[i]-=f[j]*qow[i-len-j];
else if(f[j])
{
int o=0;
for(int s=1,p=i-j+1;p<=len;++p,++s)
{
if(w[s]!=w[p])
{
o=1;break;
}
}
if(!o)f[i]--;
}
}
}
return f[n];
}
int main()
{
// freopen("word.in","r",stdin);
// freopen("word.out","w",stdout);
t=read();
qow[0]=1;
for(int i=1;i<=64;i++)
qow[i]=qow[i-1]*2;
while(t--)
{
n=read(),k=read();
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
{
f[i]=qow[i];
for(int j=1;j<=i/2;j++)
f[i]-=f[j]*qow[i-2*j];
}
cout<<f[n]<<endl;
for(int i=1;i<=n;i++)
{
w[i]=0;kmp(i);
ull tmp=init(i);
if(tmp<k)w[i]=1,k-=tmp;
}
for(int i=1;i<=n;i++)
{
if(w[i]==1)printf("b");
else printf("a");
}
printf("\n");
}
return 0;
}