我再不开$C++11$编译我就从三楼跳下去$$ ext{%%%lsc}$$
Day3
-lm -O2 -std=c++11
Before
$Day3$？
全是$Subtask$？
$frac{1}{4}$？
T1
矩阵？
好了我有一分了不会爆零了 =。=
T2
3 秒
怕不是要命……
怕是不要命……
数据结构预约……
T3
仿佛是原题， $kuku$ 了（不会$QnQ$）
不对啊，要求变多了……
$lsc$要笑死了？？（脸都紫了）。
During
T1
如果无重叠的就直接搞答案就好了……
事实上，
仿佛亦或和的意义就是
最后统计出现次数为奇数的数的异或和……
Input
10 4 1 1 10 1 5 5 4 4 1 9 4 3 3 3 5 2
Output
0
sth.
1 0 0 0 0 0 0 0 3 0 1 1 0 0 0 0 0 0 3 3 1 1 3 0 0 0 0 0 3 3 1 1 3 3 0 0 0 0 3 3 1 1 3 3 7 0 0 0 0 0 1 1 3 3 7 7 0 0 0 0 1 1 3 3 7 7 7 0 0 0 1 1 1 1 5 5 5 5 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
突然想到差分……$emm$
需要 $3$ 种不同的差分？
还可以改成 $2$ 种？
都试试……
如果成了，复杂度：
$Theta(Q+N^2)$
完了，出锅了……
有一个前缀和一直交错……
这个题的难点在那个**的三角形二维差分
会有一堆堆的重复……
解决了一个……
分方向更新？
好了，都处理好了$QwQ$
cerr 输出要 3s 哭笑不得
测了半天时间，发现好慢，
后来发现测的是暴力的时间……
拍半天发现没开时间种子……
T2
向WWB致敬！（雾
跑到 $2^30$ 只需要$2.143s$
枚举随机数？
阶乘复杂度$banrbi$炸
如果跑$DP+Qj=Subtask 1,2,3,4$
先拿两分……
$emm$
设$f_s$为选择为s时的贡献。
$count(s)=k$时更新答案……
必须按$count$的顺序更新……
完了又写跪了。
T3
这儿又有 1 分……
所以总共有 4 分？
这题还是树上dp么……
贪心？
二分？
Result&After
T1
就是二维差分，分两个方向维护。
T2
是记忆化搜索……
T3
毒瘤级Dp，主要点在从儿子到当前的转移和二元组Dp。
|
15
|
Miemeng | 100
03:12:59
|
2
03:14:00
|
1
03:14:02
|
103
03:14:02
|
Day4
获得两个好字：叒叕
Before
T1
仿佛是很呵呵的DP题
T2
矩阵……
T3
和阿塞拜疆有关系?
先模拟吧，看着很毒瘤？
During
T1
两侧乘积互质，那么两侧的因子一定是不同的
于是把每一个数因数分解并且特判 $1$
这样在 $10^6$ 下 最多有的不同的因子数就是 $7$ 个……
$$
egin{array}{rcl}
2 imes 3 imes 5 imes 7 imes 11 imes 13 imes 17 &=& 510510 \
2 imes 3 imes 5 imes 7 imes 11 imes 13 imes 17 imes 19 & = & 9699690
end{array}
$$
按因子直接枚举子集……
$3^7$ ?
这……
手摸一番……
好像行？
主要是用每一个数去做限制条件
还有剩下的因子（仿佛并没有什么意义……）
先分解质因数并把大于$sqrt{a_i}$的排在外面……
有个比较可行的小暴力：
先把所有分解的因子压到一个桶里。
每次枚举因子的子集……，然后去取所有的数……
$O(2^PN)$（只能更优）$P$：不同的因子数……
先上个无脑暴力……
大概又有了一个思路，
把所有的数先都乘到一起求一个总共的质因子
然后用容斥，计算每种因子的出现
最后把不可能的情况减去……
复杂度仿佛是 $N^2$ 的？
码力不够啊$QAQ$
各种YY：
首先可以知道，两个相同的数一定在同一个集合里（除1）
那么大于$sqrt{a_i}$的质因子就是独特的（一个数就一个）……
剩下的质因子也就 $168$ 个。
剩下的数就可以用 少于 $168+N$ 的复杂度判出交集……
如果和剩下的没有重复，就可以直接柿子算数。
只要判判交就好。
判交也可以直接维护gcd。
质因数分解处理压vector，$Theta(N*logM)$并且对每个 vector 维护$gcd$。
出点锅……
T2
想想怎么乱搞……
记忆化？
现在觉得回到每个点的路径可以直接循环处理。
每个点能够有贡献的仿佛只有两个点，所以最后其实是一棵二叉树……
可以把树建的怪一点保证复杂度。
因为d为20,所以建20层就够。
那么现在怎么建啊$QAQ$
如果暴力建……$2^N$？
我们现在只需要知道有没有那个节点就好了……
其实是一个化边为点？？
仿一下ST表……
还是复杂度恐怖。
T3
又有 1 分$QvQ$
感觉很怪……
有没有卡常大师 $N^2$ 过 $100000$
完了，我没思路了……
因为要模拟这个过程，所以猜测作者卡暴力卡的很严……
下一步就是要拿到单增的$Subtask$
感觉可以创反思长度记录……800 字反思了解一下……
跪了……
After
|
47
|
Miemeng | 0
03:14:37
|
21
03:14:38
|
31
03:14:38
|
52
03:14:38
|
看到T1的神奇颜色了嘛……CE……
总结：
Day3还行，想的还可以
Day4跪了。
粘个东西来这里：
/sandbox/1/a.cpp:11:9: error: 'long long int div [2]' redeclared as different kind of symbol
LL div[2];
^
In file included from /usr/include/c++/5/cstdlib:72:0,
from /usr/include/c++/5/ext/string_conversions.h:41,
from /usr/include/c++/5/bits/basic_string.h:5249,
from /usr/include/c++/5/string:52,
from /usr/include/c++/5/bits/locale_classes.h:40,
from /usr/include/c++/5/bits/ios_base.h:41,
from /usr/include/c++/5/ios:42,
from /usr/include/c++/5/ostream:38,
from /usr/include/c++/5/iostream:39,
from /sandbox/1/a.cpp:1:
/usr/include/stdlib.h:788:14: note: previous declaration 'div_t div(int, int)'
extern div_t div (int __numer, int __denom)
^
div跪了……emm
请开$C++11$编译$ ext{T_T}$
说一下：一定要按照用的顺序定义变量啊……
$$Huge ext{ %%%$frac{1}{4}$}$$