头像

洛白さん

$$青涩の醉挽清风Team$$




离线:2天前


最近来访(601)
用户头像
zheside
用户头像
fire_acer
用户头像
被误解是表达者的宿命
用户头像
ACMode
用户头像
云衣醉梦
用户头像
刷题大师
用户头像
xiaozd
用户头像
kzyz
用户头像
闻天语
用户头像
wqzgg
用户头像
tyjz_yyds
用户头像
LittleDrinks
用户头像
北海没有WA
用户头像
QingYao
用户头像
清风qwq
用户头像
Finn2009
用户头像
kerry2023
用户头像
wt20
用户头像
sealt
用户头像
宇宙有边


太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不发音)


随便画的

截图20230318163215.png


$模板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;
}


新鲜事 原文

洛白さん
2个月前
话说,我在2023/1/2来到了接近朝鲜边境的长白山,这正常吗? 旁白:你曾经感受过真正的寒冷吗? 我 :是的,我曾在2023/1/3在零下16度的天气里踏上过2620米的长白山。



洛白さん
2个月前

3w阅读量啦!



新鲜事 原文

洛白さん
2个月前
哈喽,2023!