526互联

AtCoder Beginner Contest 226(E,F,G)

发布时间 2023-04-05 17:25:29作者: righting

AtCoder Beginner Contest 226(E,F,G)

E（并查集）

E

这个题的大意是给我们一个无向图，我们可以把这些无向边变成有向边，让每一个点的入度都是\(1\)，问有多少种变化方式

要让有\(x\)个点的无向图，形成一棵树的边的数量是\(x-1\)，但是我们需要的是每一个点的入度为\(1\)，那么我们只还需要一条边到根节点的边即可，边的数量为\(x\),所以在一个块里面，要想里面的每一个点的入度为\(1\),即边的数量需要等于点的数量

然后已知了这些点的集合是可以满足要求的，那么这些边的方向怎么选择

我们可以先选择一条边的方向，其实后面的边要想使每一个点的入度为\(1\)，那么他们的方向也是固定的了

，所以这一块有两种方式

这道题我们可以用并查集

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <bitset>
#include <unordered_map>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long 
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,m;
int f[maxn];
int siz[maxn],e[maxn];
struct edge
{
    int x,y;
}edge[maxn];
int find (int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y)
{
    int tx=find(x);
    int ty=find(y);
    if(tx==ty) return ;
    siz[tx]+=siz[ty];
    f[ty]=tx;
    siz[ty]=0;
    return ;
}
signed main ()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        f[i]=i;
        siz[i]=1;
    }
    for (int i=1;i<=m;i++)
    {
        cin>>edge[i].x>>edge[i].y;
        merge(edge[i].x,edge[i].y);
    }
    for (int i=1;i<=m;i++)
    {
        int now=find(edge[i].x);
        e[now]++;
    }
    int ans=1;
    for (int i=1;i<=n;i++)
    {
        if(i!=find(i)) continue;
        if(siz[i]==e[i])
        {
            ans=ans*2ll%mod;
        }
        else 
        {
            ans=0;
            break;
        }
    }
    cout<<ans<<"\n";
   system ("pause");
   return 0;
}

F（组合问题）

F

这个题的大意就是我们需要构造一个序列\(P\),我们会对这个序列进行\(x\)次操作，在\(x\)此操作后，这个序列变成了\(1,2,3,...n\)的序列，我们得到\(x\)的价值，设此时的价值\(x\)可以表示成\(f(p)=x^k\),我们需要得知所有的不同的价值的和

这些排序时如何进行操作的呢,最初第\(i\)个人有\(i\)号球

对于每一个\(i\)，把第\(i\)个人的球传给第\(p_i\)个人

直到球的排序变成从\(1\)到\(n\)的有序排列为止

我们有\(t\)来表示，有一个序列\(t\)为\(3,1,2\)

第一步，我们可以得到序列\(3,1,2\)

第二步，序列变成\(2,3,1\)

第三步，序列变成\(1,2,3\)

我们可以发现，一个这样的序列是可以变成有序的，他好像是形成了一个环，按照上面的例子，\(1\)和\(3\)连起来了，\(2\)和\(1\)连起来了，\(2\)和\(3\)连起来了，形成了一个环，然后刚好要想把这个序列变成有序的，需要进行这个序列的长度次

然后这个\(n\)不是很大，所以我们可以构造环

这一个长度为\(n\)的排列，我们可以例举出环的长度和数量的组合，用\(dfs\)实现

我们可以先对所有的排序的数量，对于要存在\(cnt\)个长度为\(len\)的环的数量的组合数量\(sum\)个

\[sum=\frac{n!}{{len!}^{cnt}\times cnt!} \]

上面是环的分配，我们还需要找到这个环里面可以存在多少种组合，对于环的组合，我认为只要让一个点和另外一个不相同的点连接即可，那么就会有\((len-1)!\)个组合方式

然后我们再来考虑对于这\(n\)个排序，存在若干和环，他的价值为多少呢

我们可以知道每一个环都需要可能不同的操作次数，要想满足所有的环，最好的方法是求最小公倍数\(val\)

最好我们可以得到公式

\[ans=ans+n!\times \prod(\frac{1}{(len!)^{cnt}\times cnt!}\times(len-1)!)\times val^k \]

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <bitset>
#include <unordered_map>
using namespace std;
const int maxn=100+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long 
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,k;
int fac[maxn],fac_p[maxn][maxn],invfac[maxn],invfac_p[maxn][maxn];
int res,ans;
int lcm(int x,int y)
{
    return x*y%mod/__gcd(x,y);
}
int ksm(int x,int p)
{
    int res=1;
    while (p)
    {
        if(p&1)
        {
            res=res*x%mod;
        }
        x=x*x%mod;
        p>>=1;
    }
    return res%mod;
}
void init()
{
    fac[0]=1;
    for (int i=1;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        invfac[i]=ksm(fac[i],mod-2);
    }
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=n;j++)
        {
            fac_p[i][j]=ksm(fac[i],j);
            invfac_p[i][j]=ksm(fac_p[i][j],mod-2);
        }
    }
    return ;
}
void dfs(int now,int lmt,int val,int sum)
{
    if(!now)
    {
        int tmp=ksm(val,k)%mod*sum%mod;
        ans=(ans+tmp)%mod;
        return ;
    }
    if(now<lmt) return ;
    for (int i=lmt;i<=now;i++)
    {
        for (int j=1;i*j<=now;j++)
        {
            int tsum=sum*invfac_p[i][j]%mod;
            tsum=tsum*invfac[j]%mod*fac_p[i-1][j]%mod;
            dfs(now-i*j,i+1,lcm(val,i),tsum);
        }
    }
    return ;
}
signed main ()
{
    cin>>n>>k;
    init();
    dfs(n,1,1,fac[n]);
    cout<<ans<<"\n";
   system ("pause");
   return 0;
}

G（贪心）

G

这个题有一个\(a\)数组，\(b\)数组，其中\(a_i\)代表有\(a_i\)个能量为\(i\)的包裹，\(b_i\)代表有\(b_i\)个人最多可以拿\(i\)能量，每一个数组的长度都为\(5\)

问最后我们可以让每一个包裹都让人给拿走了吗

这个就是贪心

对于\(5\)能量，只能让\(5\)的人拿

对于\(4\)能量，先让\(4\)的人拿，再让\(5\)的人拿

对于\(3\)能量，先让\(3\)的人拿，再让\(5\)的人拿，再让\(4\)的人拿

对于\(2\)能量，按照从大到小的顺序的人（可以拿）的人拿

对于\(1\)能量，同\(2\)能量

学习

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <bitset>
#include <unordered_map>
using namespace std;
const int maxn=100+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long 
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,t;
int a[maxn],b[maxn];
void pick(int x,int y)
{
    int c=min(a[x],b[y]);
    a[x]-=c;
    b[y]-=c;
    b[y-x]+=c;
    return ;
}
void solve()
{
    for (int i=1;i<=5;i++)
    {
        cin>>a[i];
    }
    for (int j=1;j<=5;j++)
    {
        cin>>b[j];
    }
    a[0]=0,b[0]=0;
      pick(5, 5); pick(4, 4); pick(4, 5);
    pick(3, 3); pick(3, 5); pick(3, 4);
    for (int i = 5; i >= 2; -- i) pick(2, i);
    for (int i = 5; i >= 1; -- i) pick(1, i);
    for (int i=1;i<=5;i++)
    {
        if(a[i])
        {
            cout<<"No\n";
            return ;
        }
    }
    cout<<"Yes\n";
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
   system ("pause");
   return 0;
}