语法糖

字符

cstring
isalnum(c) 字母或数字 isalnum('a') → true
isalpha(c) 字母 isalpha('Z') → true
isdigit(c) 十进制数字 isdigit('5') → true
string
s.append(str) 追加 s.append("xyz")
s.insert(pos, str) 插入 s.insert(1, "abc")
s.erase(pos, len) 删除 s.erase(1, 2)
s.replace(pos, len, str) 替换 s.replace(1, 2, "new")
s.push_back(c) 末尾添加字符 s.push_back('!')
s.pop_back() 删除末尾字符 s.pop_back()
s.resize(n) 改变大小 s.resize(10, 'x')
s.swap(s2) 交换 s1.swap(s2)
输入输出
cin >> s 读取单词 遇到空白停止
getline(cin, s) 读取一行 包括空格
cin.getline(buf, size) C风格读取一行 用于字符数组
sstream 字符串流处理 #include <sstream>

生成二进制序列

递归生成会受制于层数,当N>?时会栈溢出.

迭代则类似于dfs的处理,用队列存储中间结果.假设已经获取到了n,调用此函数

void gene(){
    vector<ll>res;
    queue<string>q;
    q.push("1");
    while(q.size()){
        auto x=q.front();q.pop();
        res.push_back(stoi(x));
        if(x.size()<n)q.push(x+'0');q.push(x+'1');
    }
    for(auto &it:res)cout<<it<<'\n';
}

假设n<9,则int类型已经够用了.需要对更大的n支持,也可以用std::stol(), std::stoll()

数据结构

Segment tree

高效区间修改和查询.原理是二叉查询树.对大小为N的原始数组a[],一般开4N大小的两个数组将树和标记作为完全二叉树存储.

1.建树

分治,每次对半处理当前段.当递归到叶节点后return,聚合区间信息(最值,区间和等等).BTW,对于多组数据,记得顺手初始化标记数组Lz

build(u,l,r):
	Lz[u]=0; 
	if(leaf){St[u]=a[l];return;}
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pull(u);

这里为了方便修改将聚合语句抽象出来,觉得写左右子节点麻烦也可以写宏

merge(x,y):
	//根据需求更改
	return max(x,y);
pull(u):
	St[u]=merge(St[u<<1],St[u<<1|1]);

2.区间更新

依据当前区间与给定的修改区间的交集修改.前者为子区间时,更新完St[u]和Lz[u]就行了,否则下发标记并继续递归子区间,注意最后也要把更改拉上来,也就是push后记得pull.

update(u,d){St[u]+=d;Lz[u]+=d;}
push(u):
	if(Lz[u]){
	update(u<<1,Lz[u]);
	update(u<<a|1,Lz[u]);
	Lz[u]=0;
	}	
add(u,l,r,ql,qr,d):
	if(ql<=l&&r<=qr){
		update(u,d);return;
	}
	push(u);
	int mid=l+(r-l)/2;
	if(ql<=mid)add(u<<1,l,mid,ql,qr,d);
	if(qr>mid)add(u<<1|1,mid+1,r,ql,qr,d);
	pull(u);

对经常用到以及可能要修改的代码块封装起来,如下发标记,拉取更改,更新,子节点访问等等.

3.线段树得到以下写法:

#define L u<<1
#define R u<<1|1
const int N=5e5+7,P=998244353;
int a[N],n;
ll St[N<<2],Lz[N<<2];

ll merge(ll x,ll y){return max(x,y);}
void update(int u,ll d){
    St[u]+=d;Lz[u]+=d;
}
void push(int u){
    if(Lz[u]){
        update(L,Lz[u]);update(R,Lz[u]);
        Lz[u]=0;
    }
}
void pull(int u){St[u]=merge(St[L],St[R]);}
void build(int u,int l,int r){
    Lz[u]=0;//
    if(l==r){St[u]=a[l];return;}
    int mid=(l+r)>>1;
    build(L,l,mid);build(R,mid+1,r);
    pull(u);
}
void add(int u,int l,int r,int ql,int qr,int d){
    if(ql<=l&&qr>=r){
        update(u,d);return;
    }
    push(u);
    int mid=(l+r)>>1;
    if(ql<=mid)add(L,l,mid,ql,qr,d);
    if(qr>mid)add(R,mid+1,r,ql,qr,d);
    pull(u);
}

BTW,关于Lz初始化的实现,在一开始考虑用vector的reserve()实现,但只是预留空间,不会初始化,导致Lz不会正确重置甚至无法访问.

总之,最好的方式是建树时读取原数组顺便重置Lz数组.

算法

多源最短路径

当对全部点遍历复杂度不可接受时,考虑筛选出一些点进行多源bfs.

多源bfs,从实现上看就像从一个虚点开始的bfs,多个源点作为其邻点入队.

V lv(n+1),dis(n+1,-1);
REP1(i,1,n)lv[i]=g[i].size();
    queue<int> q;
    REP1(i,1,n){
        for(auto &v:g[i]){
            if(lv[v]>lv[i]){
                dis[i]=1; q.push(i); break;
            }
        }
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(auto& v:g[u]){
            if(lv[v]<=lv[u]&&dis[v]==-1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    REP1(i,1,n)cout<<dis[i]<<' ';cout<<'\n';

Dijkstra

Input: 

graph G=(V,E), (un)directed;Positive edge and vertex.

Init:

for all u in V:

​	dist(u)=inf; prev(u)=0;

dist(s)=0;

Dijkstra:

Q=makequeue(V)

while Q is not empty:

​	u=deletemin(Q)

​	for all edges (u,v):

​		if dist(v)>dist(u)+l(u,v): 

​		dist(v)=dist(u)+l(u,v)

​		prev(v)=u;

​	REC

单调栈

https://codeforces.com/problemset/problem/2165/A

每次选择一个小的元素,被删除的时候,代价为相邻元素中较小的一个.也就是说, 尽量和“比它大、但尽量小的那个数”合并. 要找到左右两侧第一个大于其的元素.

要解决几个问题:

  • 如何快速删除,维护,找到第一个大于元素,用什么数据结构?
  • 解决环的问题

单调递减栈,在维护的同时可以快速删除;从最大元素处拉直(作为栈底).

先考虑最简单的情况:整个数组单调,从最大元素加到倒数第二个元素(都加左侧元素(第一个大于的元素))就是结果.当出现不和谐元素,即一般情况时,要综合考虑左右侧.总之都是一个逻辑:找到最近的较大元素,维护单调栈的过程即是综合比较的过程

stack<int> stk;
void op(int st,int ed){
    REP(i,st,ed)
    {
        int x=a[i];
        while(stk.size()&&stk.top()<x){
            stk.pop();
            res+=min(stk.top(),x);
        }
        stk.push(x);
    }
}
void solve(){
    cin>>n;int p=0;
    REP(i,1,n){cin>>a[i];p=(a[p]<a[i]?i:p);}
    op(p,n);op(1,p-1);
    while(stk.size()>1){
        stk.pop();res+=stk.top();
    }
    cout<<res<<'\n';
    res=0;stk.pop();
}

从简单情况到一般情况,从找差异的过程中抽象出规则.

Kadane-最大和子序列

def max_subarray_kadane(nums):
    if not nums:
        return 0
    
    max_sum = current_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

可以看作是隐式双指针法.l,r,都在for循环第一个语句中

这样想:如果cur+a[i]<a[i],不是说明cur为负值嘛,甩掉就行了,对应左指针的更新;否则加上a[i],对应右指针的线性扫描.好处是实现简洁,指针操纵要注意的实在太多了,但不能记录l,r了…image-20251124232607722

这题可以通过1->-1,0->1来适配该算法,以统计0净数量最大的区间.相比于更改算法结构,构造一个导出数组显然更简单.注意题干,确切执行一次操作,哪怕全是1.