G::::::::::::::::::路径之迷（DFS）
题目描述
小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。
按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入描述
第一行一个整数 N (0≤N≤20)，表示地面有N×N 个方格。
第二行 N 个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行 N 个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出描述
输出一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯
比如，上图中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例
示例
输入
4 2 4 3 4 4 3 3 3
输出
#include <iostream> using namespace std; int n; int g[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int shang[25]; int zuo[25]; int shang1[25]; int zuo1[25]; bool falge; struct node{ int x,y; }; node lu[405]; bool vis[25][25]; int m=1; bool check1(){ for(int i=0;i<n;i++){ if(shang[i]!=shang1[i] || zuo[i]!=zuo1[i]){ return false; } } return true; } bool check2(int x,int y){ return x>=0&&y>=0&&x<n&&y<n; } bool check3(){ for(int i=0;i<n;i++){ if(shang1[i]>shang[i] || zuo1[i]>zuo[i]){ return false; } } return true; } void dfs(int x,int y){ if(!check3()|| falge){ //剪枝 return; } if(x==n-1&&y==n-1 && check1()){ for(int i=0;i<m;i++){ cout<<lu[i].x*n+lu[i].y<<' '; } falge=1; return; } for(int i=0;i<4;i++){ int tx=x+g[i][0]; int ty=y+g[i][1]; if(check2(tx,ty) && !vis[tx][ty]){ vis[tx][ty]=1; lu[m].x=tx; lu[m].y=ty; shang1[ty]+=1; zuo1[tx]+=1; m++; dfs(tx,ty); lu[m].x=0; lu[m].y=0; shang1[ty]-=1; zuo1[tx]-=1; m--; vis[tx][ty]=0; } } } int main(){ zuo1[0]=1; shang1[0]=1; lu[0].x=0; lu[0].y=0; vis[0][0]=1; cin>>n; for(int i=0;i<n;i++){ cin>>shang[i]; } for(int i=0;i<n;i++){ cin>>zuo[i]; } dfs(0,0); return 0; }
H::::::::::::::::::分考场(DFS)
题目描述
n 个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入描述
输入格式：
第一行，一个整数 n (1≤n≤100)，表示参加考试的人数。
第二行，一个整数 m，表示接下来有 m 行数据。
以下 m 行每行的格式为：两个整数 a,b，用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。
输出描述
输出一行一个整数，表示最少分几个考场。
输入输出样例
示例
输入
5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
输出
4
#include <iostream> using namespace std; int n,m; bool xi[105][105]; int ans=1e8; int cher[105][105]; void dfs(int p,int room){ if(room>=ans){ return; } if(p>n){ ans=min(ans,room); return; } for(int i=1;i<=room;i++){ int j=0; while(cher[i][j] && !xi[cher[i][j]][p]) j++; if(!cher[i][j]){ cher[i][j]=p; dfs(p+1,room); cher[i][j]=0; } } cher[room+1][0]=p; dfs(p+1,room+1); cher[room+1][0]=0; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; xi[a][b]=xi[b][a]=1; } dfs(1,1); //第一个人，1个教室； cout<<ans; return 0; }
I::::::::::::::::::质数拆分(DP,01背包)
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017+2=2019 视为同一种方法。
运行限制
最大运行时间：1s
最大运行内存: 128M
#include <iostream> using namespace std; long long f[2020][2020]; //前i个数组成j的方案数 bool check(int x){ if(x==1){ return false; } if(x==2){ return true; } for(int i=2;i*i<=x;i++){ if(x%i==0){ return false; } } return true; } int zhi[2020]; int main(){ int len=1; for(int i=1;i<2019;i++){ if(check(i)){ zhi[len++]=i; } } f[0][0]=1;
for(int i=1;i<len;i++){
for(int j=0;j<=2019;j++){
f[i][j]=f[i-1][j];
if(j>=zhi[i]){
f[i][j]+=f[i-1][j-zhi[i]];
}
}
}
cout<<f[len-1][2019];
return 0;
}
状态1：目标:值小于该质数时 f[i][j]=f[i-1][j];
状态2：目标:值不小于该质数时 要加上前i-1质数构成该指数的方案数f[i][j]+=f[i-1][j-zhi[i]];
J::::::::::::::::::修改数组（并查集）
题目描述
给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅,AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。
其中，1≤N≤105，1≤Ai≤106。
输出描述
输出 N 个整数，依次是最终的 A1,A2,⋅⋅⋅,AN。
输入输出样例
示例
输入
5 2 1 1 3 4
输出
2 1 3 4 5
建立一个并查集，初始化根节点都是自己，当第一次出现时，返回根节点也就是自己，然后根节点加一，下次再次查找该数时，发现自己不是大boss，然后找boss，若是下一个boss也不是大boss，就继续找，直到找到大boss。
#include <iostream> using namespace std; int a[10000005]; int find(int x){ if(a[x]!=x) a[x]=find(a[x]); return a[x]; //不是大boss去找大boss } void jiaru(int x,int y){ int tx=find(x); int ty=find(y); if(tx!=ty){ //不是一个大boss建立新的树 a[x]=y; } } int n; int main(){ cin>>n; for(int i=1;i<=10000005;i++){ a[i]=i; //初始化根节点都是自己 } for(int i=1;i<=n;i++){ int x; cin>>x; x=find(x); cout<<x<<' '; a[x]=x+1; } return 0; }
