首页 > 其他分享 >AtCoder Regular Contest 171

AtCoder Regular Contest 171

时间：2024-03-07 16:02:44浏览次数：19  
标签：AtCoder typedef int long Regular pair include 171 define

Preface

小补一场ARC，D还是很有意思的但想了半天不会，鉴定为纯纯的彩笔

A - No Attacking

考虑怎么放rook能使得留下来能放pawn的格子数量最多，手玩一下会发现先按照\((2,2),(4,4),(6,6),\cdots\)的顺序放，放满后再接着放\((1,1),(3,3),(5,5),\cdots\)是最优的

手玩一下可以得出在放了\(A\)个rook后最多能放的pawn的个数：

  • \(2A\le N\)时，个数为\((N-A)\times (A+\lceil\frac{N-2A}{2}\rceil)\)
  • \(2A>N\)时，个数为\((N-A)^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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,n,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&a,&b); int lim;
		if (a>n) { puts("No"); continue; }
		if (2*a<=n) lim=(n-a)*(a+(n-2*a+1)/2); else lim=(n-a)*(n-a);
		puts(b<=lim?"Yes":"No");
	}
	return 0;
}

B - Chmax

原问题可以被转化为，对于每个点\(i\)，若\(i<p_i\)则连一条\(i\to p_i\)的有向边，否则不连边；最后要从每个点出发都能走到\(a_i\)

首先考虑显然无解的情况，比较显然的时当有\(a_i<i\)的元素出现时一定不合法

另外我们把所有\(a_i\)相同的数看作一类，并将一类的数中下标最大的记为end，则所有end位置必须满足\(a_i=i\)

接下来考虑计算方案数，不妨考虑从前往后确定每个数的\(p_i\)取值数量，分类讨论：

  • 若\(i\)的后面还有和它一类的点\(j\)（即\(i\)不是end），则\(i\)只能连向\(j\)，此时方案数唯一
  • 若\(i\)的后面没有和它一类的点\(j\)（即\(i\)是end），则\(i\)可以在下标\(\le i\)的点中选择一个没有入度的点作为\(p_i\)

考虑第二种情况的方案数很容易计算，总复杂度\(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 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=200005,mod=998244353;
int n,a[N],d[N],bkt[N],nxt[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),bkt[i]=n+1;
	for (i=1;i<=n;++i) if (a[i]<i) return puts("0"),0; 
	for (i=n;i>=1;--i) nxt[i]=bkt[a[i]],bkt[a[i]]=i;
	for (i=1;i<=n;++i) if (nxt[i]>n&&a[i]!=i) return puts("0"),0;
	int ans=1,end=0; for (i=1;i<=n;++i)
	{
		d[i]+=d[i-1];
		if (nxt[i]<=n) { ++d[nxt[i]]; continue; }
		ans=1LL*ans*(i-d[i]-end)%mod; ++end;
	}
	return printf("%d\n",ans),0;
}

C - Swap on Tree

很有意思的一个Counting题，算是那种不难但是需要想一下的类型

考虑两种方案本质相同的充要条件，首先很容易发现一个必要条件就是选择需要操作的边集要相同，这个手玩一下会发现很显然

但显然操作的顺序也会影响，不妨拿一个菊花图为例，不难发现如选择了中心相邻的\(x\)条边，则共有\(x!\)种本质不同的结果序列

考虑将这个结论推广，不难发现总方案数等于\(\sum_{E'\in E}\prod_{i\in V} deg_{E',i}!\)，即对于某个确定的选边方案，其贡献为每个点度数（只考虑选中的边）的阶乘

要求这个也很简单，不妨统一在向下的方向上统计贡献，设\(f_{i,0/1}\)表示处理了\(i\)的子树，且\(i\)与其父亲的边是否要选中的贡献

对于每个点\(x\)，对其儿子\(y\)的\(f_{y,0/1}\)跑一个类似于背包的东西即可合并方案数，然后统计\(x\)的贡献时注意分是否要往上连讨论一下即可

总复杂度\(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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=3005,mod=998244353;
int n,x,y,f[N][2],fact[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa) DFS(to,now);
	RI i; int m=v[now].size();
	static int g[N],tmp[N]; memset(g,0,sizeof(g)); g[0]=1;
	for (auto to:v[now]) if (to!=fa)
	{
		for (i=0;i<=m;++i) tmp[i]=g[i],g[i]=0;
		for (i=0;i<=m;++i)
		{
			(g[i]+=1LL*tmp[i]*f[to][0]%mod)%=mod;
			(g[i+1]+=1LL*tmp[i]*f[to][1]%mod)%=mod;
		}
	}
	for (i=0;i<=m;++i)
	{
		(f[now][0]+=1LL*g[i]*fact[i]%mod)%=mod;
		(f[now][1]+=1LL*g[i]*fact[i+1]%mod)%=mod;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	return DFS(),printf("%d",f[1][0]),0;
}

D - Rolling Hash

感觉不难的一个题，但我犯病了想着用前缀和算Hash值的时候被常见的形式固定死了，导致没法转化出关键一步直接GG

首先由于题目中给一个串的Hash值定义和我们熟悉的字符串Hash完全相同，因此考虑设Hash函数的前缀和数组为\(h_i\)，则\(hash(l,r)=h_r-h_{l-1}\times B^{r-l+1}\)，由于式子中含有\(B^{r-l+1}\)很难处理

其实这就完全陷入了陷阱之中，我们不妨稍微修改下Hash函数前缀和的定义，直接令\(h'_i=(\sum_{j=1}^i x_j B^{n-j})\bmod P\)（注意和传统的定义的区别就是直接把每一个位置的位权定死）

这样做的好处就是可以发现此时\(hash(l,r)=(h'_r-h'_{l-1})\times \frac{1}{B^{n-r}}\)，而\(hash(l,r)\ne 0\)的充要条件就变成\(h'_{l-1}\ne h'_r\)了，这个条件就非常好

不难发现当确定了\(\{h'_i\}\)后自然就确定了\(\{x_i\}\)，而且二者可以相互转化，因此只需要判断是否有合法的\(\{h'_i\}\)序列即可

不妨把一个限制\((l,r)\)看作一条\(l-1\leftrightarrow r\)的双向边，则题目等价于判定能否用\(P\)种颜色给某个图染色，使得任意相邻两点的颜色不同

这个问题有个经典的DP做法，设\(f_{mask}\)表示将点集为\(mask\)及其导出子图染色所需的最小颜色数，每次转移的时候枚举\(mask\)的子集\(S\)，若\(S\)是独立集则转移\(f_{mask\oplus S}+1\to f_{mask}\)

总复杂度\(O(3^n)\)，应该可以用类似sosdp或者FMT之类的科技优化到\(O(2^n\times n^{O(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=17;
int P,B,n,m,l,r,E[N][N],g[1<<N],f[1<<N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; scanf("%d%d%d%d",&P,&B,&n,&m);
	for (i=1;i<=m;++i) scanf("%d%d",&l,&r),E[l-1][r]=E[r][l-1]=1;
	for (i=1;i<(1<<n+1);++i)
	for (g[i]=1,j=0;j<=n;++j) if ((i>>j)&1)
	for (k=j+1;k<=n;++k) if ((i>>k)&1) if (E[j][k]) g[i]=0;
	for (i=1;i<(1<<n+1);++i)
	for (f[i]=1e9,j=i;j;j=(j-1)&i)
	if (g[j]) f[i]=min(f[i],f[i^j]+1);
	return puts(f[(1<<n+1)-1]<=P?"Yes":"No"),0;
}

Postscript

最近慢慢要开始准备给新一届的暑假前集训搬题了，可能能补题的时间会变少一些，但还是尽量能补就补吧

标签：AtCoder,typedef,int,long,Regular,pair,include,171,define
From： https://www.cnblogs.com/cjjsb/p/18059090

相关文章

  • AtCoder Beginner Contest 343
    A-WrongAnswer(abc343A)题目大意给定\(a,b\)，输出\(c\)，使得\(a+b\neqc\)解题思路从\(0\)开始枚举\(c\)的取值即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.......
  • AtCoder Beginner Contest 321
    \[\large\text{Round12:AtCoderBeginnerContest321}\]一言:只要你在，我便无所不能。——进击的巨人感觉只有最后一道题有点意思，其他的就是时间问题，但是速度还是不够快，思维要跟上啊。有意思的是，周考考了回退背包，这里居然又来一次。。\(\text{G:ElectricCircuit}......
  • AtCoder Regular Contest 171
    \[\large\text{Round13:AtCoderRegularContest171}\]一言:我并不是要失去自由，而是要去收获那无可替代的不自由。——SSSS.电光机王几年没写了，但是我们仍然要捡回来！没啥好写的，T1，T2能力范围之内，T3不会，T4感觉很好，但是没做出来。\(\text{D:RollingHash}\)这题无论......
  • AtCoder Beginner Contest 298
    \[\large\text{Round5:AtCoderBeginnerContest298(VP)}\]一言:成一事者，是失之不渝的愚者；毁一事者，是停滞不前的贤者。——不正经的魔法讲师\(\text{Ex:SumofMinofLength}\)这次比赛总体难度不是很大，可能也是我第一次自己独立做出\(\text{Ex}\)。（虽然不是场切......
  • AtCoder Beginner Contest 315
    \[\large\text{Round6:AtCoderBeginnerContest315}\]一言:愿悲、爱恋、你和宇宙以及那颗星辰，能够永远拥抱我们。——THEBEYOND-機動戦士ガンダム40周年纪念曲这场打的一般，主要还是一开始网卡爆了把心态弄得很不好，一定程度上影响了发挥。\(\text{G:Ai+Bj+Ck......
  • AtCoder Beginner Contest 310
    \[\large\text{Round8:AtCoderBeginnerContest310(VP)}\]一言:虚伪的眼泪，会伤害别人，虚伪的笑容，会伤害自己。——反叛的鲁鲁修\(\text{F}\)竟然没有第一时间想到状压，还是太蒟了。。\(\text{F:Make10Again}\)这题看到一个子集，再加上子集和的范围只需要考虑小于......
  • AtCoder Beginner Contest 313
    \[\large\text{Round2:AtCoderBeginnerContest313(VP)}\]一言：当我拔出第二把剑时，就是为了我所爱之人——刀剑神域这场比赛真的是大败而归，只A了\(A,B,C,E\)。。。虽然但是，\(F,G\)确实不可做，但是\(D\)题还是有点可惜了。\(\text{D:OddorEven}\)感觉考场......
  • AtCoder Beginner Contest 343
    AtCoderBeginnerContest343比赛链接A-WrongAnswer思路简单的模拟，事实上我们需要注意一下当a和b都为0的情况Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ inta,b; cin>>a>>b; intans=a+b; //cout<<a+b-1<<en......
  • AtCoder Beginner Contest 343
    基本情况前四题秒了，但是都有不够优雅的地方F知道是线段树，但是写不出来，极其绝望C-343C-343(atcoder.jp)更简洁的回文判断MyCodeboolcheck_p(i64x){std::strings(std::to_string(x));intn=sz(s);for(inti=0;i<n/2;i++){if......
  • AtCoder Beginner Contest 343：起航
    AtCoderBeginnerContest343：起航2024/3/2/22:53有点儿晚了，简单总结一下。前4题都很基础，一点点小思维，其中C题边界又盲目追求刚刚好，WA了一次，总结经验，程序实际设计应该略微大于数据范围。EFG开始就做不动了，只剩了20多分钟，先通读然后看E题，E题读了半天发现大概是体积交并反......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99