单调栈

2023-12-07

算法 / 单调栈

字数统计: 703 | 阅读时长≈ 2 分钟

单调栈

定义

通常是一维数组,记录任一个元素右(左)边第一个比自身大(小)的元素的下标.

构造

分为正序构造和逆序构造两种方式.

下面我以寻找右边第一个比较自己大的单调栈为例

请注意,本文中所提及的栈的单调情况都是基于栈底到栈顶的顺序.如下图为一个单调减小的栈

正序和逆序只是角度不同,简单来说

正序是把待比较的元素放到栈里,保持栈的单调递减

逆序是把已经比较过的元素放到栈里,保持栈的单调递减

无论正序逆天,都要保证栈的有序,并且需要及时去除无用数据

图构建

2023-12-05

算法 / 图论

字数统计: 1.1k | 阅读时长≈ 5 分钟

邻接矩阵不用说ez

主要讲一下邻接表的数组实现和链式前向星:

链式前向星

是一个结构体数组


#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
 int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
 for (int i = 0; i <= n; i++) head[i] = -1;
 cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
 edge[cnt].to = v; //终点
 edge[cnt].w = w; //权值
 edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
 head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
 cin >> n >> m;
 int u, v, w;
 init();//初始化
 for (int i = 1; i <= m; i++)//输入m条边
 {
     cin >> u >> v >> w;
     add_edge(u, v, w);//加边
     /*
     加双向边
     add_edge(u, v, w);
     add_edge(v, u, w);
     */
 }
 for (int i = 1; i <= n; i++)//n个起点
 {
     cout << i << endl;
     for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
     {
         cout << i << " " << edge[j].to << " " << edge[j].w << endl;
     }
     cout << endl;
 }
 return 0;
}

俳句

2023-12-04

诗词

字数统计: 316 | 阅读时长≈ 1 分钟

我对俳句,和歌之类不是很感兴趣(1是格式本身按音节排,不适合中文.2是感觉格局较小,像是庭院景观),但也有所接触.

比较有名的和歌如万叶集中的(言叶之庭也有出现)

隐约雷鸣，阴霾天空。但盼风雨来，能留你在此。

俳句我印象深刻的倒是索尼之前办的对马岛俳句大赛,里面有

悲怆如战马，分不清旭日金甲，红了海与沙

辉落双影长，浪客转步飞剑芒，碧血黄沙凉

白日修罗场，岸边水线如刃长，红花落日光

无题

轻阴色，江风凉夜泼疏墨，天边染灯火

背景:第一次写俳句,也是唯一写过的俳句.写作时间大抵是在21年春,月考之时,窗外流云微雨,天气微寒,莫名想到夏日傍晚.
<<言语如苏打般涌现>>里有一句如下(因为是直译,格式并不正确)

夕阳时分，抢先偷跑的夏夜灯火

还有王维的

轻阴阁小雨，深院昼慵开

我觉得轻阴这词很有意境诶,还有江风,一下子感觉风的绵延飘逸.

问题集

2023-12-03

问题集

字数统计: 1.3k | 阅读时长≈ 5 分钟

构造连续子序列问题

问题形如:现有整数数组num,取其中任意个数,和为sum,即记为可以取到sum.

现问最少添加几个数才能取到1到n的所有数

一图流

现在可以构造[0,m],想构造m+1时

假设现在得到了 [0,m] 内的所有整数，如果此时新发现了一个整数 s，那么把 s加到已得到的数字中，就得到了[s,m+s]内的所有整数。

(1) 如果能找到一个小于或等于 m + 1 的数,可以直接合并,得到[0,m+s]

(2) 如果下一个数大于m+1后，就无法构造出m+1,那么就要把 m+1 加到数组中(贪心思想,最大范围嘛,如果加的比m+1小那有点亏),这样就可以得到[m+1,m+m+1]的所有数,合并之前的[0,m]即[0,m+m+1]所有数

树状数组

2023-12-01

数据结构 / 树状数组

字数统计: 388 | 阅读时长≈ 2 分钟

主要解决两类:

1:单点修改,区间求和

bit维护节点

#include<bits/stdc++.h>
using namespace std;
int bit[2000006];
int n,m;
int lowbit(int x){
	return x&(-x);
}

void add(int index,int k){
	for(int i = index;i <= n;i+=lowbit(i)){
		bit[i]+=k;
	}
}

int sum(int start,int end){
	int ans = 0;
	for(int i = end;i;i-=lowbit(i)){
		ans+=bit[i];
	}
	for(int j = start-1;j;j-=lowbit(j)){
		ans-=bit[j];
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		int tmp;
		cin>>tmp;
		add(i,tmp);
	}
	for(int i = 0;i<m;i++){
		int tmp;
		cin>>tmp;
		if(tmp==1){
			int index,num;
			cin>>index>>num;
			add(index,num);
		}
		else{
			int start,end;
			cin>>start>>end;
			cout<<sum(start,end)<<endl;
		}
	}
	return 0;
}

树结构

2023-12-01

数据结构 / 树

字数统计: 568 | 阅读时长≈ 1 分钟

struct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

排序

2023-12-01

算法 / 排序

字数统计: 605 | 阅读时长≈ 2 分钟

冒泡

两个值依次比较

优化方法:每次循环判断是否交换过元素,没有交换过就证明数组已经有序

选排

大小n的数组,遍历n次,第一次把最小的移动到索引0,第二次从1开始把第二小的移动到索引1处,以此类推

优化方法:每次遍历同时寻找最小最大值

插入排序

从1开始构造有序数组,后面的数依次比较插入数组中对应位置

优化方法:已排序的插入用二分,

从后往前排序

归并排序

把数组不断拆分然后合并,如8个数,先分成左4,右4,每个4再细分成2,2排序后回4合并再排序,再回8合并

高精度

2023-12-01

算法 / 大数处理

字数统计: 2.2k | 阅读时长≈ 11 分钟

2024.4.7更新：

重新写了下，老的在下面

加

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	int lena = a.size(), lenb = b.size();
	if(lena < lenb){
		swap(a,b);
		swap(lena, lenb);
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	
	vector<int>ans(lena + 1, 0);
	int n = ans.size();
	for(int i = 0; i < n; i++){
		if(i < lenb) ans[i] += a[i] + b[i] - '0'*2;
		else if(i < lena) ans[i] += a[i] - '0';
		if(ans[i] >= 10){
			ans[i] %= 10; 
			ans[i+1]++;
		}
	}
	bool flag = 1;
	for(int i = n-1; i >= 0; i--){
		if(ans[i] == 0 && flag) continue;
		flag = 0;
		cout<<ans[i];
	}
	if(flag && ans[0] == 0) cout<<0; 
	return 0;
}