1.DFS+特殊輸入：PTA | 程序設計類實驗輔助教學平臺

這題其他還是蠻容易，直接用遞歸即可，問題在于怎么輸入，其實可以在遞歸到底層時輸入即可，也就是邊遞歸邊輸入，另外提一嘴跟這個題沒什么關系的點（string.find找不到時返回String：：npos,同時在從莫個下標開始找是find(str,pos））具體見AC代碼：

#include<bits/stdc++.h>
using namespace std;
int ru[200010];
int n;
vector<int> edge[200100];
int shu[200010];
int dfs(int root){if(root==0){char c;cin>>c;return int(c-'0');}if(shu[root]==1){int f=1;int x1=dfs(edge[root][0]);int x2=dfs(edge[root][1]);if(x1==1&&x2==1) f=1;else f=0;return f;}if(shu[root]==2){int f=0;int x1=dfs(edge[root][0]);int x2=dfs(edge[root][1]);if(x1==1||x2==1) f=1;else f=0;return f;}if(shu[root]==3){return 1-dfs(edge[root][0]);}
}
int main(){cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;shu[i]=x;if(x==3){int u;cin>>u;ru[u]++;edge[i].push_back(u);}else{int u,v;cin>>u>>v;ru[u]++;ru[v]++;edge[i].push_back(u);edge[i].push_back(v);}}int root;for(int i=1;i<=n;i++){if(ru[i]==0) root=i;}//cout<<root<<endl;int k;cin>>k;while(k--){int ans=dfs(root);if(ans==0) cout<<"BuAi";else cout<<"Ai";if(k!=0) cout<<endl;}
}

2.DFS+剪枝：PTA | 程序設計類實驗輔助教學平臺

看到數字這么小顯然就是DFS暴力，但是直接爆搜鐵TLE，考慮優化：

實際上，我們只需要枚舉內嵌一層的矩形即可，因為最后一個可以直接推出來，因此我們需要在維護一個行和列的前綴和數組。下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int l,n;
int a[20][20];
int sumx[20],sumy[20];
int cnt=0;
bool check(){int sum1=0,sum2=0;for(int i=1;i<=n-1;i++) sum1+=l-sumx[i];for(int i=1;i<=n-1;i++) sum2+=l-sumy[i];if((l-sum1)>=0&&sum1==sum2) return 1;return 0;
}
void dfs(int x,int y){if(y==n-1){int xx=l-sumx[x];if(xx<0) return;}if(x==n-1){int yy=l-sumy[y];if(yy<0) return;}if(x==n-1&&x==y){if(check()==1) cnt++;return;}if(y==n-1){y=1;x++;}else{y++;}for(int i=0;i<=min(l-sumx[x],l-sumy[y]);i++){a[x][y]=i;sumx[x]+=i;sumy[y]+=i;dfs(x,y);sumx[x]-=i;sumy[y]-=i;}return;
}
int main(){cin>>l>>n;for(int i=0;i<=l;i++){a[1][1]=i;sumx[1]=sumy[1]=i;dfs(1,1);}cout<<cnt;
}

3.DFS+剪枝：PTA | 程序設計類實驗輔助教學平臺

這題比較正常的想法就是先枚舉順序，但是這樣也會TLE，其實我們可以邊枚舉邊檢查，檢查到不對了就直接退出，也就是進行一下剪枝，具體見AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
int n,m;
vector<int> v[maxn], v1;
bool vis[maxn];
int h[maxn];
void dfs(int x){//x是當前紙條的下標if(x==n-1){//終止條件for (int i = 0; i < v1.size();i++){//遍歷輸出if(i)cout << " ";cout << v1[i];}}for (int i = 1; i <= m; i++){if(!vis[i]){//當前紙條未使用過int flag = 1;for (int j = 0; j < v[i].size();j++){if(v[i][j]!=h[x+j])flag = 0;//不滿足題意}if(flag){v1.push_back(i);vis[i] = 1;dfs(x + v[i].size() - 1);vis[i] = 0;//回溯v1.pop_back();//回溯}}}
}
void solve(){cin >> n;for (int i = 0;i<n;i++){cin >> h[i];}cin >> m;for (int i = 1;i<=m;i++){int k, x;cin>>k;while(k--){cin>>x;v[i].push_back(x);}}dfs(0);
}
int main(){solve();
}