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 | void main() |
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 |
|
中学生网格题
题目
题意:
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 |
|
做法二:$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 | ll fac[N],facinv[N],fi[N][N]; |