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

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

时间：2024-08-25 17:38:21浏览次数：10  
标签：tmp typedef August Institute long int Div include define

Preface

两个礼拜前打的比赛拖到现在才写博客，我只能说也是个神人了

这场其实 D2 很快就想到做法了，但自己把自己给否了，后面不管了实现了一发交上去发现过了

然后这天由于 12 点左右室友就关灯睡觉了，我写完 D2 后看了眼 E 没仔细想就睡觉去了，后面发现 E 其实很 trivial

A. Distanced Coloring

签到，手玩发现答案为 \(\min(n,k)\times \min(m,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;
int t,n,m,k;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%d%d",&n,&m,&k),printf("%d\n",min(n,k)*min(m,k));
	return 0;
}

B. Removals Game

考虑在任意一个时刻，如果两个人对应的双端队列两端的元素不同，则先手一定获胜

模拟这个过程，如果两端的元素相同随便取哪一个都不会影响答案

#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;
int t,n,x;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n); deque <int> A,B;
		for (RI i=1;i<=n;++i) scanf("%d",&x),A.push_back(x);
		for (RI i=1;i<=n;++i) scanf("%d",&x),B.push_back(x);
		bool flag=0; while (A.size()>1)
		{
			int x=A.front(),y=A.back();
			if (x!=B.front()&&x!=B.back()) { flag=1; break; }
			if (y!=B.front()&&y!=B.back()) { flag=1; break; }
			A.pop_front();
			if (x==B.front()) B.pop_front(); else B.pop_back();
		}
		puts(flag?"Alice":"Bob");
	}
	return 0;
}

C. Black Circles

思博题，不难发现如果某个圆的圆心到终点的距离比起点到终点的距离短，则一定无解

反过来会发现这个圆一定追不上人，因此总可以设计一种路线来绕开它

#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=100005;
int t,n,x[N],y[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld",&n);
		for (RI i=1;i<=n;++i) scanf("%lld%lld",&x[i],&y[i]);
		scanf("%lld%lld%lld%lld",&x[n+1],&y[n+1],&x[n+2],&y[n+2]);
		auto dist=[&](CI u,CI v)
		{
			return (x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
		};
		int D=dist(n+1,n+2); bool flag=1;
		for (RI i=1;i<=n;++i)
		if (dist(i,n+2)<=D) { flag=0; break; }
		puts(flag?"YES":"NO");
	}
	return 0;
}

D1. DFS Checker (Easy Version)

要判断一个序列是否为合法的 DFS 序，很容易想到把每个点在 DFS 序中出现的位置作为其点权

那么此时一棵树满足条件当且仅当对于树上的每个点，其子树内的点权恰好构成一段连续区间 \([l,r]\)，且当前点的权值恰为 \(l-1\)

等价转化后可以变成这样一个条件，维护每个点子树内点权的最小/最大值，判断这个值和当前点点权以及子树大小的关系即可

由于本题保证树是二叉树，因此直接暴力维护复杂度是 \(O(n\log^2 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 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=300005;
int t,n,q,x,y,fa[N],p[N],a[N],sz[N],ret;
vector <int> v[N]; set <int> son[N];
inline int check(CI now)
{
	return a[now]==*son[now].begin()&&a[now]+sz[now]-1==*son[now].rbegin();
}
inline void DFS(CI now=1,CI fa=0)
{
	sz[now]=1; son[now].insert(a[now]);
	for (auto to:v[now]) if (to!=fa)
	{
		DFS(to,now); sz[now]+=sz[to];
		for (auto tmp:son[to]) son[now].insert(tmp);
	}
	ret+=check(now);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&q); ret=0; fa[1]=0;
		for (RI i=1;i<=n;++i) v[i].clear(),son[i].clear();
		for (RI i=2;i<=n;++i) scanf("%d",&fa[i]),v[fa[i]].push_back(i);
		for (RI i=1;i<=n;++i) scanf("%d",&p[i]),a[p[i]]=i;
		for (DFS();q;--q)
		{
			scanf("%d%d",&x,&y);
			swap(p[x],p[y]); x=p[x]; y=p[y];
			vector <int> vec;
			for (int tmp=x;tmp;tmp=fa[tmp]) vec.push_back(tmp);
			for (int tmp=y;tmp;tmp=fa[tmp]) vec.push_back(tmp);
			sort(vec.begin(),vec.end());
			vec.erase(unique(vec.begin(),vec.end()),vec.end());
			for (auto p:vec) if (p) ret-=check(p);
			for (int tmp=x;tmp;tmp=fa[tmp]) son[tmp].erase(a[x]);
			for (int tmp=y;tmp;tmp=fa[tmp]) son[tmp].erase(a[y]);
			swap(a[x],a[y]);
			for (int tmp=x;tmp;tmp=fa[tmp]) son[tmp].insert(a[x]);
			for (int tmp=y;tmp;tmp=fa[tmp]) son[tmp].insert(a[y]);
			for (auto p:vec) if (p) ret+=check(p);
			puts(ret==n?"YES":"NO");
		}
	}
	return 0;
}

D2. DFS Checker (Hard Version)

上面的做法需要考虑一个点的整个子树，因此基本没有优化空间

但我们真的需要用到整个子树的信息吗，能不能只考虑当前点与它的儿子间的关系呢

一个直观的想法就是检验所有儿子中最小的点权是否为当前点点权加 \(1\)，刚开始我感觉这样很对然后交上去发现 WA 了，遂发现还有形如以下这种情况

出错的原因本质上是由于只考虑最小的儿子，导致可能出现跳出当前子树又跳回来的情况

因此需要加上一个对于点权最大的儿子的 fix，用 set 维护儿子信息即可

#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=300005;
int t,n,q,x,y,fa[N],p[N],a[N],sz[N],ret;
vector <int> v[N]; set <pi> son[N];
inline int check(CI now)
{
	if (son[now].empty()) return 1;
	return a[now]+1==son[now].begin()->fi&&a[now]+sz[now]-sz[son[now].rbegin()->se]==son[now].rbegin()->fi;
}
inline void DFS(CI now=1,CI fa=0)
{
	sz[now]=1; for (auto to:v[now]) if (to!=fa)
	DFS(to,now),sz[now]+=sz[to],son[now].insert({a[to],to});
	ret+=check(now);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&q); ret=0;
		for (RI i=0;i<=n;++i) v[i].clear(),son[i].clear();
		for (RI i=2;i<=n;++i) scanf("%d",&fa[i]),v[fa[i]].push_back(i);
		for (RI i=1;i<=n;++i) scanf("%d",&p[i]),a[p[i]]=i;
		for (DFS(),son[0].insert({a[1],1});q;--q)
		{
			scanf("%d%d",&x,&y);
			swap(p[x],p[y]); x=p[x]; y=p[y];
			vector <int> vec={x,y,fa[x],fa[y]};
			sort(vec.begin(),vec.end());
			vec.erase(unique(vec.begin(),vec.end()),vec.end());
			for (auto p:vec) if (p) ret-=check(p);
			son[fa[x]].erase({a[x],x});
			son[fa[y]].erase({a[y],y});
			swap(a[x],a[y]);
			son[fa[x]].insert({a[x],x});
			son[fa[y]].insert({a[y],y});
			for (auto p:vec) if (p) ret+=check(p);
			puts(ret==n?"YES":"NO");
		}
	}
	return 0;
}

E. Cosmic Rays

今天仔细想了下然后再加上祁神告诉我用个栈维护下就行，发现就是个煞笔题

考虑增量法，先求出之前若干个 pair 加入后的答案，以及用栈维护此时每个 pair 的存活时间

对于新加入的 pair，我们肯定是将其与栈顶的 pair 作比，若二者 \(b_i\) 相同显然可以合并，前面的就不用考虑了

否则若当前栈顶的存活时间小于等于当前 pair 的存活时间，则可以弹出栈顶，直到遇到某个类型相同的 pair 或者栈为空

要注意合并时还要顺带维护出弹掉的 pair 中存活时间的最大值以更新贡献，总复杂度 \(O(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=300005;
int t,n,x,y; pi stk[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld",&n); int top=0,ans=0;
		for (RI i=1;i<=n;++i)
		{
			scanf("%lld%lld",&x,&y); int mx=0;
			while (top)
			{
				if (stk[top].se==y) x+=stk[top--].fi-mx;
				else if (stk[top].fi<=x) mx=max(mx,stk[top--].fi);
				else break;
			}
			stk[++top]={x,y}; ans=max(ans,x);
			printf("%lld%c",ans," \n"[i==n]);
		}
	}
	return 0;
}

F1. Court Blue (Easy Version) && F2. Court Blue (Hard Version)

很神秘的一个题，由于是补题就直接讲 F2 的做法了

这题的核心就是要想到当其中一个数是范围内最大的质数时，大概率是能满足 \(\gcd\) 为 \(1\) 的限制的

因此 F1 直接求出最大和次大质数然后枚举即可，复杂度和范围内相邻的两个质数间的距离有关

对于 F2 的分析也是类似，但需要用 官方题解 中质数密度的思路证明暴力复杂度就是对的，剩下的就是记忆化实现一下

#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=2e7+5,M=1500;
int t,n,m,l,f,vis[N],pri[N],cnt,ok[M][M];
LL ans; bool flag; vector <pi> rollback;
inline void init(CI n)
{
	vis[0]=vis[1]=1;
	for (RI i=2;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i;
		for (RI j=1;j<=cnt&&i*pri[j]<=n;++j)
		if (vis[i*pri[j]]=1,i%pri[j]==0) break;
	}
}
inline LL calc(CI q,CI p)
{
	LL res=1LL*q*l+1LL*p*f;
	if (p<=n) res=max(res,1LL*p*l+1LL*q*f);
	return res;
}
inline void DFS(CI q,CI p)
{
	if (__gcd(q,p)>1) return;
	ans=max(ans,calc(q,p));
	ok[n-q][m-p]=1; rollback.emplace_back(n-q,m-p);
	if (q<n&&!ok[n-q-1][m-p]) DFS(q+1,p);
	if (p==m) return (void)(flag=1);
	if (flag) return;
	if (p<m&&!ok[n-q][m-p-1]) DFS(q,p+1);
	if (flag) return;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(2e7);t;--t)
	{
		scanf("%d%d%d%d",&n,&m,&l,&f);
		int p=m; while (vis[p]) --p;
		ans=0; flag=0; rollback.clear();
		for (RI q=min(n,p-1);!flag;--q)
		{
			ans=max(ans,calc(q,p));
			if (p<m) DFS(q,p+1); else break;
		}
		for (auto [x,y]:rollback) ok[x][y]=0;
		printf("%lld\n",ans);
	}
	return 0;
}

Postscript

这两天也是摆烂摆爽了，每天就是下棋峡谷玩 Gal，但这来之不易的暑假好像也马上就要看到头了说是

标签：tmp,typedef,August,Institute,long,int,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/18379206

相关文章

  • Codeforces Round #900 (Div. 3)
    三年之后第一次打比赛，用小号打了场\(Div.3\)，居然没有AK，感觉实力退步到小学了。A.HowMuchDoesDaytonaCost?若只判断题，只要判断\(\{a_n\}\)中是否存在\(k\)即可。B.AleksaandStack构造方法不唯一，我直接输出奇数列，显然正确。C.VasilijeinCacak若只判断题......
  • Codeforces Round 967 (Div. 2) - C
    题意概述这是一个交互题。有一棵有\(n\)个节点的树，节点编号从\(1\)到\(n\)，并要求你使用以下类型的查询来猜测它："?ab"会告诉你哪个节点\(x\)在点\(a\)和\(b\)之间（\(|d(a,x)-d(b,x)|\)的值最小），其中\(d(x,y)\)是节点\(x\)和\(y\)之间的距离。如果存在不......
  • Codeforces Round 967 (Div. 2)
    A.MakeAllEqual签到题，先确定最终答案，然后把其他数删去，转化为统计众数点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglongintread(){intx=0;boolf=false;charc=getchar();while(c<......
  • Codeforces Round 967(Div.2)之赛后总结
    CodeforcesRound967(Div.2)传送锚点A.MakeAllEqual1.题面分析废话这么多，说白了就是求总数减去最多出现数的个数的值。2.解法直接用桶装一下，然后扫一遍维护最大值。3.code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+520;......
  • Codeforces Round 967 (Div. 2) ABCD
    来源：CodeforcesRound967(Div.2)做题时间：2024_08_21A.MakeAllEqual使所有元素相等的最小操作次数，就是保留最大的数字所以操作次数就是总数减去数量最多得数B.GeneratePermutation题意构造一个序列\(p\)，内部元素是\([1,2,\cdots,n]\)打乱使长度为\(n\)的初始......
  • Codeforces Round 967 (Div. 2)-D
    CodeforcesRound967(Div.2)-D这些天在留校集训……我之前空余时间在看模电，最近在玩黑猴……九月开学了估计也不能闲下来……但这个博客我还是会抽空更新的╰(°▽°)╯Problem-D-Codeforces虽然代码写得特别丑陋，但好歹是我完全想的思路——自己还de了一天bug（゜ー゜）......
  • Codeforces Round 967 (Div. 2)
    题不难。A.MakeAllEqual题意：一个圆，上面有\(n\)个数，每次可以删去相邻的两个不同数中任意一个，求至少几次使得剩下的数都一样。显然下界是出现次数最多的数且一定能取到，时间复杂度\(O(n)\)。提交记录B.GeneratePermutation题意：要求构造一个排列，使得\(x\)所在位置大......
  • CF 2001 E2 solution (967 Div.2)
    CF2001E2由于对称，所以设\(heap[u]\)为两次确定堆，且第一次弹出的是\(u\)，\(heap[u,v]\)是第一次\(u\)，第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出，那么对于其他不同的第二个弹出的点，根据对称性......
  • 题解：Codeforces Round 967 (Div. 2) B [思维/构造]
    B.GeneratePermutationtimelimitpertest:1.5secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputThereisanintegersequence\(a\)oflength\(n\),whereeachelementisinitially\(-1\).Misukihastwoty......
  • Divisiblity of Difference
    题目传送门思路首先得知道个性质，即若$a\bmodb=c\bmodb$，那么$(a-c)\bmodb=0$，因为余数在$(a-c)$中被减掉了。于是我们可以把所有余数相同的$a_i$丢进一个vector里，之后再看余数相同的$a_i$的数量有没有$\gek$，有的话就输出前$k$个数，没有就输出No。代码#i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99