题单
简单记录一下较典型的 \(\text{or}\) 较有思维含量的题。
0X00 P1123 取数游戏
考虑从上往下，从左往右依次取数。每次取完一个数将其标记掉，然后下次取前看周围八个是否有被标记的，没有就可以取，否则跳过。用 \(\text{dfs}\) 实现。
因为多测，所以记得清空。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int T,n,m,a[10][10],ans;
int X[8]={1,1,1,-1,-1,-1,0,0},Y[8]={1,-1,0,1,-1,0,-1,1};
bool mark[10][10];
void dfs(int x,int y,int cnt){
if(y>m){
dfs(x+1,1,cnt);
return ;
}
if(x>n){
ans=max(ans,cnt);
return ;
}
bool fl=0;
for(int i=0;i<8;i++){
if(mark[x+X[i]][y+Y[i]]){
fl=1;
break;
}
}
if(!fl){
mark[x][y]=1;
dfs(x,y+1,cnt+a[x][y]);
mark[x][y]=0;
}
dfs(x,y+1,cnt);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
ans=0;
memset(mark,0,sizeof(mark));
dfs(1,1,0);
cout<<ans<<endl;
}
int main(){
IOS;TIE;
cin>>T;
while(T--) solve();
return 0;
}
0X01 P1238 走迷宫
一般走迷宫我们选择用 \(\text{bfs}\)，但本题要求记录路径，所以用 \(\text{dfs}\) 更方便一些。
在深搜过程中，用栈记录走过的路径，每次到终点时输出一次就好。
比较坑的地方：本题没有SPJ，优先顺序：左上右下，所以对方向数组的顺序是有要求的，不能随便写！
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,m,sx,sy,gx,gy,ss[105][2],tot;
int X[4]={0,-1,0,1},Y[4]={-1,0,1,0};
int a[105][105];
char c;
bool mark[105][105],fl;
void print(){
fl=1;
for(int i=1;i<=tot;i++) cout<<"("<<ss[i][0]<<","<<ss[i][1]<<")->";
cout<<"("<<gx<<","<<gy<<")";
}
void dfs(int x,int y){
if(x==gx&&y==gy){
print();
return ;
}
for(int i=0;i<4;i++){
int xx=x+X[i],yy=y+Y[i];
if(mark[xx][yy]) continue ;
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
ss[++tot][0]=x,ss[tot][1]=y;
mark[x][y]=1;
dfs(xx,yy);
mark[x][y]=0;
tot--;
}
}
}
int main(){
IOS;TIE;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
mark[i][j]=(a[i][j]==0)?1:0;
}
}
cin>>sx>>sy>>gx>>gy;
dfs(sx,sy);
if(!fl) cout<<-1;
return 0;
}
0X02 UVA572 油田 Oil Deposits
每次找到 @ 时，答案 \(+1\)，并以它为起点进行 \(\text{bfs}\)，将可以搜到（在一个连通块中）的 @ 全标成 *。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,m,ans;
int X[8]={1,1,1,-1,-1,-1,0,0},Y[8]={1,-1,0,1,-1,0,1,-1};
char c[105][105];
struct node{
int x,y;
};
queue<node> q;
void bfs(int sx,int sy){
q.push({sx,sy});
c[sx][sy]='*';
while(q.size()){
node k=q.front();q.pop();
for(int i=0;i<8;i++){
int xx=k.x+X[i],yy=k.y+Y[i];
if(c[xx][yy]=='@'){
c[xx][yy]='*';
q.push({xx,yy});
}
}
}
}
int main(){
IOS;TIE;
while(1){
cin>>n>>m;
if(!n&&!m) break;
ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>c[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(c[i][j]=='@'){
ans++;
while(q.size()) q.pop();
bfs(i,j);
}
}
}
cout<<ans<<endl;
}
return 0;
}
0X03 P3818 小A和uim之大逃离 II
因为只能瞬移一次，所以可以增加一维标记，表示是否使用过瞬移了。
同时 \(vis\) 数组也需要增加一维，表示一个点是否在喝药水/不喝药水的情况下被走到过。
考虑具体怎么走：
首先，不管当前是否有喝过药水，上下左右四个方向是都可以走的。这时候，下一个点的标记应该和走向它的点相同，延续当前标记状态。
如果当前是未标记，则可以使用药水走向 \((x_{now}+d\ ,\ y_{now}+r)\) 的位置，并传下已喝过药水的标记。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,m,d,r,ans=1e9;
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0};
bool vis[1205][1205][2];
char c;
struct node{
int x,y,ans;
bool fl;
};
queue<node> q;
void bfs(){
q.push({1,1,0,0});
vis[1][1][0]=1;
while(q.size()){
node k=q.front();q.pop();
if(k.x==n&&k.y==m) ans=min(ans,k.ans);
for(int i=0;i<4;i++){
int xx=k.x+X[i],yy=k.y+Y[i];
if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy][k.fl]) continue;
q.push({xx,yy,k.ans+1,k.fl});
vis[xx][yy][k.fl]=1;
}
if(!k.fl){
int xx=k.x+d,yy=k.y+r;
if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy][1]) ;
else{
q.push({xx,yy,k.ans+1,1});
vis[xx][yy][1]=1;
}
}
}
}
int main(){
IOS;TIE;
cin>>n>>m>>d>>r;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='#') vis[i][j][0]=vis[i][j][1]=1;
}
}
bfs();
ans==1e9?cout<<-1:cout<<ans;
return 0;
}
0X04 CF767C Garland
首先统计权值总和，若不是 \(3\) 的倍数直接无解。
然后从根节点开始 \(\text{dfs}\)，每次更新其父亲结点的权值即为其本身的值与其所有孩子的值，一旦出现有子树权值之和为 \(sum\) 的 \(\frac{1}{3}\)，就储存下答案，答案个数 \(+1\) 。
最后答案个数 \(<3\) 则无解，否则就输出。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,id,t[1000005],ans[5],s[1000005];
int cnt,root,sum;
vector<int> a[1000005];
void dfs(int x,int y){
s[x]=t[x];
for(int i=0;i<a[x].size();i++){
int tmp=a[x][i];
if(tmp!=y){
dfs(tmp,x);
s[x]+=s[tmp];
}
}
if(s[x]==sum/3) ans[++cnt]=x,s[x]=0;
}
int main(){
IOS;TIE;
cin>>n;
for(int i=1;i<=n;i++){
cin>>id>>t[i];
sum+=t[i];
if(id) a[id].push_back(i);
else root=i;
}
if(sum%3) cout<<-1;
else{
dfs(root,0);
if(cnt<3) cout<<-1;
else cout<<ans[1]<<' '<<ans[2];
}
return 0;
}
0X05 CF374C Inna and Dima
先考虑如何建图。
首先把每一个字母转化为数字，然后对于每一个点枚举四个方向，如果有下一个字母，就向那个点建一条边，可以用 \(vector\) 存图比较方便。用数字标号，只需要判断 \(t_{x2,y2}=(t_{x1,y1}+1)\mod 4\) 是否成立即可，但直接用字母判断也是比较方便的。
然后考虑 \(\text{dfs}\) 搜索可以走的最长路。有以下几个注意点：
-
开始搜索的点一定是
D。 -
已经更新过答案的点就不用搜了，直接 \(\text{return}\)，也算一个剪枝过程。
-
可以选无数个点的情况就是出现环了。所以需要 \(vis\) 数组标记本次搜索经过的点，如果走到已经走过的点，直接输出
Poor Inna!结束程序。同时回溯时记得要把 \(vis\) 清空。 -
搜索时答案记录为走过的点数比较方便。因为从
D开始，所以记 \(ans=\max\{dis_{i,j}\}\)。最后若 \(ans<4\) 即输出Poor Dima!，否则 \(ans \div 4\) 就是DIMA的数量。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,m,t[1005][1005],dis[1005][1005],ans;
bool vis[1005][1005];
char c;
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0};
struct node{
int x,y;
};
vector<node> a[1005][1005];
void read(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='D') t[i][j]=0;
if(c=='I') t[i][j]=1;
if(c=='M') t[i][j]=2;
if(c=='A') t[i][j]=3;
}
}
}
bool cango(int x1,int y1,int x2,int y2){
if(t[x2][y2]==(t[x1][y1]+1)%4) return 1;
return 0;
}
void build(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int z=0;z<4;z++){
int xx=i+X[z],yy=j+Y[z];
if(xx>n||xx<1||yy>m||yy<1) continue;
if(cango(i,j,xx,yy)) a[i][j].push_back({xx,yy});
}
}
}
}
void dfs(int sx,int sy){
if(dis[sx][sy]) return;
vis[sx][sy]=1;
dis[sx][sy]=1;
for(int i=0;i<a[sx][sy].size();i++){
int jx=a[sx][sy][i].x,jy=a[sx][sy][i].y;
if(vis[jx][jy]){
cout<<"Poor Inna!";
exit(0);
}
dfs(jx,jy);
dis[sx][sy]=max(dis[sx][sy],dis[jx][jy]+1);
ans=max(ans,dis[sx][sy]);
}
vis[sx][sy]=0;
}
int main(){
IOS;TIE;
cin>>n>>m;
read();
build();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) if(!t[i][j]) dfs(i,j);
}
if(ans<4) cout<<"Poor Dima!";
else cout<<ans/4;
return 0;
}
0X06 P1074 [NOIP2009 提高组] 靶形数独
首先考虑一般数独怎么填。
首先可以按照每行 \(0\) 的个数多少排序，先安排0的个数少的，这样可以尽量少填一些格子，少尝试一些可能。然后按序记录每一个代填格子的坐标，\(xx_i,yy_i\)，按序填数。
记三个标记数组：\(H_{i,j},L_{i,j},G_{i,j}\)，分别表示第 \(i\) 行/列/宫 是否填过了 \(j\)。依次往每个待填格尝试填入 \(1\sim9\) 判断是否合法即可。
关于如何快速得到一个坐标 \((i,j)\) 属于哪一个宫，有这样一个公式：\(g_{i,j}=(i-1)+(j-1)/3+1\)，很好理解，可以提前全部算好。
加上了分数的条件，我们只需要一个分数表 \(score_{i,j}\)，填数时乘上分数，每次填完求最大值就好了。\(ans\) 初始为 \(-1\)，就不用管无解情况了。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int a[15][15],score[15][15],g[15][15],xx[105],yy[105],now,ans=-1,t;
bool H[15][15],L[15][15],G[15][15];
struct node{
int id,cnt;
}z[15];
bool cmp(node a,node b){
return a.cnt<b.cnt;
}
void pre(){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
if(i==1||j==1||i==9||j==9) score[i][j]=6;
else if(i==2||j==2||i==8||j==8) score[i][j]=7;
else if(i==3||j==3||i==7||j==7) score[i][j]=8;
else if(i==4||j==4||i==6||j==6) score[i][j]=9;
else score[i][j]=10;
g[i][j]=(i-1)/3*3+(j-1)/3+1;
}
}
for(int i=1;i<=9;i++) z[i].id=i;
}
void dfs(int p,int now){
if(p==t){
ans=max(ans,now);
return ;
}
for(int i=1;i<=9;i++){
if(!H[xx[p]][i]&&!L[yy[p]][i]&&!G[g[xx[p]][yy[p]]][i]){
H[xx[p]][i]=L[yy[p]][i]=G[g[xx[p]][yy[p]]][i]=1;
dfs(p+1,now+i*score[xx[p]][yy[p]]);
H[xx[p]][i]=L[yy[p]][i]=G[g[xx[p]][yy[p]]][i]=0;
}
}
return ;
}
int main(){
pre();
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cin>>a[i][j];
if(a[i][j]==0) z[i].cnt++;
else{
H[i][a[i][j]]=L[j][a[i][j]]=G[g[i][j]][a[i][j]]=1;
now+=a[i][j]*score[i][j];
}
}
}
sort(z+1,z+10,cmp);
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
if(a[z[i].id][j]==0){
xx[t]=z[i].id,yy[t]=j;
t++;
}
}
}
dfs(0,now);
cout<<ans;
return 0;
}
0X07 P2756 飞行员配对方案问题
匈牙利算法，用于二分图最大匹配。
详细介绍可以看 这篇博客 的【二、匈牙利算法概述】部分，大概就是什么个配对问题。
实现就是 \(\text{dfs}\)。首先遍历一个点的边，若有未访问的，就标为已访问然后处理，如果访问到的点当前无匹配，或者原来已匹配的另一方可以找到新的匹配，就将它匹配给当前点，返回匹配成功。若遍历完还不能匹配，则失败。
每个点这样取匹配一遍就能得到答案。记得每次匹配前要清空标记。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
int n,m,x,y,cnt,ans[105];
bool mark[105];
vector<int> a[105];
bool dfs(int x){
for(int i=0;i<a[x].size();i++){
int tmp=a[x][i];
if(mark[tmp]) continue;
mark[tmp]=1;
if(!ans[tmp]||dfs(ans[tmp])){
ans[tmp]=x;
return 1;
}
}
return 0;
}
int main(){
IOS;TIE;
cin>>n>>m;
while(1){
cin>>x>>y;
if(x==-1&&y==-1) break;
a[x].push_back(y);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) mark[j]=0;
if(dfs(i)) cnt++;
}
cout<<cnt<<endl;
for(int i=1;i<=m;i++){
if(ans[i]) cout<<ans[i]<<' '<<i<<endl;
}
return 0;
}