首页 > 其他分享 >AtCoder Grand Contest 046

AtCoder Grand Contest 046

时间：2023-09-27 18:56:21浏览次数：32  
标签：AtCoder const Contest int res sum long 046 include

A - Takahashikun, The Strider

问题就是要你求 \(ax\equiv 0 \pmod{360}\) 中 \(a\) 的最小值。

答案就是 \(a=\frac{360}{\gcd(x,360)}\)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int x;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	scanf("%d",&x);
	printf("%d",360/gcd(x,360));
	return 0;
}

B - Extension

考虑 DP，令 \(f_{i,j}\) 表示当前填了 \(i\) 行 \(j\) 列的方案数，因为先填行再填列和先填列再填行有重合部分，需要减去，转移为：

\[f_{i,j}=if_{i,j-1}+jf_{i-1,j}-(i-1)(j-1)f_{i-1,j-1} \]

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3005;
const int MOD=998244353;
int A,B,C,D;
long long dp[N][N];
long long dfs(int r,int c)
{
	if(r<A||c<B) return 0;
	if(dp[r][c]!=-1) return dp[r][c];
	int res=0;
	res=(res+dfs(r,c-1)*r%MOD)%MOD;
	res=(res+dfs(r-1,c)*c%MOD)%MOD;
	res=(res-dfs(r-1,c-1)*(r-1)%MOD*(c-1)%MOD+MOD)%MOD;
	return dp[r][c]=res;
}
int main()
{
	scanf("%d%d%d%d",&A,&B,&C,&D);
	memset(dp,-1,sizeof(dp));
	dp[A][B]=1;
	printf("%lld",dfs(C,D));
	return 0;
}

C - Shift

不妨将所有的根据 \(0\) 分成若干段，令 \(f_{i,j,k}\) 表示当前填的 \(i\) 段，用了 \(j\) 个 \(1\)，用了 \(k\) 次操作，转移时枚举当前段填的 \(1\) 的个数。

\[f_{i,j,k}=\sum f_{i-1,j-p,k-\max(p-a_i,0)} \]

\(a_i\) 为当前段 \(1\) 的个数。

直接实现为 \(O(n^4)\) 的，可以用前缀和瞎 jb 搞一下就是 \(O(n^3)\) 的了，代码是 \(O(n^4)\) 的。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
const int MOD=998244353;
int n,m;
char s[N];
int a[N];
int sum[N];
long long dp[N][N][N];
int main()
{
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	s[++n]='0';
	m=min(m,n);
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(s[i]=='0') cnt++;
		else a[cnt+1]++;
	for(int i=1;i<=cnt;i++)
		sum[i]=sum[i-1]+a[i];
	dp[0][0][0]=1;
	for(int i=1;i<=cnt;i++)
		for(int j=sum[i];j<=n-cnt;j++)
			for(int k=0;k<=m;k++)
				for(int p=0;p<=min(j,n-sum[i-1]-cnt);p++)
					if(k>=max(p-a[i],0)) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-p][k-max(p-a[i],0)])%MOD;
	long long ans=0;
	for(int k=0;k<=m;k++)
		ans=(ans+dp[cnt][n-cnt][k])%MOD;
	printf("%lld",ans);
	return 0;
}

D - Secret Passage

考虑一个分界点 \(i\)，我们需要知道 \(i\) 前面经过若干次操作后是否能得出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 到后面，还有 \(i\) 后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案。

考虑计算 \(i\) 前面经过若干次操作后是否能得出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 到后面，令 \(f_{i,c_0,c_1}\) 表示当前到第 \(i\) 个位置，是否可以取出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 扔到后面。那么对于 \(f_{i,c_0,c_1}\)，考虑它如何转移：

  • 当前点可以不动；
  • 当 \(s_{i+1}=0\) 时，我们可以将一个扔到后面的 \(1\) 换成 \(0\)；
  • 当 \(s_{i+1}=1\) 时同理；
  • 当 \(s_{i+1}=0\) 或 \(s_{i+2}=0\) 时，我们可以将一个 \(0\) 扔到后面，另一个数去掉；
  • 当 \(s_{i+1}=1\) 或 \(s_{i+2}=1\) 时同理。

对应的转移为：

\[f_{i,c_0,c_1}\to \begin{cases} f_{i+1,c_0,c_1} \\ f_{i+1,c_0+1,c_1-1} &(s_{i+1}=0) \\ f_{i+1,c_0-1,c_1+1} &(s_{i+1}=1) \\ f_{i+1,c_0+1,c_1} &(s_{i+1}=0\ \operatorname{or}\ s_{i+1}=0) \\ f_{i+1,c_0,c_1+1} &(s_{i+1}=1\ \operatorname{or}\ s_{i+1}=1) \end{cases} \]

考虑计算后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案，令 \(g_{i,c_0,c_1}\) 表示 \(i\) 后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案。

考虑将连续的一段 \(0\)，如果在这段中插入 \(0\) 时我们强制它插在开头，那么就可以转移了：

\[g_{i,c_0,c_1}\to \begin{cases} g_{i-1,c_0,c_1} \\ g_{i,c_0,c_1+1} &(s_{i}=0) \\ g_{i,c_0+1,c_1} &(s_{i}=1) \end{cases} \]

记得需要将空串的情况去掉。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
const int MOD=998244353;
int n;
char s[N];
long long dp[N][N][N];
bool f[N][N][N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	dp[n][0][0]=1;
	for(int i=n;i>=1;i--)
		for(int c0=0;c0<i;c0++)
			for(int c1=0;c0+c1<i;c1++)
			{
				dp[i-1][c0][c1]=(dp[i-1][c0][c1]+dp[i][c0][c1])%MOD;
				if(s[i]=='0') dp[i][c0][c1+1]=(dp[i][c0][c1+1]+dp[i][c0][c1])%MOD;
				else if(s[i]=='1') dp[i][c0+1][c1]=(dp[i][c0+1][c1]+dp[i][c0][c1])%MOD;
			}
	f[0][0][0]=true;
	for(int i=0;i<=n;i++)
		for(int c0=0;c0<=i;c0++)
			for(int c1=0;c0+c1<=i;c1++)
			{
				if(i+1<=n)
				{
					f[i+1][c0][c1]|=f[i][c0][c1];
					if(s[i+1]=='0'&&c1>0) f[i+1][c0+1][c1-1]|=f[i][c0][c1];
					if(s[i+1]=='1'&&c0>0) f[i+1][c0-1][c1+1]|=f[i][c0][c1];
				}
				if(i+2<=n)
				{
					if(s[i+1]=='0'||s[i+2]=='0') f[i+2][c0+1][c1]|=f[i][c0][c1];
					if(s[i+1]=='1'||s[i+2]=='1') f[i+2][c0][c1+1]|=f[i][c0][c1];
				}
			}
	f[n][0][0]=false;
	long long ans=0;
	for(int i=0;i<=n;i++)
		for(int c0=0;c0<=i;c0++)
			for(int c1=0;c0+c1<=i;c1++)
				if(f[i][c0][c1]) ans=(ans+dp[i][c0][c1])%MOD;
	printf("%lld",ans);
	return 0;
}

E - Permutation Cover

考虑最后的序列肯定是若干个排列相交的情况，考虑如果有一个点同时被多个排列同时覆盖，我们只需要考虑其中的两个排列。

考虑两个排列相交的情况，将某个数放在相交部分，它对当前这个数的个数的贡献为 \(1\)，否则的贡献为 \(2\)。

那么可以看出答案为无解的情况为

\[\max(a_i)\ge 2\cdot \min(a_i)+1 \]

否则一定可以构造出方案，具体证明的话看官方题解去吧。

考虑新插入某些数，枚举当前插入数的长度，贪心地构造方案：

  • 当 \(\max(a_i)\le 2\cdot \min(a_i)\) 时，直接贪心将字典序最小的加入目前的答案串。
  • 当 \(\max(a_i)= 2\cdot \min(a_i)+1\) 时，需要满足所有的 \(\max(a_i)\) 的位置都在 \(\min(a_i)\) 之前。
  • 当 \(\max(a_i)> 2\cdot \min(a_i)+1\) 时，无法构造方案。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int K=105,N=1005;
int k,n;
int a[K];
vector<int>merge(const vector<int>&a,const vector<int>&b)
{
	vector<int>res;
	size_t i=0,j=0;
	while(i<a.size()&&j<b.size())
	{
		if(a[i]<b[j]) res.push_back(a[i]),i++;
		else res.push_back(b[j]),j++;
	}
	while(i<a.size())
		res.push_back(a[i]),i++;
	while(j<b.size())
		res.push_back(b[j]),j++;
	return res;
}
int ans[N],tot;
int b[K];
bool pos[K];
vector<int>add(int len)
{
	for(int i=1;i<=k;i++)
		pos[i]=false,b[i]=a[i];
	vector<int>pre;
	for(int i=tot,j=1;i>=1&&j<=k-len;i--,j++)
		pre.push_back(ans[i]);
	for(int u:pre)
		pos[u]=true;
	for(int i=1;i<=k;i++)
		if(!pos[i]) b[i]--;
	for(int i=1;i<=k;i++)
		if(b[i]<0) return {k+1};
	int Min=*min_element(b+1,b+k+1),Max=*max_element(b+1,b+k+1);
	if(Min*2>=Max)
	{
		vector<int>res;
		for(int i=1;i<=k;i++)
			if(!pos[i]) res.push_back(i);
		return res;
	}
	else if(Min*2+1==Max)
	{
		vector<int>x,y;
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]==Max) x.push_back(i);
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]==Min) x.push_back(i);
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]!=Min&&b[i]!=Max) y.push_back(i);
		vector<int>res=merge(x,y);
		pre.insert(pre.end(),res.begin(),res.end());
		int L=0,R=(int)(pre.size())-1;
		for(int i=0;i<pre.size();i++)
		{
			if(b[pre[i]]==Max) L=max(L,i);
			if(b[pre[i]]==Min) R=min(R,i);
		}
		if(L<R) return res;
		else return {k+1};
	}
	else return {k+1};
}
void solve()
{
	vector<int>res={k+1};
	for(int len=1;len<=k&&tot+len<=n;len++)
	{
		int d=k-len;
		if(tot-d>=0)
		{
			vector<int>now=add(len);
			res=min(res,now);
		}
	}
	for(int u:res)
	{
		ans[++tot]=u;
		a[u]--;
		printf("%d ",u);
	}
	return;
}
int main()
{
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
		scanf("%d",&a[i]),n+=a[i];
	int Min=*min_element(a+1,a+k+1),Max=*max_element(a+1,a+k+1);
	if(2*Min+1<=Max)
	{
		printf("-1");
		return 0;
	}
	while(tot<n)
		solve();
	return 0;
}

F - Forbidden Tournament

考虑将原图缩点，缩完点以后的图一定是一个链状 DAG。可以发现，最多只有一个强联通分量的点的个数大于等于 \(3\)，其他最多只有一个点。

可以枚举强联通分量的个数，那么我们只需要求出点数等于 \(n-i\)，度数小于等于 \(k-i\) 的强联通图的方案数，最后乘上 \(P_{n}^i\) 就是了。

考虑计算满足条件的强联通图的方案数，不妨选一个点 \(1\)，将它的所有的入度和出度分为两个集合 \(X,Y\)，可以发现 \(X,Y\) 都是链状 DAG。

不妨将 \(X,Y\) 中的点 \(x_1,x_2,\cdots ,x_n\) 和 \(y_1,y_2,\cdots ,y_m\) 按照拓扑序排序。显然必有 \(y_m\to x_1\) 的边。可以发现，从 \(y_b\) 连向 \(x_i\) 的边必然是一个前缀，且那个分界点具有单调性。

那么就可以将问题转化到网格上，大概是一个折线计数问题，还要考虑 \(k\) 的限制，大概就是两条斜线限制一下，将路径上方的点染成黑色，其他为白色。令 \(f_{i,j}\) 表示第 \(i\) 行有 \(j\) 个黑点的方案数，DP 一下即可。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=205;
int n,k,p;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
void init(int n=200)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%p;
	inv[n]=ksm(fac[n],p-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%p;
	return;
}
long long P(int n,int m)
{
	if(m>n) return 0;
	return fac[n]*inv[n-m]%p;
}
long long f[N][N];
long long sum[N][N];
int calc(int n,int m,int k)
{
	f[0][m]=1;
	for(int i=1;i<=m-1;i++)
		f[0][i]=0;
	f[0][0]=-1;
	for(int j=0;j<=m;j++)
	{
		sum[0][j]=j>0?sum[0][j-1]:0;
		sum[0][j]=(sum[0][j]+f[0][j]+p)%p;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			f[i][j]=0;
			if(i-1+j<=k&&n-i+m-j<=k)
			{
				f[i][j]=(f[i][j]+(sum[i-1][m]-(j>0?sum[i-1][j-1]:0)+p)%p)%p;
			}
			sum[i][j]=j>0?sum[i][j-1]:0;
			sum[i][j]=(sum[i][j]+f[i][j])%p;
		}
	return f[n][0];
}
long long solve(int n,int k)
{
	if(n==1) return 1;
	long long res=0;
	for(int deg=2;deg<n;deg++)
		res=(res+calc(deg,n-deg,k))%p;
	return res*fac[n-1]%p;
}
int main()
{
	scanf("%d%d%d",&n,&k,&p);
	init();
	long long ans=0;
	for(int i=0;i<=k;i++)
		ans=(ans+P(n,i)*solve(n-i,k-i)%p)%p;
	printf("%lld",ans);
	return 0;
}

标签：AtCoder,const,Contest,int,res,sum,long,046,include
From： https://www.cnblogs.com/zhou-jk/p/17733443.html

相关文章

  • AtCoder Grand Contest 047
    A-IntegerProduct考虑将原来的数全部化为整数，乘上\(10^9\)，那么问题就变成了是否有两个数的乘积是\(10^{18}\)的倍数。考虑如果是\(10^{18}\)的倍数的话必然是\(2^{18}\)和\(5^{18}\)的倍数，那么分解出每个数的\(2,5\)因子数量，然后再看看有多少个数与它\(2,5\)的因......
  • AtCoder Grand Contest 043
    A-RangeFlipFindRoute可以发现，一条路径的最小操作数等于路径上有多少#的块，令\(f_{i,j}\)表示到\((i,j)\)的最小操作次数，直接DP就行了。注意路径上一个\(1\)的块会被算两次，需要除以\(2\)。#include<iostream>#include<cstdio>#include<cstring>usingnamesp......
  • AtCoder Grand Contest 044
    A-PaytoWin不妨将操作倒过来考虑，问题就变成了每次除以\(2,3,5\)或者\(+1,-1\)，令\(f_n\)表示将\(n\)变成\(0\)的最小花费，然后记忆化搜索即可，可以证明复杂度是对的。代码：#include<iostream>#include<cstdio>#include<map>usingnamespacestd;intT;longlong......
  • AtCoder Grand Contest 045
    A-XorBattle可以发现，从后往前扫，遇到一个\(1\)找后面是否有若干个\(0\)的位置的\(a_i\)与当前位置的异或和相等，用线性基维护一下就好了。代码：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=205;intT;intn;longlong......
  • AtCoder Beginner Contest 318
    AtCoderBeginnerContest318A-FullMoon(atcoder.jp)以\(M\)为首项,\(P\)为公差,看\(1\simN\)里包含了多少项的个数#include<bits/stdc++.h>usingi64=longlong;usingnamespacestd;typedefpair<i64,i64>PII;intmain(){ios::sync_with_stdio......
  • AtCoder Regular Contest 165
    Preface这场前三题是上周四写的，今天课有点多本来想着把最近两场CF的博客先写下的但后面发现还有CCLCC的杂谈没写，写完发现由于晚上要上课没时间了，只能先把这场先写一下A-SumequalsLCM设\(n=\prod_{i=1}^kp_i^{c_i}\)，不难发现令\(A_1=p_1^{c_1},A_2=p_2^{c_2},\cdots\)，然......
  • The 2023 ICPC Asia Regionals Online Contest (2) MDIELK
    The2023ICPCAsiaRegionalsOnlineContest(2)MDIELKMDirtyWork题意：总共有\(n\)个问题，对于第\(i\)个问题需要\(a_i\)分钟。你可以随便选择一个没过的题去写，写完以后马上交，你有\(p_i\)的概率会错，错了不能跳题，你要花额外\(b_i\)的时间去\(debug\)。问你以最佳策略的最小罚......
  • The 2023 ICPC Asia Regionals Online Contest (2)
    Preface这场打的有点捞说实话，两个小时出头的时候写完6个题就开始坐牢了K题由于我习惯性地不写数论就扔给徐神了，徐神也是很有思路写了个看着就很对的东西，但不知道为什么过不去赛后发现K其实是个很傻逼的题，类似的思路我最近补CF的时候还遇到过，但就是没细想虽然当时下机的时候和......
  • Acwing 周赛110 5046
    Acw5046思路dp，\(dp_i\)表示前i种药且吃第i种药使智商达到\(r_i\)的方案，根据题意可知\[dp_i=\sumdp_j,(r_j\in[l_i,r_i-1])\]先将各区间按右端点排序，求j的区间可用二分.代码//9.24intn,m,k;intf[N],s[N];//acw110structseg{ intl,r; booloperator<(c......
  • AtCoder Beginner Contest 321
    A-321-likeChecker(abc321A)题目大意给定一个数，问从高位到低位，数字是不是递减的。解题思路可以以字符串读入，然后依次判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99