模板题

MuxLz / 2025-01-15 / 原文

洛谷-PJ组

如何更好地食用 UVa OJ - 洛谷专栏

高精计算

字典树求解A+B

以每个数字建立字典树，建立一次查询一次

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
    int str[26];
    int sum;
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built()
{
    t=0;
    for(int i=0;i<strlen(str1);i++)
    {
         if(str1[i]=='-'){
             f1=true;continue;
         }
         if(!s[t].str[str1[i]-'0'])
         s[t].str[str1[i]-'0']=++tot;
         t=s[t].str[str1[i]-'0'];
         s[t].sum=str1[i]-'0';
    }
}
int query()
{
   int t=0;int s1=0;
   for(int i=0;i<strlen(str1);i++)
   {
           if(str1[i]=='-') continue;
           if(!s[t].str[str1[i]-'0']) return s1;
           t=s[t].str[str1[i]-'0'];
           s1=s1*10+s[t].sum;
   }
   return s1;
}
int main()
{    
  for(int i=1;i<=2;i++)
  {
      f1=false;
      scanf("%s",str1);
    built();
    if(f1)
      ss-=query();
      else ss+=query();
  }
  printf("%d",ss);
  return 0;    
}

A+B

竖式加减

ps：我抄我自己19年的题解抄的理直气壮.jpg

#include <string>
#include <iostream>
using namespace std;
int a[100],b[100],c[100];
int i,lena,lenb,lenc=1;
int main(){
	string a1,b1;
	cin >> a1 >> b1;
	lena = a1.length();
	lenb = b1.length();
	for(i=1;i<=lena;i++) a[i] = a1[lena-i]-48;
	for(i=1;i<=lenb;i++) b[i] = b1[lenb-i]-48;
	int x = 0;
	while(lenc<=lena || lenc<=lenb){
		c[lenc] = a[lenc]+b[lenc]+x;
		x = c[lenc]/10;
		c[lenc]%=10;
		lenc++;
	}
	c[lenc] = x;
	if(c[lenc]==0) lenc--;
	for(i=lenc;i>0;i--) cout<<c[i];
	return 0; 
}

A*B

基础数据结构

常用板子

https://www.zhihu.com/question/288096930

//大小比较
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
//快读
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;
} 
//快输
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
 //万能头 + 解流同步
#include <bits/stdc++.h>      
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
// 手动long long long 两个long long(9.8*1e18)当高精度用
const ll t=(ll)le9;
struct pii{
    ll fi,se;
    pii(){fi=0,se=0;} //se高位 fi低位
    pii(ll b){fi=b%t; se=b/t;}
    friend pii operator +(pii a, pii b){
        pii c;
        c.fi=a.fi+b.fi;
        c.se=a.se+b.se;
        if(c.fi<0 and c.se>0) c.se--,c.fi++;
        if(c.fi>t and c.se>=0) c.se+=c.fi/t,c.fi%=t;
        if(c.fi>0 and c.se<0) c.se++,c.fi-=t;
		if(c.fi<=-t and c.se<=0) c.se+=c.fi/t,c.fi%=t;
        return c;
    }
    friend bool operator <(pii a,pii b){
        if(a.se!=b.se) return a.se<b.se;
        return a.fi<b.fi;
    }
    friend pii max(pii a,pii b){
        if(a<b) return b;
        return a;
    }
};

  1. cin效率低的原因：默认cin与stdin总是保持同步，cin会把要输出的东西先存入缓冲区，进而消耗时间。通过关闭同步，可以有效提高cin效率；

  2. 默认情况下cin绑定的是cout，每次执行<<的时候都要调用flush，进而增加IO负担，因此可以通过tie(0)解绑。

链表

struct Node{
    Node *pre, *nxt;
    int value;
}
void ins(Node *x, Node *y){    //insert y to x->nxt
    if(x->nxt!=NULL) y->nxt=x->nxt, y->nxt->pre = y;
    x->nxt=y;
}
void del(Node *x){            //delete x
    if(x->pre!=NULL) x->pre->nxt=nxt;
    if(x->nxt!=NULL) x->nxt->pre=pre;
    free(x)                       //gc
}

栈与队列

手写实现栈与队列

struct Stack{
    int a[100010];
    int top;
    void init(){top=0;}
    void push(int x){a[++top]=x;}
	void pop(){if(top)top--;}
    int size(){return top;}
    int query(){return a[top]}
};

struct Queue{
    int q[100010];
    int l,r;
    void init(){l=0;r=0;}
    void push(int x){
        if(r==100000)r=1;else r++;
        q[r]=x;
    }
    void pop(){if(l==100000)l=1;else l++;}
    int front(){return q[l];}
    int size(){if(l<r)return r-l;else return l-r+1;}
    bool empty(){return l==r;}
};

单调栈

image-20241110090746106

单调队列

来一个题：给一个序列，求所有区间长度为L的区间最大最小值。

image-20241110092156076

在队列中维护一个单调性，即维护这L个元素的最大最小值，O(n)。

const int N=5000010     // 单调增队列
int q[N],l=1,r=1,a[N],mx,mn,inq[N],n,m;
inline void ins(int x){
    while(l<r&&q[r-1]<=a[x]) r--;     //队列不为空，且a[x]大
    q[r]=a[x];inq[r]=x;r++;      //记录新元素在原始数组中的索引
}
inline int getmax(int cur){
    for(l<r;l++)if(cur-inq[l]<m)return q[l];
}

单调队列性质

  1. 队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
  2. 队列中元素的大小必须是单调递(增/减/甚至是自定义也可以)
#include <stdio.h>
const int N=1000000+10;
inline int read(){
	int x=0,f=1;char ch;
	do{ch=getchar();if(ch==45)f=-1;}while(ch<48||ch>57);
	do{x=x*10+ch-48;ch=getchar();}while(ch>=48&&ch<=57);
	return f*x;
}
struct Queue{
	int q[N]; int l,r; int p[N];
	void init(){l=1,r=0;}
	void push(int x){q[++r]=x;}	
	void pop_front(){l++;}
	void pop_back(){r--;}
	int front_val(){return q[l];}
	int rear_val(){return q[r];}
	bool empty(){return l>r;}
	int xy_front(){return p[l];}
	void xy_fv(int i){p[r]=i;}
}Q;	
void monotone_min(int a[],int n,int k){
	Q.init();
	for(int i=1;i<=n;i++){
		while(!Q.empty()&&Q.rear_val()>=a[i]) Q.pop_back();
		Q.push(a[i]);
		Q.xy_fv(i);
		while(Q.xy_front()<=i-k) Q.pop_front();
		if(i>=k) printf("%d ",Q.front_val());
	}	
	printf("\n");
}
void monotone_max(int a[],int n,int k){
	Q.init();
	for(int i=1;i<=n;i++){
		while(!Q.empty()&&Q.rear_val()<=a[i]) Q.pop_back();
		Q.push(a[i]);
		Q.xy_fv(i);
		while(Q.xy_front()<=i-k) Q.pop_front();
		if(i>=k) printf("%d ",Q.front_val());
	}	
	printf("\n");
}
int main(){
	int n=read(),k=read();int a[N];
	for(int i=1;i<=n;i++) a[i]=read();	
	monotone_min(a,n,k);
	monotone_max(a,n,k);
	return 0;
}

优先队列

在弹出的时候，不是按照进入时间，而是按照某种给定的优先级弹出。

最常见的堆是二叉堆，priority_queue定义了一个以权值为优先级的堆。

#include<queue>      priority_queue<数据类型>

重载运算符 Kluskal·改 a.w>b.w

image-20241110094841833

例题

image-20241110101911060

一般用来做什么

image-20241110102028812

STL 平衡树

image-20241110102113536

stl平衡树的一些应用

image-20241110102533518

Set

image-20241110102301809

Map

image-20241110102454656

例题： P3307 字符串哈希

image-20241110102728829

Vector

哈希表

P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态

哈希的过程，其实可以看作对一个串的单向加密过程，并且需要保证所加的密不能高概率重复。

对于每个串，通过一个固定的转换方式，使相同串的“密”相同，不同的串 尽量 不同。

最常见的一种哈希：进制哈希：核心便是给出一个固定进制base，将这个串映射为base进制的数，即为该串的哈希值；通过比对每个串的的哈希值，即可判断两个串是否相同

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317;    // 一个非常大的质数
ull mod=212370440130137957ll;
ull hashe(char s[])
{
 int len=strlen(s);
 ull ans=0;
 for (int i=0;i<len;i++)
 ans=(ans*base+(ull)s[i])%mod+prime;    // 哈希映射
 return ans;
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
 	scanf("%s",s);
 	a[i]=hashe(s);
 }
 sort(a+1,a+n+1);
 for(int i=1;i<n;i++)
 {
 	if(a[i]!=a[i+1])
 	ans++;
 }
 printf("%d",ans);
}

哈希冲突避免

1、无错哈希

对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突（比如somebody’s birthday）

for(int i=1;i<=m;i++)//m个串
{
    cin>>str;//下一行的check为bool型 
    while(check[hash(str)])   hash[i]+=20000123;
    hash[i]+= hash(str) ;
}

2、多重哈希

使用不同的两种或多种方式哈希，然后分别比对每一种哈希值是否相同

字典树

---洛谷题解qip101大佬

Trie 树，即字典树（前缀树），是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。

image-20241029200409598

Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

image-20241029200601338

1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

image-20241029193115189

操作

映射字符

int getnum(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}

插入字符

void insert(char str[])
{
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}

查询字符

int find(char str[])
{
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}

主函数调用

int main(){
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++)
        {
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }
    return 0;
}

image-20241029201615112

image-20241029201624910

图与树

图论

存储与遍历

  • 存储

    • 邻接矩阵

    • 邻接表

      • 链式前向星

        head数组存储以该点为起点最后加入的一条边。

        next数组存储以该点位起点的上一条边。(编号)

        image-20241107143003110

  • 遍历

    • 深度优先搜索
    • 广度优先搜索

存图方式

链式前向星

只需要开一个数组存储每个点引出的第一条边，然后存储每个点作为起点的每条边，这样就可以做到不重不漏。

定义一个结构体、一个数组和一个变量

struct EDGE 
{
    int next;
    int to;
}edge[1000000];

int head[1000000];

int cnt=0;//指针

起点是用head存储的，其(带权重)构建的完整代码如下

#include<iostream>
using namespace std;
struct edge 
{ 
    int next;
    int to;
    int w;
}edge[MAXM];
int head[MAXN];//head[i]为i点的第一条边
int cnt=0;
void addedge(int u,int v,int w) //起点，终点，权值 
{
    edge[++cnt].next=head[u];//更新cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
int main()
{
	int n;
    for(int i=1;i<=n;i++)
    {
    	int a,b,w;
        addedge(a,b,w);
        //如果是无向图，还要addedge(b,a,wei);
    }
}

这里的next指的是遍历时的下一条边，head指的是遍历时的第一条边，而存边时相当于反过来操作，所以next记录上一条边，而head记录最后一条边。

边的遍历

for(int i=head[x];i!=0;i=edge[i].next)

这个循环的结束条件是i等于0，因为最后一条边，也就是存边时第一条边，在把head值存进next时，head还没有更新过，也就是0。所以当next返回0时，就说明这些边遍历完毕了。

单源点最短路径

BFS灌水 usaco火情蔓延

Floyd

Floyd O(n^3)

  • 传递闭包 ： a->b,b->c => a->c 差分约束 a>b,b>c => a>c

    • 推广 ： a - dis1 - b, b - dis2 - c => a - dis1 + dis2 = c
    • 适用于有向图、无向图或负权边

  • 初始化

    • 不可达dis设为 inf = 0x3f3f3f3f
    • 自己到自己的距离为0
    • 题目给定的边直接赋值为该边长度，双向边两边同时赋值

  • 思想

    • 枚举中转节点k
    • 检查由S经过此点到T的路径是否比原先更优
    • 更新由S到T的最短距离

  • 例题

    • P1828 香甜的黄油

    • 统计每个牧场奶牛数量，Floyd之后再枚举每个牧场作为最终牧场，计算迁移距离，最后取最小值。

    • P2419 牛大赛

      • 胜利方向失败方连边，Floyd改为t[i] [j]|=t[i] [k]&t[k] [j]

    • hdu1599 求最小环

      • image-20241107163449986
#include<bits/stdc++.h>
using namespace std;
#define INF 123456789
#define MAXN 10005
inline int read() {...} //快读
int a[MAXN][MAXN],n,m,s;
inline void floyd()
{
    for(int k=1;k<=n;k++)    //这里要先枚举k（可以理解为中转点）
	{
        for(int i=1;i<=n;i++){
            if(i==k||a[i][k]==INF) continue; //我是你或不可达
			for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
        }
    }
}
int main()
{
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++)	  
        for(int j=1;j<=n;j++)  a[i][j]=INF; //边的初始化
    for(int i=1,u,v,w;i<=m;i++)
	{
        u=read(),v=read(),w=read();
        a[u][v]=min(a[u][v],w);//边的存储，取min对付重边
    }
    floyd();
    a[s][s]=0;
    for(int i=1;i<=n;i++) printf("%d ",a[s][i]);
    return 0;
}
SPFA

SPFA O(n^2)

  • 能处理负权边的单源最短路径
  • 利用队列，多次入队，多次更新最优解(松弛)
  • 特点：只有当前被更新的点才对状态产生贡献，队列维护有用状态

用队列来保存待优化的结点（类似于BFS），每次取出队首结点，并用队首节点来对最短路径进行更新并进行松弛操作

如果要对所邻接点的最短路径需要更新，且该点不在当前的队列中，就将该点加入队列

然后不断进行松弛操作，直至队列空为止。

#include<bits/stdc++.h>
using namespace std;
// 快读
inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}

#define maxn 10005
#define maxm 500005
#define inf 1234567890
int n,m,s,cnt,dis[maxn],head[maxn];
bool vis[maxn];
// 链式前向星
struct Edge
{
      int next,to,w;
}ed[maxm];
void add(int u,int v,int w)
{
    ed[++cnt].next=head[u];
    ed[cnt].to=v;
    ed[cnt].w=w;
    head[u]=cnt;
}

queue<int> q;

inline void spfa()
{
    for(int i=1; i<=n; i++)   dis[i]=inf;//初始化
    dis[s]=0; q.push(s); vis[s]=1; //赋初值
    int u,v;
    while(!q.empty())
	{
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=ed[i].next)
		{
            v=ed[i].to;
            if(dis[u]+ed[i].w<dis[v])
			{
                dis[v]=dis[u]+ed[i].w;
                if(!vis[v])
                      vis[v]=1, q.push(v);
            }
        }
    }
}

int main(){
    n=read(),m=read(),s=read();
    for(int i=1,u,v,w;i<=m;i++)
	{
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    spfa();
    for(int i=1; i<=n; i++)
    {
        printf("%d ",dis[i]);
    }
    return 0;
}
Dijkstra

Dijkstra O(n^2logn)

  • 基于贪心的一个单源点最短路径算法，只能处理正权边
  • 实现思路
    • 将顶点化为两堆，起初第一堆只有起点V0
    • 每次从第二堆里距离V0点最近的点取出，放入第一堆，并更新最短路，直到第二堆没有节点
    • 此时维护dis[i]从V0点到i点的最小距离

Dijkstra是基于一种贪心的策略，首先用数组dis记录起点到每个结点的最短路径，再用一个数组保存已经找到最短路径的点

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点记为已经找到最短路

此时完成一个顶点，再看这个点能否到达其它点（记为v），将dis[v]的值进行更新

不断重复上述动作，将所有的点都更新到最短路径 O(N^2) --- > 堆优化 O(NlogN)

#include <iostream>
#define INF 2147483647
#define MAXN 100005
using namespace std;
struct edge {int next, to, w;} ed[MAXN];
int head[MAXN], cnt;
void addedge(int u, int v, int w) {
	ed[++cnt].next = head[u];
	ed[cnt].to = v;
	ed[cnt].w = w;
	head[u] = cnt;
}
long dis[MAXN];
bool vis[MAXN];

int main() {
    //初始化与链式前向星的构造
	int n, m, s; cin>>n>>m>>s;
	for (int i=1; i<=n; i++) dis[i] = INF;
	dis[s] = 0;
	int a, b, c;
	for (int i=1; i<=n; i++) {cin>>a>>b>>c; addedge(a,b,c);}
	//dijkstra算法核心
	int pos = s;
	while (!vis[pos]) {
		vis[pos] = 1;
		for (int i = head[pos]; i; i = ed[i].next) {
			if (!vis[ed[i].to] && dis[ed[i].to] > dis[pos] + ed[i].w)
				dis[ed[i].to] = dis[pos] + ed[i].w;   //更新dis
		}
		long minn = INF;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && dis[i] < minn)
				minn = dis[i], pos = i;     //换起点
		}
	}
	for (int i = 1; i <= n; i++)
		cout << dis[i] << " ";
}

在dis数组中选择最小值时，可以用一些数据结构来进行优化。

堆相对于线段树以及平衡树有着常数小，码量小等优点，并且堆的一个妙妙的性质就是可以在nlogn的时限内满足堆顶是堆内元素的最大（小）值。

#堆优化
struct node
{
    int w,now;
    inline bool operator <(const node &x)const
    //重载运算符把最小的元素放在堆顶（大根堆）
    {
        return w>x.w;//这里注意符号要为'>'
    }
};
priority_queue<node>q;

void dijkstra(){
   	...
    //赋初值
    q.push((node){0,s});
    while(!q.empty()){
    //堆为空即为所有点都更新
        node x=q.top();
        q.pop();
        int u=x.now;
        //记录堆顶（堆内最小的边）并将其弹出
        if(vis[u]) continue; 
        //没有遍历过才需要遍历
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        //搜索堆顶所有连边
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
            	dis[v]=dis[u]+e[i].w;
            	//松弛操作
            	q.push((node){dis[v],v});
            	//把新遍历到的点加入堆中
            }
        }
    }
    int main(){
        ...
        dijkstra();
        ...
    }
}

**有向无环图 DAG **

拓扑排序

  • 常被用来表示事件之间的依赖关系，管理任务之间的调度
  • 实现思路
    • 用一个数组记录每个点初始状态下的入度
    • 将入度为0的点加入宽度搜索的队列
    • 对于当前点，将其出边对应的所有点的入度都减1，然后判断入度是否为0，如果是，就将该点加入队尾
  • 例题
    • P2261 信息传递
      • 先拓扑排序找到所有环
      • 然后dfs每个环，求得节点最少的环

最小生成树 MST

prime

  • prime O(N^2)

    image-20241108090841527

Kluskal

  • Kluskal

    image-20241110093907989

    image-20241110093943803

    image-20241110094238944

树

树的相关知识

  • 树的存储方式：
    • 父亲节点表示法 ： fa[x] x节点的父亲
    • 儿子节点表示法 : son[n] [n]
    • 无向图表示 ： 邻接矩阵，邻接表
    • 左儿子右兄弟 - 树转二叉树
  • 树的重心和直径

    • 直径：树上的最长路径

      • 计算思路
        • ① 每个点dfs
        • ②树上任选点u，求距离u最远的点y，再求离y最远点s，y到s距离为树的直径

    • 重心：找到一个点，其所有子树中 最大的子树节点数最少的点

      • image-20241108085503869

最近公共祖先 LCA

自平衡二叉搜索树

红黑树

定义：一种高效的自平衡二叉搜索树 （来自可爱的本子喵）o(=•ェ•=)m

前置知识

二叉搜索树：

  • 左子树的所有节点值均<=父节点的值

  • 右子树的所有节点值均>=父节点的值

  • 左右子树也分别为二叉搜索树

    image-20241029202022789

普通二叉树的缺点：插入【13，14，15，16】，最坏时间复杂度O(N)

image-20241029202150748

为了避免出现这种情况，提出平衡树结构，红黑树是其中一种

红黑树查找、删除、插入时间复杂度O(logN)

插入： 234树 --- 红黑树的前身

image-20241029202528389

image-20241029202618195

红黑树的性质：【 左根右，根叶黑，不红红，黑路同 】

  • 节点是红色或黑色
  • 根节点是黑色
  • 叶子节点(最底层不存放数据的节点)都为黑色，且都为空
  • 红色节点的父节点and子节点都为黑色(不会存在两个连续的红色节点)
  • 从任一节点到叶子节点的所有路径都包含相同数量的黑色节点

image-20241029203044657

红黑树与234树等价(将红黑树所有红色节点上溢到与它们父节点同一高度---234树)

image-20241029203136679

image-20241029203146301

红黑树的黑色节点个数=234树的节点数

234树的每一个节点中：

  • 黑色节点必为父节点，红色节点为子节点(黑色中间，红色两边)

二叉搜索树的旋转

image-20241029203952970

将X的左儿子指向2，将Y的右儿子那条线擦掉，然后Y指向X

image-20241029204136966

插入

如果插入的是根节点，则为黑色

其余情况插入的节点最开始一定为红色

如果是插入红色节点，仅有一种冲突状况：可能出现连续两个红色节点，这时候需要旋转和变色来调整

红黑树的插入操作分为12种情况

其中，插入节点的父节点为黑色的4种情况，是可以直接插入，不做调整的

情况一：4种可以直接插入

image-20241029204920047

情况二：4种染色+旋转【叔父节点不是红色】之 LL/LR

image-20241029205304168

情况二：4种染色+旋转【叔父节点不是红色】之 RL/LR

image-20241029205519415

情况三：4种染色【叔父节点是红色】上溢

image-20241029205812307

删除

以234树为基础理解红黑树，1个B树节点=以黑色节点为主，若有红色节点则在其两边

B树中的删除操作 对于非叶子节点，是转换为其前驱/后继节点的删除

比如要删除6，则选择其前驱节点8或者后继节点10进行交换，然后删除前驱/后继节点

image-20241029210628895

删除操作分为两大类：

  • 红色节点：可以直接删除

  • 黑色节点：必须进行调整以满足红黑树的性质---从任一节点到叶子节点的所有路径都包含相同的黑色节点

    • 有2个红色子节点的黑色节点(不做考虑) 234树的4节点

    • 有1个红色子节点的黑色节点 234树的3节点

      用唯一的红色子节点来替代被删除的节点

      image-20241029211213345

    • 黑色叶子节点(下溢) 234树的2节点

      ①删除节点为根节点，直接删除

      ②删除节点的兄弟节点为黑色

      1、兄弟节点有红色子节点(借用兄弟子节点修复) 【 删除36 】

      image-20241029211735639

      在第一种情况下：

      image-20241029211832633

      在第二种情况下：

      image-20241029212129555

      在第三种情况下：可以随意选择左子节点或右子节点

      综上，步骤总结：

      • 在删除节点后进行旋转

      • 中心节点染为父节点的颜色

      • 两个子节点染为黑色

        2、兄弟节点没有红色子节点(父节点向下合并)

      image-20241029212709963

      兄弟节点染红，父节点染黑

      如果父节点为黑色：把父节点当作已被删除的节点处理，递归

      ③删除节点的兄弟节点为红色(转为黑色处理)

      image-20241029214955625

​ 父节点右旋，兄弟节点染黑，父节点染红，然后使用兄弟为黑色的方法进行修复

基础动态规划

image-20241108103210433

DP概念

  • 最对最优化问题，确定最优解条件，将完整问题划分成多个阶段

  • 动规问题必须包含最优子结构 : 由n-1的最优推导n的最优

  • 贪心：先做决策，只顾眼前利益；动规：基于当前最优推导出全局最优

    image-20241108104437889image-20241108104817513

    image-20241108114708241

  • 例题 斐波那契数列 求个位数

    image-20241108120149363

线性模型

最长上升子序列 LIS

  • 解释：如同1 3 0 2 6 7 9序列中的1 2 6 7 9，按顺序取出这些数，后一个数总比前一个数大的序列叫做这个序列的上升子序列。

  • 题目：对于一个个数为n的序列，求它的最长上升子序列。

  • 解法：动态规划，部分最优状态“优上加优”，设f[i]表示以a[i]结尾的最长上升子序列的长度，核心代码如下：

    for(int i=1;i<=n;i++){
    f[i]=1;
    for(int j=1;j<i;j++){
        if(a[i]>a[j])                      //上升
            f[i]=max(f[i],f[j]+1);       //最长子序列
    }
}

    变体

    image-20241108204106545

    例题1

    image-20241108204133947

    解题

    • 编号 1... ti ... n
    • 分别求最长上升和最长下降，然后枚举ti

    例题2 P2782 友好城市

    image-20241108205123710

    解题

    • 要求不能相交：排个序然后LIS

      image-20241109095112085

      image-20241108212107306

    例题3 最大上升子序列和

    题目：N个数的序列，求最大上升子序列的和

    解题

    • 定义f[i]表示以a[i]为最后一个数的递增子序列的最大和
    • f[i]=max( f[j] ) + a[i] Ans=max

最大连续子段和

  • 解释：给定一个序列(正负不定)，求连续的一段序列，使得它们和最大

  • 举例：假设有序列 ： 2 3 -1 2 2 -3 1

    那么，最大连续字段和是 2 + 3 + (-1) + 2 + 2 = 8

  • 求解：f[i] : 以a[i]为终点(连续区间右边界)的子序列的最大和

    f[i] = max( f[i-1]+a[i], a[i] ) = max( f[i-1], 0 ) + a[i] //如果左边是负数，没必要加，如果是正数，多多益善

  • 例题1 P1982 小朋友的数字

最长公共子序列 LCS

  • 解释：两个子串A=abdde，B=abeee，则最长公共子序列C=abe

  • 求法：f[i] [j]:A串匹配到了i位，B串匹配到了j位，此时LCS长度为f[i] [j]

    当A串第i位和B串第j位相同的时候，f[i] [j]=f[i-1] [j-1]+1

    ​ 其他时候，f[i] [j]=max( f[i-1] [j], f[i] [j-1] )

    image-20241109162145100

坐标类模型

  • 概念：状态比较简单，通常f[i] [j]表示i行j列

    一般移动方式会直接给出----我从哪里来，要到哪里去？

  • 例题1：

    image-20241109164047815

    例题2： P1004 方格取数

    image-20241109164646613

    image-20241109165027593

    例题3： P1002 过河卒 cv1219 骑士游历 P3126 回文路径

    image-20241114093223884

    在判断一个点有没有被马拦住时，会用到 (i−2,j−1) 和(i−1,j−2) 这两个位置，那如果不把所有的点的坐标都加上 2 （前面分析的时候只把所有的坐标加上 1），就会因为数组越界而 WA 掉一个点。

    #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置

int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; //判断这个点有没有马拦住
int main(){
    scanf("%d%d%d%d", &bx, &by, &mx, &my);
    bx += 2; by += 2; mx += 2; my += 2;
    //坐标+2以防越界
    f[2][1] = 1;//初始化
    s[mx][my] = 1;//标记马的位置
    for(int i = 1; i <= 8; i++) s[mx + fx[i]][my + fy[i]] = 1;
    for(int i = 2; i <= bx; i++){
        for(int j = 2; j <= by; j++){
            if(s[i][j]) continue; // 如果被马拦住就直接跳过
            f[i][j] = f[i - 1][j] + f[i][j - 1];
            //状态转移方程
        }
    }
    printf("%lld\n", f[bx][by]);
    return 0;
}

区间模型

背包模型

01背包

01背包问题：有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品只能取1次放入背包中，背包所有物品权重和最大是多少？

// 01背包
#include <iostream>
using namespace std;
#define MX 50010
long n, m;
long v[MX], w[MX], f[MX];
long max(long x, long y) {
	return x > y ? x : y;
}
int main() {
	cin >> n >> m;
	for (long i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	for (long i = 1; i <= n; i++) 
		for (long j = m; j >= w[i]; j--)
			f[j] = max(f[j], f[j - w[i]] + v[i]); 
	cout << f[m];
	return 0;
}

完全背包

完全背包 ：有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品可以取无限次放入背包中，背包所有物品权重和最大是多少？

01背包问题和完全背包问题的区别就在于，每个物品取的最大次数是1次还是无限次。

算法之动态规划（DP）求解完全背包问题_动态规划法求解完全背包问题-CSDN博客

for (int i = 1; i <= n; i ++ ) {
	scanf("%d %d", &w, &v);
	for (int j = w; j <= m; j++ ) {
		f[j] = (f[j] > f[j - w] + v) ? f[j] :f[j - w] + v;
	}
}
printf("%d\n", f[m]);

  • 多重背包

  • 混合背包

分组背包

// 分组背包
#include <iostream>
using namespace std;
#define MX 50010
#define MY 10010
long n, m, z, t;   // 一共t组，z是中间量
long v[MX], w[MX], f[MX], b[MX];  // b是一个桶
long g[MY][MY];
long max(long x, long y) {
	return x > y ? x : y;
}
int main() {
	cin >> m >> n;   // 总重m,总共n个
	for (long i = 1; i <= n; i++) {
		cin >> w[i] >> v[i] >> z;
		t = max(t, z); 
		b[z]++;
		g[z][b[z]] = i;
	}
	for (long i = 1; i <= t; i++)
		for (long j = m; j >= 0; j--)
			for (long k = 1; k <= b[i]; k++)
				if (j >= w[g[i][k]])
					f[j] = max(f[j], f[j - w[g[i][k]]] + v[g[i][k]]);
	cout << f[m];
	return 0;
}

  • 依赖背包

  • 二维背包与多维费用背包

搜索

一个例子：素数环
image-20241110140352460

素数环EX，既然每一层for循环都很像，那么何不让程序自己去处理呢？

image-20241110140532363

回溯法

image-20241110140600832

要点： 初始状态，目标状态，穷举范围，约束条件，状态恢复

代码框架：

  • 先判断是否达到目标状态

  • 如果达到，判断当前状态是否合法、 是否计入答案

  • 未达到，枚举可能的状态---标记本轮选择，进入下一层

  • ​ ---标记返还

DFS-栈

bfs求解素数环

int a[30],vis[20],n,ans;
inline bool check(int x){
    for(int i=2;i*i<=x;i++) if(x%i==0)return 0;
    return 1;
}
inline void dfs(int now){
    if(now==n+1){               // now 标定了目标状态，一共now个
        if(check(a[n]+a[1]))ans++;
        return;
    }
    for(int i=1;i<=20;i++){              // a[now-1]就是前一个
        if(vis[i])continue;             // i就是下一个a[now]
        if(!check[i+a[now-1]])continue;//寻找满足条件的a[now]
        vis[i]=1;a[now]=i;
        dfs(now+1);
        vis[i]=0;
    }
}
int main(){
    n=read(); 
    dfs(1);
    printf("%d\n",ans);
}

一个例题： P1238 走迷宫 dfs实现

image-20241110143356438

image-20241110143336406

一个应用：全排列

image-20241110143211226

一个新问题：P1135 奇怪的电梯

image-20241110143530549

BFS-队列

考虑这种遍历的形式：

  • 得到一个状态后，用它拓展出所有状态，然后将它丢弃
  • 每次选择当前未被丢弃的最早的一个状态进行拓展，这样就能保证优先的性质

image-20241110144023537

奇怪的电梯求解

image-20241110144122166

P1238 走迷宫 bfs实现

二者比较

bfs：具有良好的优先性质，但较难统计具体方案

dfs：易于保存方案，首选，但无法解决优先性问题，依赖系统栈会致使栈溢出

搜索的时间复杂度

image-20241110144738738

一些练习题

P1037 产生数

考虑dfs解决：首先遍历每一位，按照规则生成改位新的数进行搜索，由于映射关系不存在自环，不需要判重。

P1451 求细胞数量

这是一种常见的搜索办法，被称为染色法或flood-fill算法。本质是bfs或dfs

优化搜索

image-20241110160518313

一道老题

image-20241110160705618

我们有几个比较基础的判断：

是否做到了m层，是否最终体积为0，是否当前面积最小

优化方向

  • 最优化剪枝

    如果当前表面积+余下侧面积>之前的最优值，直接返回

  • 可行性剪枝

    如果当前剩下的做不到m层，肯定要跳出

    同理，如果剩下的太多，哪怕以最大代价做完m层都会用剩，也要跳出

    image-20241110161935920

    image-20241110164355703

剪枝的注意点

image-20241110164536762

总结

image-20241110164614530

经典剪枝例题： 骑士巡游问题

image-20241110164751192

image-20241110164920551

记忆化搜索

image-20241110165023597

记忆化搜索例题 P3183 食物链

贪心与二分

二分

image-20241111090435444

inline double find(double l, double r){
    while(r-l>eps){    //eps精度
        double mid=(l+r)/2;
        if(f(mid)==0)return mid;
        if(f(l)*f(mid)<0)r=mid;
        else l=mid;
    }
    return l;
}

二分查找

image-20241111090632823

inline int Binary_Search(int l,int r,int x){
    if(l>r)return -1;
    int mid=(l+r)>>1;
    if(a[mid]==x)return mid;
    if(x<a[mid])return Binary_Search(l,mid-1,x);
    if(x>a[mid])return Binary_Search(mid+1,r,x);
}

STL的二分查找

image-20241111091450799

image-20241111091948476

  • 在vector上的用法

    lower_bound(a.begin(), a.end(), 2)

    vector的迭代器可减，可以和数组一样减去数组名来获取下标

  • 在map、set上的用法

​ a.lower_bound(2)

​ STL的迭代器不可减，毕竟这本质是平衡树，没有下标

二分答案

image-20241111092704954

image-20241111092723605

二分答案的模板

image-20241111092827578

例题1 NOIP2011 聪明的质检员

解释：每次对给定的W，≥W的个数和乘上价值和，检验值y是所有区间检验值的和，现在的任务就是调整W使得得到的结果尽可能接近S

思路：寻找单调性---W越大，y越小，换言之，y=f(W)是一个单调函数。此时问题转变成abs(f(W)-s)的最小值，求零点或者接近零点的点，二分解决。那么如何快速计算f(w)?可以先离线求出所有矿石价值和个数的前缀和，这样可以做到一个O(1)查询一个区间，总复杂度O(nlogn)

image-20241111093635514

例题2 NOIP2012 借教室

image-20241111093820551

例题3 NOIP2015 跳石头

要求移除至多M块石头，使得选手跳跃最短距离尽可能长

寻找单调性，移除石头越多，答案一定越大，令f(x)表示当最小值不低于x时，最小需要移动多少石头，对这个函数二分答案即可。

那么怎么求这个f(x)呢？

贪心

image-20241111094243334

和动规进行比较

image-20241111094316127

什么样的题可以贪心

小栗子

image-20241111095018404

dp如何设计

image-20241111094941660

考虑贪心来求解

image-20241111094934087

小结

image-20241111095042403

大梨子

image-20241111095308041

image-20241111095410277

再次感受一下贪心算法

image-20241111095420973

例题 NOIP2004 合并果子

image-20241111095618774

例题 P1903 活动选择问题

image-20241111095858822

例题 NOIP2010 三国问题

image-20241111100000972

image-20241111100016820

例题 P1223 排队接水

image-20241111100105294

image-20241111100132432

例题 P1012 拼数

image-20241111100228360

image-20241111100240212

运用贪心思想的经典算法

image-20241111100258184

哈夫曼编码

  • 任何一个编码都不是其他编码的前缀
  • 尽量用少的字节

数据结构——哈夫曼(Huffman)树+哈夫曼编码 - 王陸 - 博客园

[译文]5分钟系列—快速理解Huffman Coding(霍夫曼编码) - 知乎

编码 do or not do

image-20241112143029549

image-20241112143135687

解码

image-20241112143043528

引例：

编码问题：

  • P5000 Hillwer编码 - 洛谷 | 计算机科学教育新生态

    • GG

  • P1246 编码 - 洛谷 | 计算机科学教育新生态 (升序)

    • #include<bits/stdc++.h>
using namespace std;
string s;
int ans,n;
int c(int m,int n)//组合数计算 
{
	if(m==0)return 1;
	int mut=1;
	for(int i=n;i>n-m;i--)mut*=i;
	for(int i=m;i>1;i--)mut/=i;
	return mut;
}
int main()
{
	cin>>s,n=s.size();
	for(int i=1;i<n;i++)
		if(s[i]<=s[i-1])cout<<0,exit(0);//判断是否存在
	for(int i=1;i<n;i++)ans+=c(i,26);//计算出位数比它小的单词数
	for(int i=0;i<n;i++)//枚举每一位
		for(char j=(i==0?'a':s[i-1]+1);j<s[i];j++)//注意考虑边界
			ans+=c(n-i-1,'z'-j);//因为字符串下标从0开始，所以是n-i-1而不是n-i
	cout<<++ans;//别忘了最后把自己加上
	return 0;
}

    • // 递推 杨辉三角
#include<iostream>
using namespace std;
string s;
int f[30][10],ans,cnt;
int main(){
    cin >> s;
    for(int i = 1;i < s.size();i++){
        if(s[i - 1] >= s[i]){
            cout << 0;
            return 0;
        }
    }
    //判断字符串是否合法（升序）
    for(int i = 1;i <= 26;i++)
        f[i][1] = 1;
    //长度为1的字符串数量都是1
    for(int j = 2;j <= 6;j++)
        for(int i = 27 - j;i > 0;i--)
            f[i][j] = f[i + 1][j - 1] + f[i + 1][j];
    //由公式，我们从上至下从右至左进行计算
    for(int j = s.size() - 1;j >= 0;j--){
        cnt++;
        for(int i = 1;i <= s[j] - 'a' + 1;i++)
            ans += f[i][cnt];
    }
    //由以上的思路计算答案
    cout << ans;
    return 0;
}

例题 P1230 智力大冲浪

image-20241111100546210

image-20241111100603796

模拟与枚举

image-20241111101655332

模拟

例题 NOIP2003 普及组] 乒乓球

模拟题注意点： 仔细读题，所有规则都从题目中提取，及时记录特判

例题 NOIP2017 时间复杂度image-20241111102719530

image-20241111102933350

枚举

例题 NOIP2011 提高组] Mayan 游戏

image-20241111103614808

image-20241111103651171

image-20241111103711460

枚举策略

为什么学枚举策略

image-20241111103804731

BFS

image-20241111104002051

哈希

image-20241111104132388

例题 P1379 八数码难题

image-20241111104353540

Two Pointers

image-20241111104515894

image-20241111104534709

折半查找

image-20241111104551758

正难则反

image-20241111104751057

提取信息

image-20241111104817379

image-20241111104911569

优化搜索

[P3417 POI2005] BANK-Cash Dispenser - 洛谷 | 计算机科学教育新生态

image-20241111105128889

大事化小

据问减枝

基础数学思维

组合计数

计数原理

排列组合

image-20241111115306146

image-20241111115340705

集合

定义运算

子集

image-20241111115502550

数论

素数

image-20241111115815204

image-20241111115903249

素数判定

image-20241111120141359

bool isRrime(int n){
	for(int i=2;i*i<=n;i++) 
        if(n%i==0) return false;
    return true;
}
筛素数

例题：第K小素数

埃氏筛

//生成不大于 n 的所有质数
bool numlist[100000001];
int prime[20000001], cnt;
void work(int n){
	for(int i=2; i<=n; i++){
		if(numlist[i]==false){
			prime[++cnt] = i ;
			for(int j=i; i*j<=n; j++)
				numlist[i*j] = true;
		}
	}
	return;
}

要想得到 n 以内的质数，就要把不大于 n 的质数的倍数全部剔除，剩下的就是质数。从 2 开始，把 2 的倍数（不包括本身）标记为合数，然后向后枚举，查到一个未标记为合数的，就把它的倍数（不包括本身）标记为合数。以此类推，查到 n 为止。
有一个小优化，把 t 的倍数标记为合数时，不是从 2t 开始，而是从 t^2 开始（因为小于 t^2 的 t 的倍数在枚举到 t 前就被标记过了）。
当然，埃氏筛效率还是低了些。例如一个数 24，它会被 2, 3, 4 三个数标记，这就重复了两次，更大的数同理。时间复杂度 O(nlogn)。

欧拉筛

bool numlist[100000001];
int prime[20000001], cnt;
void work(int n){
	for(int i=2; i<=n; i++){
		if(numlist[i]==false)
			prime[++cnt] = i ;
		for(int j=1; j<=cnt&&i*prime[j]<=n; j++){ //最大非自身因数
			numlist[i*prime[j]] = true ;      //记忆化存储
			if(i%prime[j]==0)                 //最小质因数
				break;
		} 
	}
	return;                                  //一根筋变两头堵
}

避免重复筛，应找到筛合数的一种原则：这个合数只会被它的最大非自身因数（对应最小质因数）筛。这样能保证每个合数只会被筛一次。

以下为完整代码

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
        	//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤。见原理
		}
	}
}

int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	GetPrime(n);
	while (q--)
	{
		int k;
		scanf("%d", &k);
		printf("%d\n", Prime[k]);
	}
	return 0;
}

GCD 与 LCM

最大公约数 gcd 与 最小公倍数 lcm

image-20241111120542771

int gcd(int a, int b){
    if(a>b) swap(a, b);
    if(a==o) return b;
    else return gcd(a, b%a);
}
int gcd(int a,int b){return a==0?b:gcd(a,b%a);}

image-20241111120946914

image-20241111120924238

例题：

image-20241111121133388

幂运算

原理 --- log2(b) P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态

快速幂

(1)如果将 a 自乘一次，就会变成 a^2 。再把 a2自乘一次就会变成a4 。然后是 a^8…… 自乘 n 次的结果是 a2n 。

(2)a^x * ay=a(x+y)。

(3)将 b 转化为二进制: b(11)10 = b(1011)2 = 8 + 2 + 1。

int quickPower(int a, int b)//是求a的b次方
{
	int ans = 1, base = a;//ans为答案，base为a^(2^n)
	while(b > 0)//b是一个变化的二进制数，如果还没有用完
    {
		if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
			ans *= base;//把ans乘上对应的a^(2^n)
		
        base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
		b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
	}
	return ans;
}
/*关于 b & 1：
“&”美名曰“按位与”。
          二进制
b     =    1011
1     =    0001
b&1   =    0001
因为 1（二进制）的前面几位全部都是 0，
所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。 */

取余运算

快速幂经常要结合取余运算。这里也讲一点。

取余运算有一些好用的性质，包括：

(A + B) mod  b= (A mod b + B mod b) mob b

(A x B) mod  b= ((A mod b) x (B mod b)) mob b

#include <iostream>
using namespace std;
int main() {
	long long a, b, q;
	cin >> a >> b >> q;
	long long ans = 1, base = a, b_copy = b;
	while (b > 0) {
		if (b & 1) {
			ans *= base;
			ans %= q;
		}
		base *= base;
		base %= q;
		b >>= 1;
	}
	cout << a << "^" << b_copy << " mod " << q << "=" << ans;
	return 0;
}
矩阵快速幂

矩阵乘法

//本例中计算矩阵A×矩阵B，存到矩阵C里
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){  //找到c[i][j]，开始算
			for(int k=1;k<=n;k++){
				c[i][j]+=a[i][k]*b[k][j];//矩阵乘法的定义
			}
		}
	}

另一种快速幂

image-20241106161527126

while(p>0) {
	if(p%2!=0) ans=ans*b;
    	b=b*b;
        p=p>>1;
}

矩阵乘法 + 快速幂

struct Matrix {			 														//结构体
	long long c[101][101];
} A,I;
long long n,k;
Matrix operator*(const Matrix &x,const Matrix &y) {								//重载
	Matrix a;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			a.c[i][j]=0;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			for(int k=1; k<=n; k++) {
				a.c[i][j]+=x.c[i][k]*y.c[k][j]%Mod;
				a.c[i][j]%=Mod;
			}
	return a;
}
void Fastpower_Matrix(int k){													
	for(int i=1; i<=n; i++)
		I.c[i][i]=1;															//单位矩阵定义
	while(k>0) {																//Fastpower_Matrix
		if(k%2==1) I=I*A;
		A=A*A;
		k=k>>1;
	}
}

完整代码

#include <iostream>
using namespace std;
const int Mod = 1000000007;
long long n, m;
struct Matrix {
	long long c[101][101];
} A, I;
Matrix operator*(const Matrix &x, const Matrix &y) {
	Matrix a;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a.c[i][j] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++) {
				a.c[i][j] += x.c[i][k] * y.c[k][j] % Mod;
				a.c[i][j] %= Mod;
			}
	return a;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> A.c[i][j];
	for (int i = 1; i <= n; i++)
		I.c[i][i] = 1;
	while (m > 0) {
		if (m & 1)             // 第一种快速幂
			I = I * A;
		A = A * A;
		m = m >> 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << I.c[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

前缀和

概念：

image-20241109092436687

模板：

using ll = long long;
const ll N = 1e5 + 9;
ll a[N], prefix[N];
int main(){
	ll n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n.i++) prefix[i]=prefix[i-1]+a[i];
}

拓展：

①带有逆的运算

求一段区间的异或和(亦或的逆运算是它自己，因此pre[r] ^ pre[l-1]即可 )。

image-20241106210707886

②带修改的前缀和

image-20241106211110488

③二维的前缀和

image-20241106212124842

P3406 海底高铁
int n, m, a, b, c, p[N], s[N], ans;
int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) p[i] = read();
	for (int i = 1; i < m; i++) {
		s[max(p[i], p[i + 1])]--; // 构建差分数组
		s[min(p[i], p[i + 1])]++; // 此时l=r,区间长度为1
	}
	for (int i = 1; i <= n; i++)
		s[i] += s[i-1]; //s[i]：从1到i的累计次数
	for (int i = 1; i < n; i++) {
		a = read(); b = read(); c = read();
		ans += min(a*s[i], b*s[i]+c);
	}
	cout << ans;
	return 0;
}
/*没有AK，过了60%，把int 换成long long就过了*/

原题解

#include<iostream>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std; 
int main(){
	long long n,m,x,y,ans=0;
	cin>>n>>m;
	long long p[m+1];
	long long t[n+1]={};
	long long a[n+1],b[n+1],c[n+1];
	for(long long i=1;i<=m;i++){
		cin>>p[i];
	}
	for(long long i=1;i<=n-1;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	for(long long i=1;i<=m-1;i++){
		x = min(p[i],p[i+1]);
		y = max(p[i],p[i+1]);
		t[x]++;
		t[y]--;
	}
	for(long long i=1;i<=n;i++){
		t[i]+=t[i-1];
	}
	for(long long i=1;i<=n-1;i++){
		ans+=min(a[i]*t[i],b[i]*t[i]+c[i]);
	}
	cout<<ans;
	return 0;
}

差分

概念：

image-20241109093736668

模板：

using ll = long long;
const ll N = 1e5 + 9;
ll a[N], diff[N], prefix[N];
int main(){
	ll n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n.i++) diff[i]=a[i]-a[i-1];
}

image-20241109094133325

ll m; cin>>m;
while(m--){
    ll l,r; cin>>l>>r>>x;
    diff[l]+=x, diff[r+1]+=x;              //差分
}
for(int i=1;i<=n;i++) a[i]=a[i-1]+diff[i]; //前缀和还原
for(int i=1;i<=n;i++) prefix[i]=prefix[i-1]+a[i];
while(q--){
    ll l,r; cin>>l>>r;
    cout<<prefix[r]-prefix[l-1]<<'\n';     //指令输出
}

并查集

处理一些不相交集合的合并与查询问题

Find:确定元素属于哪一个子集，可被用来确定两个集合是否属于同一子集

Union:将两个子集合并成同一个集合

image-20241110093554949

#include <iostream>
#include <stdio.h>
const int N=10000+10; 
using namespace std; 
int fa[N],n,m;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
	int xx=find(x),yy=find(y);
	fa[yy]=xx;
}
inline int read(){
	...
} 
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) fa[i]=i;
	while(m--){
		int opt=read(),x=read(),y=read();
		if(opt==1)merge(x,y);
		else{
			int xx=find(x),yy=find(y);
			xx==yy?puts("Y"):puts("N");
		}
	}
	return 0;
}

例题： P1551 亲戚 P1197 星球大战

并查集在常见算法中的应用

image-20241110093833347

KMP

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la, lb, j;
char a[MAXN], b[MAXN];
int main(){
	cin>>a+1;
	cin>>b+1;
	la = strlen(a+1);
	lb = strlen(b+1);
	for(int i=2; i<=lb; i++){
		while(j&&b[i]!=b[j+1]) j = kmp[j];
		if(b[i]==b[j+1]) j++;
		kmp[i] = j;
	}
	j = 0;
	for(int i=1; i<=la; i++){
		while(j>0&&a[i]!=b[j+1]) j = kmp[j];
		if(a[i]==b[j+1]) j++;
		if(j==lb){
			cout<<i-lb+1<<endl;
			j = kmp[j];
		}
	}
	for(int i=1; i<=lb; i++)
		cout<<kmp[i]<<" ";
	return 0;
}

第K大的数

std::nth_element()

模板题更多相关文章

今日报告-66

设置Windows10暂停更新3000天

AQS公平锁的流程

AMD锐龙7 7800X3D网游专项测试：竟比i9-13900KS强了15%

常用总线技术基本参数对比

探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅

设置Chrome浏览器自动升级

JavaScript – 小技巧 Tips

Winform无边框窗体实现拖动

STM32基础（一）

技术人的修炼---九五小庞

vue自定义事件用法及$emit

ODOO 科目配置4

sqlite 触发器 c#

postgresql在插入数据后怎么获取自增id

EF Core 的基本使用

error: failed to push some refs to 'https://github.com/*******/********.github.io.git'

欧拉降幂

编程语言能力对比

基于机器视觉的小车轨迹控制软件界面展示

随机推荐

20241101 数据结构与算法期中机试收获

Java，启动！

什么是IT技术

即将到来！

2024/11/1日 日志 关于JavaScript简介&引入方式 以及基础语法的学习

舍得-时间-工作是人的一生最重要的事情-自己要有私房钱-人的一生最重要的事情是书写自己的人生

2.TiUP 部署 DM 集群

原型模式的C++实现

python bytecode解析

09-XSS键盘监听、cookie窃取&文件上传绕过

ubuntu 24.04 部署 mysql 8.4.3 LTS

国标GB28181公网平台LiteGBS国标GB28181视频平台建筑工地无线视频联网监控系统方案

imes完工下线

android 13 更改手机信号调整

BFS(Breath First Search 广度优先搜索)

Visual Studio Code（VSCode）中设置中文界面

影响黄金价格大幅波动的因素主要有哪些？

winform用Dev的TreeList滚动到指定节点的位置

Angular 18 上手开发

SSHD服务

热门话题

Ethernaut Level 11: Elevator Attack and Blockchain Interaction

快速部署开源spug运维平台的Docker安装指南

驱动调试之printk的原理与使用

计算机思维模型及其应用

华为云发布代码大模型PanGu-Coder2，实现高效代码生成

Linux多硬盘数据存储和分区操作

构建高可用架构: 分层冗余与自动故障转移

LoRA：高效调参的大语言模型适应方法

《分布式系统的基本原理及互联网分层架构的本质》

Hadoop写流程解析

Java架构师的系统架构设计方法论中的规范要点

使用observeDOM解决BetterScroll插件在移动端无法滑动的问题

互联网一致性架构设计实践

高并发系统架构与水平扩展

混合应用的崛起：跨平台开发取代原生应用

  穗舟网 （www.seizhou.com）

本站除标明"本站原创"外所有文章版权归创作人所有，本站不承担任何法律责任和连带责任，如有冒犯请直接联系，我们将立即予以纠正并致歉。

Powered by WordPress  ·  v1.0.0-alpha