OZY退役邀请赛

发表于 更新于 分类于 评论数： 阅读次数：

OZY退役邀请赛

比赛链接

C 学前班数学题

题意：
T组询问，每组询问给定两个正整数X，Z
你要找到最小的Y满足LCM(X,Y)=Z。保证有解
$T≤10^6，X,Z\le10^{18}$

唯一要解决的问题就是$gcd (\frac{z}{x},\frac{x}{d})=1$ 最大化d

我只想到log方的，就是x不断/gcd

正解是log的，就是x也同时乘gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void main()
{
	int T=qread();
	while(T--)
	{
		ll x=qread(),z=qread();
		ll a=z/x,b=x;
		while(1)
		{
			ll d=gcd(a,b);b/=d;a*=d;
			if(gcd(a,b)==1)break;
		}
		write2((z/x)*(x/b));
	}
}

51nod2030 Zbox的刷题II

首先题意是带标号的n道题

zsy的做法：正确性比较显然
$$
考虑对每个子集统计贡献，设大小为i的子集贡献系数为bi（显然只跟集合大小有关） \\
\sum_{i=1}^n C_n^ib_i(P^{0i}+P^{1i}…)=\sum_{i=1}^n \frac{C_n^i b_i}{1-P^i} \\
a_0=0,a_n=\sum_{i=0}^n C_n^ib_i,b_n=\sum_{i=0}^n(-1)^{n-i}C_n^ia_i，NTT求b，O(nlogn)
$$

出题人做法：

先说怎么做，就是把ai看做连续点值求这个多项式的下降幂；为啥是对的，我并不知道……

loj2417 bzoj4576 「USACO 2016 US Open, Platinum」262144

我的做法：
从小到大考虑，孤立的点会变成分界点，但分割这东西我不会怎么写成函数，只能硬着头皮写了1h+，过的时候真的成就感满满（因为担心做法假）
大概就是维护一段区间，然后每次扫同一个值的所有东西，然后向上合并，然后如果这一段长度是奇数，在中间建立分割点，然后因为题目只需要求最大值是什么，所以相互独立进行两组实验，告诉左边「我舍弃了最右边那个」，告诉右边「我舍弃了最左边那个」（xgc的优秀idea）
时间复杂度为 $O(n值域)$ 这个复杂度和正解一样，但不满，所以loj登顶了，code；然后发现也有人和我一样的做法的
正解：code 非常好写……

LOJ3014 「JOI 2019 Final」独特的城市

设直径端点为S和T，按照与谁近划分两点的地盘，则节点x的独特城市一定在x到管理x的端点另一个的路径上

那么我们分别以S和T为根建树，然后最后用所属端点来决定输出哪个答案

如果用dfs遍历节点并用栈保存到根路径上所有当前合法的点，容易发现到其孩子的话最多增加一个节点x本身

那么我们现在得到一个暴力做法：依次遍历每个孩子，然后将栈内到x距离<=「其他孩子能贡献最长到x的链」的节点删除并加入x，回溯的时候还原；等所有节点都处理完了，再求出x的答案（用x的最长链更新后）

发现这样复杂度无法保证，但先别急着换做法；注意到如果那个更新的阈值递减就不用还原了，也就是说我们先用次长链更新，然后访问长孩子，再用最长链更新访问其他孩子，这样就没有还原了，于是就能保证复杂度，即每个点加入度数次，复杂度为线性；code

小学生网格题

题目
题意：
n*m四连通的网格，一个格子被控制满足下面两个条件之一:
1：这个格子被标记
2：这个格子相邻的格子都被标记
给出每个格子控制的收益和标记的代价，求最大收益-代价
1≤n,m≤100

规模、值域很小，费用流好像不是很可行，考虑最小割，黑白染色

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
	#define double long double
	typedef long long ll;
	#define pr pair<int,int>
	#define FR first
	#define SE second
	#define MP make_pair
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) putchar('-'),num=-num;
		if(num>=10) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	const int INF=0x3f3f3f3f;
	const int MOD=950009857;
	inline ll qpower(ll x,ll e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	inline ll invm(ll x){return qpower(x,MOD-2);}
	const int N=1e3+10;
	int hou[N*N];
	struct Edge{int y,g,c;}e[N*N];
	int ln=0;int oth(int k){return k&1?k+1:k-1;}
	void ins(int x,int y,int c)
	{
		// printf("(%d->%d,%d)\n",x,y,c);
		e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;
		e[++ln]=(Edge){x,hou[y],0};hou[y]=ln;
	}
	int st,ed;
	int h[N*N];queue<int> q;
	bool bfs()
	{
		memset(h,0,sizeof h);q.push(st);h[st]=1;
		while(q.size())
		{
			int x=q.front();q.pop();
			for(int k=hou[x];k>0;k=e[k].g)
			{
				int y=e[k].y;
				if(!h[y] and e[k].c) h[y]=h[x]+1,q.push(y);
			}
		}
		return h[ed]>0;
	}
	int dfs(int x,int flow)
	{
		if(x==ed or !flow) return flow;
		int tt=0;
		// printf("dfs(%d,%d)\n",x,flow);
		for(int k=hou[x];k>0;k=e[k].g)
		{
			int y=e[k].y;
			if(h[y]==h[x]+1 and e[k].c)
			{
				int out=dfs(y,min(flow-tt,e[k].c));
				e[k].c-=out;e[oth(k)].c+=out;tt+=out;
			}
			if(tt==flow) break;
		}
		if(!tt) h[x]=0;
		return tt;
	}
	const int dx[4]={0,0,-1,1};
	const int dy[4]={-1,1,0,0};
	int cost[N][N],beneft[N][N];char str[N];
	int to(char c){return ('0'<=c and c<='9'?c-'0':('a'<=c and c<='z'?10+c-'a':36+c-'A'));}
	void main()
	{
		int n=qread(),m=qread();
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str+1);
			for(int j=1;j<=m;j++) cost[i][j]=to(str[j]);
		}int ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",str+1);
			for(int j=1;j<=m;j++) beneft[i][j]=to(str[j]),ans+=beneft[i][j];
		}
		st=0,ed=N*N-1;int T=m+10,TT=T*(n+2)+10;
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
		{
			int id=T*i+j;
			for(int pp=0;pp<4;pp++)
			{
				int tx=i+dx[pp],ty=j+dy[pp];if(tx<1 or tx>n or ty<1 or ty>m) continue;
				if((i+j)&1) ins(TT*2+id,TT*3+T*tx+ty,INF);
				else ins(T*tx+ty,TT+id,INF);
			}
			if((i+j)&1) ins(st,id,cost[i][j]),ins(id,TT+id,INF),ins(TT+id,TT*2+id,beneft[i][j]);
			else ins(TT+id,TT*2+id,beneft[i][j]),ins(TT*2+id,TT*3+id,INF),ins(TT*3+id,ed,cost[i][j]);
		}
		while(bfs())
		ans-=dfs(st,INF);
		write(ans);
	}
};
int main()
{
	freopen("a.in","r",stdin);
	srand(time(0));
	mine::main();
}

中学生网格题

题目
题意：
n*m的网格，每个格子可以填1~k
定义两行是相似的，当将各行中的数升序排序后，完全一致
问使得各行两两不相似的方案数
对1e9+7取模

做法一：理论运算次数5亿，常数拉满且带模，不过我卡过去了（943ms），分享一下

考虑一行的合法情况，如果枚举m的分拆数（2e5），那么会产生 $tmp=\frac{tot!}{\prod (cnt_i!)}*C_k^{tot}$ 个本质不同的行（注意不是P，因为分拆方案可能某数字多次出现），但他们的可选择方案数都是$pp=\frac{m!}{\prod (a_i!)}$ （a是m的分拆，cnt是某个数字i在a中出现次数，tot为拆分成多少个不同的数），正确性自己思考一下，就是多重集排列；于是每次做一个n方的dp，考虑在这种拆分下选多少个

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
#define double long double//不加会wa一个点
double ff[N];
ll f[N],fac[N],facinv[N],inv[N],gg[N];int n,m,k;
void dfs(int now,int mi,ll pp,ll tot,ll tmp,double real)
{
	if(tot>k) return;
	if(now==0)//tmp种本质不同的行，这些行的方案每个都是pp种
	{
		tmp=tmp*facinv[k-tot]%MOD;real=real/ff[k-tot];
		gg[0]=1;for(int i=1;i<=n;i++) gg[i]=gg[i-1]*(tmp+MOD-i+1)%MOD*inv[i]%MOD*pp%MOD;
		for(int i=n;i>=1;i--) for(int j=i-1;j>=0;j--)
		{
			if(i-j>real) break;
			f[i]=(f[i]+f[j]*gg[i-j])%MOD;
		}
		return;
	}
	for(int i=mi;i<=now;i++) for(int cnt=1,pp2=pp*facinv[i]%MOD;cnt*i<=now and tot+cnt<=k;cnt++,pp2=pp2*facinv[i]%MOD)
		dfs(now-i*cnt,i+1,pp2,tot+cnt,tmp*facinv[cnt]%MOD,real/ff[cnt]);
}
void main()
{
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
	facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;
	inv[1]=1;for(int i=2;i<N;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	ff[0]=1;for(int i=1;i<N;i++) ff[i]=ff[i-1]*i;
	n=qread(),m=qread(),k=qread();
	f[0]=1;dfs(m,1,fac[m],0,fac[k],ff[k]);write(f[n]*fac[n]%MOD);
}

做法二：$O(n^4)$，注意到枚举具体分拆限制了复杂度，考虑用dp而不是dfs

首先做一个简单dp搞出$g(n)$表示n行相似的方案数，转移考虑枚举每种数字出现次数就好了，$O(n^4) $

然后考虑容斥dp，将行分拆成若干组，每组内相似，组间互不相似；你发现我们只需要计算组大小形如$1,1,1…lst(lst \ge1)$这样的分拆就可以了

设$f(a,lst)$表示前面有a个1，考虑前面哪个和最后那个相似，$f(a,lst)=f(a-1,1)*g(lst)-a*f(a-1,lst+1)$

$ans=f(n-1,1)，O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll fac[N],facinv[N],fi[N][N];
ll g[N],tmp[N],f[N][N];
void main()
{
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
	facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;
	for(int i=0;i<N;i++) {fi[i][1]=facinv[i];for(int j=2;j<N;j++)fi[i][j]=fi[i][j-1]*fi[i][1]%MOD;}
	int n=qread(),m=qread(),k=qread();
	for(int i=1;i<=n;i++)
	{
		memset(tmp,0,sizeof tmp);tmp[0]=1;
		for(int num=1;num<=k;num++)
			for(int x=m;x>=1;x--) for(int y=0;y<x;y++)
				tmp[x]=mm(tmp[x]+tmp[y]*fi[x-y][i]%MOD);
		g[i]=tmp[m]*qpower(fac[m],i)%MOD;
	}
	for(int lst=1;lst<=n;lst++) f[0][lst]=g[lst];
	for(int i=1;i<n;i++) for(int lst=1;lst<=n;lst++) f[i][lst]=(f[i-1][1]*g[lst]+MOD-i*f[i-1][lst+1]%MOD)%MOD;
	write(f[n-1][1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/1f5d.html
转载请注明出处，谢谢！