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

AtCoder Regular Contest 163

时间：2023-07-04 12:55:18浏览次数：46  
标签：AtCoder frac int Regular freopen mod include RI 163

Preface

补题，这场比赛的时候被拉去开科研组会了，所以就没现场打了

这两天军训在伤病连划水，白天可以好好想题目舒服的一批

这场D题确实很妙，需要一些竞赛图相关的知识才能想到转化，不过也算是学到一个重要trick了吧

A - Divide String

显然只要考虑能否分成两个串即可，首先如果存在\(i\in[2,n]\)使得\(s_i>s_1\)则直接以\(i\)为开头断开即可

否则对于所有\(s_i=s_1\)的位置，暴力检验从这里分开是否合法即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; bool flag=0; scanf("%d%s",&n,s+1);
		for (i=2;i<=n&&!flag;++i) if (s[i]>s[1]) puts("Yes"),flag=1;
		if (flag) continue;
		for (i=2;i<=n&&!flag;++i) if (s[i]==s[1])
		{
			int sign=0; for (j=1;j<=min(i-1,n-i+1);++j)
			if (s[j]!=s[i+j-1]) { sign=s[j]-s[i+j-1]; break; }
			if (sign<0||(sign==0&&i-1<n-i+1)) flag|=1;
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}

B - Favorite Game

首先我们肯定只对\(a_1,a_2\)修改是最优的，然后刚开始一眼想到二分答案，再感觉可以三分一下\(a_1\)减少的次数

然后写了一发发现样例都过不去，遂赶紧发现是个丁真题

我们给\(a_3\sim a_n\)排序后，枚举所有长度为\(m\)的区间\(a_i\sim a_{i+m-1}\)，考虑把\(a_1,a_2\)变成这个能涵盖区间所需的最小代价即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,m,a[N],ans=2e9;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+3,a+n+1),i=3;i+m-1<=n;++i)
	ans=min(ans,max(0,a[1]-a[i])+max(0,a[i+m-1]-a[2]));
	return printf("%d",ans),0;
}

C - Harmonic Mean

有意思的构造题，首先不难想到用裂项公式来构造，因为\(\frac{1}{x(x+1)}=\frac{1}{x}-\frac{1}{x+1}\)，所以我们总有如下构造方案（在\(n\ge 3\)时）：

\[1=\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+\cdots+\frac{1}{(n-1)\times n}+\frac{1}{n} \]

不难发现如果\(n\)不能表示成\(k(k+1)\)的形式的话就已经做完了，现在就是要考虑重复的情况

由于\(k(k+1)\)一定是偶数，那么如果\(n\)可以被这样表示那么\(n-1\)就一定不能被这样表示，因此我们可以先用\(n-1\)个数表示出\(\frac{1}{2}\)，然后再填一个\(\frac{1}{2}\)上去即可

举个例子对于\(n=6=2\times 3\)，按照上面的方法分解出就是\(1=\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\frac{1}{30}+\frac{1}{6}\)是不合法的

那么我们可以先处理\(n=5\)的情况，\(1=\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\frac{1}{5}\)，然后两边同乘上\(\frac{1}{2}\)得到\(\frac{1}{2}=\frac{1}{4}+\frac{1}{12}+\frac{1}{24}+\frac{1}{40}+\frac{1}{10}\)，最后再加上\(\frac{1}{2}\)就可以用\(6\)个数表示\(1\)了

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d",&n),n==1) { puts("Yes\n1"); continue; }
		if (n==2) { puts("No"); continue; }
		RI i; int t=0; for (i=1;i*(i+1)<=n;++i) if (n==i*(i+1)) t=i;
		if (!t)
		{
			for (puts("Yes"),i=1;i<n;++i)
			printf("%d ",i*(i+1)); printf("%d\n",n); continue;
		}
		for (puts("Yes"),printf("%d ",2),i=1;i<n-1;++i)
		printf("%d ",2*i*(i+1)); printf("%d\n",2*(n-1)); continue;
	}
	return 0;
}

D - Sum of SCC

首先有一个关于竞赛图的SCC的重要结论：

竞赛图强连通缩点后的DAG呈链状，前面的所有点向后面的所有点连边。

证明其实也很简单，利用归纳法逐一加入每个SCC即可，具体可以看这里

然后利用这点我们就可以把统计SCC数目转化为另一个问题了

设将图的点集\(V\)划分为\(A,B\)两个集合，且满足\(A\)中的所有点与\(B\)中的所有点的边的方向均为\(A\to B\)，则这种点集划分的方案数即为图的SCC个数加\(1\)

证明的话就考虑上面的结论，我们将缩点后的DAG链记为\(s_1,s_2,\cdots,s_k\)，当\(i<j\)时，边的方向均为\(s_i\to s_j\)

则对于\(t\in [0,k]\)，\(A=\{s_1,s_2,\cdots,s_t\}\)和\(B=\{s_{t+1},s_{t+2},\cdots,s_k\}\)均为满足上述要求的划分方案，且不存在在这之外的方案了

因此我们只要统计上面的问题的答案即可，这个很容易通过DP算出

设\(f_{i,j,k}\)表示以及处理了前\(i\)个点，其中有\(j\)条边的方向是从小到大的，且集合\(A\)的大小为\(k\)的方案数

转移的话就考虑\(i+1\)号点放在集合\(A\)还是集合\(B\)即可：

  • 若放在集合\(A\)，枚举原来\(A\)集合中的边有\(t\in[0,k]\)条方向为从小到大，则\(f_{i,j,k}\times C_k^t\to f_{i+1,j+t,k+1}\)
  • 若放在集合\(B\)，枚举原来\(B\)集合中的边有\(t\in[0,i-k]\)条方向为从小到大，则\(f_{i,j,k}\times C_{i-k}^t\to f_{i+1,j+k+t,k}\)

最后答案就是\((\sum_{i=0}^n f_{n,m,i})-C_{\frac{n(n-1)}{2}}^m\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=35,mod=998244353;
int n,m,C[N][N],f[N][N*N][N],ans;
inline int sum(CI x,CI y)
{
	return x+y>=mod?x+y-mod:x+y;
}
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,t; for (scanf("%d%d",&n,&m),i=0;i<=n;++i)
	for (C[i][0]=j=1;j<=i;++j) C[i][j]=sum(C[i-1][j],C[i-1][j-1]);
	for (f[0][0][0]=1,i=0;i<n;++i) for (j=0;j<=m;++j)
	for (k=0;k<=i;++k) if (f[i][j][k])
	{
		for (t=0;t<=k;++t) inc(f[i+1][j+t][k+1],1LL*f[i][j][k]*C[k][t]%mod);
		for (t=0;t<=i-k;++t) inc(f[i+1][j+k+t][k],1LL*f[i][j][k]*C[i-k][t]%mod);
	}
	for (ans=1,i=m+1;i<=n*(n-1)/2;++i) ans=1LL*ans*i%mod*quick_pow(i-m)%mod;
	for (ans=(mod-ans)%mod,i=0;i<=n;++i) inc(ans,f[n][m][i]);
	return printf("%d",ans),0;
}

Postscript

好题很多，慢慢补吧

标签：AtCoder,frac,int,Regular,freopen,mod,include,RI,163
From： https://www.cnblogs.com/cjjsb/p/17525474.html

相关文章

  • AtCoder Regular Contest 163 D Sum of SCC
    洛谷传送门AtCoder传送门怎么连这种相对传统的计数也不会……考虑换种方式描述强连通分量个数。考虑竞赛图缩点后存在一条极长的链，因此转化为把缩完点后的链劈成左右两个集合，使得左边集合不为空的方案数。于是我们现在只要统计点集\(A,B\)数量，满足\(A\ne\varnothing,A......
  • AtCoder Regular Contest 153 E Deque Minimization
    洛谷传送门AtCoder传送门我们考虑给定\(X\)，如何贪心地求\(f(X)\)。队列为空时加入队首或队尾都是一样的。队列不为空，设队首为\(c\)。因为我们的目标是最小化字典序，于是如果\(X_i\lec\)，我们把\(X_i\)加入队首，否则加入队尾。由此也容易发现，加入队首的数一定单调不升。......
  • AtCoder Beginner Contest 308 G Minimum Xor Pair Query
    洛谷传送门AtCoder传送门考虑没有删除操作怎么做。可以动态维护\(ans\)，新加进来一个\(x\)，我们计算\(\min\limits_{y\inS}x\oplusy\)。对\(S\)建01Trie，然后从高位往低位按位贪心，在01Trie上优先往与\(x\)这一位相同的方向走，但是前提是它的子树内有数，对于01Trie......
  • 题解 ARC163C【Harmonic Mean】
    没想出来什么优美的解法，来个乱搞。特判平凡情况\(n\le2\)，其中\(n=1\)显然有\(1=\frac{1}{1}\)，\(n=2\)无解。众所周知\(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^k}+\frac{1}{2^k}\)。注意到公式中除了\(\frac{1}{2^k}\)有重复外，其余项均无重复。容易......
  • AtCoder ABC307D 题解
    AtCoderABC307DMismatchedParentheses题解思路分析First——配对括号序列首先，每个右括号肯定是要与其左边最近的左括号配对。因此，我们便可以使用一个栈来进行存放左括号的下标。当有右括号时，便可以弹出栈顶元素，但是栈为空时，便无法配对。拿样例1举个例子：8a(b(d))c......
  • AtCoder Beginner Contest 308 A~F
    AtCoderBeginnerContest308手速有点慢A-NewScheme判断给定数字是否满足条件voidsolve(){ boolok=true; inta[10]; for(inti=1;i<=8;i++) cin>>a[i]; for(inti=1;i<=8;i++) { if(i>=2&&a[i]<a[i-1]) ok=......
  • AtCoder Beginner Contest 308
    A：1#include<cstdio>2#include<cstring>3#include<algorithm>4#include<iostream>5#include<string>6#include<vector>7#include<stack>8#include<bitset>9#include<cstdlib>10#include......
  • 【atcoder beginner 308E - MEX】
    前缀和二分查找打表枚举代码如下importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.io.StreamTokenizer;importjava.util.ArrayList;importjava.util.List;publicclassMain{publicstaticIntege......
  • AtCoder Grand Contest 021 E Ball Eat Chameleons
    洛谷传送门AtCoder传送门容易发现一个变色龙是红色当且仅当，设\(R\)为红球数量，\(B\)为蓝球数量，那么\(R\geB\)或\(R=B\)且最后一个球是蓝球。考虑如何判定一个颜色序列是否可行。考虑贪心。若\(R<B\)显然不行。若\(R\geB+n\)，每个变色龙都可以分到比蓝球......
  • AtCoder Beginner Contest 307（E,F,G)
    AtCoderBeginnerContest307（E,F,G)E(dp)E这个题大意就是我们需要组成一个长度为\(n\)的数组，满足两个相邻的数字不可以相等，其中，\(a_1\)和\(a_n\)也是相邻的，我们可以选择的数字为\(0\)到\(m-1\),问最后有多少种不同的组成方式满足以上条件。题目大意很简单，就是有点难想，如果\(a......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99