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

AtCoder Regular Contest 167

时间：2023-10-18 13:11:54浏览次数：32  
标签：AtCoder typedef include int long times Regular 167 define

Preface

补一下上周日的ARC，因为当天白天和队友一起VP了一场所以就没有精力再打一场了

这场经典C计数不会D这种贪心乱搞反而是一眼秒了，后面的EF过的太少就没看

A - Toasts for Breakfast Party

用一个类似于蛇形的放法就好了，比如对于\(n=9,m=5\)，放法为：

5 6 7 8 9
4 3 2 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=200005;
int n,m,a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+1,a+n+1,greater <int>()),j=1,i=m;i>=1;--i) b[i]=a[j++];
	for (i=1;i<=m&&j<=n;++i) b[i]+=a[j++]; LL ans=0;
	for (i=1;i<=m;++i) ans+=1LL*b[i]*b[i];
	return printf("%lld",ans),0;
}

B - Product of Divisors

首先将\(A\)质因数分解，设\(A=p_1^{c_1}\times p_2^{c_2}\times \cdots\times p_k^{c_k}\)

考虑质因子\(p_1\)对答案的贡献，\(A^B\)中\(p_1\)的次数为\(\prod_{i=2}^k (c_i\times B+1)\times (0+1+2+\cdots+c_1\times B)\)

除去原来\(A\)中\(p_1\)的次数\(c_1\)后得到答案为\(\frac{B}{2}\times \prod_{i=1}^k (c_i\times B+1)\)，不难发现对于所有的质因数得到的都是这个结果

但我们还要注意到这个式子中除以\(2\)的部分不一定能整除，因此我们需要讨论一下：

  • 当\(B\)为偶数时，直接计算即可
  • 当\(B\)为奇数时，若存在某个\(c_i\)为奇数，那么亦直接计算即可
  • 当\(B\)为奇数时，且所有\(c_i\)均为偶数时，将分子部分减\(1\)后再除以\(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=200005,mod=998244353,inv2=(mod+1)/2;
int A,B,ans;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%lld%lld",&A,&B); bool has_odd=0; ans=B%mod;
	for (i=2;i*i<=A;++i) if (A%i==0)
	{
		int c=0; while (A%i==0) A/=i,++c;
		ans=ans*(B%mod*c%mod+1)%mod;
		if (c&1) has_odd=1;
	}
	if (A>1) ans=ans*(B%mod+1)%mod,has_odd=1;
	if (B%2==0||has_odd) (ans*=inv2)%=mod;
	else ans=(ans-1+mod)*inv2%mod;
	return printf("%lld",ans),0;
}

C - MST on Line++

龟龟经典一上计数就做不来，纯躺好等着队友C了属于是

考虑将点权从小到大排序，不难发现我们不关心每个点的具体权值，只要算出最后排名为\(i\)的点贡献的次数即可

考虑用克鲁斯卡尔算法求MST的过程，我们总是尽可能的用权值小的边来连接独立的连通块

因此不妨这样考虑，设\(f_i\)表示只用前\(i\)个点时图中最多能选出的不成环的边数，则答案为：

\[\sum_{i=2}^n (f_i-f_{i-1})\times a_i \]

因此现在问题转化为求\(f_i\)，考虑先枚举确定一个\(i\)，那么排名前\(i\)小的点对应的下标则构成一个集合\(S\)

要计算\(S\)中的点最多能连出多少边，我们可以先将\(S\)中的元素升序排列

此时不难发现对于一对相邻的元素\(S_i,S_{i+1}\)，若\(S_{i+1}-S_i\le k\)，则这两点之间就可以连边，不难发现这样可以得到不成环且最多的连边数量

考虑怎么统计合法的\(S\)的数量，不妨先考虑第一个元素和第二个元素之间的贡献

我们把问题抽象为，给定一个长度为\(i\)的序列，序列中的元素升序排列且值域均为\([1,n]\)，且满足第二个元素与第一个元素之差为\(k\)，求最后合法的序列数量

发现如果没有差的限制的话这个问题的答案就是\(C_n^i\)，而现在有了这个限制相当于就是把第二个数和第一个数合并，因此方案数为\(C_{n-k}^{i-1}\)

同时我们发现对于第\(i\)个元素和第\(i+1\)个元素间的差为\(k\)的答案均是上面的式子，而我们最后要求的是\(\le k\)的限制，因此可以写出贡献的表达式

\[(i-1)\times \sum_{j=1}^k C_{n-j}^{i-1} \]

但同时我们还要推一下对于给定的\(S\)集合它对应的排列的个数，这个很容易发现就是\(i!\times (n-i)!\)，因此最后有：

\[f_i=i!\times (n-i)!\times (i-1)\times \sum_{j=1}^k C_{n-j}^{i-1} \]

不难发现暴力计算这个式子的复杂度为\(O(nk)\)，符合题目要求

PS：当然可以把后面的组合数用公式化简得到一个\(O(n)\)计算答案的式子，但不是本题想考察的地方因此就不care了

#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,mod=998244353;
int n,k,a[N],fact[N],ifac[N],f[N],ans;
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;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+1,a+n+1),init(n),i=1;i<=n;++i)
	{
		int ret=0; for (j=1;j<=k;++j) (ret+=C(n-j,i-1))%=mod;
		f[i]=1LL*fact[i]*fact[n-i]%mod*(i-1)%mod*ret%mod;
	}
	for (i=1;i<=n;++i) (ans+=1LL*(f[i]-f[i-1]+mod)*a[i]%mod)%=mod;
	return printf("%d",ans),0;
}

D - Good Permutation

做这场之前看了下榜发现比赛时D过的比C多，所以补题的时候先写了D，不得不说确实如此

这题思路很顺畅，先找出原排列的所有置换环，不难发现题目的要求就是让所有所有元素在一个置换环内，而一次交换操作实际上就是合并两个置换环

考虑如何实现字典序最小这一限制，经典的做法就是从前往后扫，贪心地确定每一位能取的最小值

我们这里的解决方法也是类似，每次考虑求出在当前位置\(i\)后面且和当前位置上的数不在一个置换环中最小的那个数\(j\)

如果\(j<i\)的话则把这两个数交换一定是最优的，否则就忽略掉等后面的数来完成合并操作

但这样只能处理一部分情况，对于形如\(2,1,4,3\)这样的情况是无法处理的，因此还需要完成合并的要求

由于经过了之前的过程我们发现对于同一个集合的数通过交换无法使得答案变优，因此在只能变劣的情况下我们贪心地从后往前处理即可

如果当前数和它后面的所有数不在一个集合内，就把这个数和后面所有数中最小的那个交换即可

用并查集维护集合关系即可，总复杂度\(O(n\times \alpha(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;
int t,n,p[N],pos[N],fa[N],vis[N];
int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&p[i]),pos[p[i]]=i,fa[i]=i,vis[i]=0;
		for (i=1;i<=n;++i) if (!vis[i])
		for (vis[j]=1,j=p[i];j!=i;j=p[j]) vis[j]=1,fa[getfa(p[j])]=getfa(p[i]);
		for (i=1;i<=n;++i) vis[i]=0;
		for (i=j=1;i<=n;++i)
		{
			while (j<=p[i]&&getfa(j)==getfa(p[i])) ++j;
			if (j>p[i]) continue; fa[getfa(j)]=getfa(p[i]);
			pos[p[i]]=pos[j]; swap(p[i],p[pos[j]]); pos[j]=i;
		}
		int mi=p[n]; for (i=n-1;i>=1;--i)
		{
			bool flag=p[i]<mi; int tmp=p[i];
			if (getfa(p[i])!=getfa(mi)) 
			fa[getfa(mi)]=getfa(p[i]),pos[p[i]]=pos[mi],swap(p[i],p[pos[mi]]),pos[mi]=i;
			if (flag) mi=tmp;
		}
		for (i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

数数苦手表示Atcoder越做越煎熬了……

标签：AtCoder,typedef,include,int,long,times,Regular,167,define
From： https://www.cnblogs.com/cjjsb/p/17771835.html

相关文章

  • Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contes
    JapanRegistryServices(JPRS)ProgrammingContest2023(AtCoderBeginnerContest324)赛后总结可悲的是：我没来得及写题解。T1Same秒切。直接输入排一遍序再遍历即可。#include<bits/stdc++.h>usingnamespacestd;intn,a[101];intmain(){cin>>n;f......
  • 比赛总结：Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginn
    比赛：JapanRegistryServices(JPRS)ProgrammingContest2023(AtCoderBeginnerContest324)A-same1.常规方法intmain(){ intn; cin>>n; vector<int>s(n);//利用vector容器可以不需要确定内存大小 for(auto&n:s) { cin>>n; } for(inti=0;i......
  • AtCoder Regular Contest 066 F Contest with Drinks Hard
    洛谷传送门AtCoder传送门下文令\(a\)为原题中的\(T\)。考虑若没有饮料，可以设\(f_i\)表示，考虑了前\(i\)道题，第\(i\)道题没做的最大得分。转移就枚举上一道没做的题\(j\)，那么\([j+1,i-1]\)形成一个连续段。设\(b_i\)为\(a_i\)的前缀和，可得：\[f_i=\max\li......
  • Atcoder Regular Contest 167
    卡B下大分了，怎么回事呢。A.ToastsforBreakfastParty发现题意是让方差尽可能小，就是让\(A\)里的值尽可能接近。所以从小到大排个序，把\(A_{N,\dots,N-M+1}\)依次放进\(1,2,\dots,M\)，再把\(A_{N-M,\dots,1}\)依次放进\(M,M-1,\dots,2M-N+1\)就赢了。B.Productof......
  • AtCoder Beginner Contest 324
    在高铁上加训！A-Same(abc324A)题目大意给定\(n\)个数，问是否都相等。解题思路判断是不是全部数属于第一个数即可。或者直接拿set去重。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(f......
  • 【题解】AtCoder-ARC167
    AtCoder-ARC167AToastsforBreakfastParty一定不会有空盘，问题转化成\(2m\)个数，其中\(2m-n\)个是\(0\)，这样一定是最大值和最小值一起，次大值和次小值一起，以此类推。提交记录：Submission-AtCoderAtCoder-ARC167BProductofDivisors\(A^B=\prod_ip_i^{Bc_i}\)，那么答案......
  • [ARC167D] Good Permutation 题解
    题意对于一个长度为\(N\)的排列\(Q\)，定义其为好的，当且仅当对于任意整数\(i\in\left[1,N\right]\)，在进行若干次操作\(i\leftarrowQ_i\)后可以得到\(i=1\)。给定一个排列\(P\)，定义一次操作为交换两个数。定义\(M\)为可以将\(P\)变为一个好的的排列的最小操......
  • AtCoder Beginner Contest 180 F Unbranched
    洛谷传送门AtCoder传送门首先进行一个容斥，把连通块最大值\(=K\)变成\(\leK\)的方案数减去\(\leK-1\)的方案数。考虑dp，设\(f_{i,j}\)表示当前用了\(i\)个点，\(j\)条边。转移即枚举其中一个连通块的大小\(k\)。为了不算重，我们强制让这个连通块包含点\(1\)，类......
  • ARC167D Good Permutation 题解
    题意给定一个长度为\(N\)的排列\((P_1,P_2,\cdots,P_N)\)。称一个排列\(P\)为“好排列”当且仅当对于所有\(1\leqx\leqN\)，都能通过不停地使\(x\leftarrowP_x\)将\(x\)变成\(1\)。通过最小次数操作将\(P\)变成“好排列”，每次操作为交换\(P\)中的两个数\(P_i\)......
  • AtCoder Beginner Contest 324
    D-SquarePermutation须知：最大的平方数的平方一定小于等于10n，平方数最多为10(n/2)（因为再大会越界）因为要求的数一定是原数的排列组合，所以它们的元素和对应的元素个数一定相同所以只要判断平方数的字符串是否与原字符串相等即可（这里可以利用排序判断）点击查看代码#include<bi......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99