位运算

64位整数乘法

思路

用快速幂思想，每一次$a*2$，然后$b/2$，就可以用O（log(n)）

代码

#include<bits/stdc++.h>
using namespace std;
long long por(long long a,long long b,long long p){
	long long res=0;
	while(b>0){
		if(b&1){
			res=(res+a)%p;
		}
		a=2*a%p;
		b/=2;
	}
	return res;
}
int main(){
	long long a,b,p;
	cin>>a>>b>>p;
	cout<<por(a,b,p);
	return 0;
} 

反思

对于高精度，连加连乘，等对于快速幂不够熟练。

起床综合征

思路

将$1$和$0$分别讨论，尽量选0，可以避免很多时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
pair<string,int> a[N];
int n,m;
int c(int k,int u){
	for(int i=1;i<=n;i++){
		int t=(a[i].second>>k)&1;
		if(a[i].first=="AND"){
			u&=t;
		}
		if(a[i].first=="XOR"){
			u^=t;
		}
		if(a[i].first=="OR"){
			u|=t;
		}
	}
	return u;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string aa;
		int tt;
		cin>>aa>>tt;
		a[i]={aa,tt};
	}
	int mus=0,ans=0;
	for(int i=29;i>=0;i--){
		int t0=c(i,0);
		int t1=c(i,1);
		if(mus+(1<<i)<=m&&t1>t0){
			ans+=(t1<<i);
			mus+=(1<<i);
		}else{
			ans+=(t0<<i);
		}
	}
	cout<<ans;
	return 0;
}

反思

这种题型没见过，要积累。

最短Hamilton路径

思路

这是个模板题，就是一道DP

首先定义一个$f_{ij}$，$i$在这表示二进制，一就是走过了。$j$走到了第$j$个点

首先，枚举$i$和$j$，在判断，如果i第一位等于0，就不要，如果都没走到这个点，那么就不要，再接下来，枚举$K$更新数值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int a[N][N];
int f[1<<N][N];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	memset(f,0x3f,sizeof f);
	f[1][0]=0;
	for(int i=0;i<(1<<n);i++){
		if(i&1)
		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]+a[k][j]);
			}
		}
	}
	cout<<f[(1<<n)-1][n-1];
	return 0;
}

飞行员兄弟

思路

对于这种，我们可以将二维转化为一维，每一行相连接。chan数组存储改变这一个所需要加上多少数。再用$get$函数来计算二维转化成一维后的位置。

那么chan数组怎么算呢？为了全面，我们只能枚举$i,j$来保证全面。 之后计算改变横和竖所要加的多少（chan[i][j]+=1<<(get(i,k)); 和chan[i][j]+=1<<(get(k,j));，$k$是枚举横和竖中所有的位置）

然后，枚举全部方案，再比较。

代码

#include<bits/stdc++.h>
using namespace std;
int chan[6][6];
int get(int x,int y){
	return x*4+y;
}
int main(){
	int t=0;
	for(int i=0;i<4;i++){
		string u;
		cin>>u;
		for(int j=0;j<4;j++){
			if(u[j]=='+'){
				t+=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++){
				chan[i][j]+=1<<(get(i,k));
				chan[i][j]+=1<<(get(k,j));
			}
			chan[i][j]-=1<<(get(i,j));
		}
	}
	vector<pair<int,int>> ans;
	for(int i=0;i<(1<<16);i++){
		int now=t;
		vector<pair<int,int>>path;
		for(int j=0;j<16;j++){
			if(i>>j&1){
				int x=j/4;
				int y=j%4;
				now^=chan[x][y];
				path.push_back({x,y});
			}
		}
		if(!now&&(ans.size()==0||path.size()<ans.size())){
			ans=path;
		}
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++){
		cout<<ans[i].first+1<<" "<<ans[i].second+1<<endl;
	}
	return 0;
} 

递推和递归

费解的开关

思路

对于第一行，我们可以通过二进制来枚举，

而除第一行外都可以通过上一行来决断所以我们就此解决了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[10][10],p[10][10];
int dfx[10]={-1,0,0,1,0},dfy[10]={0,1,-1,0,0};
void dande(int i,int j){
	for(int o=0;o<=4;o++){
		int as=i+dfx[o],bs=j+dfy[o];
		if(as<1||as>5||bs<1||bs>5){
			continue;
		}
		if(a[as][bs]==0){
			a[as][bs]=1;
		}else{
			a[as][bs]=0;
		}
	}
}
int main(){
	int n;
	cin>>n;
	while(n--){
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				char u;
				cin>>u;
				p[i][j]=u-'0';
			}
		}
		long long po=0x3f3f3f3f;
		for(int sp=0;sp<=32;sp++){
			long long s=0;
			for(int i=1;i<=5;i++){
				for(int j=1;j<=5;j++){
					a[i][j]=p[i][j];
				}
			}
			for(int i=0;i<5;i++){ 
				if(sp>>i&1){
					s++;
				//	cout<<1<<" "<<i+1<<endl;
					dande(1,i+1);
				}
			}
			for(int i=1;i<5;i++){
				for(int j=1;j<=5;j++){
					if(a[i][j]==0){
						s++;
					//	cout<<i+1<<" "<<j<<endl;
						dande(i+1,j);
					}
				}
			}
			bool pw=0;
			for(int i=1;i<=5;i++){
				if(a[5][i]==0){
					pw=1;
					break;
				}
			}
			if(!pw&&s<=6){
				po=min(s,po);
			//	cout<<s<<endl;
			}
		//	cout<<endl;
		}
		if(po==0x3f3f3f3f){
			cout<<-1<<endl;
		}else{
			cout<<po<<endl;
		}
		
	}
	return 0;
}

奇怪的汉诺塔

思路

我们要选一部分分到第三柱，然后剩余的移到最后一柱，之后再移到最后一柱，这里耗费了f[i-j]+s[j]*2

所以就要枚举j

代码

#include<bits/stdc++.h> 
using namespace std;
int f[100];
int s[100];
int main(){
	memset(s,0x3f,sizeof s);
	f[1]=1;
	int n=12;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]*2+1;
	}
	s[0]=0;
	s[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<=i;j++){
			s[i]=min(s[j]*2+f[i-j],s[i]);
		}
	//	cout<<s[i]<<endl;
	}
	for(int i=1;i<=12;i++){
		cout<<s[i]<<endl;
	}
	return 0;
}

约数之和

对于一个大于1的整数，可以分解质因数，$a=p1^{k_1}*p2^{k_2}*······pn^{k_n}$，比如$180=2^2*3^2*5^1$。

$a^b=p1^{k1*b}*p2^{k2*b}···pn^{kn*b}$;

这里面约数的个数为$(k1+1)*(k2+1)*···(kn+1)$;

约数之和就为$(p1^0+p1^1+···p1^k1)*(p2^0+p2^1+···p2^{k2})*···(pn^0+pn^1+···pn^{kn})$

我们写一个sum递归函数计算来$p$的$0$~$k$次幂之和，如果$k$为$0$就返回1；如果k为偶数则有奇数个项，我们提取一个$p$出来就为$p*sum(p,k-1)+1$，这个1就是第一项$p^0$，注意这里的p可能太大，要对m取模最终结果也要取模；如果k不为0也不是偶数那就只能是奇数，此时有偶数个项，我们把后面一半的项提取$p^{k/2+1}$就和前半部分一样，这时我们提取公因式就得到$sum(p,k/2)*(1+p向m^{k/2+1}取余）$;这里怕p太大就先对m取模，$p^{k/2+1}$用快速幂计算就能快速得到结果。

代码

#include <bits/stdc++.h>
using namespace std;
const long long mod= 9901;
long long a,b;
long long por(long long a,long long b){
	long long p=1;
	while(b!=0){
		if(b%2==1){
			p=p*a%mod;
		}
		a=a*a%mod;
		b/=2;
	}
	return p;
}
long long sum(long long k,long long p){
	if(p==0){
		return 1;
	}
	long long e;
	if(p%2==1){
		e=((sum(k,(p-1)/2)%mod)*(1+por(k,(p+1)/2)%mod))%mod;
		return e;
	}else{
		e=((sum(k,(p-2)/2)%mod)*(1+por(k,p/2)%mod)+(por(k,p)%mod))%mod;
	//	cout<<"ans:"<<e<<"  uid:"<<p<<"  z:"<<2<<"  k:"<<k<<"  p:"<<p<<endl;
		return e;
	}
}
int main() {
	long long res=1;
	cin>>a>>b;
//	cout<<"res:"<<as<<endl;
	if(a==1||b==0){
		cout<<1;
		return 0;
	}
	if (a==0){
		cout<<0;
		return 0;
	}
	for(int i=2;i<=a;i++){
		if(a%i==0){
			int s=0;
			while(a%i==0){
				s++;
				a/=i;
			}
		//	cout<<"s:"<<s*b<<"res:"<<a<<"z:"<<i<<endl;
			res=res*sum(i,s*b)%mod;
		}
	}
	cout<<(res+mod)%mod<<endl;
	return 0;
}

前缀和差分

激光炸弹

思路

本体是一道纯暴力题目，枚举爆炸范围左上角每一个点，提前用二维前缀和来O(1)的时间求总共价值多少

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int s[N][N];
int main(){
	int n,r;
	cin>>n>>r;
	for(int i=1;i<=n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		s[++x][++y]+=w;
	}
	for(int x=1;x<=5001;x++){
		for(int y=1;y<=5001;y++){
			s[x][y]+=s[x-1][y]+s[x][y-1]-s[x-1][y-1];
		}
	}
	int ans=0;
	for(int x=1;x<=5001;x++){
		for(int y=1;y<=5001;y++){
			int x1=x-r+1,y1=y-r+1;
			x1=max(x1,1);
			y1=max(y1,1);
			ans=max(s[x][y]-s[x][y1-1]-s[x1-1][y]+s[x1-1][y1-1],ans);
		}
	}
	cout<<ans;
	return 0;
}

增减序列

思路

这道题目是一维差分的思维提升题

如果要所有数都一样，那么差分数组中的数值有什么共同点呢？

仔细想想吧！

是不是除了第一位，差分序列的剩余数值都是$0$呢？

这不难证明：设$s_i$为差分序列，$p_i$为原数组

$$s_i=p_i-p_{i-1}$$

为了$p$数组是答案，所以为了差分所以除$p_0$以外，$p$数组都是一样的，便可以证明出来

最后不推了，自己看代码

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long a[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>=1;i--){
		a[i]=a[i]-a[i-1];
	}
	long long u=0,o=0;
	for(int i=2;i<=n;i++){
		if(a[i]>0){
			u+=a[i];
		}
		if(a[i]<0){
			o-=a[i];
		}
	}
	cout<<min(o,u)+abs(o-u)<<endl;
	cout<<abs(o-u)+1;
	return 0;
}

最高的牛

思路

既然最高为$p$，那么我们就假设目前全为$p$ 那么将每队都统一一下格式：第一位小，第二位大。之后再去重，就处理好关系了。

重点来了！！

对于每一对关系，除了首和尾，其他的都减一，由于不可能出现交叉关系不然就构不成了

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4,M=1e4+10;
int a[N]; 
struct P{
	int a,b;
};
P ds[M];
bool cmp(P a,P b){
	if(a.a!=b.a){
		return a.a<b.a;
	}
	return a.b<b.b;
}
int main(){
	int n,h,p,m;
	cin>>n>>p>>h>>m;
	for(int i=1;i<=n;i++){
		a[i]=h;
	} 
	for(int i=1;i<=m;i++){
		cin>>ds[i].a>>ds[i].b;
		if(ds[i].a>ds[i].b){
			int k=ds[i].a;
			ds[i].a=ds[i].b;
			ds[i].b=k;
		}
	}
	sort(ds+1,ds+1+m,cmp);
	for(int i=1;i<m;i++){
		if(ds[i].a==ds[i+1].a&&ds[i].b==ds[i+1].b){
			ds[i+1]={0,0};
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=ds[i].a+1;j<ds[i].b;j++){
			a[j]--;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<endl;
	}
//	cout<<"______________"<<endl;
//	for(int i=1;i<=m;i++){
//		cout<<ds[i].a<<" "<<ds[i].b<<endl;
//	}
	return 0;
}

二分

防线

这道题（好老套）

思路

这题最大的暴露点，就是它：

只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。

那就说明，我们可以统计一段的总和，这样就可以判断这一段是否有破绽

$$奇数+偶数=奇数$$ $$偶数+偶数=偶数$$

这就意味着只要判断奇偶性就可以判断破绽

加上二分，结果就AC了

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
long long s[N],e[N],d[N];
int n;
struct P{
	int o;
	int p;
};
long long sr(long long x){
	long long num=0;
	for(int i=1;i<=n;i++){
		if(s[i]<=x){
			num+=(min(e[i],x)-s[i])/d[i]+1;
		}
	}
	return num;
}
long long cheek(long long l,long long r){
	long long num=sr(r)-sr(l-1);
	return num;
}
P opu(int l,int r){
	int p=0;
	while(r>l){
		int mid=l+r>>1;
	//	cout<<"l:"<<l<<"|r:"<<r<<"|mid"<<mid<<"|cheek"<<cheek(l,mid)<<endl;
		if(cheek(l,mid)%2==1){
			r=mid;
		}else{
			l=mid+1;
		}
		p=mid;
	}
//		cout<<"l:"<<l<<"|r:"<<r<<"|mid"<<p<<"|cheek"<<cheek(l,p)<<endl;
	return P{l,cheek(l,l)};
}
int main(){
	int T;
	cin>>T;
	while(T--){
		long long B=0,S=0x3f3f3f3f;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s[i]>>e[i]>>d[i];
			B=max(B,e[i]);
			S=min(S,s[i]);
		}
		if(cheek(S-1,B)%2==0){
			cout<<"There's no weakness."<<endl;
		}else{
			P kl=opu(S,B);
			cout<<kl.o<<" "<<kl.p<<endl;
		}
	}
	return 0;
} 

最佳牛围栏

思路

额，这道题虽然输出不知道什么意思作者**吧

但他提示了一个关键线索：用double!

然后我们最好二分答案，不然很难判断什么时候退什么时候进。

既然目标有了，那么如何写$cheek$呢？

我们知道，为了使结果变大在$i$不变的情况下，前缀数组$sum_j$应尽量小

这样枚举$i$，代码就做出来了

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
const double eps=1e-5;
double a[N],sum[N];
int n,f;
bool cheek(double mid){
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+(a[i]-mid);
	}
	double Min=0;
	for(int i=0,j=f;j<=n;j++,i++){
		Min=min(sum[i],Min);
		if(sum[j]-Min>=0){
			return 1;
		}
	}
	return 0;
}
int main(){
	double l=0,r=0;
	cin>>n>>f;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		r=max(r,(double)(a[i]));
	}
	while(l+eps<r){
		double mid=(l+r)/2;
		if(cheek(mid)) l=mid;
		else r=mid;
	}
	cout<<(int)(r*1000); 
	return 0;
}

赶牛入圈

思路

将每个格子的三叶草离散化。

之后，便可以二分边长，对于一个正方形，可以由一个矩形扩充而来，所以便可以无视正方形。边长二分好了后，就枚举左上角的x和y再在最大值（边长）得出右下角，最后判断。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,k;
int s[N][N];
vector<pair<int,int>> a;
vector<int> as;
int find(int x){
	int l=0,r=as.size()-1;
	while(l<r){
		int mid=l+r+1>>1;
		if(as[mid]<=x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return r;
}
bool check(int mid){
	for(int x1=1,x2=1;x2<as.size();x2++){
		while(as[x2]+1-as[x1]>mid) x1++;
		for(int y1=1,y2=1;y2<as.size();y2++){
			while(as[y2]+1-as[y1]>mid)y1++;
			if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]>=m){
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	cin>>m>>k;
	as.push_back(0);
	for(int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		n=max(n,x);n=max(n,y);
		as.push_back(x);
		as.push_back(y);
		a.push_back({x,y});
	}
	sort(as.begin(),as.end());
	as.erase(unique(as.begin(),as.end()),as.end());
	for(int i=0;i<k;i++){
		int x=find(a[i].first),y=find(a[i].second);
		s[x][y]++;
	}
	for(int i=1;i<as.size();i++){
		for(int j=1;j<as.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 mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<r;
	return 0;
} 

排序

电影

思路

我们直接统计每种语言会的人数，因为数太大，需要离散化。

统计之后，一个贪心判断就行

坑点：电影的字幕或者语音可能不在科学家会饿的语言当中

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=600010;
int a[N],w[N],t[N],alls[M],idx=0,f[M];
int find(int t){
	int l=0,r=idx;
//	cout<<r<<" "<<l<<" "<<idx<<endl;
	while(l<r){
		int mid=l+r>>1;
		if(alls[mid]>=t){
			r=mid;
		}else{
			l=mid+1;
		}
	//	cout<<"alls:"<<alls[mid]<<" l:"<<l<<" r:"<<r<<" mid:"<<mid<<" t:"<<t<<endl;
	}
	return r;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		alls[idx++]=a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i];
		alls[idx++]=w[i];
	}
	for(int i=1;i<=m;i++){
		cin>>t[i];
		alls[idx++]=t[i];
	}
	sort(alls,alls+idx);
	idx=unique(alls,alls+idx)-alls-1;
	for(int i=1;i<=n;i++){
		int x=find(a[i]);
		f[x]++;
	}
	int ans=0,Max_x=0,Max_y=0;
	for(int i=1;i<=m;i++){
		int x=find(w[i]),y=find(t[i]);
		if(f[x]>Max_x){
			ans=i;
			Max_x=f[x];
			Max_y=f[y];
		}
		if(f[x]==Max_x&&f[y]>Max_y){
			ans=i;
			Max_y=f[y];
		}
	}
	if(ans==0){
		cout<<1;
		return 0;
	}
	cout<<ans;
	return 0;
}

仓货选址

思路

一道基础题，狗都做得出来但我不是狗

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int k=a[n/2];
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=abs(a[i]-k);
	}
	cout<<ans;
	return 0;
}

七夕祭

思路

首先我们只要想一想就会发现只要用 t 去模 n和m 就能根据是否整除得到字符串输出是哪个。而且整除的结果就是最后移动后的均摊结果。

然后就可以发现这是个横向和纵向的均分纸牌有木有？

不加证明地给出行和列分别求就可以了不会影响，因为这一行的点互相交换并不会影响这一列的点的个数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
long long row[N],colu[N],b[N],c[N];
int n,m,t;
long long u(int n,long long a[]){
	long long sum=t,ans=0;
	if(sum%n){
		return -1;
	}
	long long avg=sum/n;
	for(int i=1;i<=n;i++){
		b[i]=a[i]-avg;
	}
	c[1]=0;
	for(int i=2;i<=n;i++){
		c[i]=b[i]+c[i-1];
	}
	sort(c+1,c+1+n);
	long long x=c[(n+1)/2];
	for(int i=1;i<=n;i++){
		ans+=abs(c[i]-x);
	}
	return ans;
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++){
		int x,y;
		cin>>x>>y;
		row[x]++;
		colu[y]++;
	}
	long long rows=u(n,row);
	long long colus=u(m,colu);
	if(rows!=-1&&colus!=-1){
		cout<<"both "<<(rows+colus);
		return 0;
	}
	if(rows!=-1){
		cout<<"row "<<rows;
		return 0;
	}
	if(colus!=-1){
		cout<<"column "<<colus;
		return 0;
	}
	cout<<"impossible";
	return 0;
}

动态中位数

思路

用对顶堆，一道模板（不是，这题不是排序吗）

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int s;
	cin>>s;
	while(s--){
		int o=0;
		priority_queue<int> big;
		priority_queue<int,vector<int>,greater<int>> small;
		int t,m;
		cin>>t>>m;
		cout<<t<<" "<<(m+1)/2<<endl;
		for(int i=1;i<=m;i++){
			int k=0;
			cin>>k;
			if(big.size()==0||k<=big.top()){
				big.push(k);
			}else{
				small.push(k);
			}
			if(big.size()>small.size()+1){
				small.push(big.top());
				big.pop();
			}
            if(small.size()>big.size()){
				big.push(small.top());
				small.pop();
			}
			if(i&1){
				cout<<big.top()<<" ";
				o++;
				if(o%10==0){
					cout<<endl;
				}
			}
		}
		if(o%10!=0){ 
			cout<<endl;
		} 
	}
	return 0;
} 

超快速排序

思路

这道题仔细观察就会发现，每做一次操作，都会减少一个逆序对

对此，只要求逆序对就可以啦！！

代码（圆神圣体者最爱）

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N], temp[N];
long long cnt=0;
void merge_sort(int l, int r) {
	if (l>=r) return;
	int mid = l+r>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i=l,j=mid+1,k=0;
	while (i<=mid&&j<=r) {
		if (a[i]<=a[j]) temp[k++]=a[i++];
	else temp[k++]=a[j++],cnt +=mid-i+1;
	}
	while (i<=mid) temp[k++]=a[i++];
	while (j<=r) temp[k++]=a[j++];
	for (i=l,j=0;i<=r;i++,j++)a[i]=temp[j];  
}
int main(){
	while(1){
		cnt=0;
		int n;
		cin>>n;
		if(n==0){
			return 0;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		merge_sort(1,n);
		cout<<cnt<<endl;
	}
	return 0;
}

奇数码问题

思路

我们定义一个网格的奇偶性为，其按顺序从左到右逐行扫描得到的数列中，其逆序对数的奇偶。

空格左右移动是不会更改奇偶性的。但空格上下移动就需要讨论了。

上下移动对于序列的影响就是，把x前移n-1次。若这n-1个数里，有a个比x小，b个比x大（不可能等于，且满足a+b = n-1），那么，初状态逆序对为b，末状态为a，相当于总体增加了a-b（若a<b则表明是减少）。

于是我们展开讨论

只要网格奇偶性相同，就可以互相转化。（奇偶性相同为充要条件，其必要性十分容易说明，但充分性...原谅我弱）

所以

n为奇数时较容易，因a，b同奇偶，则初状态逆序对数只要为偶，Yes；反之，No。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 250000;
int c[N], temp[N];
int a[N], b[N];
LL merge_sort(int l, int r, int a[]){
    if(l>=r) return 0;
    int mid=l+r>>1,i=l,j=mid+1,k=0;
    LL res=merge_sort(l,mid,a)+merge_sort(mid+1,r,a);
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]) temp[k++]=a[i++];
        else{
            res+=mid-i+1;
            temp[k++]=a[j++];
        }
    }
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];
    for(int i=l,j=0;i<=r;i++,j++) a[i]=temp[j];
    return res;
}
int main()
{
    int n;
    while(cin>>n){
        for(int i=0,j=0;i<n*n;i++) 
        {
            cin>>c[i];
            if(c[i])a[j++]=c[i];
        }
        for(int i=0,j=0;i<n*n;i++) 
        {
            cin>>c[i];
            if(c[i])b[j++]=c[i];
        }
        long long res1=merge_sort(0, n * n - 1,a);
        memset(temp,0,sizeof temp);
        long long res2=merge_sort(0,n*n-1,b);
        memset(temp,0,sizeof temp);
        if((res1 % 2) == (res2 % 2)) cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
    return 0;
}

糖果传递

七夕祭的简化版本

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N];
long long c[N];
int main(){
	int n;
	long long ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans+=a[i];
	}
	long long avg=ans/n,sum=0;
	for(int i=1;i<=n;i++){
		c[i]=c[i-1]+(a[i]-avg);
	//	cout<<c[i]<<" ";
	}
	sort(c+1,c+1+n);
	long long x=c[(n+1)/2];
	for(int i=1;i<=n;i++){
		sum+=abs(c[i]-x);
	}
	cout<<sum;
	return 0;
}

士兵

思路

又是七夕祭……，将每名士兵移到最好的$y$，之后紧紧相依。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int x[N],y[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	sort(x+1,x+1+n);
	for(int i=1;i<=n;i++){
		x[i]=x[i]-i;
	}
	sort(y+1,y+1+n);
	sort(x+1,x+1+n);
	int sx,sy;
	if(n%2==0) {
		sx=(x[n/2]+x[n/2+1])/2;
		sy=(y[n/2]+y[n/2+1])/2;
	}
	else{
		sx=x[n/2+1];
		sy=y[n/2+1];	
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=abs(x[i]-sx)+abs(y[i]-sy);
	}
	cout<<ans;
	return 0;
}

倍增

思路

艹！又是**ACM

倍增算法，用倍增来求他们的区间，实现AC

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
long long a[N],t[N];
long long n,m,k;
bool f(int l,int r){
	int kt=0;
	for(int i=l;i<r;i++){
		t[kt++]=a[i];
	}
	sort(t,t+kt);
	long long p=0;
	for(int i=0,j=kt;i<m&&j>i;i++,j--){
		p+=(t[j-1]-t[i])*(t[j-1]-t[i]);
	}
	if(p<=k){
		return 1;
	}else{
		return 0;
	}
}
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		int ed=0,st=0;
		long long ans=0;
		while(ed<n){
			int len=1;
			while(len!=0){
				if(ed+len<=n&&f(st,ed+len)){
					ed+=len;
					len*=2;
				}else{
					len/=2;
				}
			}
			st=ed;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
} 

贪心

股票买卖

思路

这一题让吾想起了炒股的人

这一道题，我们只需要判断，如果明天价值开始下降，今天就得卖出去；明天开始涨，今天就得买。

所以就跟统计图一样不要炒股！！

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N];
int main(){
	int n;
	long long gupiao=0,money=0;
	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]&&gupiao>0){
			money+=a[i];
			gupiao--;
		}
		if(a[i]<a[i+1]&&gupiao<1){
			gupiao++;
			money-=a[i];
	//		cout<<money<<" "<<a[i]<<" "<<a[i+1]<<endl; 
		}
		
	}
	cout<<money;
	return 0;
} 

出栏预定

思路

有空位就站，没有就加。每次让他进时间最小的茅坑

用堆来记录空位，这样就不会只记录最小值，让他敬请的吃

代码

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n,p=2;
struct P{
	int p,q,lastr;
};
P a[N],b[N];
int asd[N];
int as[N]; 
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int>> > Min;
bool cmp(P a,P b){
	return a.p<b.p;
}
void sdf(int u){
	if(u>n){
		return ;
	}
	if(a[u].p>Min.top().first){
		as[a[u].lastr]=Min.top().second;
		Min.pop();
		Min.push({a[u].q,as[a[u].lastr]});
		
	}else{
		as[a[u].lastr]=p;
		Min.push({a[u].q,p++});
	}
//	cout<<u<<endl;
	sdf(++u);
}
int main(){
	cin>>n;//怎么最快找到位置， 
	for(int i=1;i<=n;i++){
		cin>>a[i].p>>a[i].q;
		a[i].lastr=i;
	}
	sort(a+1,a+1+n,cmp);
	Min.push({a[1].q,1});
	as[1]=1;
	sdf(2);
	
	cout<<p-1<<endl;
	for(int i=1;i<=n;i++){
		cout<<as[i]<<endl;
	}
	return 0;
}

肺雾设备

思路

利用勾股定理将三维的⚪投射成在陆地上的一个线段，这个线段就是雷达可放置地。之后放在与其他线段重合的位置。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
pair<double,double> f[N];
int main(){
	int n,d;
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		if(y>d){
			cout<<-1;
			return 0; 
		}
		double len=sqrt(d*d-y*y);
		f[i]={x+len,x-len};
	}
	sort(f+1,f+1+n);
	double st=-1e10;
	int res=0;
	for(int i=1;i<=n;i++){
		if(f[i].second>st){
			res++;
			st=f[i].first;
		}
	}
	cout<<res;
	return 0;
}

肺雾游戏

思路

不要问怎么知道的，问就是老师试出来的

顺序就是$左手X右手$的数值从大到小排序

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct P{
	int a,b;
};
P s[N];
bool cmp(P a,P b){
	return a.a*a.b<b.a*b.b;
}
bool e(vector<int> a, vector<int> b) {
	if (a.size()==b.size()) {
		for(int i=a.size()-1;i>=0;i--)
			if (a[i] != b[i])
				return a[i] > b[i];
		return true;
	}
	return a.size() > b.size();
}
vector<int> chu(vector<int> A,int b) {
    vector<int> res;
    int t=0,r=0;
	r=0;
    for(int i=A.size()-1;i>=0;i--)
    {	
        t =r*10+A[i];//cout<<b;
		res.push_back(t/b);
        r=t%b;
	
    }
    reverse(res.begin(), res.end());
    
    while(res.size()>1 && res.back() == 0) res.pop_back();
    return res;
}
vector<int> cheng (vector<int> A, int b) {
    vector<int> res;
    int t=0;
    for(int i=i;i<A.size()||t;i++){
      	if(i<A.size()) t+=A[i]*b;
      	res.push_back(t%10);
      	t/=10;
    }
    while(res.size()>1&&res.back()==0) res.pop_back();
    return res;
}
int main(){
	int n,w;
	vector<int> ans,cnt;
	cin>>n;
	string a;
	cin>>a>>w;
	for(int i=a.size()-1;i>=0;i--){
		cnt.push_back(a[i]-'0');
	}
	for(int i=1;i<=n;i++){
		cin>>s[i].a>>s[i].b;
	}
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n;i++){
		vector<int> num;
		num=chu(cnt,s[i].b);
		if(e(num,ans)){
			ans=num;
		}
		cnt=cheng(cnt,s[i].a);
	}
	
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i];
	}
	return 0;
}

耍杂技的肺雾

思路

将$W+S$大的放上面，小的放下面

证明过程 假设$i$从上到下依次增加 假设$Wi+1+Si+1<Wi+Si$（第$i+1$层的$W+S$小于第$i$层

交换前: 

当是i时：W1+…Wi-1-Si
当是i+1时W1+…Wi-Si+1

交换后:

当是i时：$W1+…Wi-1-Si+1
当是i+1时：$W1+…Wi-1+Wi+1-Si

1.第i+1层的交换前>第i层的交换后（多了一个Wi）

2.第i+1层的交换前>第i+1层的交换后（需证明Wi+1-Si<Wi-Si+1）

根据Wi+1+Si+1<Wi+Si转化为Wi+1-Si<Wi-Si+1可以推出

综上所述：交换后都小于交换前的第i+1层，交换前的第i+1层小于等于整体交换前，所以交换后小于等于交换前。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
struct P{
	int w,s;
};
P a[N];
bool cmp(P a,P b){
	return a.s+a.w>b.s+b.w;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].s;
	}
	sort(a+1,a+1+n,cmp);
	long long ans=-0x3f3f3f3f,num=0;
	for(int i=n;i>=1;i--){
		ans=max(num-a[i].s,ans);
//		cout<<num<<" "<<a[i].s<<" "<<a[i].w<<endl;
		num+=a[i].w;
	}
	cout<<ans;
	return 0;
}

最大的和

思路

这题的一个做法是枚举矩形的上下界位置，接着借助前缀和数组快速计算一列的元素总和，将二维的数组转换成一维的数组，然后解决一个简单的连续子数组的最大和即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N],num[N][N],f[N],Max=-0x3f3f3f3f;
int main(){
	int n;
	cin>>n;
	//输入 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j]; 
		}
	}
	//处理列前缀和； 
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++){
			num[i][j]=num[i-1][j]+a[i][j];
		}
	}
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			f[0]=-0x3f3f3f3f;
			for(int k=1;k<=n;k++){
				int t=num[r][k]-num[l-1][k];
				f[k]=max(f[k-1]+t,t);
				Max=max(f[k],Max);
			}
		}
	} 
	cout<<Max;
	return 0;
}

任务

思路

由于$y$最多是100，所以先按$x$排序，再按$y$排序（可以保证利益最大化）

之后将可以的送进多重集合。

代码

//multiset
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	while(cin>>n>>m){
		pair<int,int> a[100000],b[100010];
		for(int i=1;i<=n;i++){
			cin>>a[i].first>>a[i].second;
		}
		for(int i=1;i<=m;i++){
			cin>>b[i].first>>b[i].second;
		}
		sort(a+1,a+1+n);
		sort(b+1,b+1+m);
		multiset<int> s;
		long long ans=0,cnt=0;
		for(int i=m,j=n;i>=1;i--)
        {
            while(j>=1&&b[i].first<=a[j].first) s.insert(a[j--].second);
            auto it=s.lower_bound(b[i].second);
            if(it!=s.end())
            {
                ans+=b[i].first*500+b[i].second*2;
                s.erase(it);
                cnt++;
            }
        }
		cout<<cnt<<" "<<ans<<endl;
	}
	return 0;
}

杂题

占扑

思路

模拟即可

代码

#include<bits/stdc++.h>
using namespace std;
char a[20][10];
int ans[15];
int le[15];
int get(char x)
{
    if(x == 'A') return 1;
    if(x == 'K') return 13;
    if(x == 'Q') return 12;
    if(x == 'J') return 11;
    if(x == '0') return 10;
    if (x>='2' && x<='9')
        return x-'0';
}
int main()
{
    memset(ans,0,sizeof ans);
    for(int i=1;i<=12;i++)
        le[i]=4;
    for(int i=1;i<=13;i++)
        for(int j=1;j<=4;j++)
            cin>>a[i][j];
    for(int i=1;i<=4;i++){
        int now=get(a[13][i]);
        while(now!=13){
            ans[now]++;
            now=get(a[now][le[now]--]);
        }
    }
    int res=0;
    for(int i=1;i<=12;i++)
        if(ans[i]==4) res++;
    cout<<res;
}

数的进制转换

思路

转换模板（不会上洛谷）

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int sr,sc;
string sa,sb;
int a[N],b[N];
void so(){
	sb.clear();
	int cnt=0,k=0,j=0;
	for(int i=0;i<sa.size();i++){
		if(sa[i]>='0'&&sa[i]<='9'){
			a[cnt++]=sa[i]-'0';
		}
		if(sa[i]>='A'&&sa[i]<='Z'){
			a[cnt++]=sa[i]-'A'+10;
		}
		if(sa[i]>='a'&&sa[i]<='z'){
			a[cnt++]=sa[i]-'a'+36;
		}
	}
	while(j<cnt){
		for(int i=j;i<cnt-1;i++){
			a[i+1]+=a[i]%sc*sr;
			a[i]/=sc;
		}
		b[k++]=a[cnt-1]%sc;
        a[cnt-1]/=sc;
        if(j<=cnt&&a[j]==0) ++j;
	}
	for(int i=k-1;i>=0;i--){
		sb+=(char)(b[k-i-1]<=9?b[k-i-1]+'0':(b[k-i-1]<=35?b[k-i-1]-10+'A':b[k-i-1]-36+'a'));
	}
	reverse(sb.begin(),sb.end());
	j=0;
    while(sb[j]=='0'&&j<k-1) ++j;
    cout<<sr<<" "<<sa<<endl;
    cout<<sc<<" ";
    for(j;j<k;++j){
        cout<<sb[j];
    }
    cout<<endl<<endl;
	return ;
}
void co(){
	
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>sr>>sc>>sa;
		so();
	}
	return 0;
}

栈

编辑器

两个栈代表左边和右边，模拟栈

代码

#include<bits/stdc++.h>
using namespace std;
const int Q=1e6;
int nleft[Q],nright[Q],ns[Q],s[Q];
int lt=0,rt;
int main(){
	int q;
	cin>>q;
	s[0]=-0x3f3f3f3f;
	while(q--){
		char t;
		int us;
		cin>>t;
		if(t=='I'){
			cin>>us;
			nleft[++lt]=us;
			ns[lt]=ns[lt-1]+us;
			s[lt]=max(s[lt-1],ns[lt]);
		}else if(t=='D'){
			if(lt>0){
				lt--;
			}
		}else if(t=='L'){
			if(lt>0){
				int p=nleft[lt];
				lt--;
				nright[++rt]=p;
			}
		}else if(t=='R'){
			if(rt>0){
				int p=nright[rt];
				rt--;
				nleft[++lt]=p;
				ns[lt]=ns[lt-1]+p;
				s[lt]=max(s[lt-1],ns[lt]);
			}
		}else{
			cin>>us;
			cout<<s[us]<<endl;
		}
	}
	return 0;
} 

直方图中最大的矩形

思路

5

4 4

3 3 3 3

2 2 2 2 2

1 1 1 1 1 1 1 加粗部分为最大

该题为单调栈的经典例题，我的代码太丑了，附书上解法。

再说一下单调栈的思路，我们需维护栈的单调性，如本题我们需要保证矩形高度单调递增；

若当前枚的高度小于栈顶元素，则栈顶弹出，统计一遍答案…直到枚的高度大于等于于栈顶元

素。至于为什么栈顶可弹出且答案确定自己可以想想。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
long long h[N];
long long n,t=-1;
long long Max=-0x3f3f3f3f; 
long long l[N],r[N],stk[N];
int main(){
	while(1){
		Max=-0x3f3f3f3f;
		cin>>n;
		if(n==0){
			break;
		}
		for(int i=1;i<=n;i++){
			cin>>h[i];
		}
		h[0]=h[n+1]=-1; 
		t=-1;
		stk[++t]=0;
		for(int i=1;i<=n;i++){
			while(h[stk[t]]>=h[i]){
				t--;
			}
			l[i]=i-stk[t]; 
			stk[++t]=i;	
		}
		t=-1;
		stk[++t]=n+1;
		for(int i=n;i>=1;i--){
			while(h[stk[t]]>=h[i]){
				t--;
	 		}
			r[i]=stk[t]-i; 
			stk[++t]=i;	
		}
		for(int i=1;i<=n;i++){
			Max=max(Max,(long long)(h[i]*(l[i]+r[i]-1)));
		}
		cout<<Max<<endl;
	}
	return 0;
} 

火车进出站

思路

分析： 这道题n的数值太大，用dfs是过不了的，为此我就想着直接算出有多少种情况，假如规定 1 表示栈中进入一节车厢，0 表示栈中弹出一节车厢，那么每种火车进出栈方案都能用一串 01 序列来表示。 由于每节车厢都要进栈一次出栈一次，所以每种方案所对应的 01 序列的长度都是 2n。 那么火车进出栈方案的总数量就可以看成是所有合法的 01 串的个数。

现在我们来想一下什么样的01串是合格的，我们要知道的是栈中有车厢才能弹出，所以在任意位置，其前面的 1 的个数大于等于其前面 0 的个数。

这里就转化成了求卡特兰数问题（这个大家有兴趣的可以看一下如何推导）

你以为这道题就这样结束了，大错特错！！！如是进入了更恶心的环节，n的阶乘和$(2*n)$的阶乘都太大了！！！因此我们只能用一种可以在数据不超范围的情况下求阶乘的方法，这里我们是吧

$(2*n)$的阶乘和n的阶乘全部质因式分解，相同的因式全部消掉，这里用到的方法参考我的这道题阶乘分解。

然而！！！这样还不行哭了哭了，因为最后的结果还是很大不能让剩下的数直接相乘，这里我用到了vector来存储每一位数字，每次相乘的时候拿出一位相乘，这是一种高精度相乘的方式，具体可以看代码中的mul（）函数，但尽管我这样写了又报了超时的错！！！！

姐妹们兄弟们，如果你们能看到这里，我敬你们是条汉子，又报错了我该怎么办呢，我原本是用vector数组每个值都只存了一位数字，于是我让它们都存了八位，你以为这样过了？

nonono还有最后一丢丢丢错误，哎！！字字全是血泪，在输出的时候除了数组的最后一位，其他记得不够八位的补0，这个大家知道为什么把，最后一位中的八位数是整个数的最前面的数，前缀的0可以不要，但其他的八位数都是中间的，所以0不能省略！！！

代码

#include <bits/stdc++.h>
 
using namespace std;
const int N=120010,mod=1e8;
int st[N],prim[N],nu[N];
int cnt;
int n;
vector<long long> ans;
void func(int x)
{
    for(int i=2;i<x;i++)
    {
        if(st[i]) continue;
        for(int j=2;j*i<=x;j++) st[j*i]=1;
    }
    for(int i=2;i<=x;i++)
    {
        if(!st[i]) prim[++cnt]=i;
    }
}
vector<long long> mul(vector<long long> an,int x)
{
    vector<long long>te;
    long long t=0;
    for(int i=0;i<an.size();i++)
    {
        t+=an[i]*x;
        te.push_back(t%mod);
        t/=mod;
    }
    while(t)
    {
        te.push_back(t%mod);
        t/=mod;
    }
    return te;
}
int main()
{
    cin>>n;
    func(2*n);
    for(int i=1;i<=cnt;i++)
    {
        int k=2*n;
        int num=0;
        while(k)
        {
            k/=prim[i];
            num+=k;
        }
        nu[prim[i]]=num;
    }
 
    for(int i=1;i<=cnt&&prim[i]<=n;i++)
    {
        int k=n;
        int num=0;
        while(k)
        {
            k/=prim[i];
            num+=k;
        }
        nu[prim[i]]-=2*num;
    }
    int k=n+1;
    for(int i=1;i<=cnt&&prim[i]<=k;i++)
    {
        int num=0;
        while(k%prim[i]==0)
        {
                num++;
                k/=prim[i];
        }
        nu[prim[i]]-=num;
    }
    ans.push_back(1);
    for(int i=1;i<=2*n;i++)
    {
        while(nu[i]--) ans=mul(ans,i);
    }
    
    printf("%lld",ans.back());
    for(int i=ans.size()-2;i>=0;i--) printf("%08lld",ans[i]);
    return 0;
}