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

AtCoder Grand Contest 043

时间：2023-09-27 18:55:29浏览次数：26  
标签：AtCoder now Contest int res back push include 043

A - Range Flip Find Route

可以发现，一条路径的最小操作数等于路径上有多少 # 的块，令 \(f_{i,j}\) 表示到 \((i,j)\) 的最小操作次数，直接 DP 就行了。

注意路径上一个 \(1\) 的块会被算两次，需要除以 \(2\)。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int h,w;
char s[N][N];
int dp[N][N];
int main()
{
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)
		scanf("%s",s[i]+1);
	memset(dp,63,sizeof(dp));
	dp[1][1]=s[1][1]=='#';
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
		{
			if(i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+(s[i-1][j]!=s[i][j]));
			if(j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+(s[i][j-1]!=s[i][j]));
		}
	printf("%d",(dp[h][w]+1)/2);
	return 0;
}

B - 123 Triangle

不妨将所有 \(a_i\) 减一，问题转化成了 \(a_i\in \{0,1,2\}\) 的问题。

先考虑 \(a_i\) 只有 \(0,1\) 的情况，\(x_{i,j} = | x_{i-1,j} - x_{i-1,j+1} | = x_{i-1,j} \operatorname{xor} x_{i-1,j+1}\)。

考虑 \(a_i\) 的贡献，问题大概就是从 \((n,i)\) 到 \((1,1)\) 的路径条数，这个就是 \(C_{n-1}^{i-1}\)，答案就是 \(\sum C_{n-1}^{i-1} [a_i=1] \mod 2\)。

考虑加入了 \(2\) 时的答案。可以分为两种情况：

  • 如果 \(a\) 中有 \(1\)，则答案不可能是 \(2\)。因为如果某层如果所有的 \(1\) 都被消去了的话，则前一时刻必须所有位置都为 \(1\)；否则一定会有 \(1\) 留下来。
  • 如果 \(a\) 中没有 \(1\)，则可以将所有 \(a_i=2\) 的位置转化成 \(a_i=1\) 的情况处理。

有一个结论，

\(C_n^k\bmod 2= \begin{cases} 1 (n\operatorname{and} k = k) \\ 0 \end{cases}\)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
int n;
char s[N];
int a[N];
int cnt[3];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		a[i]=s[i]-'1';
	bool flag=false;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==1) flag=true;
		cnt[a[i]]+=(((n-1)&(i-1))==(i-1));
	}
	if(cnt[1]&1) printf("1");
	else if(!flag&&(cnt[2]&1)) printf("2");
	else printf("0");
	return 0;
}

C - Giant Graph

可以发现，最后的图肯定是一个分层图，且同层之间不会连边。

考虑一种贪心，我们肯定尽可能选层数越高的层最优。

考虑一个点 \((i,j,k)\) 是否选择，当且仅当所有层数比它高的都没有被选。可以将选看做所有后面的点都不选都是必败态，否则为非必败态，这就变成了一个组合问题。

全局的 SG 函数即为三张图分别的 SG 函数异或起来，我们需要对 \(\operatorname{SG}(x_i)\oplus \operatorname{SG}(y_j)\oplus \operatorname{SG}(z_k)=0\) 的合法 \(i,j,k\) 进行计数即可。

可以发现，每张图的 SG 函数最大不超过 \(\sqrt m\)，直接暴力枚举前两个的 SG 函数的值，得出第三个的 SG 函数的值即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
const int MOD=998244353;
int n,m;
long long ksm(long long a,long long b)
{
	a%=MOD,b%=(MOD-1);
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
vector<int>G[N];
int sg[N];
int dfs(int u)
{
	if(sg[u]!=-1) return sg[u];
	static int vis[N];
	for(int v:G[u])
	{
		dfs(v);
		vis[sg[v]]=true;
	}
	for(int i=0;;i++)
		if(!vis[i])
		{
			sg[u]=i;
			break;
		}
	for(int v:G[u])
		vis[sg[v]]=false;
	return sg[u];
}
vector<long long> getsg()
{
	for(int i=1;i<=n;i++)
		G[i].clear();
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		G[x].push_back(y);
	}
	memset(sg,-1,sizeof(sg));
	for(int i=n;i>=1;i--)
		dfs(i);
	int Max=*max_element(sg+1,sg+n+1);
	vector<long long>res;
	res.resize(Max+1);
	for(int i=1;i<=n;i++)
		res[sg[i]]=(res[sg[i]]+ksm(1e18,i))%MOD;
	return res;
}
int main()
{
	scanf("%d",&n);
	vector<long long>x=getsg(),y=getsg(),z=getsg();
	long long ans=0;
	for(int i=0;i<x.size();i++)
		for(int j=0;j<y.size();j++)
		{
			int k=i^j;
			if(k>=z.size()) continue;
			ans=(ans+x[i]*y[j]%MOD*z[k]%MOD)%MOD;
		}
	printf("%lld",ans);
	return 0;
}

D - Merge Triplets

考虑将一个块 \(A_i\)，如果 \(A_{i,j}\ge A_{i,j+1}\) 的话，我们就可以将这两个合并成一个块，三个数也可以合并。将这几个数分成一个组，可以发现，排列 \(P\) 就是若干个组按照组内的最大值排序的结果。

考虑合法的 \(P\) 需要满足的条件：

  • 每个组的大小不超过 \(3\)；
  • 每个组拼起来可以组成 \(n\) 个三元组（即为将大小为 \(1,2,3\) 的组的值分别设为 \(1,-1,0\)，那么要求权值和大于等于 \(0\) 且为 \(3\) 的倍数）。

然后就可以 DP 了，令 \(f_{i,j,k}\) 表示当前插入第 \(i\) 个数，当前组的大小为 \(j\)，权值和为 \(k\) 的方案数。当前数有两种方案，插入当前组或者新开一组，转移即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2005,M=6000;
int n,P;
int f[N*3][3][N*6];
int main()
{
	scanf("%d%d",&n,&P);
	n*=3;
	f[1][0][0+M]=1;
	for(int i=1;i<n;i++)
		for(int j=0;j<=2;j++)
			for(int k=-i;k<=i;k++)
			{
				if(j<=1) f[i+1][j+1][k+M]=(f[i+1][j+1][k+M]+1LL*f[i][j][k+M]*i%P)%P;
				if(j==0) f[i+1][0][k+1+M]=(f[i+1][0][k+1+M]+f[i][j][k+M])%P;
				else if(j==1) f[i+1][0][k-1+M]=(f[i+1][0][k-1+M]+f[i][j][k+M])%P;
				else if(j==2) f[i+1][0][k+M]=(f[i+1][0][k+M]+f[i][j][k+M])%P;
			}
	int ans=0;
	for(int k=0;k<=n;k+=3)
		ans=(ans+((long long)f[n][0][k-1+M]+f[n][1][k+1+M]+f[n][2][k+M])%P)%P;
	printf("%d",ans);
	return 0;
}

E - Topology

考虑一条绳子向一个方向前进，如果经过一个点的下面记录一个 \(d_i\)，经过一个点的上面记录一个 \(u_i\)。最后会得到一个序列，不断地在序列中删去相邻的相同元素，如果原序列能被删完，则该点集合法，否则非法。

可以发现，一个合法点集的所有子集都应该合法，且空集必须合法，可以判掉这些情况。

接下来就可以构造了。对于一个非法集合 \(S\)，且它的所有真子集均为合法的，考虑对于每种这种情况构造。

考虑一种构造方法：

  • 如果当前点到了最右边，只需要绕一圈就好了。
  • 如果当前点右边得出了一个操作序列 \(S\)，为了能使删除这个点以后合法，先从上面穿过去，记录一个 \(u_i\)，加上一个 \(S\)，然后在从上面穿回来记录一个 \(u_i\)；再从上面穿过去，记录一个 \(d_i\)，记录一个 \(S\) 的逆序操作序列，然后在从上面穿回来记录一个 \(u_i\)。

这样显然是合法的，且任意删除一个点得出的序列都是可以被删完也就是合法的。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1<<10;
int n;
char s[N];
int p[N];
vector<pair<int,int> > solve(int S,int now)
{
	vector<pair<int,int> >res;
	for(int i=now+1;i<n;i++)
		if(S&(1<<i))
		{
			vector<pair<int,int> > t=solve(S,i);
			for(int j=now;j<=i-1;j++)
				res.push_back(make_pair(j,1));
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int j=i;j>=now;j--)
				res.push_back(make_pair(j,1));
			res.push_back(make_pair(now,0));
			res.push_back(make_pair(now+1,0));
			for(int j=now+1;j<=i;j++)
				res.push_back(make_pair(j,1));
			reverse(t.begin(),t.end());
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int j=i-1;j>=now+1;j--)
				res.push_back(make_pair(j,1));
			res.push_back(make_pair(now+1,0));
			res.push_back(make_pair(now,0));
			return res;
		}
	res.push_back(make_pair(now,1));
	res.push_back(make_pair(now+1,1)); 
	res.push_back(make_pair(now+1,0));
	res.push_back(make_pair(now,0));
	return res;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<(1<<n);i++)
		p[i]=s[i]-'0';
	if(p[0]==0)
	{
		printf("Impossible");
		return 0;
	}
	for(int s=0;s<(1<<n);s++)
		if(p[s]==1)
			for(int i=s;i;i=(i-1)&s)
				if(p[i]==0)
				{
					printf("Impossible");
					return 0;
				}
	vector<pair<int,int> >ans;
	ans.push_back(make_pair(0,0));
	for(int s=1;s<(1<<n);s++)
		if(p[s]==0)
		{
			bool flag=true;
			for(int i=(s-1)&s;i;i=(i-1)&s)
				if(p[i]==0)
				{
					flag=false;
					break;
				}
			if(!flag) continue;
			vector<pair<int,int> >res;
			vector<pair<int,int> >t;
			int u=0;
			for(u=0;u<n;u++)
				if(s&(1<<u))
				{
					t=solve(s,u);
					break;
				}
			if(ans.back()!=make_pair(0,0)) res.push_back(make_pair(0,0));
			for(int i=0;i<=u-1;i++)
				res.push_back(make_pair(i,1));
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int i=u;i>=0;i--)
				res.push_back(make_pair(i,1));
			res.push_back(make_pair(0,0));
			for(auto [x,y]:res)
				ans.push_back(make_pair(x,y));
		}
	printf("Possible\n");
	int len=ans.size()-1;
	printf("%d\n",len);
	for(auto [x,y]:ans)
		printf("%d %d\n",x,y);
	return 0;
}

F - Jewelry Box

挖坑待填。

标签：AtCoder,now,Contest,int,res,back,push,include,043
From： https://www.cnblogs.com/zhou-jk/p/17733448.html

相关文章

  • 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的时候还遇到过，但就是没细想虽然当时下机的时候和......
  • AtCoder Beginner Contest 321
    A-321-likeChecker(abc321A)题目大意给定一个数，问从高位到低位，数字是不是递减的。解题思路可以以字符串读入，然后依次判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);......
  • 题解 AtCoder Beginner Contest 267 A~H
    ABC267solutionhttps://atcoder.jp/contests/abc267/ProblemA.Saturday题目描述输入一个表示星期的英文字符串，输出：还有多少天到星期六？solution依题意模拟。\(O(1)\)。ProblemB.Split?题目描述Robin有十个小球，如图排列成这样，然后Robin将一些球击飞了，他告诉你哪些......
  • AtCoder Beginner Contest 318 ABCDE
    AtCoderBeginnerContest318A-FullMoon思路：等差数列求项数//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;intmain(){ios::sync_with_stdio(false);......
  • AtCoder Beginner Contest 320 ABCDE
    AtCoderBeginnerContest320A-LeylandNumber思路：直接快速幂//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;llqmi(lla,llb){llans=1;whil......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99