526互联

Codeforces Round 890 (Div. 2) supported by Constructor Institute

发布时间 2023-08-06 22:08:04作者: 空気力学の詩

Preface

现在开始严格按照双号上分法来打CF了，大致就是每次比赛都拿两个号中分较少的那个打，这样可以保证两个号的最高分不降

然后昨天打完就后悔了，没有拿hl666那个号打导致没抓住难得的上分机会，本来可以打到橙名渡劫局的但分全加在Kusanagi_Misuzu那个号上了

不过昨天这场其实可以打的更好的，前面被C搞了导致后面时间不够宽裕了，最后写完E1还有25min其实完全可以搏一搏E2的，但就是下意识地以为自己写不来就没想了

后面一看题解妈的就是我前两天和ztc说的多重背包在总体积较小时的优化，血妈亏

A. Tales of a Sort

签到题，不难发现如果\(a_i> a_{i+1}\)，则我们只要要操作\(a_i\)次来把这两个数都变成\(0\)，因此取最大值输出即可

#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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=55;
int t,n,a[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]);
		int ans=0; for (i=1;i<n;++i) if (a[i]>a[i+1]) ans=max(ans,a[i]);
		printf("%d\n",ans);
	}
	return 0;
}

B. Good Arrays

刚开始秒出了一个假算法WA了一发，后面冷静下来才发现我是傻逼

首先特判\(n=1\)时无解，否则我们不妨令原序列所有\(a_i\ne1\)的位置都有\(b_i=1\)，而\(a_i=1\)的位置都有\(b_i=2\)

做完之后求出\(\sum_{i=1}^n b_i\)和\(\sum_{i=1}^n a_i\)比较下即可，对于多出的部分我们总可以调整使得序列仍然满足要求

#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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=100005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; LL sum=0; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
		if (n==1) { puts("NO"); continue; }
		LL ret=0; for (i=1;i<=n;++i) ret+=(a[i]!=1?1:2);
		puts(ret<=sum?"YES":"NO");
	}
	return 0;
}

C. To Become Max

这题就是很容易想一些假算法，刚开始写了个样例都过不去，后面重新想了下才过

考虑枚举最后最大值出现的位置，刚开始想着是模拟加数的过程，但十分难写

后面发现其实大可以二分最后变成的值，然后转化成判定性问题后就很好办了

假设当前变成的最大值为\(x\)，则最后这一段数一定形如\(x,x-1,x-2\cdots\)，只要中间存在某个位置大于等于目标值既可以中止了

注意特判处理到最后一个数的情况，具体实现可以看代码，复杂度\(O(n^2\log a_i)\)

#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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1005,INF=1e9;
int t,n,k,a[N];
inline bool check(CI tar)
{
	for (RI i=1,j;i<=n;++i)
	{
		int ret=0; for (j=i;j<=n;++j)
		{
			if (tar-(j-i)<=a[j]) break;
			ret+=tar-(j-i)-a[j];
			if (j==n) ret+=INF;
		}
		if (ret<=k) return 1;
	}
	return 0;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; int mx=0; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld",&a[i]),mx=max(mx,a[i]);
		int l=mx,r=mx+k,mid,ret; while (l<=r)
		if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
		printf("%lld\n",ret);
	}
	return 0;
}

D. More Wrong

比赛时过的人不多但我感觉是个很一眼的题

首先考虑一种保证正确性的做法，假设我们已经知道了\([1,i]\)中最大值的位置\(x\)

那么考虑加入\(i+1\)后最大值无非两种情况，保留\(x\)或者变成\(i+1\)

而我们只需要比较\([1,i]\)的逆序对数量是否和\([1,i+1]\)的逆序对数量相同即可

若相同则说明\(i+1\)比\([1,i]\)中的所有数都大，自然是\([1,i+1]\)的最大值，否则则说明\([1,i]\)中有至少一个数大于\(a_{i+1}\)，则说明最大值仍为\(x\)

然后要优化的话是显然的，我们用分治法每次先递归求出子区间的最大值位置，再合并即可

稍微列出最坏情况下的式子的代价算一下可以得到：

\[2\times n^2+4\times (\frac{n}{2})^2+8\times (\frac{n}{4})^2+\cdots\\ =(2+1+\frac{1}{2}+\frac{1}{4}+\cdots)\times n^2<4n^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>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
int t,n;
inline LL ask(CI l,CI r)
{
	printf("? %d %d\n",l,r); fflush(stdout);
	LL x; scanf("%lld",&x); return x;
}
inline int solve(CI l=1,CI r=n)
{
	if (l==r) return l;
	int mid=l+r>>1,lpos=solve(l,mid),rpos=solve(mid+1,r);
	if (lpos+1==rpos)
	{
		LL res=ask(lpos,rpos);
		if (res==1) return lpos; return rpos;
	}
	LL res1=ask(lpos,rpos),res2=ask(lpos,rpos-1);
	if (res1==res2) return rpos; return lpos;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t) scanf("%d",&n),printf("! %d\n",solve()),fflush(stdout);
	return 0;
}

E1. PermuTree (easy version)

首先有个很显然的性质就是每个子树内的数一定是一段连续的区间，正确性显然

因此我们考虑统计某个点的答案时，只要将它的子树划分为两类，一类是最后填的数小于它本身的，一类是大于它本身的，不难发现两类集合的大小之积就是贡献

那么问题其实可以转化为一个0/1背包问题，直接暴力做就可以通过E1了

#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_set>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=5005;
int n,x,sz[N]; vector <int> v[N]; LL ans;
inline void DFS(CI now=1)
{
	sz[now]=1; for (int to:v[now]) DFS(to),sz[now]+=sz[to];
	unordered_set <int> s; s.insert(0);
	for (int to:v[now])
	{
		unordered_set <int> t=s;
		for (int x:s) t.insert(x+sz[to]);
		s=t;
	}
	LL ret=0; for (int x:s) ret=max(ret,1LL*x*(sz[now]-1-x));
	ans+=ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
	return DFS(),printf("%lld",ans),0;
}

E2. PermuTree (hard version)

曾记得某天ztc问过我和这个一模一样的东西，当时我秒出了做法但现在我TMD的想都懒得想了可海星

考虑这个0/1背包的一大特点就是总体积和也是\(O(n)\)级别的，利用类似于根号分治的思想我们知道不同类的物品的个数很少

因此可以把它转化成多重背包来做，为了优化可以再加一个二进制分组上去，当然再极限一点的话再套个bitset也不是不行

同时有一个很有用的剪枝就是当存在某个子树的大小大于其它所有子树大小之和时可以直接计算贡献，实测发现这个剪枝非常有效

总复杂度不太好写表达式，总之大概跑1s左右

#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_set>
#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 unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1e6+5;
int n,x,sz[N],f[N]; vector <int> v[N]; LL ans;
inline void DFS(CI now=1)
{
	sz[now]=1; int mx=0; for (int to:v[now])
	DFS(to),sz[now]+=sz[to],mx=max(mx,sz[to]);
	if (mx*2>=sz[now]-1) return (void)(ans+=1LL*mx*(sz[now]-1-mx));
	int lim=(sz[now]-1)/2; map <int,int> rst;
	RI i,j; for (f[0]=1,i=1;i<=lim;++i) f[i]=0;
	for (int to:v[now]) ++rst[sz[to]];
	int ret=0; for (auto [x,y]:rst)
	{
		for (int k=1;y>=k;y-=k,k<<=1)
		{
			int v=k*x; for (j=lim;j>=v;--j)
			if (f[j-v]) f[j]=1,ret=max(ret,j);
		}
		if (y)
		{
			int v=y*x; for (j=lim;j>=v;--j)
			if (f[j-v]) f[j]=1,ret=max(ret,j);
		}
	}
	ans+=1LL*ret*(sz[now]-1-ret);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
	return DFS(),printf("%lld",ans),0;
}

Postscript

现在两个号都是2000+了，感觉有望趁状态好冲一波橙名了