526互联

2024.1.6做题总结

发布时间 2024-01-06 18:43:23作者: LiJoQiao

luogu2258 [NOIP2014 普及组] 子矩阵
本题乍一看数据范围很小，但是如果暴力的话时间复杂度为 \(O(C^r_nC^c_m)\)，在最坏情况（\(r=\frac{1}{2}n,c=\frac{1}{2}m\)）下过不了。

本题满足最优化，但是没得贪，二维好像不好跑 dp 啊。
可以枚举哪些行，然后跑一维的 dp。

我们用一个 dfs 固定一下每次考虑哪些行，然后将每列的行间差的和求出来，用一个 dp[i][j] 代表在第 \(i\) 列选了 \(j\) 列的最小代价，然后进行转移即可。

做法是 \(O(C^r_nn^3)\) 的，可以通过。

代码如下。

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=16+5,MAXM=16+5;
int n,m,r,c,a[MAXN][MAXM],ans=0x3f3f3f3f,hang[MAXN],lc[MAXM],dp[MAXM][MAXM];
bool vis[MAXN];
template<typename T>
T read(){
	T f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return f*x; 
}
namespace sol{
	int calc(int x,int y){
		int ret=0;
		for(int i=1;i<=r;++i){
			ret+=abs(a[hang[i]][y]-a[hang[i]][x]);
		}
		return ret;
	}
	void dfs(int dep,int lst){
		if(dep>=r){
			memset(dp,0x3f,sizeof(dp));
			for(int i=1;i<=m;++i)dp[i][1]=lc[i];
			for(int i=2;i<=m;++i){
				for(int j=2;j<=min(i,c);++j){
					for(int k=j-1;k<i;++k){
						dp[i][j]=min(dp[k][j-1]+calc(k,i),dp[i][j]);
					}
					dp[i][j]+=lc[i];
				}
				ans=min(ans,dp[i][c]);
			}
		}
		for(int i=lst+1;i<=n;++i){
			if(!vis[i]){
				vis[i]=1;
				hang[dep+1]=i;
				for(int j=1;j<=m;++j){
					lc[j]+=abs(a[hang[dep]][j]-a[i][j]);
				}
				dfs(dep+1,i);
				for(int j=1;j<=m;++j){
					lc[j]-=abs(a[hang[dep]][j]-a[i][j]);
				}
				vis[i]=0;
			}
		}
	}
	void solve(){
		n=read<int>();m=read<int>();r=read<int>();c=read<int>();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				a[i][j]=read<int>();
			}
		}
		for(int i=1;i+r-1<=n;++i){
			hang[1]=i;
			vis[i]=1;
			dfs(1,i);
			vis[i]=0;
		}
		printf("%d\n",ans);
	}
}
int main(){
	sol::solve();
	return 0;
}

当遇到一些二维之类的难处理的信息的时候，不妨用枚举将信息简化一下，可能会存在更优的做法。

[ABC293G] Triple Index

第一次写莫队。
题解里都说应该作为莫队的板子，我觉得是这样的。
组合数学不好，同学帮忙才过，怄火。

没啥好的数据结构可以在线维护这个问题。
但是如果在暴力的基础上，开个桶统计每个数出现次数求得一个区间的答案，把区间的左右两端加上或删去一个数的话转移是 \(O(1)\) 的。

如果用莫队的话，这个题的复杂度是 \(O(n\sqrt n)\)。

组合数部分，因为我比较菜，一开始考虑 \(C^m_n=\frac{n!}{m!(n-m)!}\)，还有怕溢出，所以用 C[i]=C[i-1]/(i-3)*i 转移的。
然而不一定存在 \((i-3)\mid C^3_{i-1}\)。
除法和乘法换过来没爆掉的话正确性可以保证，爆掉就不能保证。
后来 lzc 给我换了 C[i]=i*(i-1)*(i-2)/6;。
过了。

代码如下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN=2e5+10;
ll C[MAXN];
int n,a[MAXN],Q,bucket[MAXN],tl,tr;
ll ans[MAXN],tans;
struct query{
	int l,r,id;
}q[MAXN]; 
template<typename T>
T read(){
	T x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x;
}
namespace sol{
	bool cmp1(query x,query y){return x.l<y.l;}
	bool cmp2(query x,query y){return x.r<y.r;}
	void C_init(){
		C[0]=C[1]=C[2]=0;
		C[3]=1;
		for(ll i=4;i<MAXN;++i){
			C[i]=i*(i-1)*(i-2)/6;
		}
	}
	void solve(){
		sol::C_init();
		n=read<int>();Q=read<int>();
		for(int i=1;i<=n;++i)a[i]=read<int>();
		for(int i=1;i<=Q;++i){
			q[i].l=read<int>();q[i].r=read<int>();q[i].id=i;
		}
		sort(q+1,q+Q+1,sol::cmp1);
		int T=sqrt(Q);
		for(int i=1;i<=T;++i){
			sort(q+(i-1)*T+1,q+i*T+1,sol::cmp2);
		}
		if(T*T!=Q)sort(q+T*T+1,q+Q+1,sol::cmp2);
		tl=tr=1;++bucket[a[tl]];
		for(int i=1;i<=Q;++i){
			while(tl>q[i].l){
				--tl;
				++bucket[a[tl]];
				tans+=C[bucket[a[tl]]]-C[bucket[a[tl]]-1];
			}
			while(tr<q[i].r){
				++tr;
				++bucket[a[tr]];
				tans+=C[bucket[a[tr]]]-C[bucket[a[tr]]-1];
			}
			while(tl<q[i].l){
				tans-=C[bucket[a[tl]]]-C[bucket[a[tl]]-1]; 
				--bucket[a[tl]];
				++tl;
			}
			while(tr>q[i].r){
				tans-=C[bucket[a[tr]]]-C[bucket[a[tr]]-1]; 
				--bucket[a[tr]];
				--tr;
			}
			ans[q[i].id]=tans;
		}
		for(int i=1;i<=Q;++i){
			printf("%lld\n",ans[i]);
		}
	}
}
int main(){
	sol::solve();
	return 0;
}

莫队可以用在一些在线没思路但是查询转移比较简单的题中。

luogu1570 KC 喝咖啡

复习下二分。
做题的时候卡精度了，下次精确到 \(x\) 位小数的时候 \(eps\) 设为 \(1^{-x-2}\)。

这道题可能会有一个贪心的想法，每次选择 \(\frac{v_i}{c_i}\) 最大的，但是这个贪心假了。
反例：

3 2
1000 10
1000 100
1 1

这个题直接做不好做，但是判定很简单。
我们可以检验 \(\frac{\sum v_i}{\sum c_i}\) 与一个数 \(x\) 的关系。
两个式子同时乘 \(\sum c_i\) 就转化成检验 \(\sum v_i\) 与 \(x\times\sum c_i\) 的关系。
我们可以对于每个调料计算其 \(v_i-x\times c_i\) 的值，然后排序选取这个值大的调料，最后判断这些值的和是否大于等于 \(0\) 即可。
然后上个二分就做完了。

好像可以用 01 分数规划做，但是我不会。

代码如下。

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=200+10;
constexpr double eps=1e-5;
int n,m;
struct item{
	int v,c;
	double val;
}it[MAXN];
template<typename T>
T read(){
	T f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return f*x;
}
namespace sol{
	bool cmp(item x,item y){return x.val>y.val;}
	void solve(){
		n=read<int>();m=read<int>();
		for(int i=1;i<=n;++i){
			it[i].v=read<int>();
		}
		for(int i=1;i<=n;++i){
			it[i].c=read<int>();
		}
		double l=0,r=2e6+10;
		while(r-l>eps){
			double mid=(l+r)/2;
			for(int i=1;i<=n;++i){
				it[i].val=it[i].v-it[i].c*mid;
			}
			sort(it+1,it+n+1,cmp);
			double tot=0;
			for(int i=1;i<=m;++i){
				tot+=it[i].val;
			}
			if(tot>0){
				l=mid;
			}
			else if(tot==0)r=l=mid;
			else{
				r=mid;
			}
		}
		printf("%.3lf",l);
	}
}
int main(){
	sol::solve();
	return 0;
}

这种最优化的题可能是二分做法，对于一些式子可以将其转化一下，也许可以得到一个简单的判定，然后用二分可以做出。