AtCoder Beginner Contest 226(E,F,G)
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（组合问题）
这个题的大意就是我们需要构造一个序列\(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（贪心）
这个题有一个\(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;
}