【思特奇杯·云上蓝桥-算法集训营】第2周

1.带分数

#include <iostream>  using namespace std;  int a[10]={0，1，2，3，4，5，6，7，8，9}； int book[10]; int total=0,N; void judge(int a[]); void dfs(int step);  int main(){     cin>>N;     dfs(1);     cout<<total;     return 0; }  int num(int x,int y){     int num=0,i;     for(i=x;i<=y;i  ){         num=num*10 a[i];     }     return num; }  void judge(int a[]){     int i,j;     for(i=1;i<=7;i  ){         int interger=num(1,i);//控制分子         for(j=(9-i)/2 i;j<=9;j  ){             int fz=num(i 1,j-1);             int fm=num(j,9);             if(interger fz/fm==N&(fz%fm==0))                 total  ;         }     } }  void dfs(int step){     if(step==10){         judge(a);     }     for(int i=1;i<=9;i  ){         if(book[i]==0){             a[step]=i;             book[i]=1;             dfs(step 1);             book[i]=0;         }     } } 

2.李白打酒

#include<iostream> using namespace std;  int sum = 0;  void f(int flower,int store,int cur_sum){  if(flower==1&&store==0&&cur_sum==1){   sum  ;   return ;   }  if(flower>1){   f(flower-1,store,cur_sum-1);     }  if(store>0)  {   f(flower,store-1,cur_sum*2);  }       } int main(){  f(10,5,2);  cout<<sum<<endl;  return 0; }  

3.第39级台阶

#include<cstdio> #include <iostream> using namespace std; int sum; void dfs(int n,int k)//k步数。、、n为台阶数 {     if(n>39) return;//结束条件     if(n==39&&k%2==0)//j结束条件     {         sum  ;         return;     }     dfs(n 1,k 1)；//寻找     dfs(n 2,k 1); } int main() {     sum=0;     dfs(0,0);     cout<<sum<<endl;     return 0; }  

4.跨越雷区

#include<bits/stdc  .h> using namespace std; struct jg{     int x,y,s; }; char a[101][101]; int dir[4][2]={0，1，0，0，-1，-10}; bool bj[101][101]; queue<jg>q; jg dq,hm; int n,qsx,qsy; void bfs(); int main() {     int i,j;     cin>>n;     for(i=1;i<=n;i  )     {         for(j=1;j<=n;j  )         {             cin>>a[i][j];             if(a[i][j]=='A')             {                 qsx=i;                 qsy=j;             }         }     }     bfs();     return 0; } void bfs() {     int i,dx,dy;     dq.x=qsx;     dq.y=qsy;     dq.s=0;     q.push(dq);     bj[qsx][qsy]=true;     while(!q.empty())     {         dq=q.front();         q.pop();         if(a[dq.x][dq.y]=='B')         {             cout<<dq.s<<endl;             return;         }         for(i=0;i<4;i  )         {             dx=dq.x dir[i][0];             dy=dq.y dir[i][1];             if(dx>=0&&dx<=n&&dy>=0&&dy<=n&&!bj[dx][dy]&&a[dx][dy]!=a[dq.x][dq.y])             {                 hm.x=dx;                 hm.y=dy;                 hm.s=dq.s 1;                 bj[dx][dy]=true;                 q.push(hm);             }         }     } } 

5.迷宫

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef pair<int,int>PII; int n,m; char ct[55][55]; int dist[55][55]; int dx[4]={1，0，0，0，-1}； int dy[4]={0,-1,1,0}; void bfs(PII start){     queue<PII>q;     memset(dist,-1,sizeof(dist));     dist[start.first][start.second]=0;     q.push(start);     while(q.size()){         auto t=q.front();         q.pop();         for(int i=0;i<4;i  ){             int x=t.first dx[i];             int y=t.second dy[i];             if(x>=0 && x<n && y>=0 && y<m && dist[x][y]==-1 && ct[x][y]=='0'){                 dist[x][y]=dist[t.first][t.second] 1;                 q.push({x,y});             }         }              }      } int main(){     cin>>n>>m;     for(int i=0;i<n;i  ){         for(int j=0;j<m;j  ){             cin>>ct[i][j];         }     }     PII start,end;     start={n-1,m-1};     bfs(start);     cout<<dist[0][0];     string res;     int x=0;     int y=0;     char dir[4]={'D','L','R','U'};     while(x!=n-1 || y!=m-1){         for(int i=0;i<4;i  ){             int nx=x dx[i];             int ny=y dy[i];             if(nx>=0 && nx<n && ny>=0 && ny<m && ct[nx][ny]=='0'){                 if(dist[x][y]==1 dist[nx][ny]){                     x=nx;                     y=ny;                     res =dir[i];                     break;                 }             }         }     }     cout<<res; } 

6.跳马

#include<iostream> #include<queue> using namespace std; const int X[8] = {-2，-2，-1，，1，2，2}； const int Y[8] = {1，1，2，2，2，21,1};
int board[9][9];
struct Coordinate{
	int x,y,p;
	Coordinate(int x,int y,int p):x(x),y(y),p(p){}
};
queue<Coordinate> q;
void bfs(){
	Coordinate t = q.front();
	q.pop();
	for(int i=0;i<8;i++){
		int tx = t.x + X[i];
		int ty = t.y + Y[i];
		if(tx<1||tx>8||ty<1||ty>8||board[tx][ty])continue;
		board[tx][ty] = t.p + 1;
		q.push(Coordinate(tx,ty,board[tx][ty]));
	}
}
int main(){
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	board[x1][y1] = 1;
	q.push(Coordinate(x1,y1,1));
	bfs();
	cout<<board[x2][y2]-1<<endl;
	return 0;
}

7.路径之谜

#include <iostream>
#include <stdlib.h>
using namespace std;
 
int arr[22][22]={0}; //(i-1)*N + j - 1 
int ans[410];
int count_ans=0;
int N;
 
 bool dfs(int i, int j)
 {
 	if(i == N && j == N)
 	{
 		//判断是否所有箭都中了
 		int flag=0;
		for(int k=1; k<=N; k++)
		{
			flag+=arr[k][0];
			flag+=arr[0][k];
		 	if(flag>2)
		 		break;
		}
		//已经找到这条路了 
		if(flag == 2) 
		{
			for(int k=0; k<count_ans; k++)
				cout<<ans[k]<<" ";
			cout<<N*N-1; 
			return true;
		} 
		else
			return false;
	}
	
	if(i<1 || i>N || j<1 || j>N)//剪枝3：超出范围 
		return false; 
	if(arr[i][j] != 0)//剪枝1：走过
		return false;
	if(arr[i][0] == 0 || arr[0][j] == 0)//剪枝2：箭不够了
		return false;
	
 	arr[i][j]=1;//设为旧点，拔出箭 ，放入答案栈 
 	arr[i][0]--;
 	arr[0][j]--;
 	ans[count_ans++]= (i-1)*N + j - 1 ;
 	if(dfs(i+1,j)||dfs(i-1,j)||dfs(i,j+1)||dfs(i,j-1)) 
 		return true;
 	count_ans--;//复原 
 	arr[i][0]++;
 	arr[0][j]++;
 	arr[i][j]=0;
 	return false;
 }
 
int main()
{
	cin>>N;
	for(int i=0; i<N; i++)
		cin>>arr[0][i+1];
	for(int i=0; i<N; i++)
		cin>>arr[i+1][0];
 
	dfs(1,1);
 
	return 0;
}

8.未名湖边的烦恼

#include<bits/stdc++.h>

using namespace std;

int res(int m, int n){
	if(m < n){
		return 0;	//无鞋可借 
	}
	if(n == 0){
		return 1;//都有鞋穿了 
	} 
	return  res(m - 1, n) + res(m, n - 1);
} 

int main() {
	int m, n;
	cin >> m >> n;
	int r = res(m, n);
	cout << r;
	return 0;
}

9.大臣的旅费

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 1e4+5;
const int INF = 0x3f3f3f3f;
int n, dis[maxn];
bool book[maxn];
struct node
{
    int v, w;
    node() {}
    node(int vv, int ww): v(vv), w(ww) {}
};
vector<node> g[maxn];
 
void spfa(int u)
{
    memset(book, 0, sizeof(book));
    for(int i = 1; i <= n; i++) dis[i] = INF;
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        book[u] = 0;
        for(int i = 0; i < g[u].size(); i++)
        {
            int v = g[u][i].v;
            int w = g[u][i].w;
            if(dis[u]+w < dis[v])
            {
                dis[v] = dis[u]+w;
                if(!book[v])
                {
                    book[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
 
int solve()
{
    spfa(1);
    int tmp = 0, tmpIndex;
    for(int i = 1; i <= n; i++)
        if(dis[i] > tmp)
            tmp = dis[i], tmpIndex = i;
    spfa(tmpIndex);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(dis[i] > ans)
            ans = dis[i];
    return ans*10+(1+ans)*ans/2;
}
 
int main(void)
{
    while(cin >> n)
    {
        for(int i = 0; i < maxn; i++) g[i].clear();
        for(int i = 1; i < n; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(node(v, w));
            g[v].push_back(node(u, w));
        }
        printf("%d\n", solve());
    }
    return 0;
}

10.2n皇后问题

#include<bits/stdc++.h> 
#define N 10 
using namespace std; 

  
int n;
  
int map_Q[N][N];
  
int posb[N]={0};  
int posw[N]={0}; 
 
int tot = 0;   
 
bool checkw( int cur) //检查函数
{  
    for( int i = 1; i < cur; i++)  
        if( posw[i] == posw[cur] || abs(i-cur) == abs(posw[i]-posw[cur]))  
            return false;  
    return true;  
}   
 
bool checkb( int cur)  //检查函数
{  
    for( int i = 1; i < cur; i++)  
        if( posb[i] == posb[cur] || abs(i-cur) == abs(posb[i]-posb[cur]))  
            return false;  
    return true;  
}  
 
void dfs_white( int cur)  
{  
    if( cur == n+1)  //白皇后也全部放完，次数+1
    {  
        tot++;  
      }
    for( int i = 1; i <= n; i++)  
    {  
        if( posb[cur] == i) //表示第cur列的第i行位置已经被黑皇后占用，
            continue;        //结束当前循环，i+1
        if( map_Q[cur][i] == 0)  //再判断前提条件是否成立
            continue;  
        posw[cur] = i;    //尝试把第cur列的白皇后放在第i行上
        if( checkw(cur))   //判断能否放置白皇后
            dfs_white(cur+1);  //递归
    }  
}  
  
void dfs_black( int cur)  
{  
    if( cur == n+1)  //当黑皇后处理完时，再处理白皇后
    {  
        dfs_white(1);  
    }  
    for( int i = 1; i <= n; i++)  
    {  
       if( map_Q[cur][i] == 0)  //如果第cur列第i行满足放皇后的前提条件即 mp[cur][i] == 1
            continue;  //如果不满足，则结束当前循环，进行下一次循环即i+1。
         posb[cur] = i;     //就尝试把第cur列的黑皇后放在第i行上
        if( checkb(cur))   //然后判断该尝试是否成立，如成立，则进行递归，如不成立，则尝试把当前列的黑皇后放在下一行(i+1行)上。
            dfs_black(cur+1);  //递归
    }  
}  
  
int main(){     
   cin>>n;
   for( int i = 1; i <= n; i++)   //定义棋盘
       for( int j = 1; j <= n; j++)  
           cin>>map_Q[i][j];    

   dfs_black(1);    //先把黑皇后放在第一列
   cout<<tot<<endl; 
   
   return 0;  
}