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
转载请注明出处,谢谢!