首页 > 其他分享 >复习

复习

时间：2024-10-24 20:36:23浏览次数：1  
标签：复习 int sum tor tol now id

发出来给大伙参考吧

数学

  • 逆元递推式（需要满足模数为质数）
inv[1]=1;
inv[i]=(p-p/i)*inv[p%i]%p;

DP

\[f_i=\max_{j\lt i}f_j \]

\[f_{i,j}=\max_{k\lt j}(f_{i,k}+cost) \]

单调队列 / 对每个 \(i\) 维护单调队列

  • 二维线性 DP 存在一个同时由 \(j,k\) 影响的变量，则该状态转移方程无法用单调队列来优化

\[f_i=f_{i-1}+f\cdots+cost \]

项数较小的递推式可以套矩阵快速幂

\[f_i=\sum_{a_i=a_j} f_j \]

\[f_i=\max_{a_i\neq a_j} f_j \]

  • 比较弱的优化是可以对 \(a\) 离散化开桶前缀和，对于不等式可以考虑从整体里扣掉

  • 如果题目适用可以考虑上 bitset

算出 \(10^{10}\) 以下的复杂度先考虑能不能 bitset 套上去

板子 & trick

  • 非严格次小生成树：跑出最小生成树，枚举所有非树边，一定会和树上某一部分成环，然后断掉环上最大边，实际操作的时候采用 LCA 跳一遍端点
  • 严格次小生成树：基本同上，寻找出来之后判断是否新建边与断边相等
严格次小生成树 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct __e{
	int from,to,w;
	int id;
	bool operator <(const __e&A)const{
		return w<A.w;
	} 
};
vector<__e>v;
struct dsu{
	int fa[100001];
	void clear(int n){
		for(int i=1;i<=n;++i){
			fa[i]=i;
		}
	}
	int find(int id){
		if(fa[id]==id) return id;
		return fa[id]=find(fa[id]);
	}
	bool connect(int x,int y){
		int fx=find(x),fy=find(y);
		if(fx==fy) return false;
		fa[fx]=fy; return true;
	}
}dsu;
bool vis[300001];
int ans=0,tot;
struct edge{
	int to,w;
};
vector<edge>e[100001];
int fa[17][100001];
int w[17][100001];
int deep[100001];
void dfs(int now,int last){
//	cout<<"dfs "<<now<<" "<<last<<endl;
	for(edge i:e[now]){
		if(i.to!=last){
			fa[0][i.to]=now;
			w[0][i.to]=i.w;
			deep[i.to]=deep[now]+1;
			dfs(i.to,now);
		}
	}
}
int lca(int x,int y,int less){
	if(deep[x]<deep[y]) swap(x,y);
	int res=-1;
	for(int i=16;i>=0;--i){
		if(deep[fa[i][x]]>=deep[y]){
			if(w[i][x]<less) res=max(res,w[i][x]);
			x=fa[i][x];
		}
	}
	if(x==y) return res;
	for(int i=16;i>=0;--i){
		if(fa[i][x]!=fa[i][y]){
			if(w[i][x]<less) res=max({res,w[i][x]});
			if(w[i][y]<less) res=max({res,w[i][y]});
			x=fa[i][x];
			y=fa[i][y];
		}
	}
	if(w[0][x]<less) res=max({res,w[0][x]});
	if(w[0][y]<less) res=max({res,w[0][y]});
	return res;
}
int cx=0x3f3f3f3f3f3f3f3f;
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;++i){
		int x,y,z;scanf("%lld %lld %lld",&x,&y,&z);
		v.push_back({x,y,z,i});
	}
	sort(v.begin(),v.end());
	dsu.clear(n);
	for(__e i:v){
		if(tot==n-1){
			break;
		}
		if(dsu.connect(i.from,i.to)){
			e[i.from].push_back({i.to,i.w});
			e[i.to].push_back({i.from,i.w});
			ans+=i.w;
			tot++;
			vis[i.id]=true;
		}
	}
	deep[1]=1;
	dfs(1,0);
	for(int i=1;i<=16;++i){
		for(int j=1;j<=n;++j){
			fa[i][j]=fa[i-1][fa[i-1][j]];
			w[i][j]=max(w[i-1][j],w[i-1][fa[i-1][j]]);
		}
	}
	for(__e i:v){
		if(!vis[i.id]){
			int tmp=lca(i.from,i.to,i.w);
			if(tmp!=-1) cx=min(cx,ans-tmp+i.w);
		}
	}
	cout<<cx;
}
  • \(k\) 短路：\(dis_{i,k}\) 表示到 \(i\) 的第 \(k\) 短路，每次松弛的时候排名从小到大依次比较，小于就插入，后面的数排名依次加一
  • 最长路：SPFA，dij 无论如何跑不了最长路
线段树 2 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,p;
int a[100001];
namespace stree{
	struct tree{
		int l,r;
		int sum;
		int sum_lazy,mul_lazy;
	}t[400001];
	#define tol (id*2)
	#define tor (id*2+1)
	#define mid(l,r) mid=((l)+(r))/2
	void build(int id,int l,int r){
		t[id].l=l;t[id].r=r;
		t[id].mul_lazy=1;
		if(l==r){
			t[id].sum=a[l]%p;
			return;
		}
		int mid(l,r);
		build(tol,l,mid);
		build(tor,mid+1,r);
		t[id].sum=(t[tol].sum+t[tor].sum)%p;
	}
	void pushdown(int id){
		if(t[id].mul_lazy!=1){
			t[tol].sum=(t[tol].sum)*t[id].mul_lazy%p;
			t[tor].sum=(t[tor].sum)*t[id].mul_lazy%p;
			t[tol].sum_lazy*=t[id].mul_lazy%p;
			t[tol].sum_lazy%=p;
			t[tor].sum_lazy*=t[id].mul_lazy%p;
			t[tor].sum_lazy%=p;
			t[tol].mul_lazy*=t[id].mul_lazy%p;
			t[tol].mul_lazy%=p;
			t[tor].mul_lazy*=t[id].mul_lazy%p;
			t[tor].mul_lazy%=p;
			t[id].mul_lazy=1;
		}
		if(t[id].sum_lazy){
			t[tol].sum+=(t[tol].r-t[tol].l+1)*t[id].sum_lazy%p;
			t[tol].sum%=p;
			t[tor].sum+=(t[tor].r-t[tor].l+1)*t[id].sum_lazy%p;
			t[tor].sum%=p;
			t[tol].sum_lazy+=t[id].sum_lazy;
			t[tol].sum_lazy%=p;
			t[tor].sum_lazy+=t[id].sum_lazy;
			t[tor].sum_lazy%=p;
			t[id].sum_lazy=0;
		}
	}
	void change_sum(int id,int l,int r,int val){
		if(l<=t[id].l and t[id].r<=r){
			t[id].sum+=val*(t[id].r-t[id].l+1)%p;
			t[id].sum%=p;
			t[id].sum_lazy+=val;
			t[id].sum_lazy%=p;
			return;
		}
		pushdown(id);
		if(r<=t[tol].r) change_sum(tol,l,r,val);
		else if(l>=t[tor].l) change_sum(tor,l,r,val);
		else{
			change_sum(tol,l,t[tol].r,val);
			change_sum(tor,t[tor].l,r,val);
		}
		t[id].sum=(t[tol].sum+t[tor].sum)%p;
	}
	void change_mul(int id,int l,int r,int val){
		if(l<=t[id].l and t[id].r<=r){
			t[id].sum*=val%p;
			t[id].sum%=p;
			t[id].mul_lazy*=val%p;
			t[id].mul_lazy%=p;
			t[id].sum_lazy*=val%p;
			t[id].sum_lazy%=p; 
			return;
		}
		pushdown(id);
		if(r<=t[tol].r) change_mul(tol,l,r,val);
		else if(l>=t[tor].l) change_mul(tor,l,r,val);
		else{
			change_mul(tol,l,t[tol].r,val);
			change_mul(tor,t[tor].l,r,val);
		}
		t[id].sum=(t[tol].sum+t[tor].sum)%p;
	}
	int ask(int id,int l,int r){
		if(l<=t[id].l and t[id].r<=r){
			return t[id].sum;
		}
		pushdown(id);
		if(r<=t[tol].r) return ask(tol,l,r);
		else if(l>=t[tor].l) return ask(tor,l,r);
		else{
			return (ask(tol,l,t[tol].r)+
			ask(tor,t[tor].l,r))%p;
		}
	}
}
signed main(){
//	freopen("cth.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%d %d %d",&n,&q,&p);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	stree::build(1,1,n);
	while(q--){
		int op,x,y,k;scanf("%d %d %d",&op,&x,&y);
		if(op==1){
			scanf("%d",&k);
			stree::change_mul(1,x,y,k);
		}
		if(op==2){
			scanf("%d",&k);
			stree::change_sum(1,x,y,k);
		}
		if(op==3){
			printf("%d\n",stree::ask(1,x,y));
		}
	}
}
  • 线段树基本就 pushdown 或者 pushup 难写，写炸了大概率是细节丢掉，复盘一下，注意每个操作有没有考虑到全部变量的改变，线段树上大力分讨或者暴力合并有时候会拿到可观的分数
ST 表 
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100001];
int maxn[100001][18];
int base2[20];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
    base2[0]=1;
    for(int i=1;i<=19;++i) base2[i]=base2[i-1]*2;
    n=read();m=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        maxn[i][0]=a[i];
    }
    for(int i=1;i<=17;++i){
        for(int j=1;j<=n;++j){
            if(j+base2[i-1]-1>n) break;
            maxn[j][i]=max(maxn[j][i-1],maxn[j+base2[i-1]][i-1]);
        }
    }
    while(m--){
        int l,r;
        l=read();r=read();
        int tmp=log2(r-l+1);
        printf("%d\n",max(maxn[l][tmp],maxn[r-base2[tmp]+1][tmp]));
    }
}
  • ST 表适用于区间可重的运算，如 gcd 或 min max
  • Prim 算法和 dij 比起来，更新 dis 的时候不用带 dis[u]
  • Prim 可能在 \(m\) 远大于 \(n\) 的时候更好用，否则不如写 Kruskal
  • 二进制运算题的常见两种解决办法：拆位 / 01Trie
  • 数据结构题啥也想不出来了就想想分块
  • 神秘题啥也想不出来了就想想 DP
  • 有小于 \(30\) 的维度优先想状压
  • 判负环最好是 SPFA，因为有中途退出的可能，多测一定记得清空队列。以及最好判断入队次数而不是松弛次数，如果真的用松弛次数应该用形如 cnt[v]=cnt[u]+1 的写法而不是 cnt[v]++ 的写法
负环 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct edge{
	int to,w;
};
vector<edge>e[2001];
queue<int>q;
int dis[2001];
bool vis[2001];
int cnt[2001];
bool spfa(){
	while(!q.empty()) q.pop();
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(cnt,0,sizeof cnt);
	dis[1]=0;
	vis[1]=true;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=false;
		cnt[u]++;
		if(cnt[u]>n) return false;
		for(edge i:e[u]){
			if(dis[i.to]>dis[u]+i.w){
				dis[i.to]=dis[u]+i.w;
				if(!vis[i.to]){
					vis[i.to]=true;
					q.push(i.to);
				} 
			}
		}
	}
	return true;
}
signed main(){
	int t;scanf("%lld",&t);while(t--){
		scanf("%lld %lld",&n,&m);
		for(int i=1;i<=n;++i){
			e[i].clear();
		}
		for(int i=1;i<=m;++i){
			int x,y,z;scanf("%lld %lld %lld",&x,&y,&z);
			if(z>=0){
				e[x].push_back({y,z});
				e[y].push_back({x,z});
			}
			else e[x].push_back({y,z});
		}
		if(spfa()) cout<<"NO\n";
		else cout<<"YES\n";
	}
}
  • \(\frac{a}{b}\mod p=\frac{a\mod p}{b\mod p}\mod p\)
  • 关于差分约束：若 \(x-y\le c\)，则需要 \(x\) 至多比 \(y\) 大 \(c\)，因此从 \(y\) 向 \(x\) 连一条 \(c\) 的边，这样跑最短路出来的结果只会比 \(c\) 更小，其余的都可以通过转化形成形如 \(x-y\le c\) 的结果
  • 树的重心：\(O(n)\) 可求，可以通过钦定一个点是根节点，然后统计其所有子树中的最大大小和非子树所有节点的大小，将这个值用来更新答案
树的重心 
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>e[50001];
int size[50001],maxsize[50001];
vector<int>ans;
int sum=0x3f3f3f3f;
void dfs(int now,int last){
	size[now]=1;
	maxsize[now]=0;
	for(int i:e[now]){
		if(i!=last){
			dfs(i,now);
			size[now]+=size[i];
			maxsize[now]=max(maxsize[now],size[i]);
		}
	}
	maxsize[now]=max(maxsize[now],n-size[now]);
	if(maxsize[now]<sum){
		ans.clear();
		sum=maxsize[now];
		ans.push_back(now);
	}
	else if(maxsize[now]==sum){
		ans.push_back(now);
	}
}
int dfs2(int now,int last,int sum){
	int res=sum;
	for(int i:e[now]){
		if(i!=last){
			res+=dfs2(i,now,sum+1);
		}
	}
	return res;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n-1;++i){
		int x,y;scanf("%d %d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	int tmp=*minmax_element(ans.begin(),ans.end()).first;
	cout<<tmp<<' '<<dfs2(tmp,0,0);
	 
}
  • 树的直径：两边 dfs，第一遍任意钦定一个根节点，找出到这个点距离最大的点，再以这个点做一遍 dfs，距离最大值就是直径，找多条直径也是同理的
树的直径 
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>e[100001];
int dis[100001];
int maxdis1=0,maxdisid=0,maxdis2=0;
void dfs1(int now,int last,int sum){
	dis[now]=sum;
	if(dis[now]>maxdis1){
		maxdis1=dis[now];
		maxdisid=now;
	}
	for(int i:e[now]){
		if(i!=last){
			dfs1(i,now,sum+1);
		}
	}
}
void dfs2(int now,int last,int sum){
	dis[now]=sum;
	if(dis[now]>maxdis2){
		maxdis2=dis[now];
	}
	for(int i:e[now]){
		if(i!=last){
			dfs2(i,now,sum+1);
		}
	}
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n-1;++i){
		int x,y;scanf("%d %d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0,0);
	dfs2(maxdisid,0,0);
	cout<<maxdis2<<endl;
}
  • 缩点：最好把边存下来枚举旧边加新边，特别是有向图。缩点 tarjan 需要写栈，别忘了咋写
缩点 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[10001];
vector<int>e[10001];
vector<int>e2[10001];
int low[10001],dfn[10001],cnt;
int belong[10001],belongcnt[10001],tot;
bool vis[10001];
stack<int>st;
void tarjan(int now){
	low[now]=dfn[now]=++cnt;
	st.push(now);
	vis[now]=true;
	for(int i:e[now]){
		if(!dfn[i]){
			tarjan(i);
			low[now]=min(low[now],low[i]);
		}
		else if(vis[i]){
			low[now]=min(low[now],dfn[i]);
		}
	}
	if(low[now]==dfn[now]){
		int y;++tot;
		do{
			y=st.top();
			st.pop();
			vis[y]=false;
			belong[y]=tot;
			belongcnt[tot]+=a[y];
		}while(y!=now);
	}
}
int maxn[10001];
int indegree[10001];
int maxlen=0;
void topo(){
	queue<int>q;
	for(int i=1;i<=tot;++i){
		if(!indegree[i]){
			q.push(i);
			maxn[i]=belongcnt[i];
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		maxlen=max(maxlen,maxn[u]);
		for(int i:e2[u]){
			maxn[i]=max(maxn[i],maxn[u]+belongcnt[i]);
			maxlen=max(maxlen,maxn[i]);
			indegree[i]--;
			if(indegree[i]==0) q.push(i);
		}
	}
}
struct edge_{
	int from,to;
};
vector<edge_>v;
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i){
		int x,y;scanf("%lld %lld",&x,&y);
		e[x].push_back(y);
		v.push_back({x,y});
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(edge_ i:v){
		if(belong[i.from]!=belong[i.to]){
			e2[belong[i.from]].push_back(belong[i.to]);
			indegree[belong[i.to]]++;
		}
	}
	topo();
	cout<<maxlen;
}
线段树合并 
#include<bits/stdc++.h>
using namespace std;
int val_max=100000;
int n;
int a[100001],b[100001];
vector<int>e[100001];
int root[100001*32],rootcnt,nodecnt;
struct tree{
	int tol,tor;
	int sum;
}t[100000*32+1];
#define mid(l,r) mid=((l)+(r))/2
inline void update(int id){
	t[id].sum=t[t[id].tol].sum+t[t[id].tor].sum;
}
inline int newnode(){
	return ++nodecnt;
}
void change(int &id,int pos,int l=1,int r=val_max){
	if(!id) id=newnode();
	if(l==r){
		t[id].sum++;
		return;
	}
	int mid(l,r);
	if(pos<=mid) change(t[id].tol,pos,l,mid);
	else change(t[id].tor,pos,mid+1,r);
	update(id);
}
int ask(int id,int L,int R,int l=1,int r=val_max){
	if(L<=l and r<=R){
		return t[id].sum;
	}
	int mid(l,r);
	if(R<=mid) return ask(t[id].tol,L,R,l,mid);
	else if(L>=mid+1) return ask(t[id].tor,L,R,mid+1,r);
	return ask(t[id].tol,L,mid,l,mid)+ask(t[id].tor,mid+1,R,mid+1,r);
}
int merge(int x,int y,int l=1,int r=val_max){
	if(x==0) return y;
	if(y==0) return x;
	if(l==r){
		t[x].sum+=t[y].sum;
		return x;
	}
	int mid(l,r);
	t[x].tol=merge(t[x].tol,t[y].tol,l,mid);
	t[x].tor=merge(t[x].tor,t[y].tor,mid+1,r);
	update(x);
	return x;
}
int ans[100001];
int dfs(int now,int last){
	int mainroot=-1;
	for(int i:e[now]){
		if(i!=last){
			if(mainroot==-1) mainroot=dfs(i,now);
			else{
				int po=dfs(i,now);
				root[mainroot]=merge(root[mainroot],root[po]);
			}
		}
	}
	if(mainroot==-1){
		change(root[++rootcnt],a[now]);
		mainroot=rootcnt;
	}
	else{
		if(a[now]!=val_max) ans[now]=ask(root[mainroot],a[now]+1,val_max);
		change(root[mainroot],a[now]);
	}
	return mainroot;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	val_max=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(b+1,b+val_max+1,a[i])-b;
	}
	for(int i=2;i<=n;++i){
		int x;scanf("%d",&x);
		e[i].push_back(x);
		e[x].push_back(i);
	}
	dfs(1,0);
	for(int i=1;i<=n;++i){
		cout<<ans[i]<<'\n';
	}
}
KMP 
#include<bits/stdc++.h>
using namespace std;
string x,y;
int p[1000001];
int main(){
	cin>>x>>y;
	int lenx=(int)x.length()-1;
	int leny=(int)y.length()-1; 
	for(int i=1;i<=leny;++i){
		p[i]=p[i-1];
		while(y[p[i]]!=y[i] and p[i]!=0){
			p[i]=p[p[i]-1];
		}
		if(y[p[i]]==y[i]) p[i]++;
	}
	int j=0;
	for(int i=0;i<=lenx;++i){
		while(j!=0 and y[j]!=x[i]) j=p[j-1];
		if(y[j]==x[i]) j++;
		if(j==leny+1){
			cout<<i-leny+1<<'\n';
			j=p[j-1];
		}
	}
	for(int i=0;i<=leny;++i){
		cout<<p[i]<<' ';
	}
}

其他

  • long long
  • 开 long long 之前算一下空间，不富余就只开用开的（仔细点）
  • 最终确定之前先跑一边全部样例，确定通过应该通过的所有样例
  • 该拍就上拍子
  • 确定代码了就别乱动了，最后查的时候用个只读的编辑器打开，防止脑残
  • 最后一定要开虚拟机跑一遍，CCF 不受理因评测环境与考试环境不同导致的失分
  • 看到一句很好的话，考试是给你考试的，不是让你回忆人生经历并做出感叹的
  • 心态
  • 睡眠

提高组大纲

  • 普及组知识点只列了一部分在这里
  • 斜体并标星的不在考纲内

字符串

KMP 算法 ：P3375 【模板】KMP
字符串哈希：P3370 【模板】字符串哈希

搜索

记忆化搜索
启发式搜索（A*）：P2324 [SCOI2005] 骑士精神
双向搜索：P4799 [CEOI2015 Day2] 世界冰球锦标赛
迭代加深搜索：P1763 埃及分数

图论

最小生成树 ：P3366 【模板】最小生成树
次小生成树：P4180 [BJWC2010] 严格次小生成树
单源最短路
P3371 【模板】单源最短路径（弱化版）
P4779 【模板】单源最短路径（标准版）
单源次短路：P2865 [USACO06NOV] Roadblocks G
SPFA 判负环 ：P3385
Floyd 算法：B3647
拓扑排序：B3644 【模板】拓扑排序 / 家谱树
欧拉路：P7771 【模板】欧拉路径
二分图的判定
强联通分量 ：B3609 [图论与代数结构 701] 强连通分量 P3387
割点 ：P3388 【模板】割点（割顶）
树的重心 ：P1395 会议
树的直径 ：B4016 树的直径
最近公共祖先 ：P3379 【模板】最近公共祖先（LCA）
树上差分 ：P3128 [USACO15DEC] Max Flow P
分层图* ：P4568 [JLOI2011] 飞行路线
传递闭包* ：B3611 【模板】传递闭包
全源最短路（Johnson 算法）* ：P5905 【模板】全源最短路（Johnson）
缩点* ：P3387 【模板】缩点
边双联通分量* ：P8436 【模板】边双连通分量
点双联通分量* ：P8435 【模板】点双连通分量

动态规划

树形DP ：P1352 没有上司的舞会
状压DP ：P1896 [SCOI2005] 互不侵犯
数位DP*：P2602 [ZJOI2010] 数字计数
动态规划常见优化：
单调队列/单调栈优化
斜率优化
四边形不等式优化

数论

欧拉函数与欧拉定理
费马小定理
威尔逊定理
裴蜀定理：P4549 【模板】裴蜀定理
模运算意义下的乘法逆元
P3811 【模板】模意义下的乘法逆元
P5431 【模板】模意义下的乘法逆元 2
P2613 【模板】有理数取余
扩展欧几里得算法 ：P1082 [NOIP2012 提高组] 同余方程
中国剩余定理：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

组合数

P3807 【模板】卢卡斯定理/Lucas 定理
错位排列
鸽巢原理（抽屉原理）
容斥原理
卡特兰数：P1044 [NOIP2003 普及组] 栈

线性代数

矩阵快速幂：P3390
矩阵加速：P1962 斐波那契数列
高斯消元法：P3389

数据结构

单调栈 P5788 【模板】单调栈 | P1886 滑动窗口 /【模板】单调队列

线段树 P3373 【模板】线段树 2 | P5494 【模板】线段树分裂 | P3605 [USACO17JAN] Promotion Counting P

并查集 P2024 [NOI2001] 食物链 | P1196 [NOI2002] 银河英雄传说

其他

反悔贪心* ：P2949 [USACO09OPEN] Work Scheduling G
三分*
P3382 三分
P1883 【模板】三分 | 函数
扫描线* ：P5490 【模板】扫描线 & 矩形面积并

链

考场环境 NoiLinux 测试
树上背包问题
图论
DP
扫描线
数论与推论证明
KMP
二分图
pb_ds
莫比乌斯函数与莫比乌斯反演
模拟退火
二项式期望 DP

标签：复习,int,sum,tor,tol,now,id
From： https://www.cnblogs.com/HaneDaCafe/p/18493071

相关文章

  • MySQL 复习(一)：建表约束
    MySQL复习(一)：建表约束@目录MySQL复习(一)：建表约束1.主键约束1.1添加主键约束1.1.1建表前添加主键约束1.1.2建表后添加主键约束1.2删除主键约束2.外键约束2.1添加外键约束2.1.1建表前添加外键约束2.1.2建表后添加外键约束2.2删除外键约束3.自增约束3.1......
  • [复习] 数论基础
    [复习]数论基础模运算\[(a\pmb)\bmodp=((a\bmodp)\pm(b\bmodp))\bmodp\]\[(a\timesb)\bmodp=((a\bmodp)\times(b\bmodp))\bmodp\]积性函数\[\forall\gcd(x,y)=1,f(xy)=f(x)\timesf(y)\]完全积性函数\[\forallx,y\inN^+,f(xy)=f(x)\timesf(y)\]g......
  • 挑战中，Java面试题复习第5天，坚持就是胜利。
     ......
  • 模板复习计划
    进度模板SPFA（不带负环）FloydDijkstra拓扑排序-[已完成]单调栈单调队列Trie树KMP线性乘法逆元线性任意n个数乘法逆元-[已完成]线段树2带负环的SPFAexgcdTarjan找强连通分量差分约束康托展开网络......
  • 信息学奥赛复赛复习20-CSP-S2019-01格雷码-数据类型范围、unsigned 关键字、无符号范
    PDF文档回复:202410231P5657[CSP-S2019]格雷码[题目描述]通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00，01，10，11。格雷码（GrayCode）是一种特殊的nn位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地......
  • 信息学奥赛复赛复习20-CSP-S2019-01格雷码-数据类型范围、unsigned 关键字、无符号范
    PDF文档公众号回复关键字:202410231P5657[CSP-S2019]格雷码[题目描述]通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00，01，10，11。格雷码（GrayCode）是一种特殊的nn位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同......
  • 口语日常总结+复习+速记+应用
    学习目标：提升英语口语水平学习内容：英语口语总结练习例如：以下是100句日常交流口语：一、问候与介绍Hello!/你好！（最常见的打招呼用语）Hi!/嗨！（比较随意的打招呼）Goodmorning!/早上好！（上午问候）Goodafternoon!/下午好！（下午问候）Goodevening!/晚上好！（晚上问候）Niceto......
  • 挑战中，Java面试题复习第4天，坚持就是胜利。
    码城|第4期一分钟吃透Java面试题【悟空非空也】 ......
  • csp2024 复习计划
    啊啊啊啊啊啊啊啊啊啊啊啊啊啊先复习板子，再复习Trick和题目。1.数据结构平衡树笛卡尔树线段树、树状数组的各种Trick哈希的方法、题目2.杂算法CDQ分治、整体二分、点分治、点分树KMP可以做道大搜索练练手3.图论最小生成树、最短路建模相关......
  • 信息学奥赛复赛复习18-CSP-J2023-01小苹果-向上取整、向下取整、模拟算法
    PDF文档公众号回复关键字:202410211P9748[CSP-J2023]小苹果[题目描述]小Y的桌子上放着n个苹果从左到右排成一列，编号为从1到n。小苞是小Y的好朋友，每天她都会从中拿走一些苹果。每天在拿的时候，小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99