主页

1.带分数

#include <iostream>
using namespace std;
int x = 0, number = 0, count = 0;
 
//交换a,b两数 
void Swap(int &a,int &b)  
{
    int temp=a;
    a=b;
    b=temp;
}
//将数组区间转化为数字 
int getNum(int list[], int f, int r)  
{  
    int i = 0, num = 0;  
    for (i = f; i <= r; i++)   
        num = list[i] + num * 10; 
    return num;  
}  
void Prim(int list[], int k, int m)
{
    if(k==m-1)
    {
        int a = 0, b = 0, c = 0, bLast = 0;
        for (int i = 0; i < x; i++)
        {  
            a = getNum(list, 0, i);
            bLast=((number-a)*list[8])%10;  
            for (int j =i+(8-i)/2; j < 8; j++)
            {                               
                if(list[j]==bLast)  
                {  
                    b = getNum(list, i+1, j);
                    c = getNum(list, j+1, 8);
                    if (b % c == 0 && a + b / c == number)  
                    {   
                        ++count; 
                    } 
                    break;  
                }  
            }      
        }           
    }
    else
    {
        for(int i=k;i<m;i++)
        {
            Swap(list[k],list[i]);
            Prim(list,k+1,m);
            Swap(list[k],list[i]);
        }
    }
}
//主函数 
int main()
{
    int list[] = {1,2,3,4,5,6,7,8,9};
    cin>>number;           
    int temp = number;
    while (temp != 0)
    {  
        ++x;  
        temp /= 10;  
    }  
    Prim(list,0,9);
    cout<<count;
    return 0;
}

2.李白喝酒

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[15]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,2,2,2,2};//-1遇花,2遇店

    int n = 0;//记录总数
    do{
        int sum = 2; //初始斗酒数

        for(int i=0; i<15; i++){
            if(a[i] == -1){
                sum += a[i];
            }else{
                sum *= a[i];
            }
        }

        if(a[14]==-1&&sum==0){ //a[14]最后一次是遇花
            n +=1;  
        }       

    }while(next_permutation(a,a+15));//全排列

    cout<< n << endl;
    return 0;
}

3.第39级台阶

#include <iostream>
using namespace std;
int num=0;//方案数 

void fun(int n,int step)
//n表示有多少台阶数 ,step表示步数
{
  if(n<0)
    return;
  if(n==0)
  {
    if(step%2==0) num++;
    return;
   }
   fun(n-1,step+1);
   fun(n-2,step+1);
}

int main()
{
  fun(39,0);
  cout<<num<<endl;
}

4.穿越雷区

#include <iostream>
using namespace std;
char graph[105][105];
bool visited[105][105];
int sx, sy, ex, ey;
int n;
int minStep = 0x3FFFFFFF;
void dfs(int x, int y, int cnt, char pre) {
    if (cnt >= minStep) return;
    if (x < 0 || x >= n || y < 0 || y >= n) return;
    if (visited[x][y]) return;
    if (graph[x][y] != pre) {
        visited[x][y] = true;
        if (x == ex && y == ey) {
            minStep = min(minStep, cnt);
            return;
        }
        dfs(x + 1, y, cnt + 1, graph[x][y]);
        dfs(x - 1, y, cnt + 1, graph[x][y]);
        dfs(x, y + 1, cnt + 1, graph[x][y]);
        dfs(x, y - 1, cnt + 1, graph[x][y]);
        visited[x][y] = false;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            // 输入的同时记录起始点和终点坐标
            if (graph[i][j] == 'A') sx = i, sy = j;
            if (graph[i][j] == 'B') ex = i, ey = j;
        }
    }
    dfs(sx, sy, 0, 'T');
    if (minStep != 0x3FFFFFFF) {
       
        cout << minStep - 2;
    } else {
        cout << -1;
    }
    return 0;
}

5.迷宫

#include <iostream>
#include <string>
#include <queue>
 
using namespace std;
 
int maze[35][55];
int dir[][2] = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };
char d[4] = { 'D', 'L', 'R', 'U' };
int cnt = 0x3f3f3f3f;
bool vis[35][55];
 
struct node{
    int x;
    int y;
    string rode;
    int step;
    node(int xx, int yy, string ss, int tt)
    {
        x = xx;
        y = yy;
        rode = ss;
        step = tt;
    }
};
 
bool check(int x, int y){
    if (x <= 30 && x >= 1 && y <= 50 && y >= 1){
        return true;
    }
    return false;
}
 
void bfs(int x, int y, string s, int num){
    queue<node> q;
    q.push(node(x, y, s, num));
    while (!q.empty()){
        node now = q.front();
        q.pop();
 
        vis[now.x][now.y] = true;
 
        if (now.x == 30 && now.y == 50){
            if (now.step < cnt){
                cnt = now.step;
                cout << now.step << endl;
                cout<< now.rode << endl;
                vis[now.x][now.y] = false;
            }
            continue;
        }
 
        for (int i = 0; i < 4; i++){
            int tx = now.x + dir[i][0];
            int ty = now.y + dir[i][1];
 
            if (maze[tx][ty] == 0 && !vis[tx][ty] && check(tx, ty)){
                q.push(node(tx, ty, now.rode + d[i], now.step + 1));
            }
        }
    }
}
 
int main(){
 
    for (int i = 1; i <= 30; i++){
        for (int j = 1; j <= 50; j++){
            maze[i][j] = getchar()-'0';
        }
        getchar();
    }
 
    bfs(1, 1, "", 0);
 
    return 0;
}

6.跳马

#include<iostream>
#include<queue>
using namespace std;
const int X[8] = {-2,-2,-1,-1,1,1,2,2};
const int Y[8] = {-1,1,-2,2,-2,2,-1,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>
using namespace std;
const int X[4] = {1,-1,0,0};
const int Y[4] = {0,0,1,-1};
int n,a[21],b[21];
bool bo[21][21];
int st[401],p=0;
bool dfs(int x,int y){
    if(!a[y]||!b[x])return false;
    a[y]--,b[x]--;
    if(x==n&&y==n){
        bool bo = true;
        for(int i=1;i<=n;i++)if(a[i]||b[i])bo = false;
        if(bo){
            st[p++] = (x-1)*n+y-1;
            return true;
        }
    }
    for(int i=0;i<4;i++){
        int tx = x + X[i];
        int ty = y + Y[i];
        if(tx<1||tx>n||ty<1||ty>n)continue;
        if(dfs(tx,ty)){
            st[p++] = (x-1)*n+y-1;
            return true;
        }
    }
    a[y]++,b[x]++;
    return false;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    dfs(1,1);
    cout<<0;
    for(int i=p-2;i>=0;i--)cout<<' '<<st[i];
    return 0;
}

8.未名湖边的烦恼

#include<iostream>
using namespace std;
int fun(int n,int m)
{
    if(n<m) return 0;
    if(m==0) return 1;
    return fun(n-1,m)+fun(n,m-1); 
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<fun(n,m)<<endl;
    return 0;
}

9.大臣的旅费

10.2n 皇后问题

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
6
查看目录

目录

来自 《【思特奇杯·云上蓝桥-算法集训营】第2周》
评论

染念

博主很懒,啥都没有
145 文章数
533 评论量
4 分类数
149 页面数
已在风雨中度过 5年95天18小时9分
© 2022 染念的笔记
浙ICP备19020194号-1