搜索比赛垫底了QAQ
果然我还是太菜了
蓝瘦香菇
T1 解密牛语
这道题神坑的一点就是原串不知道为啥可以读出48的串长。。。。。缓缓扣出一个？（咕成90调半天）
其实就是搜索+疯狂剪枝，就成为O（玄学）
根据如下几个性质进行剪枝：
对于
1.串长一定为47+3*k
2.第一个s前的前缀与最后一个s后的后缀一定与原串相同。
3.两个相邻s之间串的顺序一定与原串相同
4.已出现过的串不用重复计算。
5.据说从后枚举W可以快20倍。。。有点厉害
用哈希维护一下就好了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL hash=140;
const LL p=1e5+7;
LL len,sum,flag;
LL Pow[110],Hash[51];
bool exist[11][p+3];
char s1[110],s[48]={' ','B','e','g','i','n',' ','t','h','e',' ','E','s','c','a','p','e',' ','e','x','e','c','u','t','i','o','n',' ','a','t',' ','t','h','e',' ','B','r','e','a','k',' ','o','f',' ','D','a','w','n'};
LL gethash(LL l,LL r){
return (Hash[r]-Hash[l-1]*Pow[r-l+1]%p+p)%p;
}
LL check(LL H,LL len){
for(LL i=len;i<=47;++i) if(gethash(i-len+1,i)==H) return 1;
return 0;
}
void dfs(LL now,LL lenn,char *s1){
if(now>sum){
for(LL i=1;i<=47;++i) if(s[i]!=s1[i]) return ;
flag=1;return ;
}
LL ret=0;
for(LL i=1;i<=lenn;++i) ret=(ret*hash%p+s1[i])%p;
if(exist[now-1][ret]) return ;
exist[now-1][ret]=1;
LL last=1;
for(LL i=1;i<=lenn;++i){
if(s1[i]=='C'||s1[i]=='O'||s1[i]=='W'){
if(last<i){
int Hash1=0;
for(LL j=last;j<i;++j) Hash1=(Hash1*hash%p+s1[j])%p;
if(!check(Hash1,i-last)) return ;
}
last=i+1;
}
}
LL l=1,r=0;
while(s1[l]!='C'&&s1[l]!='O'&&s1[l]!='W'&&l<=lenn){
if(s1[l]!=s[l]) l=lenn+2;
++l;
}
if(l==lenn+2||(l!=lenn+1&&s1[l]!='C')) return ;
while(s1[lenn-r]!='C'&&s1[lenn-r]!='O'&&s1[lenn-r]!='W'&&r<lenn){
if(s1[lenn-r]!=s[47-r]) r=lenn+2;
++r;
}
if(r==lenn+2||(r!=lenn&&s1[lenn-r]!='W')) return ;
char nxt[110];
for(LL i=1;i<=lenn;++i){
if(s1[i]=='C'){
for(LL j=i+1;j<lenn;++j){
if(s1[j]=='O'){
for(LL k=lenn;k>j;--k){
if(s1[k]=='W'){
ret=0;
for(LL l=1;l<i;++l) nxt[++ret]=s1[l];
for(LL l=j+1;l<k;++l) nxt[++ret]=s1[l];
for(LL l=i+1;l<j;++l) nxt[++ret]=s1[l];
for(LL l=k+1;l<=lenn;++l) nxt[++ret]=s1[l];
dfs(now+1,ret,nxt);
if(flag) return ;
}
}
}
}
}
}
}
int main(){
gets(s1+1);
len=strlen(s1+1);
// if((len-47)%3!=0){
// puts("0 0");
// return 0;
// }
sum=(len-47)/3;
Pow[0]=1;
for(LL i=1;i<=len;++i) Pow[i]=Pow[i-1]*hash%p;
Hash[0]=0;
for(LL i=1;i<=47;++i) Hash[i]=(Hash[i-1]*hash%p+(LL)s[i])%p;
// for(int i=1;i<=len;++i) cout<<Pow[i]<<' '<<Hash[i]<<'\n';
dfs(1,len,s1);
if(flag) cout<<1<<' '<<sum;
else cout<<0<<' '<<0;
}
T2 火力网
随便写写就行了
#include<bits/stdc++.h>
//#include<windows.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 read(){
int x=0,f=1;
char ch=nc();
while(!isdigit(ch)&&ch!='-')ch=nc();
if(ch=='-')ch=nc(),f=-1;
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=nc();}
return x*f;
}
inline char gc(){
char ch=nc();while(ch==' '||ch==10||ch=='\r')ch=nc();
return ch;
}
const int N=12;
bool m[N][N],put[N][N];
int cov[N][N],n;
typedef pair<int,int> pii;
#define mp make_pair
#define fi first
#define se second
inline pii con(int x,int y){
int tmp=x;
while(tmp<n&&!m[++tmp][y])if(put[tmp][y])return mp(tmp,y);
tmp=x;while(tmp>1&&!m[--tmp][y])if(put[tmp][y])return mp(tmp,y);
tmp=y;while(tmp<n&&!m[x][++tmp])if(put[x][tmp])return mp(x,tmp);
tmp=y;while(tmp>1&&!m[x][--tmp])if(put[x][tmp])return mp(x,tmp);
return mp(-1,-1);
}
inline pii find(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(!m[i][j]&&cov[i][j]==0)return mp(i,j);
return mp(-1,-1);
}
inline pii find1(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(!m[i][j]&&cov[i][j]==1)return mp(i,j);
return mp(-1,-1);
}
inline void add(int x,int y){
int tmp=x;cov[x][y]++;put[x][y]=1;
while(tmp<n&&!m[++tmp][y])cov[tmp][y]++;
tmp=x;while(tmp>1&&!m[--tmp][y])cov[tmp][y]++;
tmp=y;while(tmp<n&&!m[x][++tmp])cov[x][tmp]++;
tmp=y;while(tmp>1&&!m[x][--tmp])cov[x][tmp]++;
}
inline void del(int x,int y){
int tmp=x;cov[x][y]--;put[x][y]=0;
while(tmp<n&&!m[++tmp][y])cov[tmp][y]--;
tmp=x;while(tmp>1&&!m[--tmp][y])cov[tmp][y]--;
tmp=y;while(tmp<n&&!m[x][++tmp])cov[x][tmp]--;
tmp=y;while(tmp>1&&!m[x][--tmp])cov[x][tmp]--;
}
int ans;
bool Try(int x,int y,bool op){//0:x³åÍ» ; 1:y³åÍ»
// cerr<<"OJK "<<op<<'\n';
del(x,y);
if(op==0){
int tmp;
pii p=mp(-1,-1);
for(int i=1;i<=n;i++)if(i!=x&&!m[i][y]&&!cov[i][y]){p=mp(i,y);break;}
if(p.fi!=-1){add(p.fi,p.se);return 1;}
else{
tmp=x;
while(tmp<n&&!m[++tmp][y])if(cov[tmp][y]==1){
pii p=con(tmp,y);if(p.fi==-1)continue;
if(p.fi==tmp&&Try(p.fi,p.se,0)&&con(tmp,y).fi==-1){add(tmp,y);return 1;}
else if(p.se==y&&Try(p.fi,p.se,1)&&con(tmp,y).fi==-1){add(tmp,y);return 1;};
}
tmp=x;
while(tmp>1&&!m[--tmp][y])if(cov[tmp][y]==1){
pii p=con(tmp,y);if(p.fi==-1)continue;
if(p.fi==tmp&&Try(p.fi,p.se,0)&&con(tmp,y).fi==-1){add(tmp,y);return 1;}
else if(p.se==y&&Try(p.fi,p.se,1)&&con(tmp,y).fi==-1){add(tmp,y);return 1;};
}
add(x,y);return 0;
}
}
else{
int tmp=y;pii p=mp(-1,-1);
for(int i=1;i<=n;i++)if(y!=i&&!m[x][i]&&!cov[x][i]){p=mp(x,i);break;}
if(p.fi!=-1){add(p.fi,p.se);return 1;}
else{
tmp=y;
while(tmp<n&&!m[x][++tmp])if(cov[x][tmp]==1){
pii p=con(x,tmp);if(p.fi==-1)continue;
if(p.fi==x&&Try(p.fi,p.se,0)&&con(x,tmp).fi==-1){add(x,tmp);return 1;}
else if(p.se==tmp&&Try(p.fi,p.se,1)&&con(x,tmp).fi==-1){add(x,tmp);return 1;};
}
tmp=y;
while(tmp>1&&!m[x][--tmp])if(cov[x][tmp]==1){
pii p=con(x,tmp);if(p.fi==-1)continue;
if(p.fi==x&&Try(p.fi,p.se,0)){add(x,tmp);return 1;}
else if(p.se==tmp&&Try(p.fi,p.se,1)){add(x,tmp);return 1;};
}
add(x,y);return 0;
}
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(gc()=='X')m[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(!m[i][j]&&!cov[i][j])add(i,j),ans++;
}
bool f=0;
do{
f=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!m[i][j]&&cov[i][j]==1){
pii p=con(i,j);if(p.fi==-1)continue;
if(p.fi==i&&Try(p.fi,p.se,0)&&con(i,j).fi==-1)add(i,j),f=1,ans++;
else if(p.se==j&&Try(p.fi,p.se,1)&&con(i,j).fi==-1)add(i,j),f=1,ans++;
}
}
}
}while(f);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)if(put[i][j])cerr<<'X';
// else if(m[i][j])cerr<<"L";
// else cerr<<'.';
// cerr<<'\n';
// }
printf("%d",ans);
return 0;
}
T3 汉诺塔
咕咕咕
T4 来自风平浪静的明天
艹，flag打错地方了。。。。
也是随便写写就能过的题
#include<bits/stdc++.h>
using namespace std;
const int MAXN=310;
#define pii pair<int,int>
int n,m,tot;
char ma[MAXN][MAXN];
int vis[MAXN][MAXN];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool check(int x,int y){
memset(vis,0,sizeof(vis));
queue<pii > q[2];
int now=0,sum=1;
q[now].push(make_pair(x,y));
vis[x][y]=1;
while(!q[now].empty()){
int flag=0;
while(!q[now].empty()){
pii u=q[now].front();
q[now].pop();
int tx=u.first,ty=u.second;
for(int i=0;i<4;++i){
int nx=tx+dx[i],ny=ty+dy[i];
if(nx>n||!nx||ny>m||!ny||vis[nx][ny]) continue;
if(ma[nx][ny]=='Y'||ma[nx][ny]=='X') continue;
if(ma[nx][ny]=='H'&&flag==2) return 0;
if(ma[nx][ny]=='B'&&flag==1) return 0;
if(ma[nx][ny]=='B') flag=2;
if(ma[nx][ny]=='H') flag=1,++sum,vis[nx][ny]=1,q[now^1].push(make_pair(nx,ny));
}
}
now^=1;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%s",ma[i]+1);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(ma[i][j]=='H') ++tot;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(ma[i][j]=='H'&&check(i,j)){
cout<<i<<' '<<j;
return 0;
}
}
}
puts("-1");
}
转载：https://blog.csdn.net/g21glf/article/details/100806244
查看评论