SWUST ACM21第三次对抗赛A-C题解

• A.位运算公式
• • 思路：
  • 代码：
• B.01矩阵最大化
• • 思路：
  • 代码
• C.简单的贪心签到题
• • 思路：
  • 代码

一个简单的位运算公式
a o r b = a a n d b + a x o r b a quad orquad b = a quad and quad b + a quad xor quad b aorb=aandb+axorb
或者
a o r b = a a n d b o r a x o r b a quad orquad b = a quad and quad b quad orquad a quad xor quad b aorb=aandboraxorb
a o r b = a a n d b x o r a x o r b a quad orquad b = a quad and quad b quad xorquad a quad xor quad b aorb=aandbxoraxorb
都是可以的。所以直接上代码。

#include
using namespace std;
#define int long long
#define endl 'n'
#define fo(x,a,b) for(int x=a;x<=b;x++)
#define of(x,a,b) for(int x=a;x>=b;x--)
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PI acos(-1)
#define pb push_back
#define lowbit(a) ((a)&-(a))
#define lbit(a) (__builtin_ffsll(a))
#define ubit(a) (64-__builtin_clzll(a))
#define fi first
#define se second
int A[2003][2003],B[2003][2003];
void solve(){
	int n,m;
	cin>>n>>m;
	fo(i,1,n){
		fo(j,1,m){
			cin>>A[i][j];
		}
	}
	fo(i,1,n){
		fo(j,1,m){
			cin>>B[i][j];
		}
	}
	fo(i,1,n){
		fo(j,1,m){
			int x=A[i][j]+B[i][j];

			if(x%4==0||x%4==1)cout<<"1 ";
			else cout<<"0 ";
		}
		cout<
	close();
	int T;
	T=1;
	while(T--)solve();
    return 0;
}

经典的最大化矩阵问题，那么这里使用“垂线法”。我们需要这么几个数组：
L [ i ] [ j ] L[i][j] L[i][j]:代表 i i i行第 j j j个向左扩展最长长度.
R [ i ] [ j ] R[i][j] R[i][j]:代表 i i i行第 j j j个向右扩展最长长度.
H [ i ] [ j ] H[i][j] H[i][j]:代表 i i i行第 j j j个向上扩展最长长度.
那么我们可以 O ( n ) O(n) O(n)遍历确定H数组 因为若 m p i − 1 j mp_{i-1j} mpi−1j​与 m p i j mp_{ij} mpij​相同则说明 i ， j i，j i，j这个点不可向上衍生，那么 H [ i ] [ j ] H[i][j] H[i][j]显然为 1 1 1。如果不相同那么 H [ i ] [ j ] H[i][j] H[i][j]可以继承 H [ i − 1 ] [ j ] H[i-1][j] H[i−1][j]，转移为
H [ i ] [ j ] = H [ i − 1 ] [ j ] + 1 H[i][j] =H[i-1][j]+1 H[i][j]=H[i−1][j]+1
然后 L [ i ] [ j ] L[i][j] L[i][j]初始为 j j j，想左枚举 k k k，如果对于 1 < = k < = j 1<=k<=j 1<=k<=j的k满足 H [ i ] [ k ] > = H [ i ] [ j ] H[i][k]>=H[i][j] H[i][k]>=H[i][j]显然说明当前矩阵可以扩展到 k k k，此时我们已经事先确定了 L [ i ] [ k ] L[i][k] L[i][k]那么我们显然可以直接让 L [ i ] [ j ] = L [ i ] [ k ] L[i][j]=L[i][k] L[i][j]=L[i][k]以便大大减少时间复杂度。这就是 L L L数组的转移。 L [ i ] [ j ] = L [ i ] [ k ] L[i][j]=L[i][k] L[i][j]=L[i][k]（R数组则同理向右枚举）
现在我们可以发现， H H H数组只与 i i i和 i − 1 i-1 i−1有关，而 L L L和 R R R数组只与当前层 i i i有关那么我们可以将 H ， R ， L H，R，L H，R，L数组都变为一维数组以减少空间使用。
最后我们将 H ， L ， R H，L，R H，L，R数组全部规划完成后就会发现，对于每个点 j j j，他的 H [ j ] H[j] H[j]记录的是他的最高高度， L [ j ] L[j] L[j]是这个高度下向左衍生能衍生到多少， R [ j ] R[j] R[j]是向右衍生能衍生到多少，那么这个时候这个点衍生出来的矩形就是 ( R [ j ] − L [ j ] + 1 ) ∗ H [ j ] (R[j]-L[j]+1)*H[j] (R[j]−L[j]+1)∗H[j]然后用一个 a n s ans ans记录一下最大值即可。
这个时候知道了矩形公式的你还会不知道正方形公式吗？
当然不知道也没关系，我会告诉你的。
m i n ( R [ j ] − L [ j ] + 1 , H [ j ] ) 2 min(R[j]-L[j]+1,H[j])^2 min(R[j]−L[j]+1,H[j])2
接下来你就完成了一个洛谷蓝题，恭喜你！（可以到洛谷P1169试试哦）
上代码！

#include
using namespace std;
#define int long long
#define endl 'n'
#define fo(x,a,b) for(int x=a;x<=b;x++)
#define of(x,a,b) for(int x=a;x>=b;x--)
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PI acos(-1)
#define pb push_back
#define lowbit(a) ((a)&-(a))
#define lbit(a) (__builtin_ffsll(a))
#define ubit(a) (64-__builtin_clzll(a))
#define fi first
#define se second
int A[2003][2003],B[2003][2003];
int mp[2002][2002];

int L[2002],R[2002],H[2002];
int ans1,ans2;
int n,m;
void bl(int x){
	fo(i,1,m){
		if(x==1)H[i]=1;
		else{
			if(mp[x-1][i]!=mp[x][i])H[i]+=1;
			else H[i]=1;
		}
	}
	fo(i,1,m){
		L[i]=i;
		int l=i;
		while(l>1&&((i-l+1)%2==1?mp[x][i]!=mp[x][l-1]:mp[x][i]==mp[x][l-1])&&H[l-1]>=H[i]){
			L[i]=L[l-1];
			l=L[l-1];
		}
	}
	of(i,m,1){
		R[i]=i;
		int r=i;
		while(r=H[i]){
			R[i]=R[r+1];
			r=R[r+1];
		}
	}
	fo(i,1,m){
		ans1=max(ans1,(R[i]-L[i]+1)*H[i]);
		if(R[i]-L[i]+1>=H[i])ans2=max(ans2,H[i]*H[i]);
	}
}

void solve(){
	cin>>n>>m;
	fo(i,1,n){
		fo(j,1,m){
			cin>>A[i][j];
		}
	}
	fo(i,1,n){
		fo(j,1,m){
			cin>>B[i][j];
		}
	}
	fo(i,1,n){
		fo(j,1,m){
			int x=A[i][j]+B[i][j];
			if(x%4==0||x%4==1)mp[i][j]=1;
			else mp[i][j]=0;
		}
	}
	fo(i,1,n)bl(i);
	cout<
	close();
	int T;
	T=1;
	while(T--)solve();
    return 0;
}

简单题自然简单两句讲懂对吧，我们知道最终要尽可能把更多的石头放进水里，那么既然石头能放进水里了，水自然会升高，升高多少呢？显然是石头的体积除以水槽的底面积，那么既然水面升高的高度确定了，那我们只要让石头占用的高度尽可能小就行了呀。那么我们获得了一个公式：每个石头的贡献为： 水 面 升 高 高 度 − 石 头 高 度 水面升高高度-石头高度 水面升高高度−石头高度
因为石头只有三个面，那么直接判断一下三个面中能放下的面的最小值即可。这时我们就对每个石头计算出了他的贡献 W [ i ] W[i] W[i]。那么用一个 n o w h nowh nowh记录当前水面高度与石头高度的差值然后 s o r t sort sort一遍从小到大取石头，直到取到石头高度高于水面高度即可。

#include
using namespace std;
#define int long long
#define endl 'n'
#define fo(x,a,b) for(int x=a;x<=b;x++)
#define of(x,a,b) for(int x=a;x>=b;x--)
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PI acos(-1)
#define pb push_back
#define lowbit(a) ((a)&-(a))
#define lbit(a) (__builtin_ffsll(a))
#define ubit(a) (64-__builtin_clzll(a))
#define fi first
#define se second
const int N=2e5+5;
vectorW(N,1e8);
void solve(){
	int n,m,q;
	double nowh;
	cin>>n>>m>>nowh>>q;
	int chang=max(n,m),kuan=min(n,m);
	double S=chang*kuan;
	fo(i,1,q){
		int a,b,c;
		cin>>a>>b>>c;
		int V=a*b*c;
		double H=V/S;
		if(min(a,b)<=kuan&&max(a,b)<=chang){
			W[i]=min(W[i],c-H);
		}
		if(min(a,c)<=kuan&&max(a,c)<=chang){
			W[i]=min(W[i],b-H);
		}
		if(min(c,b)<=kuan&&max(c,b)<=chang){
			W[i]=min(W[i],a-H);
		}
	}
	sort(W.begin()+1,W.begin()+1+q);
	int ans=0;
	fo(i,1,q){
		if(nowh-W[i]>0){
			ans++;nowh-=W[i];
		}
		else break;
	}
	cout<
	close();
	int T;
	T=1;
	while(T--)solve();
    return 0;
}