526互联

Codeforces Round 901 (Div. 2)

发布时间 2023-10-03 18:06:41作者: 空気力学の詩

Preface

摆烂人闪总出列，开个小号摆烂打Div2，龟速1h写完前四题后发现后面三个题过的人数是1/2/1

遂假装挣扎了下看了下EF题面，发现F很可做就开始推式子，后面一看妈的样例都过不去才发现题目看错了

还好拿的新号打的，遂直接无限活力，启动！

后面看了下F原来比我想的还简单来着，E的做法确实不容易想到，主要太容易被位运算带偏了

A. Jellyfish and Undertale

签到

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,a,b,n,x;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; int ans=0; for (scanf("%lld%lld%lld",&a,&b,&n),i=1;i<=n;++i)
		scanf("%lld",&x),ans+=min(a-1,x); printf("%lld\n",ans+b);
	}
	return 0;
}

B. Jellyfish and Game

刚开始写个分类讨论直接光速喜提1WA，后面想到既然是Div2的B那么肯定不是大分类讨论

后面发现在\(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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=55;
int t,n,m,k,a[N],b[N]; multiset <int> A,B,ta[N],tb[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; scanf("%lld%lld%lld",&n,&m,&k); A.clear(); B.clear();
		for (i=1;i<=n;++i) scanf("%lld",&a[i]),A.insert(a[i]);
		for (i=1;i<=m;++i) scanf("%lld",&b[i]),B.insert(b[i]);
		bool flag=0; for (i=1;i<=k;++i)
		{
			if (i&1)
			{
				int min_a=*A.begin(),max_b=*B.rbegin();
				if (min_a<max_b) A.erase(A.find(min_a)),B.erase(B.find(max_b)),A.insert(max_b),B.insert(min_a);
				if (i-2>0&&ta[i-2]==A) flag=1; ta[i]=A;
			} else
			{
				int max_a=*A.rbegin(),min_b=*B.begin();
				if (min_b<max_a) A.erase(A.find(max_a)),B.erase(B.find(min_b)),A.insert(min_b),B.insert(max_a);
				if (i-2>0&&tb[i-2]==B) flag=1; tb[i]=B;
			}
			if (flag&&(k-i)%2==0) break; 
		}
		int sum=0; for (auto x:A) sum+=x; printf("%lld\n",sum);
	}
	return 0;
}

C. Jellyfish and Green Apple

贪心地尽量先用大块的苹果去满足要求即可，其实是个比B还简单的模拟题

注意无解的判断要先约分再看分母是否为\(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 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;
int t,n,m;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld",&n,&m);
		int g=__gcd(n,m),rn=n,rm=m; n/=g; m/=g;
		int x=1; while (x<=m) x<<=1; x>>=1;
		if (x!=m) { puts("-1"); continue; }
		int ans=0; for (n=rn,m=rm,x=0;n;++x)
		{
			int c=1LL<<x,d=n*c/m; n=n-m*d/c;
			ans+=m*d/c*(c-1); 
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D. Jellyfish and Mex

很一眼的题，首先不难发现如果我们要拿一个数\(x\)，那么肯定是一次性将所有的\(x\)都拿完是最优的

考虑先求出原序列的\(\operatorname{MEX}\)记为\(S\)，很显然\(a_i>S\)的数都是没用的，可以直接忽略掉

发现由于此时\([0,S-1]\)的数都有至少一个，不妨设数\(i\)的个数为\(c_i\)，则拿光\(i\)所需的代价就是\((c_i-1)\times S+i\)

然后此时会发现问题变成了一个子问题，原来的\(S\)变成了现在的\(i\)，因此很容易把现在序列的\(\operatorname{MEX}\)作为状态进行DP，则有转移方程

\[f_i=\min_\limits{0\le j<i} (c_j-1)\times i+j+f_j \]

总复杂度\(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 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=5005;
int t,n,x,c[N],f[N];
inline int DP(CI x)
{
	if (!x) return 0; if (~f[x]) return f[x];
	int ret=1e18; for (RI i=0;i<x;++i)
	ret=min(ret,x*(c[i]-1)+i+DP(i));
	return f[x]=ret;
}
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=0;i<=n;++i) c[i]=0,f[i]=-1;
		for (i=1;i<=n;++i) if (scanf("%lld",&x),x<=n) ++c[x];
		int mex=0; while (c[mex]>0) ++mex;
		printf("%lld\n",DP(mex));
	}
	return 0;
}

E. Jellyfish and Math

这题最坑的地方就是题目中给的位运算啥的是诈骗条件，最后的做法和这些都没关系，因此很容易误导人

按位考虑\(a,b,c,d,m\)的每一位，很显然如果存在两个二进制位\(i,j(i\ne j)\)满足\((a_i,b_i,m_i)=(a_j,b_j,m_j)\and (c_i,d_i)\ne (c_j,d_j)\)，那么显然无解

否则我们不难发现\((a_i,b_i,m_i)\)的三元组最多只有\(8\)种情况，而由于涉及到每一组是否出现以及对应的\((c_i,d_i)\)的不同，共有\(5^8\)种情况

因此不妨把每种情况都看作一个状态，转移就看作状态之间的边，直接跑最短路就能知道答案了

这里实现采用了较为好写的形式，虽然相比Tutorial的写法把一些理论无用的状态也包含进来了，但代码还是很好理解的

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int T,t,a,b,c,d,m,tim[1<<8][1<<8],dis[1<<8][1<<8],rst[1<<3];
map <array<int,5>,int> Rec;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),T=1;T<=t;++T)
	{
		RI i; scanf("%d%d%d%d%d",&a,&b,&c,&d,&m); memset(rst,-1,sizeof(rst));
		bool flag=1; for (i=0;i<30&&flag;++i)
		{
			int x=((a>>i)&1)|(((b>>i)&1)<<1)|(((m>>i)&1)<<2);
			int y=((c>>i)&1)|(((d>>i)&1)<<1);
			if (!~rst[x]) rst[x]=y; else if (rst[x]!=y) flag=0;
		}
		if (!flag) { puts("-1"); continue; }
		a=b=c=d=m=0; int cur=0,ans=-1;
		for (i=0;i<8;++i) if (~rst[i])
		{
			a|=(i&1)<<cur;
			b|=((i>>1)&1)<<cur;
			m|=((i>>2)&1)<<cur;
			c|=(rst[i]&1)<<cur;
			d|=((rst[i]>>1)&1)<<cur;
			++cur;
		}
		if (Rec.count({a,b,m,c,d})) { printf("%d\n",Rec[{a,b,m,c,d}]); continue; }
		dis[a][b]=0; tim[a][b]=T; queue <pi> q; q.push(pi(a,b));
		while (!q.empty())
		{
			auto [x,y]=q.front(); q.pop();
			if (x==c&&y==d) { ans=dis[x][y]; break; }
			auto trs=[&](CI nx,CI ny)
			{
				if (tim[nx][ny]!=T) tim[nx][ny]=T,dis[nx][ny]=dis[x][y]+1,q.push(pi(nx,ny));
			};
			trs(x&y,y); trs(x|y,y); trs(x,x^y); trs(x,y^m);
		}
		printf("%d\n",Rec[{a,b,m,c,d}]=ans);
	}
	return 0;
}

F. Jellyfish and EVA

铸币闪总看完题目以为每次都是知道了Asuka的选择后玩家再做出决策，然后就寄的很彻底

考虑设\(f_i\)表示从\(i\)成功走到\(n\)的概率，不难发现只要从后往前转移即可，难点在于如何确定男主的最优策略

后面发现其实如果是两人同步行动的话那策略就十分显然了，玩家肯定是每次选后继状态中最大的那个

证明的话可以用归纳法，更具体地可以去看Tutorial

然后要计算这个的话也很简单，不妨设\(g_{i,j}\)表示当后继状态有\(i\)个时，最后的排名（从大到小）第\(j\)大的状态被选中的概率，初值为\(g_{1,1}=1,g_{2,1}=\frac{1}{2},g_{2,2}=0,g_{i,1}=\frac{1}{i}\)

对于第二维大于\(1\)的情况，考虑每次必然会牺牲掉最大的那个状态，因此只要讨论Asuka选的那个数在当前数的前面还是后面即可，转移为：

\[g_{i,j}=\frac{j-2}{i}\times g_{i-2,j-2}+\frac{i-j}{i}\times g_{i-2,j-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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005;
int t,n,m,x,y; vector <int> v[N]; LDB f[N],g[N][N];
inline void init(CI n)
{
	RI i,j; for (g[1][1]=1.0L,g[2][1]=0.5L,i=3;i<=n;++i)
	for (g[i][1]=1.0L/i,j=2;j<=i;++j)
	g[i][j]=1.0L*(j-2)/i*g[i-2][j-2]+1.0L*(i-j)/i*g[i-2][j-1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(5000);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) f[i]=0,v[i].clear();
		for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y);
		for (f[n]=1.0L,i=n-1;i>=1;--i)
		{
			vector <LDB> tmp; for (auto to:v[i]) tmp.push_back(f[to]);
			sort(tmp.begin(),tmp.end(),greater <LDB>());
			for (j=0;j<tmp.size();++j) f[i]+=g[tmp.size()][j+1]*tmp[j];
		}
		printf("%.12Lf\n",f[1]);
	}
	return 0;
}

Postscript

唉国庆假唯一的一天休息也过完了，明天又要开始训练了，冲冲冲