hysbz_trm

UID: 46085, 注册于 2024-2-20 17:11:34, 最后登录于 2025-9-19 15:56:51, 最后活动于 2025-9-19 15:56:51.

解决了 83 道题目，RP: 208.29 (No. 22)

♂

个人简介

代码模板

临时文件

  #include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(long long i=a;i<=b;i++)
#define pep(i,a,b) for(long long i=a;i>=b;i--)
using namespace std;
long long maxx(long long x,long long y)
{
	return x>y?x:y;
}
long long minn(long long x,long long y)
{
	return x<y?x:y;
}
pair<long long,long long> mapp(long long x,long long y)
{
	return (pair<long long,long long>) {x,y};
}
long long n;
long long op;
long long k;
long long addr_;
string s;
string ti;
string ni;
string c_in1[300];
string c_in2[300];
struct type_kind
{
	string name;
	vector<type_kind*> son_type;
	vector<string> son_name;
	long long memo_size;
	long long memo_align;
	void clear()
	{
		name.clear();
		son_type.clear();
		son_name.clear();
		memo_align=memo_size=0;
	}
};
type_kind y_n_type[300];
long long type_num;
map<string,type_kind*> name_to_type;
struct element
{
	type_kind element_type;
	string name;
	long long address;
	void clear()
	{
		element_type.clear();
		name.clear();
		address=0;
	}
};
element y_n_elem[300];
long long ele_num;
map<string,element*> name_to_ele;
long long addr_pos;
map<pair<long long,long long>,element*> addr_to_ele;
void int_struct(string type_name,long long num,string *ar1,string *ar2)//操作1,定义结构体
{
	type_kind new_type;
	new_type.clear();
	new_type.name=type_name;
	rep(i,1,num)
	{
		new_type.son_type.push_back(name_to_type[ar1[i]]);
		new_type.son_name.push_back(ar2[i]);
	}
	long long pos=0;
	vector<type_kind*>::iterator it=new_type.son_type.begin();
	for(;it!=new_type.son_type.end();it++)
	{
		long long align=(*it)->memo_align;
		long long size=(*it)->memo_size;
		new_type.memo_align=max(new_type.memo_align,align);
		if(pos%align)
		{
			pos=(pos/align+1)*align;
		}
		pos+=size;
	}
	if(pos%new_type.memo_align)
	{
		pos=(pos/new_type.memo_align+1)*new_type.memo_align;
	}
	new_type.memo_size=pos;
	y_n_type[++type_num]=new_type;
	name_to_type[type_name]=&y_n_type[type_num];
}
void int_element(string type_name,string ele_name)//操作2，定义元素
{
	element new_ele;
	new_ele.clear();
	long long align=name_to_type[type_name]->memo_align;
	long long size=name_to_type[type_name]->memo_size;
	if(addr_pos%align)
	{
		addr_pos=((addr_pos/align+1)*align);
	}
	new_ele.address=addr_pos;
	new_ele.element_type=*name_to_type[type_name];
	new_ele.name=ele_name;
	y_n_elem[++ele_num]=new_ele;
	name_to_ele[ele_name]=&y_n_elem[ele_num];
	addr_to_ele[mapp(addr_pos,addr_pos+size-1)]=&y_n_elem[ele_num];
	addr_pos+=size;
}
long long ask_element(string ele_name)//操作3，访问元素
{
	queue<string> name;
	string tool;
	tool.clear();
	rep(i,0,(long long)ele_name.length()-1)
	{
		if(ele_name[i]=='.')
		{
			name.push(tool);
			tool.clear();
		}
		else
		{
			tool+=ele_name[i];
		}
	}
	name.push(tool);
	long long pos=name_to_ele[name.front()]->address;
	type_kind type=name_to_ele[name.front()]->element_type;
	name.pop();
	while(!name.empty())
	{
		string Name=name.front();
		name.pop();
		vector<string>::iterator it1=type.son_name.begin();
		vector<type_kind*>::iterator it2=type.son_type.begin();
		for(;it1!=type.son_name.end();it1++,it2++)
		{
			if(pos%(*it2)->memo_align)
			{
				pos=(pos/(*it2)->memo_align+1)*(*it2)->memo_align;
			}
			if(*it1==Name)
			{
				type=**it2;
				break;
			}
			else
			{
				pos+=(*it2)->memo_size;
			}
		}
	}
	return pos;
}
string ask_addr(long long addr)//操作4，访问地址
{
	if(addr>=addr_pos)
	{
		return "ERR";
	}
	element ele;
	map<pair<long long,long long>,element*>::iterator it=addr_to_ele.begin();
	for(;it!=addr_to_ele.end();it++)
	{
		if(addr<(*it).first.first or addr>(*it).first.second)
		{
			continue;
		}
		ele=*((*it).second);
		break;
	}
	long long pos_goal=addr-ele.address;
	long long pos_s=0;
	long long pos_t;
	type_kind type=ele.element_type;
	string ele_name;
	ele_name.clear();
	ele_name+=ele.name;
	while(!type.son_name.empty())
	{
		vector<type_kind*>::iterator it1=type.son_type.begin();
		vector<string>::iterator it2=type.son_name.begin();
		for(;it1!=type.son_type.end();it1++,it2++)
		{
			pos_t=pos_s+(*it1)->memo_size;
			if(pos_goal<pos_t&&pos_goal>=pos_s)
			{
				ele_name+='.'+*it2;
				type=**it1;
				break;
			}
			else
			{
				if(it1+1==type.son_type.end())
				{
					return "ERR";
				}
				long long align=(*(it1+1))->memo_align;
				if(pos_t%align)
				{
					pos_t=(pos_t/align+1)*align;
				}
				if(pos_goal<pos_t)
				{
					return "ERR";
				}
				pos_s=pos_t;
			}
		}
	}
	if(ele_name=="")
	{
		return "ERR";
	}
	return ele_name;
}
int main()
{
	y_n_type[1].name="byte";
	y_n_type[2].name="short";
	y_n_type[3].name="int";
	y_n_type[4].name="long";
	y_n_type[1].memo_align=y_n_type[1].memo_size=1;
	y_n_type[2].memo_align=y_n_type[2].memo_size=2;
	y_n_type[3].memo_align=y_n_type[3].memo_size=4;
	y_n_type[4].memo_align=y_n_type[4].memo_size=8;
	name_to_type["byte"]=&y_n_type[1];
	name_to_type["short"]=&y_n_type[2];
	name_to_type["int"]=&y_n_type[3];
	name_to_type["long"]=&y_n_type[4];
	type_num=4;
	cin>>n;
	while(n--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>s>>k;
			rep(i,1,k) cin>>c_in1[i]>>c_in2[i];
			int_struct(s,k,c_in1,c_in2);
			cout<<y_n_type[type_num].memo_size<<" "<<y_n_type[type_num].memo_align<<endl;
		}
		else if(op==2)
		{
			cin>>ti>>ni;
			int_element(ti,ni);
			cout<<y_n_elem[ele_num].address<<endl;
		}
		else if(op==3)
		{
			cin>>s;
			cout<<ask_element(s)<<endl;
		}
		else if(op==4)
		{
			cin>>addr_;
			cout<<ask_addr(addr_)<<endl;
		}
	}
	return 0;
}

三分模板（[ABC279D] Freefall）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const double M=1e-10;
int T,n;
double a,b,ans;
double f(double x){
	return b*(x-1.0)+a/sqrt(x);
}
signed main(){
		cin>>a>>b;
		int l=0,r=1e18;
		while(r-l>2){
			int len=(r-l)/3;
			int midl=l+len;
			int midr=r-len;
			if(f(midl)>f(midr)) l=midl;
			else r=midr;
		}
	ans=min(f(l),min(f(r),f(l+1)));
printf("%.10lf",ans);
	return 0;
}

小秦种树(线段树)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4*2e5+50;
int n,m,p[N],mx[N],mn[N],amx=-1e9,amn=1e9,sum[N],ans=0,xg[N];
void build(int id,int l,int r){
	if(l==r){
		sum[id]=p[l];
		if(sum[id]<=1)
			xg[id]=1;
		else
			xg[id]=0;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	xg[id]=xg[id*2]&xg[id*2+1];
	sum[id]=sum[id*2]+sum[id*2+1];
	return;
}
void find(int id,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		ans+=sum[id];
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x)
		find(id*2,l,mid,x,y);
	if(mid<y)
		find(id*2+1,mid+1,r,x,y);
	return;
}
void change(int id,int l,int r,int fl,int fr){
	if(xg[id]==1)
		return;
	if(l==r){
		sum[id]=sqrt(sum[id]);
		if(sum[id]<=1)
			xg[id]=1;
		else
			xg[id]=0;
		return;
	}
	int mid=(l+r)/2;
	if(mid>=fl)
		change(id*2,l,mid,fl,fr);
	if(mid<fr)
		change(id*2+1,mid+1,r,fl,fr);
		xg[id]=xg[id*2]&xg[id*2+1];
	sum[id]=sum[id*2]+sum[id*2+1];
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i];
	build(1,1,n);
	cin>>m;
	while(m--){
		int k,a,b;
		cin>>k>>a>>b;
		if(k==1){
			ans=0;
			find(1,1,n,a,b);
			cout<<ans<<"\n";
		}else{
				change(1,1,n,a,b);
		}
	}
	return 0;
}

线段树单点修改区间查询

#include <bits/stdc++.h>
using namespace std;
const int N=4*1e5+50;
int n,m,p[N],mx[N],mn[N],amx=-1e9,amn=1e9,sum[N],ans=0;
void build(int id,int l,int r){
	if(l==r){
		sum[id]=p[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	sum[id]=sum[id*2]+sum[id*2+1];
	return;
}
void find(int id,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		ans+=sum[id];
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x)
		find(id*2,l,mid,x,y);
	if(mid<y)
		find(id*2+1,mid+1,r,x,y);
	return;
}
void change(int id,int l,int r,int pos,int v){
	if(l==r){
		sum[id]+=v;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid)
		change(id*2,l,mid,pos,v);
	else
		change(id*2+1,mid+1,r,pos,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
signed main(){
	cin>>n>>m;
	while(m--){
		int k,a,b;
		cin>>k>>a>>b;
		if(k==0){
			change(1,1,n,a,b);
		}else{
			ans=0;
			find(1,1,n,a,b);
			cout<<ans<<"\n";
		}
	}
	return 0;
}

跳石头(二分答案)

#include <bits/stdc++.h>
#define int long long
using namespace std;
int q,n,m,a[50050],l=1,r=1e9,mid,ans;
bool check(int x){
	int sum=0,last=0;
	for(int i=1;i<=n+1;i++)
		if(a[i]-last<x) sum++;
		else last=a[i];
		return sum<=m;
}
signed main(){
	cin>>q>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	a[n+1]=q;
	r=q;
	while(l<=r){
		mid=l+(r-l)/2;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}else r=mid-1;
	}
	cout<<ans;
	return 0;
}

分解质因数

#include <bits/stdc++.h>
using namespace std;
int n;
signed main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		while(n%i==0){
			cout<<i<<"\n";
			n/=i;
		}
	}
	return 0;
}

代码优化

输入输出流关闭

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

编译设置

-std=c++11 -O2 -Wl,--stack=123456789

对拍

@echo off		
:ss			
Random.exe						
My.exe			
Std.exe		
fc  My.out Std.out		
if not errorlevel 1 goto ss 
pause

#include<bits/stdc++.h> 
using namespace std;
signed main()
{
	srand(time(0)); 
	exit(0);
}

最小生成树(Prim)

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,w[N][N],d[N],bs;
bool vis[N];
void prim(){
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	for(int i=1;i<=n;i++){
		int k=0;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&d[j]<d[k])
				k=j;
		vis[k]=1;
		for(int j=1;j<=n;j++){
			if(vis[j]==0&&w[k][j]<d[j]){
				d[j]=w[k][j];
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	memset(w,0x3f,sizeof(w));
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(w[x][y]>z)w[x][y]=w[y][x]=z;
	}
	prim();
	int ans=0,flag=1;
	for(int i=1;i<=n;i++){
		if(d[i]==0x3f3f3f3f)
			flag=0;
		ans+=d[i];
	}
	if(flag==1)cout<<ans;
	else cout<<"orz";
	return 0;
}

ycz的离散化(离散化模板）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000050;
int n,k,a[N],p;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	p=a[k];
	sort(a+1,a+n+1);
	int m=unique(a+1,a+n+1)-a;
	cout<<lower_bound(a+1,a+m+1,p)-a;
	return 0;
}

树状数组求逆序对

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5100000;
int n,m,b[N],ans,c[N],id[N];
struct node{
	int b,id;
}a[N];
int lowbit(int x){
	return x&(-x);
}
long long sum(int x){
	long long res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=c[i];
	return res;
}
void add(int x,int y){
	for(int i=x;i<=1e7;i+=lowbit(i))
		c[i]+=y;
}
bool cmp(node a,node b){
	if(a.b!=b.b) return a.b>b.b;
	else return a.id>b.id;
}
signed main(){
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
		cin>>a[i].b,a[i].id=i;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		ans+=sum(a[i].id);
		add(a[i].id,1);
	}
	cout<<ans;
	return 0;
}

并查集

#include <bits/stdc++.h>
#define MAXN 5010
int n,m,p,x,y,fa[MAXN];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void join(int c1,int c2){
	int f1=find(c1),f2=find(c2);
	if(f1!=f2) fa[f1]=f2;
}
using namespace std;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		join(x,y);
	}
	cin>>p;
	for(int i=0;i<p;i++){
		cin>>x>>y;
		if(find(x)==find(y)) cout<<"Yes"<<"\n";
		else cout<<"No"<<"\n";
	}
	return 0;
}

01背包

#include <bits/stdc++.h>
using namespace std;
const int N=305,M=20050;
int v,n,a[N],f[M],ans,b[N];
signed main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	f[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=v;j>=a[i];j--){
		f[j]=max(f[j],f[j-a[i]]+b[i]);	
	}
	for(int i=0;i<=v;i++)
		ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}

完全背包

#include <bits/stdc++.h>
using namespace std;
const int N=305,M=20050;
int v,n,a[N],f[M],ans,b[N];
signed main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	f[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=a[i];j<=v;j++){
		f[j]=max(f[j],f[j-a[i]]+b[i]);	
	}
	for(int i=0;i<=v;i++)
		ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}

多重背包(二进制拆分）

#include <bits/stdc++.h>
using namespace std;
const int N=3500,M=200500;
int v,n,a[N],f[M],ans,s[N],c,k[N];
signed main(){
	cin>>n>>v;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<=n;i++){
		int o=s[i],t=1;
		while(o>=t){
			k[++c]=t*a[i];
			o-=t;
			t*=2;
		}
		k[++c]=a[i]*o;
	}
	f[0]=1;
	for(int i=1;i<=c;i++)
		for(int j=v;j>=0;j--)
			if(f[j]==1){
		f[j]=1;
		if(k[i]+j<=v){
			f[k[i]+j]=1;
			
		}				
	}
	for(int i=1;i<=v;i++)
		if(f[i])
			ans++;
	cout<<ans;
	return 0;
}

石子合并之二(合并类Dp)(断环成链）

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,a[N],sum[N],f[N][N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],a[i+n]=a[i];
	for(int i=1;i<=2*n;i++)
		sum[i]=sum[i-1]+a[i],f[i][i]=0;
	for(int len=2;len<=2*n;len++){
		for(int i=1;i<=2*n-len+1;i++){
			int j=i+len-1;
			f[i][j]=0x3f3f3f3f;
			for(int mid=i;mid<=j-1;mid++){
				f[i][j]=min(f[i][j],f[i][mid]+f[mid+1][j]+sum[j]-sum[i-1]);
			}
		}
	}
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
		ans=min(ans,f[i][i+n-1]);
	cout<<ans;
	return 0;
}

石子合并(合并类Dp)

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int n,a[N],sum[N],f[N][N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],sum[i]=sum[i-1]+a[i],f[i][i]=0;
	for(int i=1;i<=n-1;i++)
		f[i][i+1]=a[i]+a[i+1];
	for(int len=3;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			f[i][j]=0x3f3f3f3f;
			for(int mid=i;mid<=j-1;mid++){
				f[i][j]=min(f[i][j],f[i][mid]+f[mid+1][j]+sum[j]-sum[i-1]);
			}
		}
	}
	cout<<f[1][n]<<"\n";
	return 0;
}

数字三角形

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,f[N][N],a[N][N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		f[i][1]=a[i][1]+f[i-1][1];
	for(int i=2;i<=n;i++)
		for(int j=2;j<=i;j++){
		f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
		//		else if(i-1>=1)f[i][j]=f[i-1][j]+a[i][j];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,f[n][i]);
	cout<<ans;
	return 0;
}

最长上升子序列(加强版）

#include <bits/stdc++.h>
using namespace std;
const int N=40005;
int n,a[N],f[N],ans,T;
signed main(){
	cin>>T;
	while(T--){
		ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=0;
	}
	for(int i=1;i<=n;i++){
		if(i==1){
			++ans;
			f[ans]=a[i];
		}else if(a[i]>f[ans]){
			++ans;
			f[ans]=a[i];
		}else{
			int s=a[i];
			int g=lower_bound(f+1,f+ans+1,s)-f;
			f[g]=a[i];
		}
	}
	cout<<ans<<"\n";
	}
	return 0;
}

最长上升子序列

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N],f[N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i])
				f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	cout<<ans<<"\n";
	return 0;
}

售货员的难题(状压DP)

#include <bits/stdc++.h>
using namespace std;
const int N=25;
int n,d[N][N];
int f[N][400005];
signed main(){
	cin>>n;
	memset(f,63,sizeof(f));
	f[1][1]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>d[i][j];
	for(int i=0;i<=(1<<n);i++){
		for(int j=1;j<=n;j++){
			if((i&(1<<j-1))==0){
				for(int k=1;k<=n;k++){
					if(i&(1<<k-1)){
						f[j][(1<<j-1)|i]=min(f[j][(1<<j-1)|i],f[k][i]+d[k][j]);
					}
				}
			}
		}
	}
	int ans=INT_MAX;
	for(int i=2;i<=n;i++)
		ans=min(ans,f[i][(1<<n)-1]+d[i][1]);
	cout<<ans<<"\n";
	return 0;
}

最短路(Floyd)

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,t,m,u[N],o;
int w[N][N],ans=INT_MAX,d[N];
void f(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
			w[i][j]=min(w[i][j],max(w[i][k],w[k][j]));
	}
}
signed main(){
	int T;
	cin>>n>>m>>T;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			w[i][j]=1e9;
	for(int i=1;i<=n;i++) w[i][i]=0;
	for(int i=1;i<=m;i++){
		int x,y,l;
		cin>>x>>y>>l;
		w[x][y]=l;
//		w[y][x]=l;
	}
	f();
	while(T--){
		int s,t;
		cin>>s>>t;
		if(w[s][t]!=1e9)cout<<w[s][t]<<"\n";
		else cout<<-1<<"\n";
	}
	return 0;
}

扩展欧几里得

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,x,y,gcd,c;
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=c/a,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int tx=x;
	x=y;
	y=tx-(a/b)*y;
	return d;
}
signed main(){
	cin>>a>>b>>c;
	int gcd=exgcd(a,b,x,y);
	x=(x%b+b)%b;
	b=b/gcd;
	cout<<x<<"\n";
	for(int i=1;i<gcd;i++)
		cout<<x+i*b<<"\n";
	return 0;
}

乘法逆元

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,p,inv[3000050],mod=1e9+7,a,b;
int c(int a,int b){
	int ans=1;
	for(int i=1;i<=b;i++)
		ans=ans*(a-b+i)%mod*inv[i]%mod;
	return ans;
}
int fpow(int ds,int zs,int modsss){
	int sumsumsum=1;
	while(zs){
		if(zs&1)sumsumsum = (sumsumsum*ds)%modsss;
		ds = (ds*ds)%modsss;
		zs>>=1;
	}
	return sumsumsum;
}
signed main(){
	cin>>n>>a>>b;
	inv[1]=1;
	p=mod;
	for(int i=2;i<=max(a,b);i++)
		inv[i]=(p-p/i)*inv[p%i]%p;
	cout<<(fpow(2,n,mod)-c(n,a)-c(n,b)+3*mod-1)%mod;
	return 0;
}

树状数组 3 ：区间修改，区间查询

#include <bits/stdc++.h>
#define int long long
using namespace std;
long long c[2][100005];
int a[100005],n,m;
int lowbit(int x){
	return x&(-x);
}
long long sum(int x,int op){
	long long res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=c[op][i];
	return res;
}
void add(int x,int y,int op){
	for(int i=x;i<=n;i+=lowbit(i))
		c[op][i]+=y;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		add(i,a[i],0);
		add(i+1,-a[i],0);
		add(i,1ll*(n-i+1)*a[i],1);
		add(i+1,-1ll*(n-i)*a[i],1);
	}
	while(m--){
		int x,y,d;
		char op;
		cin>>op;
		scanf("%lld%lld",&x,&y);
		if(op=='C'){
			scanf("%lld",&d);
			add(x,d,0);
			add(y+1,-d,0);
			add(x,(n-x+1)*d,1);
			add(y+1,-(n-y)*d,1);
		}else{
			long long ans=sum(y,1)-1ll*(n-y)*sum(y,0);
			ans-=sum(x-1,1)-1ll*(n-x+1)*sum(x-1,0);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

树状数组 2 ：区间修改，单点查询

#include <bits/stdc++.h>
using namespace std;
const int N=5100000;
int n,m,a[N],b[N];
long long c[N];
int lowbit(int x){
	return x&(-x);
}
long long sum(int x){
	long long res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=c[i];
	return res;
}
void add(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=y;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i]-a[i-1];
		add(i,b[i]);
	}
	while(m--){
		int op,x,y,k;
		scanf("%d",&op);
		if(op==1){ 
			scanf("%d%d%d",&x,&y,&k);
			add(x,k);
			add(y+1,-k);
		}
		else{ 
			scanf("%d",&x);
			printf("%lld\n",sum(x));
		}
	}
	return 0;
}

树状数组 1 ：单点修改，区间查询

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5100000;
int n,m,a[N],c[N];
int lowbit(int x){
	return x&(-x);
}
int sum(int x){
	long res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=c[i];
	return res;
}
void add(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=y;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		add(i,a[i]);
	}
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1) add(x,y);
		else printf("%lld\n",sum(y)-sum(x-1));
	}
	return 0;
}

RMQ

#include<bits/stdc++.h>
using namespace std;
int n,q;
int s[20],mx[50050][20],mn[50050][20];
void pre(){
	int x=log2(n);
	for(int i=1;i<=x;i++)
		for(int j=1;j+s[i]-1<=n;j++){
			mx[j][i]=max(mx[j][i-1],mx[j+s[i-1]][i-1]);
			mn[j][i]=min(mn[j][i-1],mn[j+s[i-1]][i-1]);
		}
}
int rmq(int a,int b){
	int x=log2(b-a+1);
	int t1=max(mx[a][x],mx[b-s[x]+1][x]);
	int t2=min(mn[a][x],mn[b-s[x]+1][x]);
	return t1-t2;
}
signed main(){
	cin>>n>>q;
	s[0]=1;
	for(int i=1;i<=15;i++)
		s[i]=s[i-1]*2;
	for(int i=1;i<=n;i++){
		cin>>mx[i][0];
		mn[i][0]=mx[i][0];
	}
	pre();
	while(q--){
		int x,y;
		cin>>x>>y;
		cout<<rmq(x,y)<<"\n";
	}
	return 0;
}

最近公共祖先(LCA)

#include <bits/stdc++.h>
using namespace std;
const int N=1000050;
int n,q,d[N],f[N][105],s[105];
vector<int> v[N];
void dfs(int x,int fa,int dep){
	d[x]=dep;
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(y==fa) continue;
		f[y][0]=x;
		dfs(y,x,dep+1);
	}
}
int lca(int x,int y){
	if(d[y]<d[x]) swap(x,y);
	int k=log2(d[y])+1;
	for(int i=k;i>=0;i--)
		if(d[y]-s[i]>=d[x])
			y=f[y][i];
	if(x==y) return x;
	for(int i=k;i>=0;i--)
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
void pre(){
	for(int j=1;s[j]<=n;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
}
signed main(){
	scanf("%d%d",&n,&q);
	s[0]=1;
	for(int i=1;i<=20;i++)
		s[i]=s[i-1]*2;
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0,1);
	pre();
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

树的重心

#include <bits/stdc++.h>
using namespace std;
const int N=20050;
int n,f[N],g[N],h;
vector<int> v[N];
bool vis[N];
void dfs(int x){
	vis[x]=1;
	f[x]=1;
	g[x]=0;
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(vis[y]) continue;
		dfs(y);
		f[x]+=f[y];
		g[x]=max(g[x],f[y]);
	}
	g[x]=max(g[x],n-f[x]);
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
		ans=min(ans,g[i]);
	for(int i=1;i<=n;i++)
		if(g[i]==ans)
			h=1,cout<<i<<"\n";
	if(h==0)
		cout<<"NONE"<<"\n";
	return 0;
}

树的直径

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
int n,s,ans,zz,res;
struct node{
	int v,w;
};
vector<node> v[N];
void dfs(int x,int fa,int sum){
	if(sum>ans)
		ans=sum,zz=x;
	for(int i=0;i<v[x].size();i++){
		node y=v[x][i];
		if(y.v==fa) continue;
		dfs(y.v,x,sum+y.w);
	}
}
signed main(){
	cin>>n>>s;
	for(int i=1;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		v[x].push_back({y,w});
		v[y].push_back({x,w});
		res+=w;
	}
	dfs(s,0,0);
	ans=0;
	dfs(zz,0,0);
	cout<<2*res-ans;
	return 0;
}

最小生成树(Kruskal)

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
int n,m,c[N],fa[N],ans,sw=INT_MAX;
struct node{
	int x,y,w;
}a[N];
bool cmp(node a,node b){
	return a.w<b.w;
}
int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
void add(int x,int y){
	int p=find(x),q=find(y);
	if(p!=q)
		fa[p]=q;
}
void kru(){
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		int p=find(a[i].x),q=find(a[i].y);
		if(p!=q){
			ans+=a[i].w;
			add(a[i].x,a[i].y);
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>c[i],sw=min(sw,c[i]);
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].w;
		a[i].w=a[i].w*2+c[a[i].x]+c[a[i].y];
	}
	kru();
	cout<<ans+sw<<"\n";
	return 0;
}

快速幂


int ksm(int a,int b,int c){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%c;
		b>>=1,a=a*a%c;
	}
	return ans;
}

线性筛

void init(int n){
	memset(v,0,sizeof(v));
	int tot=0;
	for(int i=2;i<=n;i++){
		if(!v[i]){
			p[++tot]=i;
		}
		for(int k=1;k<=tot;k++){
			if(i*p[k]>n)
				break;
			v[i*p[k]]=1;
			if(i%p[k]==0)
				break;
		}
	}
}

最短路(Dijkstra)


#include <bits/stdc++.h>
using namespace std;
const int N=400050;
struct node{
	int v,w;
};
vector<node> v[N];
bool operator<(node a,node b){
	return a.w>b.w;
}
priority_queue<node> q;
int n,m,s,dis[N];
bool vis[N];
void dij(int s){
	for(int i=0;i<=n;i++)
		dis[i]=INT_MAX;
	dis[s]=0;
	q.push({s,0});
	while(!q.empty()){
		node x=q.top();
		q.pop();
		if(vis[x.v]) continue;
		vis[x.v]=1;
		for(int i=0;i<v[x.v].size();i++){
			node y=v[x.v][i];
			if((long long)dis[x.v]+y.w<dis[y.v]){
				dis[y.v]=dis[x.v]+y.w;
				q.push({y.v,dis[y.v]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		v[x].push_back({y,w});
	}
	dij(s);
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
	return 0;
}

拓扑排序

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,in[N],ans[N],tot;
vector<int> v[N];
queue<int> q;
void topsort(){
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			ans[++tot]=i;
			q.push(i);
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i];
			in[y]--;
			if(in[y]==0){
				ans[++tot]=y;
				q.push(y);
			}
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int y;
		while(cin>>y){
			if(y==0) break;
			v[i].push_back(y);
			in[y]++;
		}
	}
	topsort();
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}

快读快写

#include<bits/stdc++.h>
#define INPUT long long
using namespace std;
const int INPUT_Len = 50;
inline INPUT Read(){char n;INPUT Re,f=1;while((n=getchar())<'0'||n>'9'){if(n==EOF)exit(0);if(n=='-')f=-1;}Re=n-48;while((n=getchar())>='0'&&n<='9')Re=Re*10+(n-48);return Re*f;}
inline void Write(INPUT x, char End = '\n'){if(x==0){putchar('0');putchar(End);return;}else if (x < 0)putchar('-'),x=-x;char Prime[INPUT_Len];INPUT Ind=0;while(x){Prime[++Ind]=(char)(x%10+48);x /= 10;}for(int i=Ind;i>=1;i--)putchar(Prime[i]);putchar(End);}
signed main(){
	return 0;
}

优化大礼包

再加上优化大礼包

#include<bits/stdc++.h>
#pragma GCC optimize(2) 
// 如果CE，把第四行删了
#pragma GCC optimize(3) 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline") 
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow") 
#pragma GCC optimize("-falign-functions") 
#pragma GCC optimize("-fcse-skip-blocks") 
#pragma GCC optimize("-fcse-follow-jumps") 
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining") 
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define INPUT long long
using namespace std;
const int INPUT_Len = 50;
inline INPUT Read(){char n;INPUT Re,f=1;while((n=getchar())<'0'||n>'9'){if(n==EOF)exit(0);if(n=='-')f=-1;}Re=n-48;while((n=getchar())>='0'&&n<='9')Re=Re*10+(n-48);return Re*f;}
inline void Write(INPUT x, char End = '\n'){if(x==0){putchar('0');putchar(End);return;}else if (x < 0)putchar('-'),x=-x;char Prime[INPUT_Len];INPUT Ind=0;while(x){Prime[++Ind]=(char)(x%10+48);x /= 10;}for(int i=Ind;i>=1;i--)putchar(Prime[i]);putchar(End);}
signed main(){
	return 0;
}

周氏机配方:启发式权值线段树莫队RMQ迭代加深后缀自动机网络流阿朵莉树莫比乌斯反演吉司机树合并迭代加深搜索Dil定理BMS笛卡尔树拉格朗日反演二项式定理康IOI托展开优化插头DP优化版本

通过的题目
P1010

P1047

P1059

P1066

P1070

P1096

P1135

P1221

P1280

P1355

P1511

P1531

P1565

P1693

P1711

P1735

P1855

P2084

P2127

P2245
P2424

P2442

P2561

P2673

P3620

P2726

P2756

P3156

P3437

P3504

P3670

P3894

P3916

P3931

P3940

P3942

P4974

P5610

P5614

P5615
P5618

P5624

P5625

P5626

P5636

P5637

P5638

P5639

P5640

P5641

P5642

P5645

P5649

P5659

P6072

P6073

P9288

P9401

P8121

P9400
P6450

P6454

P6457

P6462

P6466

P10836

P10843

P10844

P10906

y0004

y0009

y0005

P11165

P11167

y0006

P11169

y1019

y1023
最近活动

图论: 26
字符串: 21
动态规划: 17
KMP: 15
字符串哈希: 11
斜率优化: 9
最大流: 7
网络流: 7
单调队列/单调栈优化: 6
费用流: 5
最小割: 4
算法基础: 4
二分: 4
二分图最大匹配: 3
最小费用最大流: 3
二分图最小点覆盖: 3
数据结构: 2
hall定理: 2
闭合子图问题: 2
扩展KMP: 2

hysbz_trm

个人简介

代码模板

再加上优化大礼包

通过的题目

最近活动

题目标签

状态

开发

支持