https://vjudge.net/contest/210085#overview
A
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
2 1
简单dfs，不多解释
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 using namespace std; int n,k; char mp[10][10]; bool vis[10]; int flag=0; void dfs(int res,int ans) { if(ans==k) { flag++; return ; } if(res>n)return ; for(int j=1;j<=n;j++) { if(mp[res][j]=='#'&&!vis[j]) { vis[j]=true; dfs(res+1,ans+1); vis[j]=false; } } dfs(res+1,ans); } int main() { while(scanf("%d%d",&n,&k)!=EOF){ if(n==-1)break; getchar(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) { scanf("%c",&mp[i][j]); } getchar(); } memset(vis,false,sizeof(vis)); flag=0; dfs(1,0); printf("%d ",flag); } return 0; }
B --------------简单题+复杂的数据处理+简单dfs 就直接略了（二维改三维真的头疼）
C
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers:
N and
K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
题意： 给数a和b；
要求a-->b 方式：1，+1
2，-1
3， *2
求最少的步数
思路： bfs等步数跑，，就可以求出最小的步数 （仔细琢磨推算吧，刚开始写的时候脑子还是晕的）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 using namespace std; int vis[100005]={0}; int o,p; struct node{ int x,step; //x表示值 step表示步数 }s1,s2; //s1用来存第一次变换，s2用来第二次变换 queue<node>que; void solve(int x,int step) { s2.x=x; vis[x]=1;//标记数值x已经走过了 s2.step=step+1; que.push(s2); } int bfs(int a,int b) { int zz; s1.x=a; s1.step=0; que.push(s1); while(!que.empty()) { s1=que.front(); que.pop(); if(s1.x==b)return s1.step; zz=s1.x-1; if(zz>=0&&zz<=100005&&!vis[zz]) { solve(zz,s1.step); } zz=s1.x+1; if(zz>=0&&zz<=100005&&!vis[zz]) { solve(zz,s1.step); } zz=s1.x*2; if(zz>=0&&zz<=100005&&!vis[zz]) { solve(zz,s1.step); } } return -1; } int main() { while(cin>>o>>p) { int sun=bfs(o,p); cout<<sun<<endl; } return 0; }
E
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2 6 19 0
Sample Output
10 100100100100100100 111111111111111111
题意：
给一个数n，让你找出一个只有1，0，组成的十进制数，要求是找到的数可以被n整除。
解题思路：
最高位为1， 接下来每一位不是0就是1，双入口bfs
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 using namespace std; typedef unsigned long long ll; ll tem,n; void bfs(int n) { queue<ll>que; // while(!que.empty()) // que.pop(); que.push(1); while(!que.empty()) { tem=que.front(); que.pop(); if(tem%n==0){cout<<tem<<endl;break;} que.push(tem*10); que.push(tem*10+1); } } int main() { int n; while(cin>>n) { if(n==0)break; bfs(n); } return 0; }
F
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
1733
3733
3739
3779
8779
8179
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
3 1033 8179 1373 8017 1033 1033
Sample Output
6 7 0
题意： 给定两个素数（四位数），求第一个数经过几次转换可以得到第二个素数。
转换方式：是变换数中某一位的数字（第一位不能为零，其它的变换数字是0~~9），变换之后的数也为素数。
思路：bfs。搜索求最短路径，非常easy就想到广度优先搜索。由于广度优先搜索。第一次搜到得到的步数就是最少的步数。另外打素数表提高推断的时候的效率。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 typedef long long ll; using namespace std; struct node{ int x[4]; int step; }; node st,st1,now; ll ans=0; int a,b,c,d,sum; int vis[maxn]; int m,n,t; bool solve(int n)//素数判定 { for(int i=2;i<=sqrt(n);i++) { if(n%i==0) return false; } return true; } int bfs() { memset(vis,0,sizeof(vis)); queue<node>que; while(!que.empty())que.pop(); st.x[0]=m/1000; st.x[1]=(m/100)%10; st.x[2]=(m/10)%10; st.x[3]=m%10; st.step=0; que.push(st); while(!que.empty()) { st1=que.front(); que.pop(); if(st1.x[0]==a&&st1.x[1]==b&&st1.x[2]==c&&st1.x[3]==d) return st1.step; for(int i=0;i<4;i++) for(int j=0;j<=9;j++) { if(i==0&&j==0)continue; //表示第一位置不能为0 if(st1.x[i]==j)continue; //表示如果和原始数值相等的话就不用变换 now.x[0]=st1.x[0]; now.x[1]=st1.x[1]; now.x[2]=st1.x[2]; now.x[3]=st1.x[3]; now.step=st1.step; now.x[i]=j; sum=now.x[0]*1000+now.x[1]*100+now.x[2]*10+now.x[3]; if(solve(sum)&&!vis[sum]) { vis[sum]=1; now.step++; que.push(now); } } } return -1; } int main() { //prime(); cin>>t; while(t--) { cin>>m>>n; a=n/1000;b=(n/100)%10;c=(n/10)%10;d=n%10; ll zz=bfs(); if(zz==-1) cout<<"Impossible"<<endl; else cout<<zz<<endl; } return 0; } 素数筛法的板子（用于判断素数或者求出大区间内所有素数） // 优化后的筛法就可以避免这种不必要的删去操作 //#define Max 1000000 //bool prime[Max]; //void IsPrime(){ // prime[0]=prime[1]=0;prime[2]=1; // for(int i=3;i<max;i++) // prime[i]=i%2==0?0:1; // int t=(int)sqrt(Max*1.0); // for(int i=3;i<=t;i++) // if(prime[i]) // for(int j=i*i;j<Max;j+=2*i)//优化 // prime[j]=0; //} //这就是素数的二次筛法，博士独创~~~~~ //与前两种筛法不同，此种筛法中prime[i]=2*i+3（即：我们只存储奇数，偶数肯定不是素数的） //#define Max 1000000 //bool prime[Max>>1]; //void IsPrime(){ // memset(prime,true,sizeof(prime)); // int n=Max>>1,m=(int)(sqrt(Max*1.0)/2.0); // for(int i=0;i<=m;i++) // if(prime[i]) // for(int j=2*i*i+6*i+3;j<=n;j+=2*i+3) // isprime[j]=false; //}