A - 棋盘问题
题意
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
解法：n皇后的变形，注意放的位置不一定，并不是每一行都要放，计个step，然后dfs每一个点时，记得回溯上去处理一下，把vis[i]置为0，step--即可，然后处理完此次结束后，dfs（x+1),处理下一位；
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
int step,ans,n,k;
char mp[][];
bool vis[];
void dfs(int x){
if(step==k){
ans++;
return ;
}
if(x>=n)return ;
for(int i=;i<n;i++){
if(!vis[i]&&mp[x][i]=='#'){
step++;
vis[i]=;
dfs(x+);
vis[i]=;
step--;
}
}
dfs(x+);
}
int main(){
while(~scanf("%d %d",&n,&k)){
memset(vis,,sizeof vis);
if(n+k<)break;
rep(i,,n-){
scanf("%s",mp[i]);
}
ans=step=;
dfs();
printf("%d\n",ans); }
return ;
}
B - Dungeon Master
题意:就是个三维迷宫，直接广搜即可，用一个方向数组
#include<bits/stdc++.h>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
const int maxn=1e5+;
bool isprime[maxn];
void makeprime(){
memset(isprime,true,sizeof isprime);
isprime[]=;
for(int i=;i*i<=maxn;i++){
if(isprime[i]==)continue;
for(int j=i*;j<=maxn;j+=i){
isprime[j]=;
}
}
// rep(i,1,maxn){
// cout<<i<<" "<<isprime[i]<<endl;
// }
}
struct point{int num,step;};
int ans,p,q;
bool vis[maxn];
bool bfs(){
memset(vis,,sizeof vis);
vis[p]=;
point tmp,next;
tmp.num=p,tmp.step=;
queue<point>Q;
Q.push(tmp);
while(!Q.empty()){
tmp=Q.front();
Q.pop();
vis[tmp.num]=;
if(tmp.num==q){
ans=tmp.step;
return true;
}
int t=tmp.num;
for(int i=;i<;i++){
for(int j=;j<=;j++){
t=tmp.num;
if(i==){
t-=t%;
t+=j;
}
else if(i==){
t-=t%/*;
t+=j*;
}
else if(i==){
t-=t%/*;
t+=j*;
}
else if(i==){
t-=t%/*;
t+=j*;
}
if(t==tmp.num||t<||vis[t]||!isprime[t])continue;
next.num=t,next.step=tmp.step+;
vis[t]=;
Q.push(next);
}
} }
return false;
}
int main(){
makeprime();
int cas;
scanf("%d",&cas);
while(cas--){
memset(vis,,sizeof vis);
scanf("%d %d",&p,&q);
ans=;
if(bfs())printf("%d\n",ans);
else printf("Impossible\n"); }
return ;
}
题意：给你n和m，问几步能走到，直接广搜即可
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define fi first
#define se second
#define check(x) (x<=N&&x>=0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
const int N=1e5+;
bool vis[N];
int step[N];
int n,k;
void bfs(){
queue<int>Q;
vis[n]=;
step[n]=;
Q.push(n);
while(!Q.empty()){
int s=Q.front();
if(s==k)return ;
Q.pop();
if(check(s+)&&!vis[s+]){
vis[s+]=;
step[s+]=step[s]+;
Q.push(s+);
}
if(check(s-)&&!vis[s-]){
vis[s-]=;
step[s-]=step[s]+;
Q.push(s-);
}
if(check(s<<)&&!vis[s<<]){
vis[s<<]=;
step[s<<]=step[s]+;
Q.push(s<<);
}
}
}
int main(){
while(~scanf("%d%d",&n,&k)){
if(n>=k){
printf("%d\n",n-k);
}
else {
memset(vis,false,sizeof vis);
memset(step,,sizeof step);
bfs();
printf("%d\n",step[k]);
}
} return ;
}
D - Fliptile（学到许多）
题意： 给你一个01网格图，问你怎么按这些点，使得网格图全部置为0，找出字典序最小的方案；
解法： 这题用到二进制思想，解法就是枚举第一行的按键，然后剩下的每一行都可以由上一行递推而来；
递推公式为：press[i][j]=(mp[i-1][j]+press[i-1][j]+press[i-1][j+1]+press[i-2][j]+press[i-1][j-1])&1;
最后判断一下情况是否符合，即最后一行按键是否能全部熄灭，
这里我犯了一个错误，就是判断最后一行时没有按照递推公式算导致错误；
然后枚举第一行的按键用到了二进制，即枚举0<i<(1<<m)，表示有m位二进制数，然后用位运算截取每一位数，即为 press[1][j]=(i>>(m-j))&1;
over
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int mp[][],ans[][],press[][];
int n,m;
const int inf=0x3f3f3f3f;
int guess(){ for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
press[i][j]=(mp[i-][j]+press[i-][j]+press[i-][j+]+press[i-][j]+press[i-][j-])&;
}
}
for(int j=;j<=m;j++){
if((press[n][j]+mp[n][j]+
press[n-][j]+press[n][j-]+press[n][j+])&!=)
return inf;
} int cnt=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
cnt+=press[i][j];
}
} return cnt;
}
int main(){ while(~scanf("%d%d",&n,&m)){
memset(mp,,sizeof mp);
memset(ans,,sizeof ans);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&mp[i][j]);
int res=inf;
for(int i=;i<(<<m);i++){
memset(press,,sizeof press);
int test=;
for(int j=;j<=m;j++){
press[][j]=(i>>(m-j))&;
}
// cout<<"test:"<<i<<" "<<guess()<<endl;
// for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)
// printf("%d%c",press[i][j],j==m?'\n':' '); int sum=guess();
if(res>sum){
res=sum;
memcpy(ans,press,sizeof press);
}
}
if(res==inf)printf("IMPOSSIBLE\n");
else {
// cout<<"test:"<<endl;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
printf("%d%c",ans[i][j],j==m?'\n':' '); }
}
return ;
}
E - Find The Multiple
题意：就是给你一个数，让你找它的一个只含01倍数的十进制数，
解法：直接深搜，但开始T了一发，没有做好剪树枝
计一个flag，如果搜到目标就停止；这样就能过了；
#include<cstdio>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
int n,flag;
ull ans;
void dfs(ull x,int step){
if(flag)return ;
if(x%n==){
flag=;
ans=x;
return ;
}
if(step==)return ;
dfs(x*+,step+);
dfs(x*,step+);
}
int main(){
// cout<<1000000000000000110%6<<endl;
while(~scanf("%d",&n),n){
ans=,flag=;
dfs(*1ll,);
printf("%lld\n",ans);
}
return ;
}
F - Prime Path
题意：就是给你两个素数，问你移动几步，使得由p走到q，而且每次移动只能变为素数，问你要变换几步；
解法：直接广搜即可；注意枚举每一位的情况；
#include<bits/stdc++.h>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
const int maxn=1e5+;
bool isprime[maxn];
void makeprime(){
memset(isprime,true,sizeof isprime);
isprime[]=;
for(int i=;i*i<=maxn;i++){
if(isprime[i]==)continue;
for(int j=i*;j<=maxn;j+=i){
isprime[j]=;
}
}
// rep(i,1,maxn){
// cout<<i<<" "<<isprime[i]<<endl;
// }
}
struct point{int num,step;};
int ans,p,q;
bool vis[maxn];
bool bfs(){
memset(vis,,sizeof vis);
vis[p]=;
point tmp,next;
tmp.num=p,tmp.step=;
queue<point>Q;
Q.push(tmp);
while(!Q.empty()){
tmp=Q.front();
Q.pop();
vis[tmp.num]=;
if(tmp.num==q){
ans=tmp.step;
return true;
}
int t=tmp.num;
for(int i=;i<;i++){
for(int j=;j<=;j++){
t=tmp.num;
if(i==){
t-=t%;
t+=j;
}
else if(i==){
t-=t%/*;
t+=j*;
}
else if(i==){
t-=t%/*;
t+=j*;
}
else if(i==){
t-=t%/*;
t+=j*;
}
if(t==tmp.num||t<||vis[t]||!isprime[t])continue;
next.num=t,next.step=tmp.step+;
vis[t]=;
Q.push(next);
}
} }
return false;
}
int main(){
makeprime();
int cas;
scanf("%d",&cas);
while(cas--){
memset(vis,,sizeof vis);
scanf("%d %d",&p,&q);
ans=;
if(bfs())printf("%d\n",ans);
else printf("Impossible\n"); }
return ;
}
G - Shuffle'm Up
题意：就是给你两堆牌，问你怎么洗才能洗到目标状态，如果洗不到，输出-1；
解法：模拟洗牌的过程，如果洗到初始的状态，说明洗不到，
这里我犯了一个错误，就是在在下标里面写位运算会出错，也不知tmp[i*2]=s2[i];道为什么；
tmp[i*2]=s2[i]; 写成tmp【i>.>1】就不对了
#include<iostream>
#include<string>
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
using namespace std;
typedef long long ll;
string tmp,s1,s2,s12,goal;
int step,n,ans;
void bfs(){ s1=tmp.substr(,n);
s2=tmp.substr(n,n);
for(int i=;i<n;i++){
tmp[i*]=s2[i];
tmp[i*+]=s1[i];
}
step++;
if(tmp.compare(goal)==){
ans=step;
return ;
}
if(tmp.compare(s12)==){
ans=-;
return ;
}
bfs();
}
int main(){
int t,cas=;
// scanf("%d",&t);
cin>>t;
while(t--){
// scanf("%d",&n);
cin>>n>>s1>>s2>>goal;
tmp=s1+s2;
s12=tmp;
ans=step=;
bfs();
printf("%d %d\n",cas++,ans);
}
return ;
}
待更新；
PS：还是太菜了，要坚持刷题，写博客；