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

3.7万

zheside
fire_acer

ACMode

xiaozd
kzyz

wqzgg
tyjz_yyds
LittleDrinks

QingYao

Finn2009
kerry2023
wt20
sealt

# 南蛮图腾

## 样例 #1

### 样例输入 #1

2


### 样例输出 #1

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


## 样例 #2

### 样例输入 #2

3


### 样例输出 #2

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


# 方法一

$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

$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 双塔问题

## 题目描述

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

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

## 样例 #1

### 样例输入 #1

1


### 样例输出 #1

2


## 样例 #2

### 样例输入 #2

2


### 样例输出 #2

6


## 提示

【限制】

【提示】

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

$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问题

## 样例 #1

### 样例输入 #1

2 7


### 样例输出 #1

1001


## 简单做一下吧！

$\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 希望计算出该图中最小生成树中的最长边的长度。

## 样例 #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 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(){
for(int i = 1; i <= n; i ++) fa[i] = i;
for(int i = 1; i <= m; i ++){
}
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);
}
}
}


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];
}
}
}
}


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

$完整の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 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];
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;
}
edge[++ cnt].q = q;
edge[cnt].z = z;
}
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];
}
}
}
}
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(){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
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个月前

2个月前

2个月前