P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=14;
int n,ans=0;
int a[N][N]={},vis[N][N]={};
vector<int>rcd(n+1);
void dfs(int dep){if(dep==n+1){if(ans<=2){for(int i=1;i<=n;i++)cout<<rcd[i]<<" \n"[i==n];}ans++;return ;}//此時該搜索第n+1行說明前n行已經排列完成了 for(int i=1;i<=n;i++){if(vis[dep][i])continue;//如果出現過就直接跳過rcd[dep]=i;for(int _i=1;_i<=n;_i++)vis[_i][i]++;//這一列都是0for(int _i=dep,_j=i;_i>=1&&_j>=1;--_i,--_j)vis[_i][_j]++;//左上for(int _i=dep,_j=i;_i>=1&&_j<=n;--_i,++_j)vis[_i][_j]++;//右上for(int _i=dep,_j=i;_i<=n&&_j<=n;++_i,++_j)vis[_i][_j]++;//右下for(int _i=dep,_j=i;_i<=n&&_j>=1;++_i,--_j)vis[_i][_j]++;//左下dfs(dep+1);//搜索下一行//回溯for(int _i=1;_i<=n;_i++)vis[_i][i]--;//這一列都是0for(int _i=dep,_j=i;_i>=1&&_j>=1;--_i,--_j)vis[_i][_j]--;//左上for(int _i=dep,_j=i;_i>=1&&_j<=n;--_i,++_j)vis[_i][_j]--;//右上for(int _i=dep,_j=i;_i<=n&&_j<=n;++_i,++_j)vis[_i][_j]--;//右下for(int _i=dep,_j=i;_i<=n&&_j>=1;++_i,--_j)vis[_i][_j]--;//左下}
}
int main(){cin>>n;dfs(1);//從第一行開始搜索cout<<ans;return 0;
}#include <bits/stdc++.h>
using namespace std;
const int N=16;
int a[N];//表示第i行皇后放在a[i]列
int n,cnt;
// int vis[N][N];
vector<int>ans;
int nd=3;
bool check(int x){//輸入行,不與每一行的皇后成關系就行
//檢查x行 a[x]列的皇后是否可以放for(int i=1;i<x;i++){//遍歷之前的所有行if(a[i]==a[x]||a[i]-i==a[x]-x||a[x]+x==a[i]+i)return 0;}//主對角線行-列=行-列 副對角線上行+列=行+列
//若位于同一列 或位于同一主對角線上或者位于同一副對角線上就不行return 1;
}
void dfs(int dep){if(dep==n+1){cnt++;//該搜索第n+1行了就說明前n行已經拍好了if(nd-->0){for(int i=0;i<n;i++){cout<<ans[i]<<" \n"[i==n-1];}}return ;}for(int i=1;i<=n;i++){a[dep]=i;//遍歷假設放在了(dep,a[dep])位置if(!check(dep))continue;//如果不行 跳ans.push_back(i);//存起來放在了第i列dfs(dep+1);//搜索下一行ans.pop_back();//回溯a[dep]=0;//數組的a[dep]按理也得恢復現場}}
int main(){cin>>n;dfs(1);cout<<cnt;return 0;
}?P2392 kkksc03考前臨時抱佛腳 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
//dp[j]表示只考慮前面幾個商品 在總時間為j的條件下所能得到的最大價值(最大時間)
int main(){for(i=1;i<=4;i++)cin>>a[i];for(i=1;i<=4;i++){sum=0; for(j=1;j<=a[i];j++){cin>>homework[j];//輸入sum+=homework[j];}//總時間累加
//最快洗車時間的問題for(j=1;j<=a[i];j++)for(k=sum/2;k>=homework[j];k--)//只要是總和的一半dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);//01背包t+=sum-dp[sum/2];//累加為另一個腦子memset(dp,0,sizeof(dp));}cout<<t;//輸出return 0;
}?P1443 馬的遍歷 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N=406;
int xx[]={2,2,-2,-2,1,-1,1,-1};
int yy[]={1,-1,-1,1,2,-2,-2,2};//八個方向
int mp[N][N];int cnt=0;int n,m;void bfs(int x,int y,int c){//廣度優先搜索模板queue<PII>q;q.push({x,y});mp[x][y]=c;while(!q.empty()){auto cur=q.front();q.pop();int cx=cur.first;int cy=cur.second;for(int i=0;i<8;i++){int tx=cx+xx[i];int ty=cy+yy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[tx][ty]==-1){mp[tx][ty]=mp[cx][cy]+1;//從上一個的轉移一次 所以要在上一次的基礎上+1q.push({tx,ty});}}}
}void solve(){cin>>n>>m;int x,y;cin>>x>>y;memset(mp, -1, sizeof(mp));// mp[x][y]=0;bfs(x,y,0);for(int i=1;i<=n;i++){//一定要看好時從(0,0)開始還是從(1,1)開始for(int j=1;j<=m;j++){printf("%-5d",mp[i][j]);//-5是每一行開頭的那個元素不產生占位5 4 3 2 這樣//5是每一行從開頭就產生占位 5 4 3 2這樣}cout<<'\n';}
}signed main(){int t=1;while(t--)solve();return 0;
}#include <iostream>
#include <queue>
using namespace std;
int k[205], n; // k[i] 表示在i樓能向上或向下走多少步struct node { // 定義一個結構體int point, step; // point是現在在哪一樓，step是現在點了幾次按鈕到達這一樓
};bool vis[205]; // 記錄之前是否到達過（或者可以到達）這個樓數，那么下一次的統計的步數肯定大于等于這一樓記錄過的最少步數，不更新這一樓的答案。int BFS(int a, int b) {queue < node > q;q.push(node{a, 0});while (q.size()) { // 隊列里還有元素就用隊頭元素嘗試更新node p = q.front();if (p.point == b) { // 到了目標樓層return p.step; // 返回步數}q.pop();if (p.point + k[p.point] >= 1 && p.point + k[p.point] <= n && ! vis[p.point + k[p.point]]) { // 往上走，符合條件（在1~n層之間）且沒被訪問過（說明是第一次入隊，也就是這次被訪問就是最短的步數）q.push((node){p.point + k[p.point], p.step + 1});vis[p.point + k[p.point]] = 1;}if (p.point - k[p.point] >= 1 && p.point - k[p.point] <= n && ! vis[p.point - k[p.point]]) { // 往下走q.push((node){p.point - k[p.point], p.step + 1});vis[p.point - k[p.point]] = 1;}}return -1; // 無解
}int main() {int a, b;cin >> n >> a >> b;for (int i = 1; i <= n; i++) cin >> k[i];//每個電梯的能量值cout << BFS(a, b);
}P1135 奇怪的電梯 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)?
#include <iostream>
#include <queue>
using namespace std;
int k[205], n; // k[i] 表示在i樓能向上或向下走多少步struct node { // 定義一個結構體int point, step; // point是現在在哪一樓，step是現在點了幾次按鈕到達這一樓
};bool vis[205]; // 記錄之前是否到達過（或者可以到達）這個樓數，那么下一次的統計的步數肯定大于等于這一樓記錄過的最少步數，不更新這一樓的答案。int BFS(int a, int b) {queue < node > q;q.push(node{a, 0});while (q.size()) { // 隊列里還有元素就用隊頭元素嘗試更新node p = q.front();if (p.point == b) { // 到了目標樓層return p.step; // 返回步數}q.pop();if (p.point + k[p.point] >= 1 && p.point + k[p.point] <= n && ! vis[p.point + k[p.point]]) { // 往上走，符合條件（在1~n層之間）且沒被訪問過（說明是第一次入隊，也就是這次被訪問就是最短的步數）q.push((node){p.point + k[p.point], p.step + 1});vis[p.point + k[p.point]] = 1;}if (p.point - k[p.point] >= 1 && p.point - k[p.point] <= n && ! vis[p.point - k[p.point]]) { // 往下走q.push((node){p.point - k[p.point], p.step + 1});vis[p.point - k[p.point]] = 1;}}return -1; // 無解
}int main() {int a, b;cin >> n >> a >> b;for (int i = 1; i <= n; i++) cin >> k[i];cout << BFS(a, b);
}P2895 [USACO08FEB] Meteor Shower S - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)?
P1036 [NOIP2002 普及組] 選數 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
int n,k;
const int N=26;
int a[N],vis[N]={0};
int ans=0;
typedef long long ll;
bool isprime(int x){for(int i=2;i<=x/i;i++){if(x%i==0)return 0;}return 1;
}
void dfs(int m, int sum, int startx){//最重要的遞歸
//m代表現在選擇了多少個數
//sum表示當前的和
//startx表示升序排列，以免算重if(m == k){//如果選完了的話if(isprime(sum))ans++;//ans加一return ;}for(int i = startx; i < n; i++)//往后找dfs(m + 1, sum + a[i], i + 1);//遞歸//步數要加一，和也要加//升序起始值要變成i+1,以免算重return ;//這一個步驟下，所有的都枚舉完了//直接返回去
}
int main(){scanf("%d%d",&n,&k);//輸入for(int i = 0; i < n; i++)scanf("%d",&a[i]);//循環讀入dfs(0,0,0);//調用函數printf("%d\n",ans);//輸出答案return 0;//結束程序
}
//另一種思路錯的原因是因為可能出現 1 2 1 1 3 6 7這樣的情況P2036 [COCI2008-2009 #2] PERKET - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)?
#include<bits/stdc++.h> //非常穩健的萬能頭
using namespace std;
long long int s[20],b[20],f[20]; //s表示酸度，b表示甜度，f記錄是否查找
long long int n,j,c=1,y=0,ans=99999999999; //ans記錄最小值
void dfs(int x){if(x>n)return ; //最多選n種調料，超過不做操作for(int i=1;i<=n;i++){if(f[i]==0) //沒有查找過的才操作{c*=s[i];y+=b[i];ans=min(ans,abs(c-y)); //取最小值f[i]=1; //記錄dfs(x+1);f[i]=0; //回溯c/=s[i];y-=b[i];}}
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>s[i]>>b[i];}dfs(1);cout<<ans;
}?
#include <btis/stdc++.h>
using namespace std;
int a[15],b[15],n,ans=1<<30; //a表示酸度，b表示甜度，ans為最終答案。
void dfs(int i,int sj,int th){if(i>n){if(!th)return ; //如果沒有選任何一種材料。ans=min(ans,abs(sj-th)); //否則更新答案。return ;}dfs(i+1,sj,th); //選dfs(i+1,sj*a[i],th+b[i]); //不選
}
int main(){int i;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d %d",&a[i],&b[i]);dfs(1,1,0); //搜索，注意酸度初始值一定為1，甜度初始值一定為0.printf("%d",ans);return 0;
}?
?
![[筆記] wsl 禁用配置 win系統環境變量+代理](http://pic.xiahunao.cn/[筆記] wsl 禁用配置 win系統環境變量+代理)