a^b & 增加模数

模版

#include<bits/stdc++.h>
using namespace std;

long long q(int a,int k,int p) {
	long long cn=1;
	while(k){
		if (k&1)cn=cn*a%p;  
		k>>=1;  
		a=(long long)a*a%p;  
	}
	return cn;
}

int main() {
	int a,k,p;
	cin>>a>>k>>p;
	cin>>a>>k>>p;
	if(a==0){
		cout<<0;
		return 0;
	}
	if(k==0)
	{	
		if(p==1)cout<<0;
		else cout<<1;
		return 0;
	}	cout<<q(a,k,p)<<'\n';
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

long long q(int a,int k,int p) {
	long long cn=1;
	while(k){
		if (k&1)cn=cn*a%p;  
		k>>=1;  
		a=(long long)a*a%p;  
	}
	return cn%p;
}

int main() {
	int t;
	cin>>t;
	while(t--){
		int p,n;
		cin>>p>>n;
		int s=0;
		for(int i=1;i<=n;i++){
			int x,y;
			cin>>x>>y;
			s=(s+q(x,y,p))%p;
		}
		cout<<s<<"\n";
	}
	return 0;
}

64位整数乘法

龟速乘

将a看成二进制数，再按快速幂的思想去做

#include<bits/stdc++.h>
#define int long long
using namespace std;

long long q(int a,int k,int p) {
	long long cn=0;
	while(k){
		if(k&1)cn=(cn+a)%p;  
		k>>=1;  
		a=(long long)(a+a)%p;  
	}
	return cn%p;
}

signed main() {
	int a,b,p;
	cin>>a>>b>>p;
	cout<<q(a,b,p);
	return 0;
}

起床困难综合症

now每经过一扇门，都会改变答案的每一位，所以我没可以枚举每一位，贪心最优答案，要满足以下条件

1. now+(1<<i)<m
2. 取一效果好于取零

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
pair<string,int>p[100010];
int c(int k,int x){
	for(int i=1;i<=n;i++){
		int t=p[i].second>>k&1;
		if(p[i].first=="OR")x=x|t;
		if(p[i].first=="XOR")x=x^t;
		if(p[i].first=="AND")x=x&t;
	}
	return x;
}
signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second;
	int an=0,na=0;
	for(int i=29;i>=0;i--){
		int t0=c(i,0);
		int t1=c(i,1);
		if(na+(1<<i)<=m&&t1>t0){
			an+=(1<<i);
			na+=(1<<i);
		}
		else an+=(t0<<i);
	}
	cout<<an;
	return 0;
}

最短Hamilton路径

如果有一条线路从 i到 j的最短路径，会由两部分组成，这条路上的点集，以及最终 停下的位置。 通过这个，我们可以写出状态表示和状态计算：

1. 状态表示$f_{i,j}$ ，点集状态为 i，此时达到点 j的所有状态

2. 属性：最小值

   状态计算： $f_{i,j}=min(f_{i^{1<<j},k}+w_{k,j})$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1<<20][20],w[20][20],n;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];
	memset(f,0x3f,sizeof f);
	f[1][0]=0;
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				for(int k=0;k<n;k++){
					f[i][j]=min(f[i][j],f[i^(1<<j)][k]+w[k][j]);
				}
			}
		}
	}
	cout<<f[(1<<n)-1][n-1];
	return 0;	
}

飞行员兄弟

1. 枚举所有开关操作或者不操作，一共有

种操作$2^{16}$

2. 预处理编号，将状态用整数state表示

3. 对于某个 (i, j) 操作，可以预处理出改变的值，即同行和同列

4. 枚举过程中不断更新答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ch[4][4],st;
int get(int x,int y){return x*4+y;}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			char x;
			cin>>x;
			if(x=='+'){
				st+=(1<<get(i,j));
			}
		}
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				ch[i][j]+=(1<<get(i,k));
				ch[i][j]+=(1<<get(k,j));
			}
			ch[i][j]-=(1<<get(i,j));
		}
	}
	vector<pair<int,int>>an;
	for(int i=0;i<1<<16;i++){
		int t=st;
		vector<pair<int,int>>v;
		for(int j=0;j<16;j++){
			if((i>>j)&1){
				t=t^ch[j/4][j%4];
				v.push_back({j/4,j%4});
			}
		}
		if(t==0&&(an.size()==0||an.size()>v.size()))an=v;
		
	}
	cout<<an.size()<<"\n";
	for(int i=0;i<an.size();i++)cout<<an[i].first+1<<' '<<an[i].second+1<<"\n";
	return 0;	
}

/*
	a[4][4] --> 状态 --> 16位二进制数 sta
	a[i][j] sta (i*4+j)
	a[i][j] --> conv
	sta ^ conv[i][j] --> 第i行，第j列的所有数字改变
get(i,j) 4*i+j
for(i:0~3)
	for(j:0~3)
		for(k:0~3) 枚举行(或列)中的所有元素
			conv[i][j] += (1<<get(i,k))
			conv[i][j] += (1<<get(k,j))
	conc...-=(1<<get(i,j))
vetor<PII> ans
for(i:0~1<<16-1)
	temp = sta; v<PII> path
	for(j:0~15)
if(i的第j位==1) --> i的第j位为:i&(1<<j) 或 i<<j&1
	temp^conv[j/4][j%4]
	path push...{j/4 j%4}
if(temp==0&&(ans.size()==0||ans.size>path.size))ans=path;

注意：题目中要求输出的下标从1开始，所以所有下标输出时加1

*/

递归实现指数型枚举&递归实现组合型枚举& 递归实现排列型枚举

模版

#include<bits/stdc++.h>
using namespace std;
int st[20],n;
void dfs(int w){
	if(w==n+1){
		for(int i=1;i<=n;i++)if(st[i])cout<<i<<' ';
		cout<<"\n";
		return;
	}
	st[w]=1;
	dfs(w+1);
	st[w]=0;
	dfs(w+1);
}
int main(){
	cin>>n;
	dfs(1);
	return 0;	
}

#include<bits/stdc++.h>
using namespace std;
int n,st[55],c;
void dfs(int w,int g){
	if(g==c){
		for(int i=1;i<=n;i++)if(st[i])cout<<i<<' ';
		cout<<"\n";
		return;
	}
	if(w==n+1)return;
	st[w]=1;
	dfs(w+1,g+1);
	st[w]=0;
	dfs(w+1,g);
}
int main(){
	cin>>n>>c;
	dfs(1,0);
}

#include<bits/stdc++.h>
using namespace std;
int n,a[15],l[15];
void dfs(int c){
	if(c==n){
		for(int i=0;i<n;i++)cout<<l[i]<<" ";
		cout<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		if(!a[i]){
			a[i]=1;
			l[c]=i;
			dfs(c+1);
			a[i]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(0);
}

费解的开关

每次枚举一个开关他周围的五个位置按下，超过次数退出

#include<bits/stdc++.h>
using namespace std;
int st[33][33],mi=100000000;
int dx[10]={0,1,0,-1,0};
int dy[10]={0,0,1,0,-1};
int t;
struct P{
	int x,y;
};
void g(int i,int j){
	for(int x=0;x<5;x++)st[i+dx[x]][j+dy[x]]=!st[i+dx[x]][j+dy[x]];
}
P ch(){
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(st[i][j]==0)return {i,j};
		}
	}
	return {-1,-1};
}
void dfs(int c){
	P v=ch();
	if(v.x==-1&&v.y==-1){
		mi=min(mi,c-1);
	}
	if(c>=mi||c>6)return;
	for(int i=0;i<5;i++){
		int x=v.x+dx[i];
		int y=v.y+dy[i];
		if(x<1||y<1||x>5||y>5)continue;
		g(x,y);
		
		dfs(c+1);
		g(x,y);
	}	
}

int main(){

	cin>>t;
	while(t--){
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				char x;
				cin>>x;
				st[i][j]=x-'0';
			}
		}
		mi=100000000;
		dfs(1);
		if(mi==100000000)cout<<-1<<"\n";
		else cout<<mi<<"\n";
	}
}

奇怪的汉诺塔

三塔：a[i]=2*a[i-1]+1;

四塔：b[i]=min(b[i],b[j]*2+a[i-j]);

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[15],b[15];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	a[1]=1;
	for(int i=2;i<=12;i++)a[i]=2*a[i-1]+1;
	for(int i=1;i<=12;i++){
		b[i]=a[i];
		for(int j=1;j<i;j++){
			b[i]=min(b[i],b[j]*2+a[i-j]);
			
		}
		cout<<b[i]<<"\n";
	}
	return 0;	
}

约数之和

先分解质因数，记得分解的时候每次是+b

再利用公式：$a的约数之和=(x_1^0+x_1^1+……+x_1^{m_1})*(x_2^0+x_2^1+……+x_2^{m_2})*……*(x_v^0+x_v^1+……+x_v^{m_v})$

最后卡一下常

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> mp;
int n,b,m=9901,s=1;
signed main() {
	cin>>n>>b;
	if(n==0){
		cout<<0;
		return 0;
	}
	for(int i=2;i<=n/i;i++) {
		while(n%i==0) {
			n/=i;
			mp[i]+=b; 
		}
	}
	if(n>1)mp[n]+=b;  
	for(auto i:mp) {
		int su=1,a=i.first,b=i.second;
		while(b>5){
			su=su*(a*a%9901*a*a%9901*a%9901)+a*a%9901*a*a%9901+a*a%9901*a+a*a+a+1;
			su=su%9901;
			b-=5;
		}
		while(b--)su=(su*a+1) % m;
		s=s*su%m; 
	}
	cout<<s;
}

分形之城

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
struct P{
	int x,y;
};
int jl(int x,int y,int xx,int yy){
	x=x*10-5;
	y=y*10-5;
	xx=xx*10-5;
	yy=yy*10-5;
	int a=abs(x-xx),b=(y-yy);
	return (int) round(sqrt(a*a+b*b));
}
P dfs(int n,int m){
	if(n==0)return {0,0};
	int l=1ll<<(n-1),c=1ll<<(2*(n-1));
	P p=dfs(n-1,m%c);
	int x=p.x,y=p.y;
	int z=m/c;
	if(z==0)return{y,x};
	if(z==1)return{x,y+l};
	if(z==2)return{x+l,y+l};
	if(z==3)return{-1-y+2*l,-x-1+l};
}
signed main(){
	cin>>t;
	while(t--){
		int n,a,b;
		cin>>n>>a>>b;
		P aa=dfs(n,a-1);
		P bb=dfs(n,b-1);
		double x=abs(aa.x-bb.x),y=(aa.y-bb.y);
		double z=sqrt(x*x+y*y)*10;
		printf("%.0lf\n",z);
	}
	
	return 0;	
}

分形

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[3333][3333],p[10];
void dfs(int x,int y,int n){
//	cout<<x<<' '<<y<<' '<<n<<"\n";
	if(n==0){
		a[x][y]=1;
		return;
	}
	dfs(x,y,n-1);
	dfs(x,y+p[n]-p[n-1],n-1);
	dfs(x+p[n]-p[n-1],y,n-1);
	dfs(x+p[n-1],y+p[n-1],n-1);
	dfs(x+p[n]-p[n-1],y+p[n]-p[n-1],n-1);
}
signed main(){
	int t;

	p[0]=1;
	for(int i=1;i<=6;i++)p[i]=p[i-1]*3;
	while(cin>>t&&t!=-1){
		int n;
		n=t;
		n--;
	
		dfs(1,1,n);
		for(int i=1;i<=p[n];i++){
			for(int j=1;j<=p[n];j++){
				if(a[i][j]==1)cout<<'X',a[i][j]=0;
				else cout<<' ';
			}
			cout<<"\n";
		}
		cout<<"-\n";
	}
	return 0;	
}

激光炸弹

二维差分模版题

#include<bits/stdc++.h>

using namespace std;
int s[5010][5010],mi=-10000000;
signed main() {
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		
		int x,y,z;
		cin>>x>>y>>z;
		s[x+1][y+1]+=z;
	}
	for(int i=1;i<=5001;i++)for(int j=1;j<=5001;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
	for(int i=1;i+q-1<=5001;i++){
		for (int j=1;j+q-1<=5001;j++){
			int ii=i+q-1;
			int jj=j+q-1;
			
			mi=max(mi,s[ii][jj]-s[ii][j-1]-s[i-1][jj]+s[i-1][j-1]);
		}
	}
	cout<<mi;
}

增减序列

设b[i]=a[i]-a[i-1],p,q;

如果 b[i]>=0并且i>1 p+=b[i];

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],b[100010],n,p,q;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i],b[i]=a[i]-a[i-1];
		if(b[i]>=0&&i>1)p+=b[i];
		else if(b[i]<0&&i>1)q+=abs(b[i]);
	}
	cout<<max(p,q)<<"\n"<<abs(p-q)+1;
}

最高的牛

先差分，再把每只牛加上h

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct P{
	int x,y;	
};
map<pair<int,int>,int> u;
int n,p,h,m,a[100010];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>p>>h>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x>y)swap(x,y);
		if(!u[{x,y}]){
			u[{x,y}]=1;
			a[x+1]--;
			a[y]++;
			
		}
	}
	for(int i=1;i<=n;i++)a[i]+=a[i-1],cout<<a[i]+h<<"\n";
	return 0;	
}

防线

我们可以通过公式算出1~x范围内的防具数量，因此我们可以二分防具数量

#include<bits/stdc++.h>
#define int long long
using namespace std;
int s[200010],t[200010],d[200010],k[200010],n,ss,uu;
unordered_map<int,int>u;
int c(int a){
	long long su=0;
	for(int i=1;i<=n;i++)if(s[i]<=a)su+=(min(a,t[i])-s[i])/d[i]+1;
	return su;
}
bool ch(int a,int b){
	return(c(b)-c(a-1))%2==1;
}
signed main(){
	int tt;
	cin>>tt;
	while(tt--){
		int mi=0x3f3f3f3f3f3f3f3f,ma=-100;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s[i]>>t[i]>>d[i];
			mi=min(mi,s[i]),ma=max(ma,t[i]);
		}
		long long su=0;
		for(int i=1;i<=n;i++) su+=(t[i]-s[i])/d[i]+1;
		if(su%2==0){cout<<"There's no weakness.\n";continue;}
		int l=mi,r=ma,d=0;
		while(l<r){
			int mid=(l+r)>>1;
			if(ch(l,mid))r=mid;
			else l=mid+1;
		}
		cout<<l<<' '<<c(l)-c(l-1)<<"\n";
	}
	
	return 0;	
}

最佳牛围栏

我们可以算出牛栏的平均值，因此就可以对牛栏进行二分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010];
double s[100010];
const double jd=1e-5;
bool c(double mi){
	for(int i=1;i<=n;i++)s[i]=s[i-1]+(a[i]-mi);
	double Mi=0;
	for(int i=0,j=m;j<=n;i++,j++){
		Mi=min(Mi,s[i]);
		if(s[j]-Mi>=0)return 1;
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	double l=0,r=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		r=max(r,(double)a[i]);
	}
	while(l+jd<r){
		double mi=(l+r)/2;
		if(c(mi))l=mi;
		else r=mi;
	}
	cout<<(int)(r*1000);
	return 0;	
}

赶牛入圈

离散化所有下标，前缀和数组维护区间三叶草数量， 二分边长， 判断范围内是否有c个三叶草

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s[1111][1111];
vector<pair<int,int>>a;
vector<int>al;
int f(int x){
	int l=0,r=al.size()-1;
	while(l<r){
		int mi=l+r+1>>1;
		if(al[mi]<=x)l=mi;
		else r=mi-1;
	}
	return r;
}
bool ch(int mi){
	for(int x=1,xx=1;xx<al.size();xx++){
		while(al[xx]+1-al[x]>mi)x++;
		for(int y=1,yy=1;yy<al.size();yy++){
			while(al[yy]+1-al[y]>mi)y++;
			if(s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1]>=m)return 1;
		}
	}
	return 0;
}
signed main(){
	cin>>m>>k;
	al.push_back(0);
	for(int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		n=max(n,max(x,y));
		al.push_back(x);
		al.push_back(y);
		a.push_back({x,y});
	}
	sort(al.begin(),al.end());
	al.erase(unique(al.begin(),al.end()),al.end());
	for(int i=0;i<k;i++){
		int x=f(a[i].first),y=f(a[i].second);
		s[x][y]++;
	}
	for(int i=1;i<al.size();i++){
		for(int j=1;j<al.size();j++){
			s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		}
	}
	int l=1,r=n;
	while(l<r){
		int mi=l+r>>1;
		if(ch(mi))r=mi;
		else l=mi+1;
	}
	cout<<r;	
}

电影

先离散化所有数

再通过语音排序

最后找到最多人喜欢语音的电影，再找喜欢字幕最多的

#include<bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int>u;
struct P{
	int sy;
	int zm;
	int id;
}a[200010],b[200010];
int tt=0;
bool cmp(P a,P b){
	if(u[a.sy]==u[b.sy])return u[a.zm]>u[b.zm];
	else return u[a.sy]>u[b.sy];
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		u[x]++;
	}
	cin>>m;
	int mx=-100,ma=-100,w;
	for(int i=1;i<=m;i++)cin>>a[i].sy,mx=max(mx,u[a[i].sy]);
	for(int i=1;i<=m;i++)cin>>a[i].zm,a[i].id=i;
	for(int i=1;i<=m;i++){
		if(u[a[i].sy]==mx){
			if(u[a[i].zm]>ma){
				ma=u[a[i].zm];
				w=i;
			}
		}
	}
	cout<<w;
	return 0;	
}

货仓选址

公式

算出(n+1)/2，每个数在减去a[(n+1)/2]（要套绝对值）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],n;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	int mi=(n+1)/2;
	int c=0;
	for(int i=1;i<=n;i++){
		c+=abs(a[i]-a[mi]);
	}
	cout<<c;
	return 0;	
}

七夕祭

行列互不干扰

求行和列就按货仓选址的公式

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int n,m,t,h[100010],l[100010],s[100010];
struct p{
	int x,y;
}a[100010];
int ch(int c,int a[]){
	if(t%c!=0)return -1;
	for(int i=1;i<=c;i++)a[i]=a[i-1]+(a[i]-t/c);
	sort(a+1,a+1+c);
	int cn=0;
	for(int i=1;i<=c;i++)cn+=abs(a[i]-a[c/2+1]);
	return cn;
}
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++)cin>>a[i].x>>a[i].y,h[a[i].x]++,l[a[i].y]++;
	int gh=ch(n,h);
	int gl=ch(m,l);
	if(gh==gl&&gl==-1)cout<<"impossible";
	else if(gh>gl&&gl==-1)cout<<"row "<<gh;
	else if(gl>gh&&gh==-1)cout<<"column "<<gl;
	else cout<<"both "<<gh+gl;
	
	return 0;	
}

动态中位数

建一个大根堆p，和小根堆q

当p没值的时候加入

当a[i]<=p.top,加p

否则加入q

长度差距超过(q大为1,p大为2)把多的放在少的里

中位数是p.top

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],h,n;
priority_queue<int>q;  
priority_queue<int,vector<int>,greater<int>>p;  
void pu(int x){
	if(q.size()==0||x<=q.top())q.push(x);
	else p.push(x);
	if(q.size()==p.size()+2)p.push(q.top()),q.pop();
	if(p.size()==q.size()+1)q.push(p.top()),p.pop();
}
signed main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>h>>n;
		q=priority_queue<int>();  
		p=priority_queue<int,vector<int>,greater<int>>();  

		for(int i=1;i<=n;i++)cin>>a[i];
		cout<<h<<' '<<(n+1)/2<<"\n";
		int g=0;
		for(int i=1;i<=n;i++){
			pu(a[i]);
			if(i%2==1){
			
				cout<<q.top()<<" ";
				g++;
				if(g==10){
					g=0;
					cout<<"\n";
				}
			}
		}
		if(g>0)cout<<"\n";
	}
	return 0;	
}

超快速排序

求逆序对

#include<bits/stdc++.h>
using namespace std;
int a[1000010],t[1000010];
long long c=0;	int n;
void m(int a[],int l,int r) {
	if (l>=r) return;
	int mi=(l+r)/2;
	m(a,l,mi);
	m(a,mi+1,r);
	int k=0,i=l,j=mi+1;
	while(i<=mi&&j<=r) {
		if (a[i]<=a[j])t[k]=a[i],k++,i++;
		else t[k]=a[j],k++,j++,c+=mi-i+1;
	}
	while(i<=mi)t[k++]=a[i++];
	while(j<=r)t[k++]=a[j++];
	for(int i=l,j=0;i<=r;i++,j++)a[i]=t[j];
}
int main(){
	while(cin>>n&&n!=0){
		c=0;
		for(int i=1;i<=n;i++)cin>>a[i];
		m(a,1,n);
		cout<<c<<"\n";
	}
}

奇数码问题

性质，两个互通的局面逆序对奇偶性一样

#include<bits/stdc++.h>
using namespace std;
int x[1000010],y[1000010],t[1000010];
long long c;
void m(int a[],int l,int r) {
	if (l>=r) return;
	int mi=(l+r)/2;
	m(a,l,mi);
	m(a,mi+1,r);
	int k=0,i=l,j=mi+1;
	while(i<=mi&&j<=r) {
		if (a[i]<=a[j])t[k]=a[i],k++,i++;
		else t[k]=a[j],k++,j++,c+=mi-i+1;
	}
	while(i<=mi)t[k++]=a[i++];
	while(j<=r)t[k++]=a[j++];
	for(int i=l,j=0;i<=r;i++,j++)a[i]=t[j];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	while(cin>>n){
		if(n==1){
			cin>>x[0]>>x[0];
			cout<<"TAK\n";
			continue;
		}
		int idx=0;
		for(int i=1;i<=n*n;i++){
			int a;
			cin>>a;
			if(a!=0)x[++idx]=a;
		}
		idx=0;
		for(int i=1;i<=n*n;i++){
			int a;
			cin>>a;
			if(a!=0)y[++idx]=a;
		}
		c=0;
		m(x,1,n*n-1);
		long long xx=c;
		c=0;
		m(y,1,n*n-1);
		long long yy=c;
		if(xx%2==yy%2)cout<<"TAK\n";
		else cout<<"NIE\n";
	}

}

糖果传递

更货仓选址一样

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int n,m,t,h[1000010],l[1000010],s[1000010];
struct p{
	int x,y;
}a[100010];
int ch(int c,int a[]){

	for(int i=1;i<=c;i++)a[i]+=a[i-1];
	for(int i=1;i<=n;i++)a[i]-=i*a[n]/n;
	sort(a+1,a+1+c);
	int cn=0;
	for(int i=1;i<=c;i++)cn+=abs(a[i]-a[c/2+1]);
	return cn;
}
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	
	
	for(int i=1;i<=n;i++)cin>>h[i],t+=h[i];
	cout<<ch(n,h);
	
	return 0;	
}

士兵

y轴取平均值

x轴按货仓选址

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],b[100010],n;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[i]-=i;
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int mi=n/2+1;
	int c=0;
	for(int i=1;i<=n;i++)c+=abs(a[i]-a[mi]);
	for(int i=1;i<=n;i++)c+=abs(b[i]-b[mi]);
	cout<<c;
	return 0;	
}

天才ACM

假设当前区间的起点是1,可能的终点设为r,初始步长p=1,l=r=1 1.每次判断区间[,r+p)的校验值是否合法 2.如果合法,r+=p,p<<=1并重复1 3.如果不合法,则p>>=1 (1)如果p==0,本次区间查找完成,退出。 (2)否则重复步骤1

再加归并优化

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,an,k,a[500010],b[500010],c[500010];
int ch(int l,int mi,int r){
	for(int i=mi;i<r;i++) b[i]=a[i];
	sort(b+mi,b+r);
	int i=l,j=mi,p=0;
	while(i<mi&&j<r){
		if(b[i]<=b[j])c[p++]=b[i++];
		else c[p++]=b[j++];
	}
	while(i<mi)c[p++]=b[i++];
	while(j<r)c[p++]=b[j++];
	int s=0;
	for(int i=0;i<m&&i<p;i++,p--)s+=pow(c[i]-c[p-1],2);
	return s<=k;
}
signed main(){
	
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		for(int i=0;i<n;i++)cin>>a[i];
		an=0;
		int ed=0,pd=0;
		while(pd<n){
			int len=1;
			while(len){
				if(pd+len<=n&&ch(ed,pd,pd+len)){
					pd+=len;
					len*=2;
					if(pd>=n)break;
					for(int i=ed;i<pd;i++){
						b[i]=c[i-ed];
					}
				}else len/=2;
			}
			ed=pd; 
			an++;
		}
		cout<<an<<"\n";
	}
	return 0;	
}

股票买卖

只要的一天卖完，第二天买值，那么就加上

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200010],q;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		if(a[i]<a[i+1]){
			q+=a[i+1]-a[i];
		}
	}
	cout<<q;
	return 0;	
}

防晒

每只牛按他最小可接受的防晒霜分配即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f[100010];
struct P{
	int mi,ma;
}a[1000010];
map<int,int>mp;
bool cmp(P a,P b){
	return a.ma<b.ma;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)cin>>a[i].mi>>a[i].ma;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		f[x]+=y;
	}
	sort(a+1,a+1+n,cmp);
	int c=0;
	f[0]=f[10001]=n;
	for(int i=1;i<=n;i++){
		for(int j=a[i].mi;j<=a[i].ma;j++){
			if(f[j]){
				f[j]--;
				c++;
				break;
			}
		}
	}
	cout<<c;
	return 0;	
}

畜栏预定

1. 将所有牛按照开始吃草的顺序排序

2. 用小根堆维护当前最先结束的畜栏

3. 如果当前牛能安排到堆顶的畜栏，则安排进去，否则就新建一个畜栏

#include<bits/stdc++.h>
#define int long long
using namespace std;
pair<pair<int,int>,int>c[50010];
int n,id[50010];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i].first.first>>c[i].first.second;
		c[i].second=i;
	}
	sort(c+1,c+1+n);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>d;
	for(int i=1;i<=n;i++){
		if(d.empty()||d.top().first>=c[i].first.first){
			pair<int,int> ns={c[i].first.second,d.size()};
			id[c[i].second]=ns.second;
			d.push(ns);
		}
		else{
			pair<int,int>ns=d.top();
			d.pop();
			ns.first=c[i].first.second;
			id[c[i].second]=ns.second;
			d.push(ns);
		}
	}
	cout<<d.size()<<"\n";
	for(int i=1;i<=n;i++)cout<<id[i]+1<<"\n";
	return 0;	
}

雷达设备

1. 将所有区间按右端点从小到大排序

2. 如果当前区间包含最后一个选择的点 last ，则跳过；否则新建一个新的点，该点的位置就是区间的右端点。特判 y>d 的情况。

#include<bits/stdc++.h>
#define int long long
using namespace std;
pair<pair<int,int>,int>c[50010];
int n,id[50010];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i].first.first>>c[i].first.second;
		c[i].second=i;
	}
	sort(c+1,c+1+n);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>d;
	for(int i=1;i<=n;i++){
		if(d.empty()||d.top().first>=c[i].first.first){
			pair<int,int> ns={c[i].first.second,d.size()};
			id[c[i].second]=ns.second;
			d.push(ns);
		}
		else{
			pair<int,int>ns=d.top();
			d.pop();
			ns.first=c[i].first.second;
			id[c[i].second]=ns.second;
			d.push(ns);
		}
	}
	cout<<d.size()<<"\n";
	for(int i=1;i<=n;i++)cout<<id[i]+1<<"\n";
	return 0;	
}

国王游戏

按两只手乘积去排序

#include<bits/stdc++.h>
using namespace std;
struct P{
	unsigned long long int z,y;
}s[11111];
bool cmp(P a,P b){
	return a.z*a.y<b.z*b.y;
}
vector<int> add(vector<int>A,int b){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size()||t;i++){
		if(i<A.size())t+=A[i]*b;
		C.push_back(t%10);
		t/=10;
	}
	while(C.size()>1&&C.back()==0)C.pop_back();
	return C;
}
vector<int> app(vector<int>A,int b){
	vector<int> C;
	int t=0,r=0;
	for(int i=0;i<A.size();i++){
		t=r*10+A[i];
		C.push_back(t/b);
		r=t%b;
	}
	reverse(C.begin(), C.end()); 
	while(C.size()>1 && C.back() == 0) C.pop_back();
	reverse(C.begin(), C.end()); 
	return C;
}
bool cpp(vector<int> a,vector<int> b){
	if(a.size()==b.size()){
		for(int i=0;i<a.size();i++)if(a[i]!=b[i])return a[i]>b[i];
		return 1;
	}
	return a.size()>b.size();
}
int main(){
	unsigned long long int n,a,b;
	cin>>n>>a>>b;
	s[0].z=a,s[0].y=b;
	for(unsigned long long int i=1;i<=n;i++)cin>>s[i].z>>s[i].y;	
	sort(s+1,s+1+n,cmp);
	vector<int>mi;
	mi.push_back(0);
	vector<int>q;
	q.push_back(1);
	for(unsigned long long int i=1;i<=n;i++){
		q=add(q,s[i-1].z);
		reverse(q.begin(), q.end()); 
		vector<int>l=app(q,s[i].y);
		reverse(q.begin(), q.end()); 
		if(cpp(l,mi))mi=l;
	}
	for(int i=0;i<mi.size();i++)cout<<mi[i];
	return 0;	
}

给树染色

先父节点先染色了，再子节点合并。父节点中，权值大的肯定优先选。

合并时，平均值更大更优

#include<bits/stdc++.h>
using namespace std;
//#define int long long
struct P{
	int f,si,su;
	double avg;
}f[1111];
int ro,n;
int fi(){
	int id=0;
	double avg=0;
	for(int i=1;i<=n;i++){
		if(i!=ro&&avg<f[i].avg){
			id=i,avg=f[i].avg;
		}
	}
	return id;
}

signed main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	int r=0;
	cin>>n>>ro;
	for(int i=1;i<=n;i++){
		cin>>f[i].su;
		r+=f[i].su;
		f[i].si=1;
		f[i].avg=f[i].su;
	}
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		f[b].f=a;
	}
	for(int i=0;i<n-1;i++){
		int p=fi();
		r+=f[f[p].f].si*f[p].su;
		for(int j=1;j<=n;j++){
			if(f[j].f==p){
				f[j].f=f[p].f;
			}
		}
		f[p].avg=-1;
		f[f[p].f].su+=f[p].su;
		f[f[p].f].si+=f[p].si;
		f[f[p].f].avg=1.0*f[f[p].f].su/f[f[p].f].si;
		
	}
	cout<<r;
	return 0;	
}

耍杂技的牛

按重量与强壮度之和排序

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
struct P{
	int w,s;
}a[50010];
int n;
bool cmp(P a,P b){
	return a.w+a.s<=b.w+b.s;
}
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].s;
	sort(a+1,a+1+n,cmp);
	int s=0,ss=0,mx=-0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		s=ss-a[i].s;
		mx=max(mx,s);
		ss+=a[i].w;
	}
	cout<<mx;
	return 0;	
}

最大的和

用列的前缀和求最大的和

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int a[111][111],n,an=-0x3f3f3f3f3f3f3f3f;
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			a[i][j]+=a[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int l=0;
			for(int k=1;k<=n;k++){
				l=max(l,0ll)+a[j][k]-a[i-1][k];
				an=max(an,l);
			}
		}
	}
	cout<<an;
	return 0;	
}

任务

机器：按工作时间降序排序，工作时间相同则按级别降序排序。

任务：按所需时间降序排序，时间相同则按难度级别降序排序。

使用双指针遍历机器，将满足要求机器加入集合。

使用 multiset 维护候选机器的级别，以便快速查找满足当前任务级别要求的最小级别机

器。

#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int n, m;
struct P {
	int x, y;
} a[100010], b[100010];
bool cmp(P a, P b) {
	if (a.x == b.x)return a.y > b.y;
	return a.x > b.x;
}
INT main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y;
		for (int i = 1; i <= m; i++)cin >> b[i].x >> b[i].y;
		sort(a + 1, a + 1 + n, cmp);
		sort(b + 1, b + 1 + m, cmp);
		int  i = 1, j = 1, s = 0, k = 0;
		multiset<int>st;
		for (; j <= m; j++) {
			P t = b[j];
			while (i <= n && a[i].x >= t.x) {

				st.insert(a[i].y);
				i++;
			}
			auto it = st.lower_bound(t.y);
			if (it != st.end()) {
				k += 500ll * t.x + 2ll * t.y;
				s++;
				st.erase(it);

			}
		}
		cout << s << ' ' << k << "\n";
	}


	return 0;
}

占卜DIY

按题面意思用栈模拟即可

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
struct P{
	int p,st;
};
int tt[30];
deque<P>st[20];
int get(char a){
	if(a=='A')return 1;
	else if(a=='J')return 11;
	else if(a=='Q')return 12;
	else if(a=='K')return 13;
	else if(a=='0')return 10;
	else return a-'0';
}
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(int i=1;i<=13;i++){
		char a,b,c,d;
		cin>>a>>b>>c>>d;
		st[i].push_back({get(d),0});
		st[i].push_back({get(c),0});
		st[i].push_back({get(b),0});
		st[i].push_back({get(a),0});
	}
	while(st[13].size()){
		auto a=st[13].back();
		st[13].pop_back();
		a.st=1;
		while(a.p!=13){
			st[a.p].push_back(a);
			int tt=a.p;
			a=st[a.p].front();
			st[tt].pop_front();
			a.st=1;
		}
	}
	for(int i=1;i<=13;i++){
		for(int j=0;j<st[i].size();j++){
			if(st[i][j].p!=13&&st[i][j].st==1){
				tt[st[i][j].p]++;
			}
		}
	}
	int  an=0;
	for(int i=1;i<=13;i++)if(tt[i]==4)an++;
	cout<<an;
	return 0;	
}

袭击

法1（100TLE）

先排序

接着进行分治

每次把点分成两边

算出平面点对后

再合并

#include<bits
/stdc++.h>
using namespace std;
const int N = 200005;
const double INF = 1e15;
const double eps = 1e-6;
int n;
double mind;
struct point // 结构体存所有点
{
	double x, y; // 存每个点的坐标
	bool type; // 存每个点的类型
	bool operator < (const point &t) const // 用于将所有点按 x 坐标从小到大排序
	{
		return x < t.x;
	}
} points[N], tmp[N]; // points 存输入的每个点，tmp 存分治时对于每个点要处理的点
double get_dist(point a, point b) // 返回点 a 和点 b 的直径距离
{
	if (a.type == b.type) return mind ; // 如果这两个点的类型不同，返回当前最优答案即可。
	double dx = a.x - b.x, dy = a.y - b.y; // 计算出这两个点横纵坐标的差值
	return sqrt(dx * dx + dy * dy); // 返回这两个点的平面距离
}
double dfs(int l, int r)
{
	if (l == r) return INF ; // 如果剩下区域只有一个点，那么为了避免更新答案，返回正无穷
	int mid = l + r >> 1; // 找到剩下区域内中间的点的位置。
	double mid_x = points[mid].x; // 取出该点的 x 坐标，与该坐标距离超过ans 的点不计入考虑。
	double ans = min(dfs(l, mid), dfs(mid + 1, r)); // 分治计算出上述未被更新的 ans
// 先将 points 中的 [l, mid] 和 [mid + 1, r] 两段进行按 y 轴坐标进行按序归并
// 注意这里一定要归并，后面对于每个点我们才能快速找出对应的（至多） 6 个点，以保证总时间复杂度是 O(n log n)
	int i = l, j = mid + 1, cnt = 0;
	while (i <= mid && j <= r)
		if (points[i].y < points[j].y) tmp[cnt ++ ] = points[i ++ ];
	else tmp[cnt ++ ] = points[j ++ ];
	while (i <= mid) tmp[cnt ++ ] = points[i ++ ];
	while (j <= r) tmp[cnt ++ ] = points[j ++ ];
	for (i = l; i <= r; i ++ ) points[i] = tmp[i - l];
// 找到所有在 [mid_x - ans, mid_x + ans] 中的点，存入 tmp
	cnt = 0;
	for (i = l; i <= r; i ++ )
		if (points[i].x >= mid_x - ans && points[i].x <= mid_x + ans) // 如果说该点距离 mid_x 的距离小于 ans，那么需要考虑该点
			tmp[cnt ++ ] = points[i];
// 下面第二层循环中，有 tmp[i].y - tmp[j].y <= ans 这个判断，才能保证我们对于每个点最多只考虑六个点
// 这样在每层递归中，就可以保证时间复杂度是线性的，否则时间复杂度是平方级别的
	for (i = 0; i < cnt; i ++ ) // 处理所有 tmp 中的点
		for (j = i - 1; ~j && tmp[i].y - tmp[j].y + eps <= ans; j -- )
			ans = min(ans, get_dist(tmp[i], tmp[j])); // 更新 ans
	mind = min(mind, ans);
	return ans;
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{
		scanf("%d", &n);
		for (int i = 0; i < n; i ++ )
		{
			scanf("%lf %lf", &points[i].x, &points[i].y); // 输入所有核电站的坐标
			points[i].type = false; // 核电站的 type 制成
			
		}
		for (int i = n; i < n << 1; i ++ )
		{
			scanf("%lf %lf", &points[i].x, &points[i].y); // 读入所有特工的坐标
			points[i].type = true; // 特工的 type 制成 true
		}
		mind = get_dist(points[0], points[(n << 1) - 1]);
		sort(points, points + (n << 1)); // 将所有点按 x 坐标排序
		printf("%.3lf\n", dfs(0, (n << 1) - 1)); // 分治函数的返回值即为答案
	}
	return 0;
}

数的进制转换

模版

#include<bits/stdc++.h>
using namespace std;
#define int long long
int get(char x){
	if(x>='0'&&x<='9')return x-'0';
	if(x>='A'&&x<='Z')return x-'A'+10;
	if(x>='a'&&x<='z')return x-'a'+36;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	
	while(t--){
		int a,b;
		vector<int>s1,s2;
		string s;
		cin>>a>>b>>s;
		for(int i=0;i<s.size();i++)s1.push_back(get(s[i]));
		reverse(s1.begin(),s1.end());
		while(s1.size()){
			int t=0;
			for(int i=s1.size()-1;i>=0;i--){
				s1[i]+=t*a;
				t=s1[i]%b;
				s1[i]/=b;
			}
			s2.push_back(t);
			
			while(s1.size()&&s1.back()==0)s1.pop_back();
			
		}
		cout<<a<<' '<<s<<"\n";
		cout<<b<<' ';
		reverse(s2.begin(),s2.end());
		for(int i=0;i<s2.size();i++){
			if(s2[i]>=36)cout<<char(s2[i]-36+'a');
			else if(s2[i]>=10)cout<<char(s2[i]-10+'A');
			else cout<<s2[i];
		}
		cout<<"\n\n";
	}
	return 0;	
}

编辑器

用栈模拟

#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int> st;
stack<int> ts;
int t[1000010],g=0,f[1000010],l[1000010];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int q,mx=-10000000;
	cin>>q;
	while(q--){
		char c;
		cin>>c;
		if(c=='I'){
			int  x;
			cin>>x;
		
			st.push(x);
			t[++g]=x;
			l[g]=l[g-1]+t[g];
			if(g>1)f[g]=max(f[g-1],l[g]);
			else f[g]=l[g];
		}
		else if(c=='D'){
			if(st.size()){
				st.pop();
				g--;
			}
			else{
				continue;
			}
		}
		else if(c=='L'){
			if(st.size()){
				ts.push(st.top());
				st.pop();
				g--;
			}
			else{
				continue;
			}
		}
		else if(c=='R'){
			if(ts.size()){
				st.push(ts.top());
				t[++g]=ts.top();
				l[g]=l[g-1]+t[g];
				if(g>1)f[g]=max(f[g-1],l[g]);
				else f[g]=l[g];
				ts.pop();
			}
			else{
				continue;
			}
		}
		else{
			int x;
			cin>>x;
			cout<<f[x]<<"\n";
		}
	
	}
	return 0;	
}

直方图中最大的矩形

单调栈维护左边界

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],st[100010],l[100010],r[100010],n,tt;
signed main(){
	while(cin>>n&&n!=0){
		for(int i=1;i<=n;i++)cin>>a[i];
		a[0]=a[n+1]=-1,tt=0,st[0]=0;
		for(int i=1;i<=n;i++){
			while(a[st[tt]]>=a[i])tt--;
			l[i]=i-st[tt];
			st[++tt]=i;
		}
		tt=0,st[0]=n+1;
		for(int i=n;i>=1;i--){
			while(a[st[tt]]>=a[i])tt--;
			r[i]=st[tt]-i;
			st[++tt]=i;
		}
		int c=0;
		for(int i=1;i<=n;i++)c=max(c,(r[i]+l[i]-1)*a[i]);
		cout<<c<<"\n";
		
	}
	return 0;
}

火车进出栈问题

卡特兰因数+高精度

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6000010,M=120010;
int r[6000010],tt,q[120010],st[1200010];
void ml(int b){
	int t=0;
	for(int i=0;i<=tt;i++){
		r[i]=r[i]*b+t;
		t=r[i]/1000000000;
		r[i]%=1000000000;
	}
	while(t){
		r[++tt]=t%1000000000;
		t/=1000000000;
	}
}
int g(int n,int p){
	int s=0;
	while(n)s+=n/p,n/=p;
	return s;
}
signed main(){
	int n;
	cin>>n;
	for(int i=2;i<=2*n;i++)for(int j=i+i;j<=2*n;j+=i)st[j]=1;
	for(int i=2;i<=n*2;i++)if(!st[i])q[i]=g(n*2,i)-g(n*2-n,i)*2;
	int k=n+1;
	for(int i=2;i<=k;i++)while(k%i==0)k/=i,q[i]--;
	r[0]=1;
	for(int i=2;i<=n*2;i++)while(q[i]--)ml(i);
	printf("%lld",r[tt]);
	for(int i=tt-1;i>=0;i--)printf("%09lld",r[i]);
	return 0;
}

火车进栈

枚举组合数，再用模拟的方法判定是否可行

#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<char>a,b;
string s;
int st[200010];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>s;
//	int c=0,mx=0;
	for(int i=0;i<s.size();i++){
//		mx=max(mx,c);
//		cout<<a.size()<<' '<<c<<"\n";
		if(s[i]=='{'||s[i]=='['||s[i]=='('){
			a.push(s[i]);
		}
		else{
			if(a.size()==0){
			continue;
			}
			else{
				char y=s[i],x=a.top();
				a.pop();
				int f=0;
				if((x=='('&&y==')')||(x=='['&&y==']')||(x=='{'&&y=='}'))f=1;
				else f=0;
				if(f){
					st[i]=1;
					int j=i;
					while(st[j])j--;
					st[j]=1;
				}
				else a=b;
			}
		}
	}
	int c=0,mx=0;
	for(int i=0;i<s.size();i++){
		if(st[i]){
			c++;
			mx=max(mx,c);
		}
		else c=0;
	}
	cout<<mx;
	return 0;
}

括号画家

用栈维护

#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<char>a,b;
string s;
int st[200010];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>s;
//	int c=0,mx=0;
	for(int i=0;i<s.size();i++){
//		mx=max(mx,c);
//		cout<<a.size()<<' '<<c<<"\n";
		if(s[i]=='{'||s[i]=='['||s[i]=='('){
			a.push(s[i]);
		}
		else{
			if(a.size()==0){
			continue;
			}
			else{
				char y=s[i],x=a.top();
				a.pop();
				int f=0;
				if((x=='('&&y==')')||(x=='['&&y==']')||(x=='{'&&y=='}'))f=1;
				else f=0;
				if(f){
					st[i]=1;
					int j=i;
					while(st[j])j--;
					st[j]=1;
				}
				else a=b;
			}
		}
	}
	int c=0,mx=0;
	for(int i=0;i<s.size();i++){
		if(st[i]){
			c++;
			mx=max(mx,c);
		}
		else c=0;
	}
	cout<<mx;
	return 0;
}

表达式求值

模版，注意维护括号和负号

#include<bits/stdc++.h>
#include<stack>
#include<unordered_map>
using namespace std;

stack<long long> num;
stack<char> op;

void eval() {
	long long b = num.top(); num.pop();
	long long a = num.top(); num.pop();
	char c = op.top(); op.pop();
	long long x;
	if (c == '+') x = a + b;
	else if (c == '-') x = a - b;
	else if (c == '*') x = a * b;
	else if (c == '/') x = a / b;
	else{
		x=1;
		while(b--)x*=a;
	}
	num.push(x);
}

unordered_map<char, long long> pr{{'+',1},{'-',1},{'*',2},{'/',2},{'^',2}};

signed main() {
	string s;
	cin >> s;
	long long d=0;
	
	for (long long i = 0; i < s.size(); i++) {
		auto c = s[i];
		if (isdigit(c)) {
			long long x = 0, j = i;
			while (j < s.size() && isdigit(s[j]))
			{
				x = x * 10 + s[j] - '0';
				j++;
			}
			i = j - 1;
			num.push(x);
		}
		else if (c == '(') op.push(c),d++;
		else if (c == ')') {
			if(d==0)continue;
			d--;
			while (op.top() != '(') eval();
			op.pop();
		}
		else {
			if(s[i-1]=='('||s[i-1]=='+'||s[i-1]=='-'||s[i-1]=='*'||s[i-1]=='/'){
				long long x = 0, j = i+1;
				i++;
				while (j < s.size() && isdigit(s[j]))
				{
					x = x * 10 + s[j] - '0';
					j++;
				}
				i = j - 1;
				num.push(-x);
			}
			else{
				while (op.size() && op.top() != '(' && pr[c] <= pr[op.top()])
					eval();
				op.push(c);
			}
		
		}
	}
	while (op.size()){
		if(op.top()=='('){
			op.pop();
		}
		else eval();
	};
	if(num.size()>0)cout << num.top();
	else cout<<0;
	return 0;
}

城市游戏

最大矩阵取决于这个数到上一个不达标的点的距离，和能持续的宽度

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,long long>u;
long long ma=1,n,m;
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char a;
			cin>>a;
			if(a=='F')u[j]++;
			else u[j]=0;
			long long c=1,k=u[j];
			for(long long p=j-1;p>=1&&u[p];p--){
				c++;
				k=min(k,u[p]);
				ma=max(ma,c*k);
			}
		}
	}
	cout<<3*ma;	
}

小组队列

直接模拟即可

#include<bits/stdc++.h>
using namespace std;
int st[1000010],n,cn;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	while(cin>>n&&n!=0){
		printf("Scenario #%d\n",++cn);
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			for(int j=1;j<=x;j++){
				int y;
				cin>>y;
				st[y]=i;
			}
		}
		queue<int>xz;
		queue<int>zn[1010];
		string s;
		while(cin>>s&&s!="STOP"){
			if(s=="ENQUEUE"){
				int x;
				cin>>x;
				int cr=st[x];
				if(zn[cr].size()==0)xz.push(cr);
				zn[cr].push(x);
			}
			else{
				cout<<zn[xz.front()].front()<<"\n";
				zn[xz.front()].pop();
				if(zn[xz.front()].size()==0)xz.pop();
			}
		}
		cout<<"\n";
	}
	
	return 0;	
}

双栈排序

先dfs二分图染色 如果 flag为1输出零 便利color 如果color[i]是0，加入栈1输出a 否则 加入栈二，输出c 然后再看栈一能否弹出,能弹出输出b

再看栈1和2能否弹出 栈一弹出输出b 栈二弹出输出a 注意t组数据

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010],f[1010];
int color[1010];
bool g[1010][1010], flag;
void dfs(int u,int c){
	color[u]=c;
	for (int i=1;i<=n;i++)
		if(g[u][i]){
			if(color[i]==c) flag=false;
			if(color[i]==-1) dfs(i,!c);
		}
}
int main(){
	int t;
	cin>>t;
	while(cin>>n&&t--){
		for(int i=1;i<=n;i++)cin>>a[i];
		f[n+1]=n+1;
		memset(g,0,sizeof g);
		for (int i=n;i;i--)f[i]=min(f[i+1],a[i]);
		for (int i=1;i<n-1;i++)
			for(int j=i+1;j<n;j++)
				if (a[i]<a[j]&&f[j+1]<a[i])
					g[i][j]=g[j][i]=1;
		memset(color,-1,sizeof color);
		flag=1;
		for (int i=1;i<=n;i++)
			if (color[i]==-1){
				dfs(i,0);
			}
		if (!flag){
			cout<<0<<"\n";
			continue;
		}
		stack<int>stk1,stk2;
		int now=1;
		for(int i=1;i<=n;i++){
			if(color[i]==0) stk1.push(a[i]),cout<<"a ";
			else{
				stk2.push(a[i]);
				cout<<"c ";
				while(i<n&&color[i+1]==0){
					i++;
					stk1.push(a[i]),cout<<"a ";
					while(stk1.size()&&stk1.top()==now){
						stk1.pop();
						now++;
						cout<<"b ";
					}
				}
			}
			while(stk1.size()&&stk1.top()==now||stk2.size()&&stk2.top()==now){
				if(stk1.size()&&stk1.top()==now){
					stk1.pop();
					now++;
					cout<<"b ";
				}
				else{
					stk2.pop();
					now++;
					cout<<"d ";
				}
			}
		}
		cout << endl;
	}
	
	return 0;
}

蚯蚓

用三个队列去存，先讲述加入第一个队列

每次把三个队列的对头中的最大值切成两端的蚯蚓分开,就能实现o(1)查找

#include<bits/stdc++.h>
using namespace std;
int n,m,q,u,v,t,q1[100010],q2[7000010],q3[7000010],dta,hh1,hh2,hh3,tt1,tt2=-1,tt3=-1;
int gm(){
	int x=INT_MIN;
	if(hh1<=tt1)x=max(x,q1[hh1]);
	if(hh2<=tt2)x=max(x,q2[hh2]);
	if(hh3<=tt3)x=max(x,q3[hh3]);
	if(hh1<=tt1&&x==q1[hh1])hh1++;
	else if(hh2<=tt2&&x==q2[hh2])hh2++;
	else hh3++;
	return x;
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
	for(int i=0;i<n;i++)scanf("%d",&q1[i]);
	sort(q1,q1+n);
	reverse(q1,q1+n);
	tt1=n-1;
	for(int i=1;i<=m;i++){
		int x=gm();
		x+=dta;
		if(i%t==0)printf("%d ",x);
		int l=x*1ll*u/v;
		int r=x-l;
		dta+=q;
		l-=dta,r-=dta;
		q2[++tt2]=l,q3[++tt3]=r;
	}
	puts("");
	for(int i=1;i<=n+m;i++){
		int x=gm();
		if(i%t==0)printf("%d ",x+dta);
	}
	puts("");
	return 0;
}

双端队列

模版

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
pair<int, int> a[200010];
int n;
int main(){
	cin >> n;
	for(int i=0;i<n;i++)cin>>a[i].x,a[i].y=i;
	sort(a,a+n);
	int r=1,f=-1;
	for(int i=0,la=n+1;i<n;){
		int j=i;
		while(j<n&&a[j].x==a[i].x) j++;  
		int mi=a[i].y,ma=a[j-1].y;
		if(f==-1){
			if(la>ma)la=mi; 
			else f=1,la=ma;
		}
		else{
			if(la<mi)la=ma;
			else r++,la=mi,f=-1;
		}
		i=j;
	}
	cout<<r;
	return 0;
}

最大子序和

单调队列维护区间信息

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int n,m,a[300010],s[300010],q[300010],hh,tt;
//queue<int>q;
INT main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],s[i]=a[i]+s[i-1];
	int r=-0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		while(i-q[hh]>m&&hh<=tt)hh++;
		r=max(r,s[i]-s[q[hh]]);
		while(s[q[tt]]>=s[i]&&hh<=tt)tt--;
		q[++tt]=i;
	}
	cout<<r;
	return 0;	
}

滑动窗口

经典模版题

#include<bits/stdc++.h>
using namespace std;
int a[1000010],q[1000010],h,t=-1,n,k;
int main() {
	scanf("%d%d",&n,&k);
	for (int i=0;i<n;i++)scanf("%d",&a[i]);
	for (int i=0;i<n;i++) {
		while(h<=t&&i-k+1>q[h])h++;  
		while(h<=t&&a[q[t]]>=a[i])t--;  
		q[++t]=i;
		if(i-k+1>=0)printf("%d ",a[q[h]]); 
	}
	printf("\n");
	h=0,t=-1;  
	for(int i=0;i<n;i++){
		while(h<=t&&i-k+1>q[h])h++;
		while(h<=t&&a[q[t]]<= a[i])t--;
		q[++t]=i;
		if(i-k+1>=0)printf("%d ",a[q[h]]);
	}
}

邻值查找

利用集合来找到绝对值差的最小值

#include<bits/stdc++.h>
using namespace std;
set<pair<int,int>>s; 
int n,a;
int main() {
	cin>>n>>a;
	s.insert({a,1});
	for(int i=2;i<=n;i++){
		cin>>a;
		s.insert({a, i});
		set<pair<int,int>>::iterator it=s.find({a,i}); 
		pair<int,int>cn;
		cn.first=0x3f3f3f3f;
		if(++it!=s.end())cn ={(*it).first-a,(*it).second};
		it--;
		if(it--!=s.begin()&&cn.first>=a-(*it).first)cn={a-(*it).first,(*it).second};
		cout<<cn.first<<" "<<cn.second<<"\n";
	}
	return 0;
}

内存分配

对于每个请求

1. 删掉释放时间 <= 当前时间 的内存，删除后判断是否满足

2. 判断请求是否可以满足，如果不可以，则插入等待队列

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int n;
queue<pair<int, int>> wa; 
set<pair<int, int>> rs; 
priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>> ed;
int mt, cnt;
bool give(int t,int m,int p){
	for (auto it=rs.begin();it!=rs.end();it++){
		auto jt=it;
		jt ++ ;
		if (jt!=rs.end()){
			if (m<=jt->x-(it->x+it->y-1)-1){
				int start = it->x + it->y;
				rs.insert({start,m});
				ed.push({t+p,start});
				return true;
			}
		}
	}
	return false;
}
void fs(int t){
	while (ed.size()&&ed.top().x<=t){
		int f = ed.top().x;
		while (ed.size()&&ed.top().x==f){
			auto top=ed.top();
			ed.pop();
			auto it=rs.lower_bound({top.y,0});
			rs.erase(it);
		}
		mt=f;
		while (wa.size()){
			auto front=wa.front();
			if (give(f,front.x, front.y))wa.pop();
			else break;
		}
	}
}
int main(){
	cin >> n;
	int t, m, p;
	rs.insert({-1,1});
	rs.insert({n,1});
	while (cin>>t>>m>>p,t||m||p){
		fs(t);
		if (!give(t,m,p)){
			wa.push({m,p});
			cnt++;
		}
	}
	fs(2e9);
	cout<<mt<<"\n"<<cnt;
	return 0;
}

雪花雪花雪花

对雪花进行哈希，再查找

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[6],b[6],P=100003;
struct S{
	int s[6];
};
vector<S>sn[100010];
int g(){
	int s=0,k=1;

	for(int i=0;i<6;i++){
		s=(s+b[i])%P;
		k=(k*b[i])%P;
	}
	
	return (s+k)%P;
}
bool jj(){
//	cout<<1;
	for(int i=0;i<6;i++){
		for(int j=0;j<6;j++){
			bool v=1;
			for(int k=0;k<6;k++){
				if(b[(i+k)%6]!=a[(j+k)%6]){
					v=0;
					break;
				}
			}
			if(v)return 1;
			v=1;
			for(int k=0;k<6;k++){
				if(b[(i+k)%6]!=a[(j-k+6)%6]){
					v=0;
					break;
				}
			}
			if(v)return 1;
		}
	}
	return 0;
}
bool in(){
	int h=g();
	for(int i=0;i<sn[h].size();i++){
//		
		memcpy(a,sn[h][i].s,sizeof a);
		if(jj())return 1;
	}
//	cout<<1;
	S sn1;
	memcpy(sn1.s,b,sizeof sn1.s);
	sn[h].push_back(sn1);
	return 0;
}

signed main(){

	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
//	cout<<1;
	for(int i=1;i<=n;i++){
	
		for(int j=0;j<6;j++){
			cin>>b[j];
		}
		if(in()){
			cout<<"Twin snowflakes found.";
			return 0;
		}	
	}
	cout<<"No two snowflakes are alike.";
	return 0;
}

回文子串的最大长度

哈西+二分找回文子串

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
unsigned long long h[N],h1[N],p[N],cn=1;
bool check(int mi,int S){
	for(int i=1,j=mi;j<S;i++,j++){
		int i1=S-i,j1=S-j;
		if(h[j]-h[i-1]*p[j-i+1]==h1[i1]-h1[j1-1]*p[i1-j1+1])return 1;
	}
	return 0;
}
int main(){
	string s;
	while(cin>>s&&s!="END"){
		s=" "+s;
		int len=s.size();
		p[0]=1;
		for(int i=1;i<len;i++){
			h[i]=h[i-1]*131+s[i]-'a'+1;
			p[i]=p[i-1]*131;
		}
		for(int i=len-1;i>=1;i--){
			h1[len-i]=h1[len-i-1]*131+s[i]-'a'+1;
		}
		int l=0,r=len-1>>1;
		while(l<r){
			int mi=l+r+1>>1;
			if(check(mi<<1,len)) l=mi;
			else r=mi-1; 
		}
		int l1=0,r1=len-1>>1;
		if(len-1>>1==0) r1--;
		while(l1<r1){
			int mi=l1+r1+1>>1;
			if(check((mi<<1)+1,len)) l1=mi;
			else r1=mi-1;
		}
		cout<<"Case "<<cn++<<": "; 
		cout<<max(l<<1,(l1<<1)+1)<<endl;
	}
	return 0;	
}

后缀数组

模版

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,sa[300010];
ull h[300010],p[300010];
char s[300010];
ull g2(int l,int r){return h[r]-h[l-1]*p[r-l+1];}
ull g1(int a,int b){
	int l=0,r=min(n-a,n-b)+1;
	while(l<r){
		int mi=l+r+1>>1;
		if(g2(a,a+mi-1)==g2(b,b+mi-1))l=mi;
		else r=mi-1;
	}
	return l;
}
bool cmp(int a,int b){
	int l=g1(a,b);
	return s[a+l]<s[b+l];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	p[0]=1;
	for(int i=1;i<=n;i++){
		sa[i]=i;
		h[i]=h[i-1]*131+s[i];
		p[i]=p[i-1]*131;
	}
	sort(sa+1,sa+1+n,cmp);
	for(int i=1;i<=n;i++)printf("%d ",sa[i]-1);
	puts("");
	for(int i=1;i<=n;i++){
		if(i==1)printf("0 ");
		else printf("%d ",g1(sa[i],sa[i-1]));
	}
	return 0;
}

矩阵

二维哈希

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ull;
char st[1010];
ull f[1010][1010],p[1000010];
int n,m,a,b,P=131;
ull get(ull f[],int l,int r){
	return f[r]-f[l-1]*p[r-l+1];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>m>>n>>a>>b;
	p[0]=1;
	for(int i=1;i<=m*m;i++)p[i]=p[i-1]*P;
	for(int i=1;i<=m;i++){
		cin>>st+1;
		for(int j=1;j<=n;j++){
			f[i][j]=f[i][j-1]*P+st[j]-'0';
		}	
	}
	unordered_set<ull>ha;
	for(int i=b;i<=m;i++){
		ull s=0;
		int l=i-b+1,r=i;
		for(int j=1;j<=n;j++){
			s=s*p[b]+get(f[j],l,r);
			if(j>a)s=s-get(f[j-a],l,r)*p[a*b];
			if(j>=a)ha.insert(s);
		}
	}
	int k;
	cin>>k;
	while(k--){
		ull s=0;
		for(int i=0;i<a;i++){
			cin>>st;
			for(int j=0;j<b;j++){
				s=s*P+st[j]-'0';
				
			}
	
		}
		if(ha.count(s))puts("1");
		else puts("0");
	}
	return 0;
}