526互联

Codeforces Round 892 (Div. 2)

发布时间 2023-08-13 21:08:45作者: 空気力学の詩

Preface

最接近橙名的一场，可惜给我一个小时也没想到E的关键点，后面徐神一点拨就懂了

虽然现在这个号已经到渡劫局了但因为之前有场比赛给了ztc一份代码然后他直接没咋改交上去了，估计下次roll Rating的时候这个号要掉200来分了

嘛不过也无所谓反正下次打另一个号冲分，而且像我这种永远写不来Div2 E的人纯靠手速打上2100真的有说服力吗

A. United We Stand

签到题，把最大的数都放在\(c\)即可，当且仅当所有数相等时无解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,a[N],b[N],c[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=0; for (i=2;i<=n;++i) if (a[i]!=a[1]) flag=1;
		if (!flag) { puts("-1"); continue; }
		int nb=0,nc=0,mx=0; for (i=1;i<=n;++i) mx=max(mx,a[i]);
		for (i=1;i<=n;++i) if (a[i]!=mx) b[++nb]=a[i];
		for (i=1;i<=n;++i) if (a[i]==mx) c[++nc]=a[i];
		for (printf("%d %d\n",nb,nc),i=1;i<=nb;++i)
		printf("%d%c",b[i]," \n"[i==nb]);
		for (i=1;i<=nc;++i) printf("%d%c",c[i]," \n"[i==nc]);
	}
	return 0;
}

B. Olya and Game with Arrays

不难发现由于所有数的最小值一定会在某个序列中造成贡献，那么我们不妨把所有数组中的最小值都扔到一个数组中

维护每个数组的次小值然后找一个最小的减去即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=25005;
int t,n,m,x,mi[N],smi[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		{
			scanf("%d",&m); vector <int> num;
			for (j=1;j<=m;++j) scanf("%d",&x),num.push_back(x);
			sort(num.begin(),num.end());
			mi[i]=num[0]; smi[i]=num[1]; 
		}
		int allmi=mi[1],mismi=smi[1]; LL sum=0;
		for (i=1;i<=n;++i) allmi=min(allmi,mi[i]),mismi=min(mismi,smi[i]),sum+=smi[i];
		printf("%lld\n",allmi+sum-mismi);
	}
	return 0;
}

C. Another Permutation Problem

很有意思的一个题，首先由于数据范围很小我们可以直接暴力枚举\(\max_{j = 1}^{n} p_j \cdot j\)的值

然后贪心地从大到小考虑每个\(p_i\)，将它能匹配的数中最大的找出来和它匹配即可

我刚开始的时候用了个set实现，然后跑了手\(n=250\)发现要跑5s……

但直觉告诉我们\(\max_{j = 1}^{n} p_j \cdot j\)的值肯定不会太小，然后把\(n=250\)的输出来一看大概是\(57000+\)左右，所以就把枚举\(\max_{j = 1}^{n} p_j \cdot j\)的值调整成\([\max(n^2-15000,1),n^2]\)即可

后面问了下ztc发现其实可以把set那个地方用并查集维护，就是删去一个数的时候把它接到前面的数上，就可以用大致线性的复杂度来做了

但据说这题可以打表发现最优的答案就是把\(\{1,2,3,\cdots,n\}\)的某个后缀翻转，这样就可以枚举后缀然后做到总复杂度\(O(n^2)\)了，不过原理未知

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=255;
int t,n;
inline int solve(CI x)
{
	set <int> s; RI i; int ret=0;
	for (i=1;i<=n;++i) s.insert(i);
	for (i=n;i>=1;--i)
	{
		auto it=s.upper_bound(x/i);
		if (it==s.begin()) return 0;
		--it; ret+=*it*i; s.erase(it);
	}
	return ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; int ans=0; for (scanf("%d",&n),i=max(1,n*n-15000);i<=n*n;++i)
		ans=max(ans,solve(i)-i); printf("%d\n",ans);
	}
	return 0;
}

D. Andrey and Escape from Capygrad

首先由于这题传送区间的性质，不难发现答案随着起点的增加是不减的，这就提醒我们可以从大到小递推答案

考虑用类似扫描线的思路维护出每个点被覆盖的区间，那么这些区间的\(f_{b_i}\)中的最大值就可以用来更新答案

离散化下标后用树状数组维护最值即可，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
struct ifo
{
	int x,id;
	inline ifo(CI X=0,CI ID=0)
	{
		x=X; id=ID;
	}
	friend inline bool operator < (const ifo& A,const ifo& B)
	{
		return A.x>B.x;
	}
}o[N]; int t,n,l[N],a[N],b[N],r[N],q,x[N],rst[N],cnt,tot,ans[N];
class Tree_Array
{
	private:
		int mx[N],lim;
	public:
		#define lowbit(x) (x&-x)
		inline void init(CI n)
		{
			lim=n; for (RI i=1;i<=lim;++i) mx[i]=0;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret=max(ret,mx[x]); return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=lim;x+=lowbit(x)) mx[x]=max(mx[x],y);
		}
		#undef lowbit
}BIT;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),cnt=0,i=1;i<=n;++i)
		scanf("%d%d%d%d",&l[i],&r[i],&a[i],&b[i]),
		rst[++cnt]=l[i],rst[++cnt]=r[i],rst[++cnt]=a[i],rst[++cnt]=b[i];
		for (scanf("%d",&q),i=1;i<=q;++i) scanf("%d",&x[i]),rst[++cnt]=x[i];
		sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
		auto find=[&](CI x)
		{
			return lower_bound(rst+1,rst+cnt+1,x)-rst;
		};
		for (tot=0,i=1;i<=n;++i)
		{
			l[i]=find(l[i]); r[i]=find(r[i]); a[i]=find(a[i]); b[i]=find(b[i]);
			o[++tot]=ifo(b[i],i);
		}
		for (i=1;i<=q;++i) x[i]=find(x[i]),o[++tot]=ifo(x[i],n+i);
		for (sort(o+1,o+tot+1),BIT.init(cnt),i=1;i<=tot;++i)
		{
			int tmp=max(rst[o[i].x],BIT.get(o[i].x));
			if (o[i].id<=n) BIT.add(l[o[i].id],tmp); else ans[o[i].id-n]=tmp;
		}
		for (i=1;i<=q;++i) printf("%d%c",ans[i]," \n"[i==q]);
	}
	return 0;
}

E. Maximum Monogonosity

首先看到绝对值的式子就考虑拆绝对值，我们分四种情况来转移，最后取\(\max\)后一定能得到正确的答案

考虑朴素的DP，\(f_{i,j}\)表示前\(i\)个数，选的区间长度为\(j\)的最大答案，则转移方程为：

\[f_{k,j}+|a_{k+1}-b_i|+|b_{k+1}-a_i|\to f_{i,j+(i-k)} \]

乍一看感觉因为第二个下标的缘故很难维护答案，其实稍作观察就会发现转移只能在\(i-j\)相同的\(f_{i,j}\)之间发生

因此我们对于所有\(i-j\)的值以及\(4\)种情况分别维护最大值即可\(O(1)\)转移了，复杂度\(O(nk)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=3005,INF=1e18,s1[4]={1,1,-1,-1},s2[4]={1,-1,1,-1};
int t,n,k,a[N],b[N],f[N][N],mx[N][4];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j,s; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld",&a[i]);
		for (i=1;i<=n;++i) scanf("%lld",&b[i]);
		for (f[0][0]=0,i=1;i<=k;++i) f[0][i]=-INF;
		for (i=1;i<=n;++i) for (j=1;j<=i;++j) f[i][j]=-INF;
		auto calc=[&](CI x,CI y,CI tp)
		{
			return f[x][x-y]+a[x+1]*s1[tp]+b[x+1]*s2[tp];
		};
		for (s=0;s<4;++s) for (mx[0][s]=calc(0,0,s),i=1;i<=n;++i) mx[i][s]=-INF;
		for (i=1;i<=n;++i)
		{
			for (j=0;j<=k;++j) f[i][j]=f[i-1][j];
			for (j=0;j<=min(i,k);++j)
			{
				int dlt=i-j; for (s=0;s<4;++s)
				f[i][j]=max(f[i][j],mx[dlt][s]-b[i]*s1[s]-a[i]*s2[s]);
				for (s=0;s<4;++s) mx[dlt][s]=max(mx[dlt][s],calc(i,dlt,s));
			}
		}
		printf("%lld\n",f[n][k]);
	}
	return 0;
}

Postscript

F题因为今天下午打百度之星所以没时间补了，而且看了一眼感觉不容易就先弃了