伍衍的博客
总结
伍衍 LV2 金丹期 LV 2 @ 2025-4-15 20:32:20

$T1$ $a$ ^ $b$

思路：

标准的快速幂模版题，直接写就行了。

代码：

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

$T2$ 增加模数

思路：

和上题一样，就是多个快速幂加在一起，每一个都对 $m$ 取模，最后加起来再取一次模即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int qmi(int a,int b,int p){
    int ans=1; 
    while(b){
        if(b&1) ans=ans*a%p;
        b/=2;
        a=a*a%p;
    }
    return ans%p;
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        int m,h;
        cin >> m >> h;
        int cnt=0;
        for(int i=1;i<=h;i++){
            int a,b;
            cin >> a >> b;
            cnt+=qmi(a,b,m);
        }
        cout << cnt%m << endl;
    }
}

$T3$ $64$ 位整数乘法

思路：

本题是快速幂的变体，只不过把乘号变成了加号。（~~高精度也可以，但不建议食用~~）

代码：

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

$T4$ 起床困难综合症

思路：

首先用一个全 $1$ 数和一个全 $0$ 数计算每一位在初始是 $0$ 或 $1$ 的情况下最终会变成 $0$ 还是 $1$ ，如果从 $0$ 变成 $1$ ，则直接加入 $ans$ ；若从 $1$ 变成 $1$ 且初始伤害加上这一位后小于 $m$ ，则也加入，否则不加入。最后输出结果即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
        int n,m;
        cin >> n >> m;
        int a=0,b=(1>>30)-1;
        for(int i=1;i<=n;i++){
                string op;
                int t;
                cin >> op >> t;
                if(op=="AND") a&=t,b&=t;
                else if(op=="OR") a|=t,b|=t;
                else a^=t,b^=t;
        }
        int ans=0,ys=0;
        for(int i=30;i>=1;i--){
                int f=1<<i-1;
                if(a&f) ans+=f;
                else if(b&f&&ys+f<=m) ans+=f,ys+=f;
        }
        cout << ans;
}

$T5$ 最短 $Hamilton$ 路径

思路：

状压 DP:

状态表示：f[i][j] 表示点集为 $i$ ，最终到达 $j$ 的状态。

属性： $min$

状态计算：f[i][j]=min(f[i][j],f[i^1<<j][k]+a[k][j])

代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int a[20][20];
int f[1<<20][20];
signed 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];
}

$T6$ 飞行员兄弟

思路

1.枚举所有开关操不操作，转为二进制。

2.将初始状态存入二进制。

3.预处理每一位变化后的结果，用change数组存储，到时候直接 $xor$ 。

4.开始枚举，并不断更新答案。

代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int cg[10][10];
int st=0;
int get(int x,int y){
	return (4*x)+y;
}
int mul(int a,int b){
	return (a+b-1)/b;
}
int main(){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			char c;
			cin >> c;
			if(c=='+') 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++){
				cg[i][j]+=(1<<get(i,k))+(1<<get(k,j));
			}
			cg[i][j]-=1<<get(i,j);
		}
	}
	vector<PII> ans;
	for(int i=0;i<(1<<16);i++){
		int st2=st;
		vector<PII> path;
		for(int j=0;j<16;j++){
			if(i>>j&1){
				st2^=cg[j/4][j%4];
				path.push_back({j/4,j%4});
			}
		}
		if(st2==0&&(ans.empty()||ans.size()<path.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;
}

$T1$ 递归实现指数型枚举

思路：

递归模版

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int flag[50];
int n;
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++){
            if(flag[i]==1) cout << i << " ";
        }
        cout << endl;
        return;
    }
    flag[u]=1;
    dfs(u+1);
    flag[u]=0;
    dfs(u+1);
}
signed main(){
    cin >> n;
    dfs(1);
}

$T2$ 递归实现组合型枚举

思路：在上题基础上，限制答案数量即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
vector<int> A;
void dfs(int u){
    if(A.size()==m){
        for(int i=0;i<A.size();i++){
            cout << A[i] << " ";
        }
        cout << endl;
        return;
    }if(u>n) return;
    A.push_back(u);
    dfs(u+1);
    A.pop_back();
    dfs(u+1);
}
signed main(){
    cin >> n >> m;
    dfs(1);
}

$T3$ 递归实现排列型枚举

思路：

上一题的加强版，对于每一个数都要进行一次递归。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int flag[55];
vector<int> s;
void dfs(int u){
    if(u>n){
        for(int i=0;i<n;i++){
            cout << s[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(flag[i]==0){
            flag[i]=1;
            s.push_back(i);
            dfs(u+1);
            s.pop_back();
            flag[i]=0;
        }
    }
}
signed main(){
    cin >> n;
    dfs(1);
}

$T4$ 费解的开关

思路：

用一次DFS枚举出从初始状态到每个状态要多少步，询问时直接调用答案。

代码：

#include <bits/stdc++.h>
#define int long long
#define qwq ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n";
using namespace std;
const int N=(1<<25)+10;
bool a[10][10];
short ans[N];
int n=5;
void fan(bool &a){
    a=!a;
}
int get_num(bool a[10][10]){
    int num=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            num=num*2+a[i][j];
        }
    }
    return num;
}
void dfs(bool a[10][10],int x,int y,int step){
    int num=get_num(a);
    if(ans[num]<=step) return;// 早就可以完成了，无需DFS
    ans[num]=step;
    if(step>=6) return;// 为什么等于6也要停止呢？因为6在前面已经赋值过了，接下来无需再算
    for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		{
			if(i==x&&j==y) continue;
			fan(a[i][j]),fan(a[i-1][j]),fan(a[i+1][j]),fan(a[i][j-1]),fan(a[i][j+1]);
			dfs(a,i,j,step+1);
            fan(a[i][j]),fan(a[i-1][j]),fan(a[i+1][j]),fan(a[i][j-1]),fan(a[i][j+1]);
		}
    }
}
signed main(){
    qwq;
    memset(ans,0x3f,sizeof ans);
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            a[i][j]=1;
        }
    }
    dfs(a,-1,-1,0);// 找出每个状态需要多少步
    int t;
    cin >> t;
    while(t--){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char c;
                cin >> c;
                a[i][j]=c-'0';
            }
        }
        int num=get_num(a);
        if(ans[num]==0x3f3f){
            cout << -1 << endl;
        }else{
            cout << ans[num] << endl;
        }
    }
}

$T5$ 奇怪的汉诺塔

思路（正常）：

对于三塔问题，我们知道 $t_i=2*t_{i-1}+1=2^i-1$ 。

那么对于四塔问题：我们要移动 $i$ 个盘子，那么要先把 $j$ 个盘移动到B柱，再将剩下的 $i-j$ 个盘子用三柱移动到柱盘，最后将 $j$ 个盘子移到D柱。

即 $f_i=min \{{2*f_j+t_{i-j}}_{(1<=j<i)}\}$

思路（玄学找规律做法）：

首先 $f_0=0$ 接下来的一个 $+1$ ,两个 $+2$ ,三个 $+4$ ，以此类推。

代码（正常）：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t[15],f[15];
signed main(){
	t[1]=f[1]=1;
	for(int i=2;i<=12;i++) t[i]=t[i-1]*2+1;
	cout << 1 << endl;
	for(int i=2;i<=12;i++){
		int mn=2e9;
		for(int j=1;j<i;j++){
			mn=min(mn,f[j]*2+t[i-j]);
		}
		f[i]=mn;
		cout << f[i] << endl;
	}
}

代码（找规律）：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int flag[13]={0,1,3,5,9,13,17,25,33,41,49,65,81};
signed main(){
    for(int i=1;i<=12;i++){
        cout << flag[i] << endl;
    }
}

$T6$ 约数之和

思路：建立递归函数 dfs(a,b)=a^0+a^1+a^2+...+a^b

当 $b$ 为奇数时，可以套公式，dfs(a,b)=dfs(a,b/2)*(1+qmi(a,b/2+1)) 。

偶数时也能套公式，但最好直接转为奇数，即 dfs(a,b)=dfs(a,b-1)*a+1 。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=9901;
int ans=1;
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b/=2;
		a=a*a%mod;
	}
	return res;
}
int dfs(int a,int b){
	if(!b) return 1;//a^0=1,递归终止 
	//if(b%2==1) dfs(a,b)=(a^0+a^1+...+a^b)=(a^0+a^1+...+a^b/2)+a^(b/2+1)*(a^0+a^1+...+a^b/2)=dfs(a,b/2)*(1+a^(b/2+1))
	if(b&1) return (dfs(a,b/2)*(1+qmi(a,b/2+1)))%mod;
	//else dfs(a,b)=dfs(a,b-1)*a+1 原因见讲义
	return (dfs(a,b-1)*(a%mod)+1)%mod; 
}
signed main(){
    int a,b;
    cin >> a >> b;
    if(!a){
    	cout << 0;
    	return 0;
    }
    for(int i=2;i<=a/i;i++){
    	if(a%i!=0) continue;
    	int cnt=0;
    	while(a%i==0){
    		a/=i;
    		cnt++;
		}
		ans*=dfs(i,cnt*b);// dfs(a,b) 表示 a^0+a^1+...+a^b 
		ans%=mod;
	}
	if(a>1) ans*=dfs(a,b);
	ans%=mod;
	cout << ans;
}

$T7$ 分形之城

首先，我们知道，求距离非常简单，最难得点是求出两个编号的坐标。那么怎么求坐标呢，我们可以用DFS求。

边界：到最后一层（等级为1的子城市）时，返回(0,0)。

递归：传入两个参数：等级和编号。每次递归等级-1，编号模cnt(cnt表示等级-1层的街区总数)。那么如何处理递归的答案，即把上一等级的位置转移到本层呢？

处理（大重点）:首先，如果在左上角，则是沿着对角线\翻转，只需让x,y颠倒即可。

如果在右上角，则让y增加len,左上角则将x,y均增加len。(len表示上一个等级的边长)

如果在左下角，则是沿着对角线/翻转，变为len-y-1和len-x-1。（具体原因可自己画图推理）~~（还好不是长方形）~~ 而由于往下移了，所以x坐标要在增加一个len。

代码：

#include <bits/stdc++.h>
#define x first
#define y second
typedef long long ll;
using namespace std;
ll sq(ll x){
    return x*x;
}
pair<ll,ll> get(ll n,ll m){
    if(!n) return make_pair(0,0);
    ll len=1ll<<(n-1),cnt=1ll<<(2*(n-1));
    pair<ll,ll> ans=get(n-1,m%cnt);
    ll x=ans.first,y=ans.second;
    ll s=m/cnt;
    if(s==0) return make_pair(y,x);
    else if(s==1) return make_pair(x,y+len);
    else if(s==2) return make_pair(x+len,y+len);
    else return make_pair(2*len-y-1,len-x-1);
}
signed main(){
    ll t;
    cin >> t;
    while(t--){
        ll n,a,b;
        cin >> n >> a >> b;
        pair<ll,ll> wza,wzb;
        double ans=0;
        wza=get(n,a-1);
        wzb=get(n,b-1);
        ll x=abs(wza.first-wzb.first),y=abs(wzb.second-wza.second);
        ans=sqrt(sq(x)+sq(y))*10;
        printf("%.0f\n",ans);
    }
}

$T8$ 分形

思路：由于数据不大，可以直接用一个800*800的数组模拟即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
bool a[800][800];
int dfs(int u,int x,int y){//自身是左上角 
	if(u==1){
		a[x][y]=1;
		return 1;
	}
	int cd=dfs(--u,x,y);//确定间隔数 
	u++;
	dfs(--u,x,y+cd+cd);//递归右上角
	u++;
	dfs(--u,x+cd,y+cd);//递归中间
	u++;
	dfs(--u,x+cd+cd,y);//递归左下角
	u++;
	dfs(--u,x+cd+cd,y+cd+cd);//递归右下角 
	u++;
	return cd*3;//返回间隔数 
}
signed main(){
    int n;
    while(1){
        cin >> n;
        if(n<0) return 0;
        memset(a,0,sizeof a);
        int cd=dfs(n,1,1);
        for(int i=1;i<=cd;i++){
        	for(int j=1;j<=cd;j++){
        		if(a[i][j]) cout << "X";
        		else cout << " ";
			}
			cout << endl;
		}
		cout << "-\n";
    }
}

$T1$ 激光炸弹

思路：先用前缀和，然后直接暴力即可（数据水）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int a[N][N];
int main(){
	int n,r;
	cin >> n >> r;
	if(r>5001) r=5001;//题目中的下标从 0 开 始，所以最大坐标为 5001 
	for(int i=1;i<=n;i++){
		int x,y,w;
		cin >> x >> y >> w;
		a[++x][++y]+=w;
	}
	int mxx=5001;
	for(int i=1;i<=mxx;i++){
		for(int j=1;j<=mxx;j++){
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	int mx=0;
	for(int i=r;i<=mxx;i++){
		for(int j=r;j<=mxx;j++){
			mx=max(mx,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
		}
	}
	cout << mx;
}

$T2$ 增减序列

思路：差分题变型（带有亿丢丢的数学）

看完应该都知道要用差分吧。

首先，我们要明白，当数组数字一样时，差分数组是怎样的，应该是除了第一个数，其余的数都为0。于是，我们的题目就变成了：给定n个数，每次选两个数一加一减，最后让除了第一个数以外，其他数都变为0。

那我们怎么做呢？首先，我们额外创造一个b[n+1]，模拟从i加到n的情况。（加下来思路忽略b[1]）首先，如果有一正一负，那么肯定要正加负减，最后肯定只剩下min(z,f)个数字(z表示正数和，f表示负数和的绝对值)，他们再单独与b[1]或b[n+1]加减，就产生了abs(p-q)+1种可能(从全与b[n+1]匹配到全与b[1]匹配)，总共需要min(p,q)+abs(p-q)=max(p,q)次，有abs(p-q)+1种可能。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N],b[N];
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        b[i]=a[i]-a[i-1];
    }
    int z=0,f=0;
    for(int i=2;i<=n;i++){
        if(b[i]<0) f-=b[i];
        else z+=b[i];
    }
    cout << max(z,f) << endl << abs(z-f)+1;
}

$T3$ 最高的牛

思路：一开始所有牛身高都为h，每给一条信息就将A,B中间牛身高都减一即可（用差分）。注意去重

代码：

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> mp;
const int N=1e4+50;
int q[N],q2[N];
int main()
{
    int n,p,h,m;
    cin >> n >> p >> h >> m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        if(a>b) swap(a,b);
        if(mp[make_pair(a,b)]) continue;
        q2[a+1]--;
        q2[b]++;
        mp[make_pair(a,b)]=1;
    }
    for(int i=1;i<=n;i++)
    {
        q[i]=q[i-1]+q2[i];
        cout << h+q[i] << endl;
    }
    return 0;
}

$T1$ 防线

思路：首先，这题既然要二分，就一定有二段性，那么我们就可以用前缀和来做，这样就可以让弱点前面都是偶数，弱点后面都是奇数。

由于数据过大，我们不能直接直接预处理，而是用一个函数算出每组防具在x前面有多少个，最后直接二分即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define qwq ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
using namespace std;
const int N=2e5+50;
int n;
struct P{
    int s,e,d;
};
P a[N];
int get(int x){ // 数组存不下，所以用前缀和函数
    int sum=0;
    for(int i=1;i<=n;i++){
        // 算出x前面一共有多少个防具
        if(a[i].s<=x) sum+=(min(x,a[i].e)-a[i].s)/a[i].d+1; // 取min是因为防具位置可能没到x，至于+1，请参考植树问题
    }
    return sum;
}
bool check(int mid){
    return get(mid)%2;
}
signed main(){
    qwq;
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=1;i<=n;i++){
            int aa,b,c;
            cin >> aa >> b >> c;
            a[i].s=aa;
            a[i].e=b;
            a[i].d=c;
        }
        int l=0,r=(1ll<<31)-1;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        int ans=get(l)-get(l-1);// ans表示l有多少个防具，跟前缀和同理
        if(ans%2){
            cout << l << " " << ans << endl;
        }else{
            cout << "There's no weakness." << endl;
        }
    }
}

$T2$ 最佳牛围栏

思路：直接二分答案，每次找出最大平均值是大于mid还是小于mid，最后输出即可。

小技巧：算前缀和时可以直接将所有a[i]减mid，方便直接判断。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
double a[N];
double s[N];
int n,f;
bool check(double mid){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+(a[i]-mid);// 为什么减mid呢？因为mid表示平均值，全减mid后还大于0表示平均值>mid，反之亦然
    }
    double mn=0;
    for(int j=f;j<=n;j++){
    	mn=min(mn,s[j-f]);
        if(s[j]-mn>=0) return 1;
    }
    return 0;
}
signed main(){
    cin >> n >> f;
    double r;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        s[i]=s[i-1]+a[i];
        r=max(r,a[i]);
    }
    double l=1e-8;
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout << (int)(r*1000);//注意是 r 不是 l 
}

$T3$ 赶牛入圈

思路：先离散化所有的下标，再二分答案即可，其中check要用前缀和维护边长。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
vector<int> lsh;
int s[N][N];
int c,n;
pair<int,int> a[N];
//由于下标有序，所以离散函数get_zb直接用二分查找即可
int get_zb(int x){
    int l=0,r=lsh.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(lsh[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
bool check(int mid){
    for(int x1=1,x2=1;x2<lsh.size();x2++){
        while(lsh[x2]-lsh[x1]+1>mid) x1++;
        for(int y1=1,y2=1;y2<lsh.size();y2++){
            while(lsh[y2]-lsh[y1]+1>mid) y1++;
            if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]>=c) return 1;
        }
    }
    return 0;
}
signed main(){
    cin >> c >> n;
    lsh.push_back(0);
    for(int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
        lsh.push_back(a[i].first);
        lsh.push_back(a[i].second);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    for(int i=1;i<=n;i++){
        int x=get_zb(a[i].first),y=get_zb(a[i].second);
        // 以上均是离散化模板
        s[x][y]++;
    }
    for(int i=1;i<lsh.size();i++){
        for(int j=1;j<lsh.size();j++){
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
        }
    }
    int l=1,r=10000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
	cout << l;
}

$T1$ 电影

思路（卡常）：用map统计每个电影让多少人很开心，多少人较开心，最后排序即可。（关输入输出流可以直接卡常过）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct P{
	int love,like,num;
};
const int N=2e5+50;
P a[N];
unordered_map<int,int> mp;
bool cmp(P a,P b){
	if(a.love==b.love) return a.like>b.like;
	return a.love>b.love;
}
signed 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++){
		int yy;
		cin >> yy;
		mp[yy]++;
	}
	cin >> m;
	for(int i=1;i<=m;i++){
		a[i].num=i;
	}
	for(int i=1;i<=m;i++){
		int yy;
		cin >> yy;
		a[i].love=mp[yy];
	}for(int i=1;i<=m;i++){
		int yy;
		cin >> yy;
		a[i].like=mp[yy];
	}
	sort(a+1,a+n+1,cmp);
	cout << a[1].num;
}

$T2$ 货仓选址

思路：选中间（偶数则看心情选一个），然后绝对值相加。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N];
signed main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	int z=n/2+1,cnt=0;
	for(int i=1;i<=n;i++){
		if(i==z) continue;
		cnt+=abs(a[z]-a[i]);
	}
	cout << cnt;
}

$T3$ 七夕祭

思路：横竖均为环形均分纸牌问题，具体分析方法见小蓝书 (《算法竞赛进阶指南》) P37-39页。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
int col[N],row[N];
int b[N];
int n,m,t;
int get(int n,int a[]){
    if(t%n) return 2e9;
    int pj=t/n,ans=0;
    for(int i=2;i<=n;i++){
        b[i]=b[i-1]+a[i]-pj;//换了一种形式写，本质不变
    }
    sort(b+1,b+n+1);
    int mid=(n+1)/2;
    for(int i=1;i<=n;i++) ans+=abs(b[mid]-b[i]);
    return ans;
}
signed main(){
    cin >> n >> m >> t;
    for(int i=1;i<=t;i++){
        int x,y;
        cin >> x >> y;
        row[x]++,col[y]++;
    }
    int a=get(n,row),b=get(m,col);
    if(a!=2e9&&b!=2e9) cout << "both " << a+b;
    else if(a!=2e9) cout << "row " << a;
    else if(b!=2e9) cout << "column " << b;
    else cout << "impossible"; 
}

$T4$ 动态中位数

思路：对顶堆

用两个堆，小根堆存储大的那一半数，大根堆存储小的那一半数。

每次插入时，通过和两个堆的堆顶比较确定进哪个堆，优先进大根堆（小的那一半），要输出时输出大根堆堆顶（也可以输出小根堆堆顶，但是要优先进小根堆）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int t;
	cin >> t;
	while(t--){
		priority_queue<int> q;
		priority_queue<int,vector<int>,greater<int> > q2;
		int n,m;
		cin >> n >> m;
		cout << n << " " << (m+1)/2 << endl;
		int cnt=0;
		for(int i=1;i<=m;i++){
			int x;
			cin >> x;
			q2.push(x);
			if(q.size()&&q.top()>q2.top()){
				int a=q.top(),a2=q2.top();
				q.pop(),q2.pop();
				q2.push(a),q.push(a2);
			}
			if(q2.size()>q.size()+1){
				q.push(q2.top());
				q2.pop();
			}
			if(i%2==1){
				cout << q2.top() << " ";
				if(++cnt%10==0) cout << endl;
			}
		}
		if(cnt%10) cout << endl;
	}
}

$T5$ 超快速排序

思路：求逆序对原题

代码：有展示的必要吗？

$T6$ 奇数码问题

思路：

直接记性质吧：两个互通的奇数码局面，逆序对的奇偶性相同

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=503;
int q[N*N],q2[N*N],temp[N*N];
long long ans;
void merge_sort(int q[],int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j]){
			temp[k]=q[i];
			k++;i++;
		}else{
			temp[k]=q[j];
			k++;j++;
			ans+=mid-i+1;
		}
	}
	while (i<=mid) temp[k++]=q[i++];
	while (j<=r) temp[k++]=q[j++];
	for(int i=l,j=0;i<=r;i++,j++){
		q[i]=temp[j];
	}
}
int main(){
	ios::sync_with_stdio(0);
//	cin.tie(0);
	cout.tie(0);
	int n;
	while(cin >> n){
		if(n==1){
			int a,b;
			cin >> a >> b;
			cout << "TAK\n";
			continue;
		}
		int f=0;
        for(int i=1;i<=n*n;i++){
        	int x;
            cin >> x;
            if(x==0) f=1;
            else q[i-f]=x;
        }
        f=0;
        for(int i=1;i<=n*n;i++){
        	int x;
            cin >> x;
            if(x==0) f=1;
            else q2[i-f]=x;
        }
		ans=0;
        for(int i=0;i<=N*N-1;i++){
        	temp[i]=0;
		}
        merge_sort(q,1,n*n-1);
        long long num1=ans;
        ans=0;
        for(int i=0;i<=N*N-1;i++){
        	temp[i]=0;
		}
        merge_sort(q2,1,n*n-1);
        long long num2=ans;
        ans=0;
        if((num1&1)==(num2&1)) cout << "TAK\n";
        else cout << "NIE\n";
	}
}

$T7$ 糖果传递

思路：和七夕祭一样，看小蓝书去。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000050],s[1000050],t,c[1000050];
int get(int n,int a[]){
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	long long pj=t/n,ans=0;
	for(int i=1;i<=n;i++) c[i]=s[i-1]-(i-1)*pj;
	sort(c+1,c+n+1);
	int mid=(n+1)/2;
	for(int i=1;i<=n;i++) ans+=abs(c[mid]-c[i]);
	return ans;
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        t+=a[i];
    }
    cout << get(n,a);
}

$T8$ 士兵

思路：y轴直接货仓选址，x轴由于是站成一排，所以每个a[i]减去i。要记住，减完还要再排一次序

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+50;
int x[N],y[N],n;
signed main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x[i] >> y[i];
	}
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);
    for(int i=1;i<=n;i++){
        x[i]-=i-1;
    }
    sort(x+1,x+n+1);
    int mid=(n+1)/2,ans=0;
    for(int i=1;i<=n;i++){
        ans+=abs(x[i]-x[mid])+abs(y[i]-y[mid]);
    }
    cout << ans;
}

$T1$ 天才ACM

思路：倍增枚举分段即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+50;
int n,m,k;
int ans;
int a[N],s[N];
int sq(int x){
    return x*x;
}
int check(int l,int r){
    int idx=0;
    for(int i=l;i<r;i++){
        s[idx++]=a[i];
    }
    sort(s,s+idx);
    int sum=0;
    for(int i=0;i<m&&i<idx;i++,idx--){
        sum+=sq(s[i]-s[idx-1]);
    }
    return sum;
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        ans=0;
		int bg=0,ed=0;
        while(ed<n){// 纯纯的倍增
            int cd=1;
            while(cd){
                if(ed+cd<=n&&check(bg,ed+cd)<=k){
                    ed+=cd;
                    cd<<=1;
                }else cd>>=1;
            }
            bg=ed;
            ans++;
        }
        cout << ans << endl;
    }
}

$T1$ 股票买卖

思路：卖法：峰值卖，谷值买。巧算：只要a[i]>a[i+1],就把ans加上a[i]-a[i+1]（我没用巧算）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N];
struct P{
    int x,y;
};
vector<P> b;
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
    	int j=i+1;
        while(a[j-1]<a[j]&&j<=n) j++;
        if(i!=j-1) b.push_back(P{a[i],a[j-1]});
        i=j-1;
	}
    int sum=0;
    for(int i=0;i<b.size();i++){
        sum+=b[i].y-b[i].x;
    }
    cout << sum;
}

$T2$ 防晒

思路：将所有奶牛按右边界maxSPF排序，对于每头奶牛，用满足条件的，SPF值最小的那瓶。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2.5e3+50;
pair<int,int> nx[N],sc[N];
bool cmp(pair<int,int> a,pair<int,int> b){
    return a.second<b.second;
}
bool cmp2(pair<int,int> a,pair<int,int> b){
    return a.first<b.first;
}
signed main(){
    int c,l;
    cin >> c >> l;
    for(int i=1;i<=c;i++){
        cin >> nx[i].first >> nx[i].second;
    }for(int i=1;i<=l;i++){
        cin >> sc[i].first >> sc[i].second;
    }
    sort(nx+1,nx+c+1,cmp);
    sort(sc+1,sc+l+1,cmp2);
    int cnt=0;
    for(int i=1;i<=c;i++){
        for(int j=1;j<=l;j++){
            if(nx[i].first<=sc[j].first&&sc[j].first<=nx[i].second&&sc[j].second!=0){
                // cout << i << " " << j << endl;
                // cout << nx[i].first << " " << nx[i].second << " " << sc[j].first << " " << sc[j].second << endl;
                sc[j].second--;
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
}

$T3$ 畜栏预定

思路：首先将所有奶牛按开始时间排序，然后用小根堆维护畜栏，优先选结束时间最快的那一个，没有则新建一个插入。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+50;
struct PII{
	int first,second;
	PII(int f,int s):first(f),second(s){}
	bool operator<(const PII &T)const { return first>T.first;}// 小根堆的另一种写法，重定义
};
struct PI2{
	int first,second,num;
	bool operator<(const PI2 &T)const { return first<T.first;}
};
PI2 a[N];
priority_queue<PII> b;
int c[N],idx;
signed main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i].first >> a[i].second;
        a[i].num=i;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(!b.size()){
            idx++;
            b.push(PII(a[i].second,idx));
            c[a[i].num]=idx;
//            cout << "---------------" << endl;
        }else{
            PII tp=b.top();
//            cout << "min:" << tp.first << " " << tp.second << endl;
            if(tp.first<a[i].first){
//            	cout << "POP!\n";
                b.pop();
//                cout << "push:" << a[i].second << " " << tp.second << endl;
                b.push(PII(a[i].second,tp.second));
                c[a[i].num]=tp.second;
            }else{
//            	cout << "NO POP!\n";
                idx++;
//                cout << "push:" << a[i].second << " " << idx << endl;
                b.push(PII(a[i].second,idx));
                c[a[i].num]=idx;
            }
//            cout << "---------------" << endl; 
        }
    }
    cout << idx << endl;
    for(int i=0;i<n;i++){
        cout << c[i] << endl;
    }
}

$T4$ 雷达设备

思路：首先，如果y坐标超出，则直接输出-1，否则先记录每个小岛可以被雷达覆盖的范围，再通过s记录每个可以用一个雷达覆盖的小岛组中，第一个小岛的右端点。最后输出s的变更次数请辅助代码理解

代码：

#include <bits/stdc++.h>
#define int long long
#define PII pair<double,double>
using namespace std;
const int N=1e3+50;
PII a[N];
signed main(){
	int n,d;
	cin >> n >> d;
    bool flag=0;
	for(int i=0;i<n;i++){
		int x,y;
		cin >> x >> y;
		if(y>d){
			flag=1;
            break;
		}
		double cd=sqrt(d*d-y*y);
		a[i]={x+cd,x-cd};//算出可被雷达覆盖的区间，存放顺序是先右后左
		// cout << a[i].second << " " << a[i].first << endl;
	}
    if(flag){
        cout << -1;
    }else{
	    sort(a,a+n);
        int ans=0;
		double s=-1e20;//s记录每个小岛组（可以用一个雷达覆盖的小岛称为雷达组）第一个区间的右端点 
        for(int i=0;i<n;i++){
            if(s<a[i].second){
                ans++;
                s=a[i].first;
            }
        }
        cout << ans; 
    }
}

$T5$ 国王游戏

思路：按左右手乘积排序，注意要高精度。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+50;
pair<int,int> a[N];
vector<int> to_vector(int x){
    vector<int> C;
    while(x){
        C.push_back(x%10);
        x/=10;
    }
    return C;
}
bool cmp2(vector<int> &A, vector<int> &B)
{
	if(A.size() != B.size())
		return 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;
}
vector<int> mul(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.back() == 0 && C.size() > 1) 
		C.pop_back();	
	return C;
}
vector<int> div(vector<int> &A, int b)
{
	vector<int> C;
	int t = 0,r = 0;
	for(int i = A.size() - 1; i >= 0; i --)
	{
		t = r * 10 + A[i];
		C.push_back(t / b);
		r = t % b;
	}
	reverse(C.begin(), C.end());
	while(C.back() == 0 && C.size() > 1)
		C.pop_back();
	return C;
}
vector<int> max_vector(vector<int> A,vector<int> B){
	if(cmp2(A,B)) return A;
	return B;
}
signed main(){
    int n;
    cin >> n;
    for(int i=0;i<=n;i++){
        cin >> a[i].first >> a[i].second;
        a[i].second*=a[i].first;
        swap(a[i].first,a[i].second);
    }
    sort(a+1,a+n+1);
    vector<int> mx(1,0),cf(1,1);
    for(int i=0;i<=n;i++){
        if(i) mx=max_vector(mx,div(cf,a[i].first/a[i].second));
        cf=mul(cf,a[i].second);
    }
    for(int i=mx.size()-1;i>=0;i--){
        cout << mx[i];
    }
}

$T6$ 给树染色

思路：父节点优先染色，再将子节点进行合并。并保存染色顺序。等所有节点都染成一个点时，按照保存的顺序将各个节点依次染色，计算出花费的代价。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,r;
const int N=3e3+50;
struct P{
    int father,size,num;
    double pj;
};
P a[N];
int find(){
    double mx=0;
    int xi=1;
    for(int i=1;i<=n;i++){
        if(i!=r&&a[i].pj>mx) mx=a[i].pj,xi=i;
    }
    return xi;
}
int main(){
    int ans=0;
    cin >> n >> r;
    for(int i=1;i<=n;i++){
        cin >> a[i].num;
        ans+=a[i].num;
        a[i].size=1;
        a[i].pj=a[i].num;
    }
    for(int i=1;i<n;i++){
        int a1,b;
        cin >> a1 >> b;
        a[b].father=a1;
    }
    for(int i=1;i<n;i++){
        int x=find(),y=a[x].father;
        ans+=a[y].size*a[x].num;
        for(int j=1;j<=n;j++){
            if(a[j].father==x) a[j].father=y;
        }
        a[x].pj=-1;
        a[y].size+=a[x].size;
        a[y].num+=a[x].num;
        a[y].pj=1.0*a[y].num/a[y].size;
    }
    cout << ans;
}

$T7$ 耍杂技的牛

思路：按两值相加的结果排序（从小到大）

代码：

#include <bits/stdc++.h>
#define int long long
#define w first
#define s second
#define PII pair<int,int>
using namespace std;
const int N=5e4+50;
PII a[N];
bool cmp(PII a1,PII b){
    return a1.w+a1.s<b.w+b.s;
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i].w >> a[i].s;
    sort(a+1,a+n+1,cmp);
    int fxz=-2e9,sum=0;
    for(int i=1;i<=n;i++){
        fxz=max(fxz,sum-a[i].s);
        sum+=a[i].w;
    }
    cout << fxz;
}

$T8$ 最大的和

思路：用两层循环枚举y坐标区间，通过前缀和算出值，x坐标范围按最大子串的方法求，前缀和为a[i][j]+=[i-1][j];

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int a[N][N];
signed main(){
    int n,ans=-2e9;
    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 qzh=0;
    		for(int k=1;k<=n;k++){
    			if(qzh<0) qzh=0;
    			qzh+=a[j][k]-a[i-1][k];
    			ans=max(ans,qzh);
			}
		}
	}
	cout << ans;
}

$T9$ 任务

思路：把机器和任务都优先按时间降序排列。随后找出每个任务可以用哪些机器完成。再用lower_bound()找出最没用的那台（时间和难度最小的那台），计算利润，增加数量，随后删除此机器。

代码：

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define PII pair<int,int>
using namespace std;
const int N=1e5+50;
PII a[N],b[N];
bool cmp(PII a,PII b){
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
signed main(){
    int n,m;
    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+n+1,cmp);
        sort(b+1,b+m+1,cmp);
        int i=1,j=1,sy=0,num=0;
        multiset<int> st;
        for(j=1;j<=m;j++){
            PII t=b[j];
            while(i<=n&&a[i].x>=t.x){
                st.insert(a[i++].y);
            }
            auto it=st.lower_bound(t.y);
            if(it!=st.end()){
                num++;
                sy+=500ll*t.x+2ll*t.y;
                st.erase(it);
            }
        }
        cout << num << " " << sy << endl;
    }
}

$T1$ 占卜DIY

思路：模拟题，注意用双端队列二维数组。

代码：

#include<bits/stdc++.h>
using namespace std;
struct P{
    bool vis;
    int num;
};
deque<P> a[20];
int vis[100];
int main(){
    P st;
    for (int i=1;i<=13;i++){
        for (int j=1;j<=4;j++){
        	char l;
            cin >> l;
            if(l=='A'){
                st.num=1;
                st.vis=0;
                a[i].push_front(st);
            }else if(l=='J'){
                st.num=11;
                st.vis=0;
                a[i].push_front(st);
            }else if(l=='Q'){
                st.num=12;
                st.vis=0;
                a[i].push_front(st);
            }else if(l=='K'){
                st.num=13;
                st.vis=0;
                a[i].push_front(st);
            }else if(l=='0'){
                st.num=10;
                st.vis=0;
                a[i].push_front(st);
            }else{
                st.num=l-'0';
                st.vis=0;
                a[i].push_front(st);
            }
        }
    }
    P top;
    P top2;
    for (int t=0;t<4;t++){
        top=a[13].back();
        a[13].pop_back();
        top.vis=1;
        if(top.num==13) continue;
        while(top.num!=13){
            a[top.num].push_back(top);
            top2=top;
            top=a[top.num].front();
            a[top2.num].pop_front();
            top.vis=1;
        }
    }
    for (int i=1;i<=13;i++){
        for (int j=0;j<a[i].size();j++){
            if(a[i][j].vis) vis[a[i][j].num]++;
        }
    }
    int ans=0;
    for(int i=1;i<=12;i++){
        if(vis[i]==4) ans++;
    }
    cout << ans << endl;
}

$T2$ 袭击

思路：一题平面最近点对的变形题，注意用vis数组标注好阵营，最后判断时，如果vis值一样，则将距离设为无穷大，其余遵循平面最经典对的求法。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
struct PII{
    double x,y;
    bool vis;
    bool operator<(const PII &T) const{
        return x<T.x;
    }
};
PII a[N],tmp[N];
double dist(PII a,PII b){
  //依赖于归并的平面最近点对
    if(a.vis==b.vis) return 2e9;
    double _x=a.x-b.x,_y=a.y-b.y;
    return sqrt(_x*_x+_y*_y);
}
double dfs(int l,int r){
    if(l>=r) return 2e9;
    int mid=l+r>>1;
    double ans=min(dfs(l,mid),dfs(mid+1,r));
    {
    // 不要问为什么加括号，问就是防止命名重复
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(a[i].y>a[j].y){
            tmp[k++]=a[i++];
        }else{
            tmp[k++]=a[j++];
        }
    }
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(int i=0,j=l;i<k;i++,j++){
        a[j]=tmp[i];
    }
    }
    int k=0;
    for(int i=l;i<=r;i++){
        if(a[i].x<=a[mid].x+ans&&a[i].x>=a[mid].x-ans) tmp[k++]=a[i];
    }
    for(int i=0;i<k;i++){
        for(int j=i-1;j>=0&&tmp[i].y-tmp[j].y<ans;j--){
            ans=min(ans,dist(tmp[i],tmp[j]));
        }
    }
    return ans;
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> a[i].x >> a[i].y;
            a[i].vis=0;
        }
        for(int i=n;i<2*n;i++){
            cin >> a[i].x >> a[i].y;
            a[i].vis=1;
        }
        sort(a,a+2*n);
        printf("%.3lf\n",dfs(0,2*n-1));
    }
}

$T3$ 数的进制转换

思路：f进制高精度除法模版题

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int t;
    cin >> t;
    while(t--){
        int x,y;
        string a,b;
        cin >> x >> y >> a;
        vector<int> x2,y2;
        for(int i=0;i<a.size();i++){
            if(a[i]>='0'&&a[i]<='9') x2.push_back(a[i]-'0');
            else if(a[i]>='A'&&a[i]<='Z') x2.push_back(a[i]-'A'+10);
            else x2.push_back(a[i]-'a'+36);
        }
        reverse(x2.begin(),x2.end());
        while(x2.size()){
            int r=0;
            // 高精除,但是非十进制
            for(int i=x2.size()-1;i>=0;i--){
                x2[i]+=r*x;
                r=x2[i]%y;
                x2[i]/=y;
            }
            y2.push_back(r);
            while(x2.back()==0&&x2.size()>0) x2.pop_back();
        }
        reverse(y2.begin(),y2.end());
        for(int i=0;i<y2.size();i++){
            if(y2[i]<=9) b+=char(y2[i]+'0');
            else if(y2[i]>=10&&y2[i]<=35) b+=char(y2[i]+'A'-10);
            else b+=char(y2[i]+'a'-36);
        }
        cout << x << " " << a << endl << y << " " << b << endl << endl;
    }
}

$T1$ 编辑器

思路：模拟题，用对顶栈模拟光标

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
deque<int> a,b;
const int N=2e6+50;
int s[N],mx[N];
int xb=1;
signed main(){
    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        int t;
        if(c=='I'||c=='Q') cin >> t;
        if(c=='I'){
            a.push_back(t);
            s[xb]=s[xb-1]+t;
            if(xb==1) mx[1]=s[1];
            else mx[xb]=max(mx[xb-1],s[xb]);
            xb++;
        }else if(c=='D'){
            if(xb-1) a.pop_back(),xb--;
        }else if(c=='L'){
            if(!a.size()) continue;
            int ss=a.back();
            b.push_front(ss);
            a.pop_back();
            xb--;
        }else if(c=='R'){
            if(!b.size()) continue; 
            t=b.front();
            b.pop_front();
            a.push_back(t);
            s[xb]=s[xb-1]+t;
            if(xb==1) mx[1]=s[1];
            else mx[xb]=max(mx[xb-1],s[xb]);
            xb++;
        }else{
            cout << mx[t] << endl;
        }
    }
}

$T2$ 直方图中最大的矩形

思路：用单调栈维护一个升序的序列，遇到小的就将所有大于它的数变为它，并更新乘算结果。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N],cunt[N];
deque<int> q;
signed main(){
    while(1){
        int mx=0;
        int n;
        cin >> n;
        if(!n) return 0;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            if(q.empty()||a[i]>=q.back()){
                q.push_back(a[i]);
                cunt[q.size()]=1;
            }else{
                int cnt=0;
                while(q.size()&&q.back()>a[i]){
                    int bc=q.back();
                    cnt+=cunt[q.size()];
                    mx=max(mx,bc*cnt);
                    q.pop_back();
                }
                q.push_back(a[i]);
                cunt[q.size()]=cnt+1;
            }
        }
        int cnt=0;
        while(q.size()){
            int bc=q.back();
            cnt+=cunt[q.size()];
            mx=max(mx,bc*cnt);
            q.pop_back();
        }
        cout << mx << endl;
    }
}

$T3$ 火车进出栈问题

思路：卡特兰数+高精度，公式 $C^{2n}_n÷(n+1)$ 。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=6e6+50,M=120050,eth=1e9;
LL ans[N],SIZE;
int q[M];
bool vis[M];
void mul(int b){
	LL t=0;
	for(int i=0;i<=SIZE;i++){
		ans[i]=ans[i]*b+t;
		t=ans[i]/eth;
		ans[i]%=eth;
	}
	while(t){
		ans[++SIZE]=t%eth;
		t/=eth;
	}
}
void cout(){
	printf("%lld",ans[SIZE]);
	for(int i=SIZE-1;i>=0;i--) printf("%09lld",ans[i]);
	cout << endl;
}
int get(int a,int b){
	int s=0;
	while(a) s+=a/b,a/=b;
	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){
			vis[j]=1;
		}
	}
	for(int i=2;i<=2*n;i++){
		if(!vis[i]){
			q[i]=get(n*2,i)-get(n,i)*2;
		}
	}
	int k=n+1;
	for(int i=2;i<=k;i++){
		while(k%i==0){
			k/=i;
			q[i]--;
		}
	}
	ans[0]=1;
	for(int i=2;i<=n*2;i++){
		while(q[i]--){
			mul(i);
		}
	}
	cout();
}

$T4$ 火车进栈

思路：DFS暴力枚举，但要注意当栈为空时，不可出栈

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
deque<int> s1,s2;
int n,sl;
int z=1;
void dfs(int u){
    if(sl==20) return;
    if(u==n){
        for(int i=0;i<n;i++){
            cout << s1[i];
        }
        cout << endl;
        sl++;
    }
//    cout << "s2:  ";
//    for(int i=0;i<s2.size();i++){
//    	cout << s2[i] << " ";
//	}
//	cout << endl;
    if(s2.size()!=0){
        s1.push_back(s2.back());
        s2.pop_back();
        dfs(u+1);
        s2.push_back(s1.back());
        s1.pop_back();
    }
    if(z<=n){
        s2.push_back(z++);
        dfs(u);
        z--;
        s2.pop_back();
    }
}
signed main(){
    cin >> n;
    dfs(0);
}

$T5$ 括号画家

思路：（我的代码不是按这个思路来的，这个更简单一些）

遇到左括号堆栈里，有括号配对就累计，不配对就和max比较并更新，随后清零重新累加。

代码（仅供参考，与思路有些不符，不要抄袭 ~~（毕竟太长了）~~）:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
int cnt[N];
vector<char> q;
bool left(char c){
    return c=='('||c=='{'||c=='[';
}bool right(char c){
    return !left(c);
}char pd(char c){
    if(c==')') return '(';
    if(c==']') return '[';
    return '{';
}
signed main(){
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(left(s[i])){
            q.push_back(s[i]);
        }else{
            if(q.empty()) continue;
            if(q.back()==pd(s[i])){
                cnt[i]=1;
                int j=i;
                while(cnt[j]) j--;
                cnt[j]=1;
                q.pop_back();
            }else{
            	q.clear();
			}
        }
    }
    int mx=0,tj=0;
    for(int i=0;i<s.size();i++){
        if(cnt[i]) tj++;
        else tj=0;
        mx=max(mx,tj);
    }
    cout << mx << endl;
}

$T6$ 表达式求值

思路：模版题变形，注意新加入计算负数和去除多余括号。

代码：

#include <bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> jc;
string s;
bool check(char a,char b){
	int A,B;
	if(a=='+'||a=='-') A=1;
	else if(a=='*'||a=='/') A=2;
	else A=3;
	if(b=='+'||b=='-') B=1;
	else if(b=='*'||b=='/') B=2;
	else B=3;
	return A<=B; 
}
void JS(){
	int b=num.top();
    num.pop();
	int a=num.top();
    num.pop();
	char c=jc.top();
    jc.pop();
	int 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=pow(a,b);
	num.push(x);
}
void solve(){
    int kh=0;
    for(int i=0;i<s.size();i++){
    	if(s[i]=='`') continue;
        char c=s[i];
        if(isdigit(c)){
            int x=0,z=i;
            while(z<s.size()&&isdigit(s[z])){
				x=x*10+s[z]-'0';
				z++;
			}
			i=z-1;
			num.push(x);
        }else if(c=='('){
            kh++;
            jc.push(c);
        }else if(c==')'){
            if(!kh) continue;
            kh--;
            while (jc.top()!='(') JS();
			jc.pop();
        }else if(c=='-'&&(s[i-1]=='('||i==0)){
        	int x=0,z=i+1;
            while(z<s.size()&&isdigit(s[z])){
				x=x*10+s[z]-'0';
				z++;
			}
			i=z-1;
			num.push(x*-1);
		}else{
            while(jc.size()&&jc.top()!='('&& check(c,jc.top()))
				JS();
			jc.push(c);
        }
    }
	while(jc.size()) JS();
    cout << num.top();
}
int main(){
    while(1){
    	getline(cin,s);
    	int aa=0,bb=0;
    	for(int i=0;i<s.size();i++){
    		if(s[i]=='(') aa++;
    		if(s[i]==')') bb++;
		}
		if(aa>bb){
			int op=aa-bb;
			for(int i=0;i<s.size();i++){
				if(op&&s[i]=='('){
					op--;
					s[i]='`';
				}
			}
		}
		solve();
		return 0;
	}
}

$T7$ 城市游戏

思路：玉蟾宫原题，思路写在代码里~

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
int a[N][N],u[N][N],l[N][N],r[N][N];
/*
u[i][j]:从(i,j)这个点往上走能达到的最大高度
l[i][j]:从(i,j)这个点往左走能达到的最小纵坐标
r[i][j]:从(i,j)这个点往右走能达到的最大纵坐标 
*/
signed main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin >> c;
			if(c=='F') a[i][j]=u[i][j]=1,l[i][j]=r[i][j]=j;// 赋初始值，最少能到达的高度是1,最少能延伸到的纵坐标就是当前的纵坐标(j) 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]&&a[i][j-1]) l[i][j]=l[i][j-1];// 如果左边(a[i][j-1])是1(还能走),那么左边(i,j-1)能到达的位置(l[i][j-1])肯定已经被算过了(j是正序遍历的) 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			if(a[i][j]&&a[i][j+1]) r[i][j]=r[i][j+1];// 同理,由于这里是j+1,所以j是倒序遍历 
		}
	}
	int mx=0; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i-1][j]&&a[i][j]){// 还能往上走
				u[i][j]=u[i-1][j]+1; // 更新
				// 由于矩形的宽度不可能扩大，所以l[i][j]取max(右移)，r[i][j]取min(左移) 
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			mx=max(mx,(r[i][j]-l[i][j]+1)*u[i][j]);
		}
	}
	mx*=3;
	cout << mx;
}

$T8$ 双栈排序

思路：答案要求字典序最小，因此用染色法染色时，需要优先将点分配到第一个栈中。先随便求一个方案，再将方案中所有连续的b,c区间排序，连续的a,d区间排序即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
int n;
int a[N],f[N],color[N];
bool g[N][N];
bool dfs(int u,int c){
	color[u]=c;
	for(int i=1;i<=n;i++){
		if(g[u][i]){
			if(color[i]==c) return 0;
			if(color[i]==-1&&!dfs(i,!c)) return 0;
		}
	}
	return 1;
}
signed main(){
	int t;
	cin >> t;
    while(t--){
        memset(g,0,sizeof g);
        memset(color,-1,sizeof color);
    	cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        f[n+1]=n+1;
        for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]);
        for(int i=1;i<=n;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;
                }
            }
        }
        bool flag=1;
        for(int i=1;i<=n;i++){
            if(color[i]==-1&&!dfs(i,0)){
                flag=0;
                break;
            }
        }
        if(!flag){
            cout << 0 << endl;
            continue;
        }
        stack<int> stk1,stk2;
        int now=1;
        for(int i=1;i<=n;i++){
            if(color[i]==0){
                while(stk1.size()&&stk1.top()==now){
                    stk1.pop();
                    cout << "b ";
                    now++;
                }
                stk1.push(a[i]);
                cout << "a ";
            }else{
                while(1){
                    if(stk1.size()&&stk1.top()==now){
                        stk1.pop();
                        cout << "b ";
                        now++;
                    }
                    else if(stk2.size()&&stk2.top()==now){
                        stk2.pop();
                        cout << "d ";
                        now++;
                    }
                    else break;
                }
                stk2.push(a[i]);
                cout << "c ";
            }
        }
        while(1){
            if(stk1.size()&&stk1.top()==now){
                stk1.pop();
                cout << "b ";
                now++;
            }
            else if(stk2.size()&&stk2.top()==now){
                stk2.pop();
                cout << "d ";
                now++;
            }
            else break;
        }
        cout << endl;
    }
}

$T1$ 小组队列

思路；纯模拟，队列套队列

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> mp;
struct P{
    deque<int> q;
    int num;
};
deque<P> d;
void solve(int qwe){
    int t;
    cin >> t;
    if(t==0) exit(0);
    for(int i=1;i<=t;i++){
        int n;
        cin >> n;
        for(int j=1;j<=n;j++){
            int x;
            cin >> x;
            mp[x]=i;
        }
    }
    string ml;
    cout << "Scenario #" << qwe << endl;
    while(1){
        cin >> ml;
        if(ml=="ENQUEUE"){
            int x;
            cin >> x;
            int y=mp[x];
            int flag=0;
            for(int i=0;i<d.size();i++){
                if(d[i].num==y){
                    d[i].q.push_back(x);
                    flag=1;
                    break;
                }
            }
            if(!flag){
                deque<int> f;
                f.push_back(x);
                d.push_back(P{f,y});
            }
        }else if(ml=="DEQUEUE"){
            if(d.empty()) continue;
            while(d.front().q.empty()&&d.size()) d.pop_front();
            cout << d.front().q.front() << endl;
            d.front().q.pop_front();
        }else{
            return;
        }
    }
}
signed main(){
    int i=0;
    while(1){
    	d.clear();
        solve(++i);
    }
}

$T2$ 蚯蚓

用三个队列共同维护原数值，[px]那段数值，x-[px]那段数值，其他模拟即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
queue<int> a,b,c;
const int N=1e5+50;
int a1[N];
bool cmp(int a,int b){
	return a>b;
}
signed main(){
    int n,m,q,u,v,t;
    cin >> n >> m >> q >> u >> v >> t;//p=u/v
    int T=0;
    for(int i=1;i<=n;i++){
        int ai;
        cin >> ai;
        a1[i]=ai;
    }
    sort(a1+1,a1+n+1,cmp);
    for(int i=1;i<=n;i++){
        a.push(a1[i]);
    }
    int dq=0;
    for(int ccf=1;ccf<=m;ccf++){
        int A,B,C,x;
        A=B=C=-2e9;
        if(!a.empty()) A=a.front();
        if(!b.empty()) B=b.front();
        if(!c.empty()) C=c.front();
        x=max(A,max(B,C));
        if(x==A){
            a.pop();
        }else if(x==B){
            b.pop();
        }else{
            c.pop();
        }
        x+=dq;
        T++;
        if(T==t) T=0,cout << x << " ";
        b.push(x*u/v-dq-q);
        c.push(x-(x*u/v)-dq-q);
        dq+=q;
    }
    cout << endl;
    int NM=n+m;
    T=0;
    while(NM--){
        int A,B,C,x;
        A=B=C=-2e9;
        if(!a.empty()) A=a.front();
        if(!b.empty()) B=b.front();
        if(!c.empty()) C=c.front();
        x=max(A,max(B,C));
        if(x==A){
            a.pop();
        }else if(x==B){
            b.pop();
        }else{
            c.pop();
        }
        T++;
        if(T==t) T=0,cout << x+m*q << " ";
    }
}

$T3$ 双端队列

思路：先将数组排好序，再分成尽量少的几段，使得每一段都对应原问题中一个合法的双端队列。

代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define num second
using namespace std;
const int N=2e5+50;
PII a[N];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i].x;
		a[i].num=i;
	}
	sort(a,a+n);
	int ans=1,flag=0;
	for(int i=0,ed=n+1;i<n;){
		int j=i;
		while(j<n&&a[j].x==a[i].x) j++;
		int mn=a[i].num,mx=a[j-1].num;
		if(!flag){
			if(ed>mx) ed=mn;
			else flag=1,ed=mx;
		}else{
			if(ed<mn){
				ed=mx;
			}else{
				flag=0,ed=mn;
				ans++;
			}
		}
		i=j;
	}
	cout << ans << endl;
}

$T4$ 最大子序和

思路：用一个单调队列维护区间信息即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+50;
int a[N];
deque<int> q;
signed main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
    	cin >> a[i];
    	a[i]+=a[i-1];
	}
	int mx=a[1];
	for(int i=1;i<=n;i++){
		if(q.size()){
			if(q.front()<i-m) q.pop_front();
			mx=max(mx,a[i]-a[q.front()]);
		}
		while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
		q.push_back(i);
	}
	cout << mx;
}

$T5$ 滑动窗口

思路：模版题

代码：勉为其难给一下吧

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+50;
int a[N];
deque<int> q;
signed main(){
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        while(q.size()&&i-k+1>q.front()) q.pop_front();
        while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) cout << a[q.front()] << " ";
    }
    cout << endl;
    q.clear();
    for(int i=0;i<n;i++){
        while(q.size()&&i-k+1>q.front()) q.pop_front();
        while(q.size()&&a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) cout << a[q.front()] << " ";
    }
}

$T1$ 邻值查找

思路：利用STL set寻找绝对值差的最小值即可。

代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=1e5+50;
set<PII> s;
int main(){
	int a,n;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    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> ans={0x3f3f3f3f,0};
    	if(++it!=s.end()) ans={(*it).first-a,(*it).second};
    	it--;
    	if(it--!=s.begin()&&ans.first>=a-(*it).first) ans={a-(*it).first,(*it).second};
		cout << ans.first << " " << ans.second << endl;
	}
}

$T1$ 雪花雪花雪花

思路：字符串的最小表示法模版题。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[7],rea[7],as[N][7],rnd[13],idx[N];
int t;
unordered_map<int,int> mp;
void get(int a[]){
	for(int i=0;i<12;i++){
		rnd[i]=a[i%6];
	}
	int i=0,j=1;
	while(i<6&&j<6){
		int k;
		for(k=0;k<6&&rnd[i+k]==rnd[j+k];k++) if(k==6) break;
		if(rnd[i+k]>rnd[j+k]){
			i+=k+1;
			if(i==j) i++;
		}else{
			j+=k+1;
			if(i==j) j++;
		}
	}
	int ans=min(i,j);
	for(int i=0;i<6;i++) a[i]=rnd[i+ans];
}
bool cmp(int a[],int b[]){
	for(int i=0;i<6;i++){
		if(a[i]<b[i]) return 1;
		if(b[i]<a[i]) return 0;
	}
	return 0;
}
bool CMP(int a,int b){
	return cmp(as[a],as[b]);
}
bool eql(int a[],int b[]){
	for(int i=0;i<6;i++){
		if(b[i]!=a[i]) return 0;
	}
	return 1;
}
signed main(){
	cin >> t;
	for(int cps=0;cps<t;cps++){
		for(int i=0;i<6;i++){
			cin >> a[i];
			rea[i]=a[i];
		}
		reverse(rea,rea+6);
		get(a);
		get(rea);
		if(cmp(a,rea)){
			memcpy(as[cps],a,sizeof a);
		}else{
			memcpy(as[cps],rea,sizeof rea);
		}
		idx[cps]=cps;
	}
	sort(idx,idx+t,CMP);
	for(int i=1;i<t;i++){
		if(eql(as[idx[i]],as[idx[i-1]])){
			puts("Twin snowflakes found.");
			return 0;
		} 
	}
	puts("No two snowflakes are alike.");
}

$T2$ 兔子与兔子

思路：字符串哈希

代码：

#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;
const int N=1000500,P=131;
int n,m;
ULL h[N],p[N];
ULL get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
int main(){
	string str;
	cin >> str;
	n=str.size();
	cin >> m;
	p[0]=1;
	str=" "+str;
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*P+str[i];
		p[i]=p[i-1]*P;
	}
	while(m--){
		int l1,r1,l2,r2;
		cin >> l1 >> r1 >> l2 >> r2;
		if(get(l1,r1)==get(l2,r2)) cout << "Yes\n";
		else cout << "No\n";
	}
}

$T3$ 回文子串的最大长度

思路：hash+二分查找子串。

代码：

#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;
const int N=2e6+50,base=131;
char s[N];
ULL hl[N],hr[N],p[N];
ULL get(ULL h[],int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
    while(scanf("%s",s+1),strcmp(s+1,"END")){
    	int n=strlen(s+1);
    	for(int i=2*n;i>=1;i-=2){
    		s[i]=s[i/2];
    		s[i-1]='a'+26;
		}
		n*=2;
		p[0]=1;
		for(int i=1,j=n;i<=n;i++,j--){
			hl[i]=hl[i-1]*base+s[i]-'a'+1;
			hr[i]=hr[i-1]*base+s[j]-'a'+1;
			p[i]=p[i-1]*base;
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			int l=0,r=min(i-1,n-i);
			while(l<r){
				int mid=l+r+1>>1;
				if(get(hl,i-mid,i-1)!=get(hr,n-(i+mid)+1,n-(i+1)+1)) r=mid-1;
				else l=mid;
			}
			if(s[i-l]<='z') ans=max(ans,l+1);
			else ans=max(ans,l);
		}
		cout << "Case " << T++ << ": " << ans << "\n";
	}
	return 0;
}

$T4$ 后缀数组

思路：

SA数组求法(cmp)：用二分找到两个后缀的最长公共前缀，再根据最长公共前缀后面的字符来确定大小。 Height数组球法：遍历SA数组，Height[i]为SA[i]和SA[i-1]之间的最长公共前缀长度。（Height[1]除外，其等于0）

代码:

#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;
const int N=3e5+50,base=131;
string s;
ULL h[N],p[N];
int idx[N],n;
int get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
int max_qj(int a,int b){
	int l=0,r=min(n-a+1,n-b+1);
	while(l<r){
		int mid=l+r+1>>1;
		if(get(a,a+mid-1)==get(b,b+mid-1)) l=mid;
		else r=mid-1;
	}
	return l;
}
bool cmp(int a,int b){
	int len=max_qj(a,b);
	int x=a+len>n?-2e9:s[a+len];
	int y=b+len>n?-2e9:s[b+len];
	return x<y;
}
int main(){
	cin >> s;
	s=" "+s;
	p[0]=1;
	n=s.size()-1;
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*base+s[i]-'a'+1;
		p[i]=p[i-1]*base;
		idx[i]=i;
	}
	sort(idx+1,idx+n+1,cmp);
	for(int i=1;i<=n;i++){
		cout << idx[i]-1 << " ";
	}
	cout << endl;
	for(int i=1;i<=n;i++){
		if(i==1){
			cout << 0 << " ";
			continue;
		}
		cout << max_qj(idx[i],idx[i-1]) << " ";
	}
}

$T5$ 矩阵

思路：二维hash。

代码：

#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;
const int N=1e3+50;
ULL hs[N][N],_131[N*N];
ULL get(ULL f[],int l,int r)
{
    return  f[r]-f[l-1]*_131[r-l+1];
}
int main(){
	int n,m,a,b;
	cin >> n >> m >> a >> b;
	_131[0]=1,_131[1]=131;
	for(int i=2;i<=m*m;i++){
		_131[i]=_131[i-1]*131;
	}
	for(int i=1;i<=n;i++){
		string s;
		cin >> s;
		s=" "+s;
		for(int j=1;j<=m;j++){
			hs[i][j]=hs[i][j-1]*131+s[j]-'0';
		}
	}
	unordered_set<ULL> hash;
	for(int i=b;i<=m;i++){
		ULL emp=0;
		int l=i-b+1,r=i;
		for(int j=1;j<=n;j++){
			emp=emp*_131[b]+get(hs[j],l,r);
			if(j>a) emp-=get(hs[j-a],l,r)*_131[a*b];
            if(j>=a) hash.insert(emp);
		}
	}
	int q;
	cin >> q;
	while(q--){
		ULL emp=0;
		for(int i=0;i<a;i++){
			string s;
			cin >> s;
			for(int j=0;j<b;j++){
				emp=emp*131+s[j]-'0';
			}
		}
		cout << (hash.count(emp)?1:0) << endl;
	}
}

总结

T1T1T1 aaa^bbb

T2T2T2 增加模数

T3T3T3 646464位整数乘法

T4T4T4 起床困难综合症

T5T5T5 最短HamiltonHamiltonHamilton路径

T6T6T6 飞行员兄弟

T1T1T1 递归实现指数型枚举

T2T2T2 递归实现组合型枚举

T3T3T3 递归实现排列型枚举

T4T4T4 费解的开关

T5T5T5 奇怪的汉诺塔

T6T6T6 约数之和

T7T7T7 分形之城

T8T8T8 分形

T1T1T1 激光炸弹

T2T2T2 增减序列

T3T3T3 最高的牛

T1T1T1 防线

T2T2T2 最佳牛围栏

T3T3T3 赶牛入圈

T1T1T1 电影

T2T2T2 货仓选址

T3T3T3 七夕祭

T4T4T4 动态中位数

T5T5T5 超快速排序

T6T6T6 奇数码问题

T7T7T7 糖果传递

T8T8T8 士兵

T1T1T1 天才ACM

T1T1T1 股票买卖

T2T2T2 防晒

T3T3T3 畜栏预定

T4T4T4 雷达设备

T5T5T5 国王游戏

T6T6T6 给树染色

T7T7T7 耍杂技的牛

T8T8T8 最大的和

T9T9T9 任务

T1T1T1 占卜DIY

T2T2T2 袭击

T3T3T3 数的进制转换

T1T1T1 编辑器

T2T2T2 直方图中最大的矩形

T3T3T3 火车进出栈问题

T4T4T4 火车进栈

T5T5T5 括号画家

T6T6T6 表达式求值

T7T7T7 城市游戏

T8T8T8 双栈排序

T1T1T1 小组队列

T2T2T2 蚯蚓

T3T3T3 双端队列

T4T4T4 最大子序和

T5T5T5 滑动窗口

T1T1T1 邻值查找

T1T1T1 雪花雪花雪花

T2T2T2 兔子与兔子

T3T3T3 回文子串的最大长度

T4T4T4 后缀数组

T5T5T5 矩阵

状态

开发

支持

关于

登录