USACO 2020 US Open Gold

发表于 分类于

USACO 2020 US Open Gold题解。

Haircut

题意

一个数组，对于每个 $i\in[0,n)$，若将 $\geq i$ 的数全部变成 $i$，求逆序对个数。

$n\leq 10^5$

题解

考虑一个逆序对 $(a_j,a_k)$ 在哪些 $i$ 有贡献，显然是在 $[a_k+1,n)$ 处会产生贡献，然后树状数组随便算就好了。

Favorite Colors

题意

一个有向图，需要给点染上颜色。颜色从 $1$ 开始标号。若存在边 $(b,a),(c,a)$，则 $b,c$ 必须颜色相同。

求在满足颜色数最大的时候，的最大字典序。

$n\leq 2\times 10^5$

题解

考虑在 $a$ 处考虑，对于连向 $a$ 的两个点 $b,c$ 而言，我们可以把他们看成一个点。把这两个点的信息合并到一起。然后如果合并后这个点也有两个或以上连向它的点，则也要把这些点合并。因此开一个队列记录有哪些 $a$ 是需要对连向它的点进行合并的。

合并用启发式合并即可。

时间复杂度 $O(n\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2e5+5;
int n,m;
unordered_set<int> s[N];
vector<int> adj[N];
queue<int> q;
int fa[N],vis[N];
inline void merge(int x,int y)
{
	if(s[x].size()<s[y].size()) swap(x,y);
	for(auto v:s[y]) s[x].insert(v),fa[v]=x;
	for(auto v:adj[y]) adj[x].pb(v);
	adj[y].clear();
	if(adj[x].size()>1) q.push(x);
}
int main()
{
	FO(fcolor);
	n=read(); m=read();
	fo(i,1,m)
	{
		int x=read(),y=read();
		adj[x].pb(y);
	}
	fo(i,1,n)
	{
		fa[i]=i; s[i].insert(i);
		if(adj[i].size()>1) q.push(i);
	}
	for(int u,v,w;!q.empty();)
	{
		u=q.front();
		if(adj[u].size()<=1) {q.pop(); continue;}
		v=fa[adj[u].back()];
		adj[u].pop_back();
		w=fa[adj[u].back()];
		if(v==w) continue;
		merge(v,w);
	}
	int cnt=0;
	fo(i,1,n)
	{
		if(!vis[fa[i]]) vis[fa[i]]=++cnt;
		printf("%d\n",vis[fa[i]]);
	}
	return 0;
}

Exercise

题意

一个 $n$ 阶置换，定义这个置换的次数为 $(1,2,\cdots,n)$ 按照该置换进行操作，用最少的大于 $0$ 的操作数，使得所有的 $i$ 最后都回到原来的位置上。

问所有的 $k$ 的和，满足存在至少一个置换的次数为 $k$。答案对 $m$ 取模。

$n\leq 10^4$

题解

显然一个置换的次数为所有环长的LCM。

刚开始想的时候还以为要搞什么Min-Max容斥之类的。

结果你发现只需要一个贪心，对于某个 $p^k$ 而言，假设出现在了LCM中，那么只需要一个单独的环，长度为 $p^k$ 即可。其他的环大可不必有 $p$ 的倍数，而多出来的用自环就可以搞定。

也就是判断一个 $k$ 是否合法可以先将其质因数分解：$k=\prod_{i=1}^mp_i^{q_i}$。然后判断是否满足 $\sum_{i=1}^mp_i^{q_i}\leq n$ 即可。

那么考虑枚举质因子进行 DP，设 $f_{i,j}$ 表示考虑到第 $i$ 个质数，当前总和为 $j$ 的所有的 $k$ 的和，然后枚举 $i^l$ 进行转移。

时间复杂度 $O(\frac{n}{\ln n}n\log n)=O(n^2)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=10002;
const int M=2000;
ll mod;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
ll f[N][M];
int pri[M],cnt,n;
bool bo[N];
inline void init(int n)
{
	fo(i,2,n)
	{
		if(!bo[i]) {pri[++cnt]=i;}
		for(int j=1;j<=cnt&&i*pri[j]<=n;j++)
		{
			bo[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}

int main()
{
	FO(exercise);
	n=read(); mod=read();
	init(n);
	f[0][0]=1;
	fo(j,1,cnt)
	{
		fo(i,0,n)
		{
			f[i][j]=Add(f[i][j],f[i][j-1]);
			for(int k=1,t=pri[j];t<=i;k++,t*=pri[j])
				f[i][j]=Add(f[i][j],Mul(f[i-t][j-1],t));
		}
	}
	ll ans=0;
	fo(i,1,n) ans=Add(ans,f[i][cnt]);
	printf("%lld",Add(ans,1));
	return 0;
}