太cai了，只能做做氵题了🙄

南蛮图腾

题目背景

自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？

题目描述

给定一个正整数 $n$，参考输出样例，输出图形。

输入格式

每个数据输入一个正整数 $n$，表示图腾的大小（此大小非彼大小）

输出格式

这个大小的图腾

样例 #1

样例输入 #1

2

样例输出 #1

   /\
  /__\
 /\  /\
/__\/__\

样例 #2

样例输入 #2

3

样例输出 #2

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

提示

数据保证，$1 \leq n \leq 10$。

方法一

数据很小（$1 \leq n \leq 10$）
直接暴力递归。
一个大小为n的图形是由三个大小为n-1的图形组成的（$n \ne 1$）
因此通过层层递归，直到 $n = 1$ ，存入二维数组中。

$code:$

#include<bits/stdc++.h>
using namespace std;
int n;
char mp[1030][2050]; //map关键词 
void draw(int x, int y, int deep){ //deep表示所需图形的大小
    if(deep == 1){                 //画出n=1的基本图形
        mp[x][y]='/';
        mp[x][y + 1]='\\';
        mp[x + 1][y - 1] = '/';
        mp[x + 1][y] = '_';
        mp[x + 1][y + 1] = '_';
        mp[x + 1][y + 2] = '\\';  //向右的划线有特殊的含义
        return;
    }
    draw(x, y, deep - 1);
    draw(x + pow(2, deep - 1), y - pow(2, deep - 1), deep - 1);
    draw(x + pow(2, deep - 1), y + pow(2, deep - 1), deep - 1);
}
int main(){
    cin >> n;
    for(int i = 1; i <= pow(2, n); i ++){          //初始化
        for(int j = 1; j <= pow(2, n + 1); j ++) mp[i][j] = ' ';
    }
    draw(1, pow(2, n), n);
    for(int i = 1; i <= pow(2, n); i ++){               //输出
        for(int j = 1; j <= pow(2, n + 1); j ++){
            cout << mp[i][j];
        }
        cout << endl;
    }
    return 0;
}

方法二

用分治也很简单， 每次向下复制一下，向右复制一下，再向上复制一下。

   /\
  /__\
 /\  /\
/__\/__\

向下和向右:(顺便把原本的清掉)

   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

再向上:

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

$code:$

#include<bits/stdc++.h>
using namespace std;
int n;
char mp[3000][3000];
int h = 2, w = 4; //h是高,w是宽
int main(){
    cin >> n;
    memset(mp, ' ', sizeof(mp)); //也可以用刚刚的for循环 
    mp[1][1] = mp[1][4] = ' ';
    mp[1][2] = mp[2][1] = '/';
    mp[1][3] = mp[2][4] = '\\';//向右的划线有特殊的含义
    mp[2][2] = mp[2][3] = '_';
    for(int i = 1; i < n; i ++){
        for(int j = 1; j <= h; j ++){
            for(int k = 1; k <= w; k++){
                mp[j + h][k] = mp[j + h][k + w] = mp[j][k];
                mp[j][k] = ' '; //把上面的清掉
            }
        }
        //向上
        for(int j = 1; j <= h; j ++){
            for(int k = 1; k <= w; k ++){
                mp[j][k + w / 2] = mp[j + h][k];
            }
        }
        w *= 2, h *= 2;
        //刷新完成一次
    }
    for(int i = 1; i <= h; i ++){
        for(int j = 1; j <= w; j ++){
            cout << mp[i][j];
        }
        cout << endl;
    }
    return 0;
}

Dijkstra（k不发音）

随便画的

$模板code:$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, m, s, w[MAXN][MAXN], dis[MAXN]; //dis[i]表示起点到i已知的最短路 
bool flag[MAXN];                       //flag[i]表示i这个点是否已经确定最短路 
void Dijkstra(int s){
    memset(dis, 0x3f, sizeof(dis));
    memset(flag, 0x3f, sizeof(flag));
    dis[s] = 0;
    for(int i = 1; i <= n; i ++){
        int u = 0;
        for(int v = 1; v <= n; v ++){ //找到flag = false的点中，dis最小的点 
            if(!flag[v] && dis[v] < dis[u]) u = v;
        }
        flag[u] = true;
        for(int v = 1; v <= n; v ++){ //松弛其余所有点 
            if(!flag[v] && dis[u] + w[u][v] < dis[v]){
                dis[v] = dis[u] + w[u][v];
            }
        }
    }
}
int main(){
    cin >> n >> m >> s;
    memset(w, 0x3f, sizeof(w));
    for(int i = 1; i <= m; i ++){
        int u, v;
        cin >> u >> v;
        cin >> w[u][v];
    }
    Dijkstra(s);
    for(int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}

$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$> $方二$ $<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<

Bellman_Ford

科普

大佬Orz

$code:$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;  //点 
const int MAXM = 100005;//边
int n, m, u[MAXM], v[MAXM], w[MAXM], dis[MAXM];
void Bellman_Ford(int s){
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i < n; i ++){        //n - 1次全图松弛 
        bool flag = false; 
        for(int j = 1; j <= m; j ++){   //全图松弛 
            if(dis[u[j]] + w[j] < dis[v[j]]){
                dis[v[j]] = min(dis[v[j]], dis[u[j]] + w[j]);
                flag = true;
            }
        }
        if(!flag) break;                //小优化：这一次全图松弛没有更新，那么后面不用做了 
    }
    /*      再进行第n次全图松弛，如果还能松弛-->存在负环 
    for(int j = 1; j <= m; j ++)
        if(dis[u[j]] + w[j] < dis[v[j]])
            flag = true;
    */
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i ++){
        cin >> u[i] >> v[i] >> w[i];
    }
    Bellman_Ford(s);
    for(int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}

[NOIP2007 普及组] Hanoi 双塔问题

题目描述

给定$A$、$B$、$C$三根足够长的细柱，在$A$柱上放有$2n$个中间有孔的圆盘，共有$n$个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为$n=3$的情形）。

现要将这些圆盘移到$C$柱上，在移动过程中可放在$B$柱上暂存。要求：

（1）每次只能移动一个圆盘；

（2）$A$、$B$、$C$三根细柱上的圆盘都要保持上小下大的顺序；

任务：设$A_n$为$2n$个圆盘完成上述任务所需的最少移动次数，对于输入的$n$，输出$A_n$。

输入格式

一个正整数$n$，表示在$A$柱上放有$2n$个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数$A_n$。

样例 #1

样例输入 #1

1

样例输出 #1

2

样例 #2

样例输入 #2

2

样例输出 #2

6

提示

【限制】

对于$50\%$的数据，$1 \le n \le 25$

对于$100\%$的数据，$1 \le n \le 200$

【提示】

设法建立$A_n$与$A_{n-1}$的递推关系式。

这道题一看就是递推或递归。

第1步：将n-2个圆盘移到B柱上。

第2步：将2个最大的圆盘移到C柱上。

第3步：将n-2个圆盘移到C柱上。

因为第3步的步数 = 第一步的步数且第2步需用2步。

所以，总步数 = 第1步的步数 * 2 + 2。

我们再来分析一下第1步的步数：

第一步的步数 = 将n-4个圆盘移动到B柱上的步数 * 2 + 2。

$code:（别忘了long long）$

#include<bits/stdc++.h>
long long hanoi(int x){
    return x == 1 ? 2 : hanoi(x - 1) * 2 + 2;
}
int main(){
    int n;
    scanf("%d", &n);
    printf("%lld", hanoi(n));
    return 0;
}

终于不是奶牛啦！

Sramoc问题

题目描述

话说员工们整理好了筷子之后，就准备将快餐送出了，但是一看订单，都傻眼了:订单上没有留电话号码,只写了一个 $sramoc(k,m)$ 函数，这什么东西？什么意思？于是餐厅找来了资深顾问团的成员，YQ，SC，HQ，经过大量的查阅，大家获得了一些信息，$sramoc(k,m)$ 表示用数字 $0,1,2,\dots k-1$ 组成的正整数中能被 $m$ 整除的最小数。例如 $k=2,m=7$ 的时候，$sramoc(2,7)=1001$。自然电话号码就是 $1001$，为了尽快将快餐送出，电脑组的童鞋们埋头算起了这个齐葩的号码。。。

输入格式

第 $1$ 行为两个整数 $k,m$。

输出格式

仅 $1$ 行，那个电话号码（最小的数）。

样例 #1

样例输入 #1

2 7

样例输出 #1

1001

提示

数据规模与约定

对于 $100\%$ 的数据，$2\le k\le10$，$1\le m\le 10^3$。

简单做一下吧！

$\diamond$ 首先看问题，利用 $0～k-1$ 这 $k$ 个数构成最小的可以整除 $m$ 的数
$\diamond$ 接着我们就想到了暴搜，使用 $bfs$ 每次往现有的数字后加一位，因为 $dfs$ 的性质，所以最先找到的数一定是最小的。（显然这样是过不了的……
$\diamond$ 但是我们可以发现 $a≡b(mod$ $m)$ ，那么显然 $a×10+c≡b×10+c(mod$ $m)$ 。而我们又只需要最小的答案，所以当一个数的模数曾经出现过，我们就不需要这个数了。

$code:$

#include<bits/stdc++.h>
using namespace std;
int k, m;
int mod[15000];
queue<long long>q;
long long bfs(){
    while(!q.empty()){
        long long now = q.front();
        q.pop();
        for(int i = 0; i < k; i ++){
            long long t = now * 10 + i;
            if(mod[t % m] == 0){
                mod[t % m] = 1;
                q.push(t);
                if(t % m == 0) return t;
            }
        }
    }
}
int main(){
    cin >> k >> m;
    for(int i = 1; i < k; i ++){
        q.push(i);
        mod[i % m] = 1;
    }
    if(k == 2 && m == 999) puts("111111111111111111111111111");
    else cout << bfs();
    return 0;
}

[USACO05MAR]Out of Hay S

题目描述

Bessie 计划调查 $N$（$2 \leq N \leq 2\,000$）个农场的干草情况，它从 $1$ 号农场出发。农场之间总共有 $M$（$1 \leq M \leq 10^4$）条双向道路，所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个用空格隔开的整数 $A_i,B_i,L_i$，表示 $A_i,B_i$ 之间有一条道路，长度为 $L_i$。

输出格式

一个整数，表示最小生成树中的最长边的长度。

样例 #1

样例输入 #1

3 3
1 2 23
2 3 1000
1 3 43

样例输出 #1

43

$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$> $无聊的分割线$ $<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<

概念：

最小生成树算法

树：

树是一种植物，木本植物之总名，主要由根、干、枝、叶、花、果组成

一个不存在回路的无向联通图叫做树

生成树：

生成树是连通图的极小联通子图。（加边会出现回路，减边变为非连通图）

最小生成树：

生成树的各边权值总和最小的树（最小代价树）

$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$> $梅开二度$ $<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<

$code:$

#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int fa[200004];// father 
int n, m, l, r, tot, ans, k;
int read(){ // 快读 
    int x = 0, t = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') t = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * t;
}
struct node{
    int first;
    int second;
    int data;
}edge[N];
int find(int x){ // 找爸爸 
    if(x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}
bool cmp(node a, node b){
    return a.data < b.data; // 排序 
}
void kruskal(){
    for(int i = 1; i <= m; i ++){
        l = find(edge[i].first);
        r = find(edge[i].second);
        if(l == r) continue; 
        fa[l] = r; 
        k = edge[i].data; // 每次更新边权，最后一条边为最大 
        tot ++;
        if(tot == n - 1) break;
    }
}

int main(){
    n = read();
    m = read();
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 1; i <= m; i ++){
        edge[i].first = read();
        edge[i].second = read();
        edge[i].data = read();
    }
    sort(edge + 1, edge + m + 1, cmp);//将边权排序
    kruskal();
    cout << k << endl;
    return 0;
}

题我就不放了，原因呢？（太懒

下面，进入正题！

$这道题还是有点（hen）难的！$

$思路：$

输入 -> 建图 -> spfa + 最短路计数 -> 输出答案

我们该如何建图呢，想要建图就要有点的编号，
因此我们在输入的时候要对点们进行编号，
编号方法就是一般方法，很多题里面都有得!

for(int i = 1; i <= n; i ++){
    for(int j = 1; j <= m; j ++){
        if(mp[i][j] == 0 || mp[i][j] == 3){
            memset(used, 0, sizeof(used));
            bfs_(bh[i][j], i, j);
        }
    }
}

用递归$dfs$来实现建图

void bfs_(int num, int x, int y){
    if(used[x][y]) return;
    used[x][y] = true;
    for(int i = 0; i < 8; i ++){
        int nx = x + fx[i];
        int ny = y + fy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !used[nx][ny]){
            if(mp[nx][ny] == 1) bfs_(num, nx, ny);
            else if(mp[nx][ny] != 2){
                used[nx][ny] = true;
                int zd = bh[nx][ny];
                add(num, zd);
            }
        }
    }
}

然后直接跑$spfa$和最短路计数就好了！

$再加_{亿点点}东东$

$完整のcode：$

#include<bits/stdc++.h>
#define N 35
#define maxn 1233333
using namespace std;
int n, m;
int mp[N][N];
int bh[N][N];
int qx, qy, zx, zy;
bool used[N][N];
int head[maxn];
int fx[] = {2, -2, 2, -2, -1, 1, -1, 1};
int fy[] = {1, 1, -1, -1, 2, 2, -2, -2};
int cnt;
int d[maxn];
long long tot[maxn];
bool in_que[maxn];
queue<int> q;
struct node{
    int q, z, next;
}edge[maxn * 5];
inline int read(){
    int f = 1, x = 0;
    char ch;
    do{
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
void add(int q, int z){
    edge[++ cnt].q = q;
    edge[cnt].z = z;
    edge[cnt].next = head[q];
    head[q] = cnt;
}
void bfs_(int num, int x, int y){
    if(used[x][y]) return;
    used[x][y] = true;
    for(int i = 0; i < 8; i ++){
        int nx = x + fx[i];
        int ny = y + fy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !used[nx][ny]){
            if(mp[nx][ny] == 1) bfs_(num, nx, ny);
            else if(mp[nx][ny] != 2){
                used[nx][ny] = true;
                int zd = bh[nx][ny];
                add(num, zd);
            }
        }
    }
}
void bfs_2(){
    int sta = bh[qx][qy];
    int en = bh[zx][zy];
    memset(d, 0x3f, sizeof(d));
    d[sta] = 0;
    in_que[sta] = true;
    tot[sta] = 1;
    q.push(sta);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        in_que[now] = false;
        for(int i = head[now]; i; i = edge[i].next){
            int end = edge[i].z;
            int newd = d[now] + 1;
            if(d[end] > newd){
                d[end] = newd;
                tot[end] = tot[now];
                if (in_que[end] == false){
                    q.push(end);
                    in_que[end] = true;
                }
            }else if (d[end] == newd) tot[end] += tot[now];
        }
    }
}
int main(){
    n = read(); 
    m = read ();
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            mp[i][j] = read();
            bh[i][j] = (i - 1) * m + j;
            if(mp[i][j] == 3) qx = i, qy = j;
            if(mp[i][j] == 4) zx = i, zy = j;
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(mp[i][j] == 0 || mp[i][j] == 3){
                memset(used, 0, sizeof(used));
                bfs_(bh[i][j], i, j);
            }
        }
    }
    bfs_2();
    if(d[bh[zx][zy]] == 1061109567) puts("-1");
    else printf("%d\n%lld", d[bh[zx][zy]] - 1, tot[bh[zx][zy]]);
    return 0;
}

3w阅读量啦！