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

Atcoder Regular Contest 167

时间:2023-10-16 20:12:43浏览次数:38  
标签:Atcoder le int mn long 因数 Regular 167 排列

卡 B 下大分了,怎么回事呢。

A. Toasts for Breakfast Party

发现题意是让方差尽可能小,就是让 \(A\) 里的值尽可能接近。
所以从小到大排个序,把 \(A_{N,\dots,N-M+1}\) 依次放进 \(1,2,\dots,M\),再把 \(A_{N-M,\dots,1}\) 依次放进 \(M,M-1,\dots,2M-N+1\) 就赢了。


B. Product of Divisors

大家快看,这里有一个试图在质因数分解后的指数上推点式子,于是卡 B 1h 的樱雪喵 /cf

Description

给定 \(A,B\),问 \(A^B\) 所有因数的积不断除以 \(A\),最多能除几次。
\(A\le 10^{12},B\le 10^{18}\)。

Solution

发现因数是成对的,对每个因数都有 \(x\times \frac{A^B}{x}=A^B\),设 \(A^B\) 的因数个数为 \(n\)。
如果 \(n\) 是偶数,把因数两两分成 \(\frac{n}{2}\) 对,每对的积都是 \(A^B\),\(A^B\) 的因数之积就是 \(A^{(Bn/2)}\),答案是 \(\frac{Bn}{2}\)。
如果是奇数,说明 \(A^B\) 是完全平方数,我们把这个数单独拆出来考虑,\(A^B\) 的因数之积是 \(A^{B(n-1)/2}\times \sqrt{A^B}\),答案也是这个。
注意完全平方数分为 \(A\) 本身是完全平方数和 \(B\) 是偶数两种情况。
于是就做完了,时间复杂度瓶颈在质因数分解,\(O(\sqrt{A})\)。

Code
bool flag=0;
signed main()
{
    A=read(),B=read();
    if((int)sqrt((long long)A)*(int)sqrt((long long)A)==A) flag=1;
    for(int i=2;i*i<=A;i++)
    {
        if(A%i==0)
        {
            a[++cnt]=i;
            while(A%i==0) b[cnt]++,A/=i;
        }
    }
    if(A>1) b[++cnt]=1;
    int res=1;
    for(int i=1;i<=cnt;i++) res=res*(b[i]*B%mod+1)%mod;
    if(B%2==0||flag) res=(res+mod-1)%mod;
    res=res*qpow(2,mod-2)%mod*B%mod;
    if(B%2==0||flag) res=(res+B/2)%mod;
    cout<<(long long)res<<endl;
    return 0;
}

C. MST on Line++

完全不会做,人菜,没救了。

Description

给定正整数 \(n,K\) 和一个长度为 \(n\) 的序列 \(A\)。对于一个 \(1\sim n\) 的排列 \(P\),我们定义 \(f(P)\) 为以下问题的答案:

给一个 \(n\) 个点的无向带权图,对于两点 \(i<j\),当且仅当 \(j-i\le K\) 时,它们之间有边,边权为 \(\max(A_{P_i},A_{P_j})\)。
求这个图的最小生成树边权和。

对于所有可能的排列 \(P\),求出它们的 \(f(P)\) 之和,答案对 \(998\,244\,353\) 取模。

\(1\le K< N\le 5000\),\(1\le A_i \le 10^9\)。

Solution

发现我们只要求出每条边被选了几次,就可以统计出它们的权值和。
考虑 Kruskal 求最小生成树的过程,发现按边权排序后,我们会选择哪些边只与边之间的大小关系有关,与具体的边权无关。那么我们把 \(A_i\) 升序排序后,令第 \(i\) 类边表示边权为 \(A_i\) 的边,就可以只关心每类边分别选了几次。

考虑如下的子问题:

给定一个边权的限制 \(a\) 和一个排列 \(P\),对于 \(i<j\),\(i,j\) 之间有无权边当且仅当 \(j-i\le K\) 且 \(\max(P_i,P_j)\le a\)。求在边之间不形成环的条件下最多选择几条边。

对于一个排列 \(P\),边权为 \(A_i\) 的边被选择的条数就是 \(a=i\) 时的答案减掉 \(a=i-1\) 时的答案。
设 \(f_{i}\) 表示所有排列 \(P\) 在 \(a=i\) 时该子问题的答案之和。那么有:

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

考虑 \(f_i\) 怎么求。

对于一个排列 \(P\),我们令所有 \(P_j\le i\) 的下标 \(j\) 构成集合 \(Q\),\(Q\) 中的元素升序排序。因为边权是取 \(\max\),不在 \(Q\) 内的点一定没有任何连边。
故所有 \(Q_j-Q_{j-1}\le K\) 的下标之间都有连边,且把它们都选上一定是不劣的。对于一个排列 \(P\) 的答案就是 \(\sum\limits_{j=2}^i [Q_j-Q_{j-1}\le K]\)。

枚举一个 \(j\),对于所有排列计算满足 \(Q_j-Q_{j-1}\le K\) 的数量。\(Q_j-Q_{j-1}=k\) 的排列有 \(\binom{n-k}{i-1}\) 个,\(\le K\) 的就有 \(\sum\limits_{j=1}^K \binom{n-j}{i-l}\) 个。那么一共有 \(i-1\) 对相邻的下标,一个 \(Q\) 序列对答案的贡献是 \((i-1)\sum\limits_{j=1}^K\binom{n-j}{i-l}\)。

一个 \(Q\) 序列对应的排列 \(P\) 的个数是 \(i!(n-i)!\),最终的式子是

\[f_i=i!(n-i)!(i-1)\sum_{j=1}^K \binom{n-j}{i-1} \]

求 \(f_i\) 的时间复杂度为 \(O(nK)\),求答案的时间复杂度为 \(O(n)\)。

Code
#define int long long
const int N=5005,mod=998244353;
int n,K,a[N];
int f[N],jc[N],c[N][N];
il void init(int mx)
{
    for(int i=0;i<=mx;i++)
        for(int j=0;j<=i;j++) c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%mod:1;
}
signed main()
{
    n=read(),K=read(); init(n);
    for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1);
    jc[0]=1;
    for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=K;j++) f[i]=(f[i]+jc[i]*jc[n-i]%mod*(i-1)%mod*c[n-j][i-1]%mod)%mod;
    // for(int i=1;i<=n;i++) cout<<"f "<<i<<" "<<f[i]<<endl;
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+a[i]*(f[i]+mod-f[i-1])%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

D. Good Permutation

Description

对于一个 \((1,2,\dots,N)\) 的排列 \(Q\),称其是好的,当且仅当

  • 对于每个整数 \(i \in [1,N]\),在若干次 \(i \gets Q_i\) 后能够得到 \(i=1\)。

给定一个排列 \(P\),每次操作可以交换两个数。使用最小的操作次数,使得 \(P\) 成为一个好的排列,若有多种解,输出字典序最小的。

Solution

怎么连着两场 D<C 呢?

对于每个 \(i\),我们连边 \(i\to P_i\),那么这张图形成了若干个不相交的环。\(P\) 是一个好的排列当且仅当图上只有一个环。
从小到大依次贪心确定每一位的值,设当前位为 \(i\):

  • 如果存在至少一个 \(P_j=u,j>i\),满足 \(i,j\) 不在一个环且 \(u<P_i\),我们找到最小的 \(u\),并 \(\text{swap}(P_i,P_j)\)。
  • 否则我们不希望字典序变大,尽量不换。但如果 \(i\) 是它所在连通块的最后一个位置,必须要换,找到后面最小的 \(u\),设 \(P_j=u\),并 \(\text{swap}(P_i,P_j)\)。

判断是否在一个环使用并查集,用一个 set 维护每个连通块之间的大小关系。

Code
const int N=2e5+5;
#define pii pair<int,int>
#define fi first
#define se second
int n,a[N];
int fa[N],mn[N],siz[N],pos[N];
set<pii> s;
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y); if(x==y) return;
    s.erase(pii(mn[x],x)),s.erase(pii(mn[y],y));
    fa[x]=y,siz[y]+=siz[x],mn[y]=min(mn[y],mn[x]);
    s.insert(pii(mn[y],y));
}
int main()
{
    int T=read();
    while(T--)
    {
        s.clear();
        n=read();
        for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]]=i;
        for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1,mn[i]=i,s.insert(pii(i,i));
        for(int i=1;i<=n;i++) merge(i,a[i]);
        for(int i=1;i<=n;i++)
        {
            if(s.size()==1) break;
            auto it=s.begin();
            while(find(it->se)==find(i)) it++;
            int u=it->fi;
            if(u<a[i]||siz[find(i)]==1) 
            {
                int j=pos[u]; swap(a[i],a[j]),swap(pos[a[i]],pos[a[j]]);
                merge(i,j);
            }
            siz[find(i)]--;
        }
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

标签:Atcoder,le,int,mn,long,因数,Regular,167,排列
From: https://www.cnblogs.com/ying-xue/p/ARC167.html

相关文章

  • 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......
  • AtCoder Beginner Contest 324 DF题题解
    比赛链接D-SquarePermutation其实比较简单,但是比赛时候脑子不转了,竟然在尝试枚举全排列,然后算了一下复杂度直接不会做了。正解应该是枚举完全平方数,底数枚举到\(sqrt(10^{14})\)即可,因为n最大为13。然后统计一下这个完全平方数各个数字出现了多少个,和读入的比较一下是......
  • Python_regular expression基础
     ......
  • Atcoder Beginner Contest 324 F Beautiful Path 题解-分数规划
    为了更好的阅读体验,请点击这里分数规划小技巧:尽可能将式子写成存在某种取值,使得不等式成立的形式。不然可能需要绕几个弯才能想出来。题目链接题目大意:给出一个DAG,每条边有一个\(b_i,c_i\),保证从编号小的边向编号大的边连边,且\(1\)到\(n\)必有路径,求\(1\)到\(n\)......
  • AtCoder Beginner Contest 321 C-321-like Searcher
    可以观察到0-9的所有子集都能恰组成一个满足题目条件的数字,所以共有1022个数{除空集和0}方法就是二元枚举,找出所有数然后排序。#include<iostream>#include<cstdio>#include<vector>#include<algorithm>usingnamespacestd;usingll=longlong;vector<ll>v;sig......