ACM_acm答案
ACM由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“acm答案”。
Dijkstra 模板
/*************************************** * About:
有向图的Dijkstra算法实现 * Author:
Tanky Woo * Blog:
www.daodoc.comt=0;
if(flag == 0){
printf(“Non”);
}
else{
for(int i=min;i
if(mark[i]==1 && arr[i]==0)
cnt++;
}
}
if(cnt==1)
printf(“Yesn”);
else
printf(“Non”);}
} return 0;搜索算法模板
BFS：
1.#include 2.#include 3.#include 4.#include 5.using namespace std;6.const int maxn=100;7.bool vst[maxn][maxn];// 访问标记
8.int dir[4][2]={0,1,0,-1,1,0,-1,0};// 方向向量 9.10.struct State // BFS 队列中的状态数据结构 11.{ 12.int x,y;// 坐标位置
13.int Step_Counter;// 搜索步数统计器 14.};15.16.State a[maxn];17.18.boolCheckState(State s)// 约束条件检验 19.{ 20.if(!vst[s.x][s.y] &&...)// 满足条件 1: 21.return 1;22.else // 约束条件冲突 23.return 0;24.} 25.26.void bfs(State st)27.{ 28.queue q;// BFS 队列
29.State now,next;// 定义2 个状态，当前和下一个 30.st.Step_Counter=0;// 计数器清零 31.q.push(st);// 入队
32.vst[st.x][st.y]=1;// 访问标记 33.while(!q.empty())34.{ 35.now=q.front();// 取队首元素进行扩展
36.if(now==G)// 出现目标态，此时为Step_Counter 的最小值，可以退出即可 37.{ 38.......// 做相关处理 39.return;40.} 41.for(int i=0;i
57.int main()58.{ 59.......60.return 0;61.}
代码：
胜利大逃亡
Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.Input 输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1
特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.Output 对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.Sample Input 1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0
Sample Output 11
代码：
#include #include #include #include #include
using namespace std;
int tx[] = {0,1,-1,0,0,0,0};
int ty[] = {0,0,0,1,-1,0,0};
int tz[] = {0,0,0,0,0,1,-1};
int arr[55][55][55];int known[55][55][55];// 访问标记 int a,b,c,d;struct state{
int x,y,z;
// 所在的坐标
int step_count;//统计搜索步数。};
int check(int x, int y, int z){
if(x>=1 && x=1 && y=1 && z
return 1;
return 0;} int bfs(int a, int b, int c){
queue q;
state temp, now;
temp.x=1;
temp.y=1;
temp.z=1;
// 对压入队列的state元素进行初始化
q.push(temp);
known[1][1][1] = 1;// 第一个元素已经访问;
while(!q.empty()){
now = q.front();
if(now.x == a && now.y == b && now.z == c &&(known[a][b][c]-1)
return known[a][b][c]-1;
}
int fangxiang=1;
for(;fangxiang
temp = now;
temp.x += tx[fangxiang];
temp.y += ty[fangxiang];
temp.z += tz[fangxiang];
if(check(temp.x, temp.y, temp.z)&&!known[temp.x][temp.y][temp.z]){
known[temp.x][temp.y][temp.z] = known[now.x][now.y][now.z]+1;
q.push(temp);
}
}
q.pop();
}
return-1;} int main(){
int t;
int i, j, k;
scanf(“%d”,&t);
while(t--){
scanf(“%d%d%d%d”,&a, &b, &c, &d);
memset(known,-1,sizeof(known));
memset(arr,-1,sizeof(arr));
for(i=1;i
for(j=1;j
for(k=1;k
arr[i][j][k]=0;
known[i][j][k]=0;
// 对访问标记进行初始化 置为0，1 代表已经访问过。
scanf(“%d”,&arr[i][j][k]);
}
}
}
int cur = bfs(a, b, c);
printf(“%dn”,cur);
}
return 0;}
超级密码
Problem Description Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息: 密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0
注意:由于宝藏的历史久远,当时的系统最多只能保存500位密码.因此如果得到的密码长度大于500也不能用来开启房门,这种情况也被认为密码不存在.Input 输入数据的第一行是一个整数T(1
注意:在给出的M个数字中,如果存在超过10的数,我们约定用A来表示10,B来表示11,C来表示12,D来表示13,E来表示14,F来表示15.我保证输入数据都是合法的.Output 对于每组测试数据,如果存在要求的密码,则输出该密码,如果密码不存在,则输出“give me the bomb please”.注意:构成密码的数字不一定全部都要用上;密码有可能非常长,不要试图用一个整型变量来保存密码;我保证密码最高位不为0(除非密码本身就是0).Sample Input 3 22 10 3 7 0 1 10 1 1 16 3 A B C
Sample Output 110 give me the bomb please CCB
代码：
#include #include #include #include using namespace std;
int num[20],vis[5005];int n,c,m;
struct node {
int s[505];//将每一位的字符压入此数组
int len;};
int print(node a)//输出函数 {
int i;
for(i = 0;i
{
if(a.s[i]
printf(“%d”,a.s[i]);
else
printf(“%c”,a.s[i]+'A'-10);
}
printf(“n”);}
int mod(node a)//由于数字大，采用这种大数取模方式 {
int i,tem = 0;
for(i = 0;i
{
tem =(tem*c+a.s[i])%n;//由于是n进制，tem在前面的基础上乘以进制数c在加上下一位，如果能整除n，那必定是n的倍数，则成立
}
return tem;}
int BFS(){
memset(vis,0,sizeof(vis));
node a;
queue Q;
a.len = 0;
int i,r;
for(i = 1;i
{
if(num[i])//这个数是给出的样例
{
a.s[0] = i;//压入数组
a.len = 1;//长度变化
r = mod(a);
if(!r)//模为0，则肯定是n的倍数，输出
{
print(a);
return 1;
}
else
{
if(!vis[r])//余数不能与之前出现过的余数相同，因为前面出现过的序列，肯定包含同样余数却在后面出现的序列
{
vis[r] = 1;//标记该余数已被访问
Q.push(a);
}
}
}
}
while(!Q.empty())
{
a = Q.front();
Q.pop();
for(i = 0;i
{
if(num[i])
{
a.s[a.len] = i;
a.len++;
r = mod(a);
if(!r)//一直找到能整除n的方案
{
print(a);
return 1;
}
else
{
if(!vis[r] && a.len
{
vis[r] = 1;
Q.push(a);
}
}
a.len--;//是不是觉得这里与a.len++这句话会无限重复，导致a.len一直为1？错了！要注意，在r与之前出现过的余数相同是，这次的a是没有压入队列的，也就是这次的a.len减少了，但是在队列中的a.len却没有减少！
}
}
}
return 0;}
int main(){
int t,i;
char str[2];
scanf(“%d”,&t);
while(t--)
{
scanf(“%d%d%d”,&n,&c,&m);
memset(num,0,sizeof(num));
for(i = 0;i
{
scanf(“%s”,str);
if(str[0]>='0' && str[0]
num[str[0]-'0'] = 1;
else
num[str[0]-'A'+10] = 1;
}
if(n)
{
int flag;
flag = BFS();
if(!flag)
printf(“give me the bomb pleasen”);
}
else
{
if(num[0])
printf(“0n”);
else
printf(“give me the bomb pleasen”);
}
}
return 0;}
DFS:
1./* 2.该DFS 框架以2D 坐标范围为例，来体现DFS 算法的实现思想。3.*/ 4.#include 5.#include 6.#include 7.using namespace std;8.const int maxn=100;9.bool vst[maxn][maxn];// 访问标记 10.int map[maxn][maxn];// 坐标范围
11.int dir[4][2]={0,1,0,-1,1,0,-1,0};// 方向向量，(x,y)周围的四个方向 12.13.bool CheckEdge(int x,int y)// 边界条件和约束条件的判断 14.{ 15.if(!vst[x][y] &&...)// 满足条件 16.return 1;17.else // 与约束条件冲突 18.return 0;19.} 20.21.void dfs(int x,int y)22.{ 23.vst[x][y]=1;// 标记该节点被访问过
24.if(map[x][y]==G)// 出现目标态G，最终的目标。25.{ 26.......// 做相应处理 27.return;28.} 29.for(int i=0;i
Prime Ring Problem Problem Description A ring is compose of n circles as shown in diagram.Put natural number 1, 2,..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.Note: the number of first circle should always be 1.Input n(0
You are to write a program that completes above proce.Print a blank line after each case.Sample Input 6 8
Sample Output Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
#include #include #include #include using namespace std;
int str[25];int known[25];int num;int cases=1;
bool isPrime(int x){ for(int i = 2;i
if(x % i == 0)return 0;
return 1;}
void DFS(int n, int len){ int i;if(len==n && isPrime(str[n-1]+1)){
for(i=0;i
printf(“%d ”, str[i]);
}
printf(“n”);} else{
for(i=2;i
if(isPrime(i+str[len-1])&&!known[i]){
known[i]=1;
str[len] = i;
DFS(n, len+1);// 在这里注意不能使用len++ 因为这会影响len的值 而在返回的时候这个值是不应该被影响的known[i]=0;
}
} } }
void init(){ memset(known, 0, sizeof(known));known[1] = 1;str[0] = 1;}
int main(int argc, char *argv[]){ int n;num = 1;while(~scanf(“%d”,&n)){
init();
printf(“Case %d:n”,cases++);
DFS(n, 1);}
return 0;}
棋盘覆盖2 #include #include #include #include char board[10][10];
//记录棋盘状态
int place[10];
//记录一列是否已经放过棋子 int n,k;int cnt,num;
//cnt 是放棋子的方案数，num是已放棋子数目
using namespace std;void dfs(int i){ int j;if(k==num){
cnt++;
//board[i][j]='&';
return;} if(i>=n)
return;for(j=0;j
if(!place[j]&& board[i][j]=='#')
{
place[j]=1;
num++;
dfs(i+1);
place[j]=0;
num--;
}//i行不放棋子
dfs(i+1);}
int main(){ while(scanf(“%d%d”,&n,&k)){
getchar();
if(n==-1&&k==-1)
break;
for(int i=0;i
{
for(int j=0;j
scanf(“%c”,&board[i][j]);
getchar();
}
memset(place,0,sizeof(place));
cnt=0;
num=0;
dfs(0);
printf(“%dn”,cnt);
}
return 0;}
