首页 > 其他分享 >EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)

EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)

时间：2024-07-01 17:45:15浏览次数：21  
标签：Summer typedef const Institute long int Div include define

Preface

沟槽的又掉分了，难得凑齐了五个人打LOL结果只玩了两把就去打这场CF了，早知道继续玩了

这场经典开局不顺，C想了一堆假做法到30min的时候才出，D题上来就莽一个贪心然后爆WA两发后还不知道错哪了，卡到90min的时候心态小崩

滚去看了眼E马上秒了后回来发现D是个很一眼的DP，写完后就只剩下30min了

最后尝试逆转一个F1的 \(O(n^4)\) 区间DP，但感觉细节有点多写不完了就写了个迭代加深+卡时的爆搜，最后也是经典逆转失败

总结就是太唐氏了，急需队友拯救一下

A. Upload More RAM

签到，答案为 \(1+(n-1)\times k\)

#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<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,k;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%d",&n,&k),printf("%d\n",(n-1)*k+1);
	return 0;
}

B. K-Sort

定义 \(b_i=\max(0,a_{i-1}-a_i)\)，不难发现此时操作为选出 \(\{b_i\}\) 的一些位置，将这些位置上的值减 \(1\)，操作的代价就是选出的位置数量 \(+1\)

显然贪心地每次选尽可能多的位置是最优的，手玩一下贡献就是 \(\sum_{i=1}^n b_i+\max_\limits{1\le i\le n} b_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>
#include<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,h[N],f[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",&h[i]);
		for (f[n]=h[n],i=n-1;i>=1;--i) f[i]=max(h[i],f[i+1]+1);
		printf("%d\n",f[1]);
	}
	return 0;
}

C. Basil's Garden

刚开始想假了搞了一堆用单调栈分段的神秘做法，后面发现就是个丁真递推题

令 \(f_i\) 表示第 \(i\) 朵花的高度第一次变为 \(0\) 的时间，显然 \(\{f_i\}\)单调不升

那我们可以倒着递推，从 \(f_n=h_n\) 开始，假设现在考虑第 \(i\) 朵花

不难发现如果它减少的时候不受右边的花的影响，贡献为 \(h_i\)；如果会因为 \(i+1\) 挡住它（挡住的次数一定是一次），则贡献为 \(f_{i+1}+1\)；两者取较大的递推即可

#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<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,h[N],f[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",&h[i]);
		for (f[n]=h[n],i=n-1;i>=1;--i) f[i]=max(h[i],f[i+1]+1);
		printf("%d\n",f[1]);
	}
	return 0;
}

D. World is Mine

首先将原数组离散化，显然我们只关系本质不同的数有多少个以及每个数有多少个，设转化后的数组为 \(c\)

不难发现Alice的策略很trivial，即每次在所有能选的蛋糕中选权值最小的，因此我们要考虑的只有Bob的行为

假设Bob想要让Alice拿不到第 \(i\) 个蛋糕，则需要满足 \(c_i<=i-1\)，即假设之前的 \(i-1\) 个蛋糕都给Alice，Bob需要在这些轮次中把第 \(i\) 个蛋糕拿完

这个条件是有可加性的，即我们令 \(f_{i,j}\) 表示当前处理了前 \(i\) 个蛋糕，当Alice拿的蛋糕数量减去Bob拿的蛋糕权值为 \(j\) 时，Alice最少会拿到多少个蛋糕，转移如下：

  • 下个蛋糕给Alice：\(f_{i+1,j+1}\leftarrow f_{i,j}+1\)
  • 下个蛋糕给Bob：\(f_{i+1,j-c_{i+1}}\leftarrow f_{i,j}\ (j\ge a_{i+1})\)

总复杂度 \(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<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005,INF=1e9;
int t,n,a[N],c[N],f[N][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) c[i]=0;
		for (i=1;i<=n;++i) scanf("%d",&a[i]),++c[a[i]];
		sort(a+1,a+n+1); n=unique(a+1,a+n+1)-a-1;
		for (i=1;i<=n;++i) a[i]=c[a[i]];
		for (i=0;i<=n;++i) for (j=0;j<=n;++j) f[i][j]=INF;
		for (f[0][0]=i=0;i<n;++i) for (j=0;j<=n;++j)
		{
			if (f[i][j]==INF) continue;
			f[i+1][j+1]=min(f[i+1][j+1],f[i][j]+1);
			if (a[i+1]<=j) f[i+1][j-a[i+1]]=min(f[i+1][j-a[i+1]],f[i][j]);
		}
		int ans=INF; for (i=0;i<=n;++i) ans=min(ans,f[n][i]);
		printf("%d\n",ans);
	}
	return 0;
}

E. Wonderful Tree!

这题从下往上的贪心策略显然，若当前点 \(x\) 不满足要求则在其儿子中选一个点 \(y\) 增加其权值

而增加 \(a_y\) 的时候可能会连带着需要修改 \(y\) 的儿子，从而产生一条到叶子的路径上都要修改的情况

而对每个点进行增加操作时根据操作次数的不同对应的代价也不同，手玩一下后我们可以发现以下形式化策略

对每个点用若干个二元组 \((c_1,v_1),(c_2,v_2),\dots,(c_k,v_k),(c_{k+1},\infty)\) 来刻画在其上增加权值的贡献，意义为前 \(v_1\) 次增加贡献为 \(c_1\)；接下来的 \(v_2\) 次增加贡献为 \(c_2\)；以此类推……

最后当前面的贡献都增加完后，后面还有无限次增加贡献为 \(c_{k+1}\) 的操作可以进行

不难发现这个模型是支持子树合并的，即我们每次将子树内的信息合并后贪心地先选贡献小的即可

直接暴力实现的复杂度是 \(O(n^2)\) 的，感觉可以用线段树合并和线段树上二分做到 \(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<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005;
int t,n,x,a[N],g[N],ans; vector <int> v[N]; vector <pi> f[N];
inline void DFS(CI now=1)
{
	if (v[now].empty()) return (void)(g[now]=1); g[now]=1e9;
	RI i; int sum=0; static int tmp[N];
	for (auto to:v[now]) DFS(to),sum+=a[to],g[now]=min(g[now],g[to]);
	for (i=1;i<=n;++i) tmp[i]=0;
	for (auto to:v[now]) for (auto [dep,val]:f[to]) tmp[dep]+=val;
	if (sum<=a[now])
	{
		int left=a[now]-sum;
		for (i=1;i<g[now]&&left>0;++i)
		{
			int dlt=min(left,tmp[i]);
			left-=dlt; tmp[i]-=dlt; ans+=dlt*i;
		}
		if (left>0) ans+=left*g[now];
	} else f[now].push_back(pi(1,sum-a[now]));
	for (i=1;i<=n;++i) if (tmp[i]) f[now].push_back(pi(i+1,tmp[i]));
	++g[now];
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
		for (i=2;i<=n;++i) scanf("%lld",&x),v[x].push_back(i);
		ans=0; DFS(); printf("%lld\n",ans);
		for (i=1;i<=n;++i) v[i].clear(),f[i].clear();
	}
	return 0;
}

F1. Interesting Problem (Easy Version) && F2. Interesting Problem (Hard Version)

很有启发性的一个区间DP题，虽然感觉这个降状态维数的trick之前见过但比赛的时候一点没想起来

首先不难发现最优的操作序列形如括号序列，即将每次删除的元素分别看成左右括号，则它们在原数组中构成的一定是个合法的括号序列

因此就有一个区间DP的思路，令 \(f_{l,r,x}\) 表示对于区间 \([l,r]\)，在其左侧已经进行的操作次数为 \(x\) 次时，\([l,r]\) 区间内最多能进行多少次操作

这个东西的上界是 \(O(n^4)\) 的，可以通过F1的数据，但要通过F2就需要将其优化至 \(O(n^3)\)

后面问了zzh✌发现可以对状态进行限定，即钦定 \(f_{l,r}\) 为将区间 \([l,r]\) 全部删完需要左边至少操作多少次

之所以这么设状态是因为我们考虑 \([l,m],[m+1,r]\) 这两个相邻的区间，右边的对左边没有任何影响；而右边的区间可以视左边操作的情况适时进行操作，因为我们只要知道操作次数的上界即可

具体的转移的话考虑枚举最后和左端点 \(l\) 匹配的右括号 \(i\)，则区间 \([l,r]\) 内的操作流程为：

先将 \([l+1,i-1]\) 整个区间删完；再将 \((l,i)\) 删除；在这个过程中适时地对 \([i+1,r]\) 进行操作直至将其删完

不难根据定义写出转移方程，而得到了 \(f_{l,r}\) 后我们可以利用另一个DP来计算答案

令 \(g_i\) 表示前 \(i\) 个数中最多能操作多少次，然后每次枚举下次删除的一段来转移即可

假设现在要判断 \([l,r]\) 这段能否被删除，则需要满足 \(f_{l,r}\le g_{l-1}\)，由于 \(\{g_i\}\) 定义的是最多操作次数，因此这个DP的转移是正确的

总复杂度 \(O(n^3)\)

#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<assert.h>
#include<unordered_set>
#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 pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=805,INF=1e9;
int t,n,a[N],f[N][N],g[N];
inline int DP(CI l,CI r)
{
	if (l>r) return 0;
	if (a[l]>l||(a[l]%2)!=(l%2)) return INF;
	if (~f[l][r]) return f[l][r];
	int need=(l-a[l])/2,ret=INF;
	// split into [l+1,i],(l,i),[i+1,r]
	for (RI i=l+1;i<=r;i+=2) if (DP(l+1,i-1)<=need)
	ret=min(ret,max(need,DP(i+1,r)-(i-l-1)/2-1));
	return f[l][r]=ret;
}
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",&a[i]);
		for (i=1;i<=n;++i) for (j=1;j<=n;++j) f[i][j]=-1;
		for (i=0;i<=n;++i) g[i]=0;
		for (i=1;i<=n;++i)
		{
			g[i]=max(g[i],g[i-1]);
			for (j=i+1;j<=n;j+=2)
			if (DP(i,j)<=g[i-1])
			g[j]=max(g[j],g[i-1]+(j-i+1)/2);
		}
		printf("%d\n",g[n]);
	}
	return 0;
}

Postscript

值得一提的是打完这场3h的场后当天晚上一直亢奋地睡不着，一直熬到4点左右才睡

然后第二天9点半左右就醒了然后怎么都睡不着，只能浑浑噩噩地去考下午的英语，喜提爆炸

不过不管怎么说真正的暑假已经开始了，估计这剩下的半年时间是我个人ACM生涯甚至算竞生涯的尾声了，希望能有个好点的结局吧

标签：Summer,typedef,const,Institute,long,int,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/18278515

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99