[ZJOI2015]诸神眷顾的幻想乡

题目描述
幽香是全幻想乡里最受人欢迎的萌妹子,这天,是幽香的2600岁生日,无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 粉丝们非常热情,自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 这时幽香发现了一件非常有趣的事情,太阳花田有$n$块空地。在过去,幽香为了方便,在这$n$块空地之间修建了$n-1$条边将它们连通起来。也就是说,这$n$块空地形成了一个树的结构。
有$n$个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺,他们选择了$c$中颜色的衣服,每种颜色恰好可以用一个$0$到$c-1$之间的整数来表示。并且每个人都站在一个空地上,每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了,感觉也非常开心。
粉丝们策划的一个节目是这样的,选中两个粉丝A和B(A和B可以相同),然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来(包括端点),幽香就能看到一个长度为A到B之间路径上的所有粉丝的数目(包括A和B)的颜色序列。一开始大家打算让人一两个粉丝(注意:A,B和B,A是不同的,他们形成的序列刚好相反,比如红绿蓝和蓝绿红)都来一次,但是有人指出这样可能会出现一些一模一样的颜色序列,会导致审美疲劳。
于是他们想要问题,在这个树上,一共有多少可能的不同的颜色序列(子串)幽香可以看到呢? 太阳花田的结构比较特殊,只与一个空地相邻的空地数量不超过20个。
输入输出格式
输入格式:
第一行两个正整数$n,c$。表示空地数量和颜色数量。 第二行有$n$个$0$到$c-1$之间,由空格隔开的整数,依次表示第i块空地上的粉丝的衣服颜色。(这里我们按照节点标号从小到大的顺序依次给出每块空地上粉丝的衣服颜色)。 接下来$n-1$行,每行两个正整数$u,v$,表示有一条连接空地$u$和空地$v$的边。
输出格式:
一行,输出一个整数,表示答案。
输入输出样例
输入样例#1:
7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5
输出样例#1:
30
说明
对于所有数据,$1\leq n \leq 100000, 1 \leq c \leq 10$。
对于$15\%$的数据,$n\leq 2000$。
另有$5\%$的数据,所有空地都至多与两个空地相邻。
另有$5\%$的数据,除一块空地与三个空地相邻外,其他空地都分别至多与两个空地相邻。
另有$5\%$的数据,除某两块空地与三个空地相邻外,其他空地都分别至多与两个空地相邻

从叶子节点DFS整棵树,然后插进广义SAM里。。。。

发表在 SAM | 留下评论

交易一中集训Day[7]

又是有测试的一天。。。
大力猜结论~!
观察找规律~!
WA的一声就哭了.jpg
TLE的一声就哭了.jpg
T1猜了两个小时的结论。。。。
然后只有15分。。。。
T3二分乱搞。。。。成功TLE。。。。。
zrO ljt大佬要不是2SAT打炸了就随手A题了啊 Orz
被吕老板支配的恐惧

趣题选讲很资瓷!
大力猜结论!
嘴巴随口A(x
见到了很久以前的题目啊。。。。。
感觉好亲切(x
诱骗萌新的博弈题啊。。。。
说起来学校现在都不怎么搞科技节活动了呢。。。。
似乎除了水火箭以外就没了。。。。。

做不出来这道题就别想出去(误

WP自带Markdown居然会把代码块里的大于小于号转义。。。。
真是可怕极了

发表在 未分类 | 留下评论

HDU 4609 3-idiots

Problem Description
King OMeGa catched three men who had been streaking in the street. Looking as idiots though, the three men insisted that it was a kind of performance art, and begged the king to free them. Out of hatred to the real idiots, the king wanted to check if they were lying. The three men were sent to the king's forest, and each of them was asked to pick a branch one after another. If the three branches they bring back can form a triangle, their math ability would save them. Otherwise, they would be sent into jail.
However, the three men were exactly idiots, and what they would do is only to pick the branches randomly. Certainly, they couldn't pick the same branch - but the one with the same length as another is available. Given the lengths of all branches in the forest, determine the probability that they would be saved.
Input
An integer T(T≤100) will exist in the first line of input, indicating the number of test cases.
Each test case begins with the number of branches N(3≤N≤105).
The following line contains N integers a_i (1≤a_i≤105), which denotes the length of each branch, respectively.
Output
Output the probability that their branches can form a triangle, in accuracy of 7 decimal places.
Sample Input
2
4
1 3 3 4
4
2 3 3 4
Sample Output
0.5000000
1.0000000
Source
2013 Multi-University Training Contest 1
Recommend
liuyiding

令$a_i$表示数$i$有多少个,对$a$求一遍卷积就可以得到任选两个数,和为$x$的方案数,这里注意要去一下重。考虑到任意三个不能构成三角形的数,都有且仅有一个数大于等于另外两个数的和,所以我们搞一个前缀和就好了。
R数组的计算不能放到外面。。。。。
代码写得丑。。。。
格式化软件差点不给格式化。。。。

发表在 FFT, HDU | 2条评论

交易一中集训Day[6]

与Ferric Ion认识的第30天(((
解锁成就 聊得♂火热

这个世界需要更多的懒觉!(不
起来和Ferric聊了一会。。。。。
学弟们都好强啊qwq
要被学弟们虐了qwq
PJ这次快压事故也真是。。。。
说起来快压这种辣鸡软件居然还没惹出事来?

谷歌浏览器访问官网会提示该网站会诱骗用户安装有损浏览体验的程序

点进去看了看发现这个破软件甚至还有压缩赚钱项目?!
想钱想疯了吧都。。。。
有空研究一下它的格式搞个反快压压缩。。。。
7z大法好。。。。

尝试使用Topcoder 一直连不上。。。。 辣鸡TC。。。。。

看费马大定理的时候百科里提到了一个模曲线。。。。
搜索一下这都是什么鬼东西(╯‵□′)╯︵┻━┻
你根本不是我认识的那个谷歌(╯‵□′)╯︵┻━┻
不敢想关了安全搜索会出来什么东西。。。
细看百度的结果都是什么模型压力曲线 XX模拟曲线
这样看来似乎百度的结果更糟糕些。。。。。
必硬、数字这些搜出来的结果和百度也差不多。。。。
被WP的Markdown折腾得死去活来。。。。
一堆插件没一个好用的。。。。。
晚上和ljt讨论引水入城能不能用费用流做。。。。
结果发现建不出图来。。。
然后想费用流的一条边费用能不能流过多少都只算1的费用。。。。
Rank1大佬x1 金牌爷x1 队爷x1 均表示不会做。。。
然后发现好像是NP的。。。。。
瑟瑟发抖

发表在 未分类 | 留下评论

交易一中集训Day[5]

这几天一直在修博客的Markdown和Latex的兼容问题。。。。
跳票了几天。。。。
都快忘了干了些啥。。。

聊天记录回忆一波。。。。。
深入FFT。。。。。

  • 开始
    妙啊
    还不错哟

  • 这是啥

  • 这又是啥
  • 数论?
  • DP?
  • 数据结构?

作为一个省一都没有的蒟蒻连最最朴素的DP都想不出来qwq
进入掉线模式
中午去xjk宾馆洗澡。。。。。。
神奇的派酒店。。。
大概是$\pi$主题。。。
Wifei密码都是31415926
那么问题来了,为什么没有$\mathrm{e}$酒店$\gamma$酒店$\phi$酒店(误
见到了平生见过的最窄的电梯。。。。感觉差不多只有一人宽
魔改WP插件。。。加入他的语录。。。
下午杂题选讲
被Topcoder支配的恐惧

晚上被HN同学成功拐跑。。。
全然忘记自己带着房卡。。。
走在路上一拍脑袋突然想起来结果手机还欠费。。。。
最后在电话接通之前老师就已经开车找到我们了。。。。

发表在 未分类 | 留下评论

交易一中集训Day[4]

虽然今天有测试。。。但是还是不可避免地起晚了
事实证明,这个“先进”的冲水系统一点都不好用。。。。
什么都冲不下去

看到题之后瞬间就懵了。。。。
数论全家桶是什么鬼啊(╯‵□′)╯︵┻━┻
大胆猜一波性质。。。

你的公司有n个妹子,她们要开演唱会,第i个人有一个迷之分数$a_i$,观众对一组妹子的满意度定义为这些妹子迷之分数的平均数减去中位数,你需要选出一些妹子参加比赛,使得观众的满意度最大。
输出保留四位小数
$n \leq 200000 , 0 \leq a_i \leq 10^9$
样例输入
4
1 2 3 12
样例输出
3.0000

手玩了样例猜测选前两个和最后一个,特判N<=2去玩后面。。。。。。
T2奥妙重重的排列数 T3奥妙重重的组合数
xjb打表找规律。。。。T2在OEIS上查到了递推式。。。。
T3根本找不到。。。。。
快结束前又返回去拍了一下T1。。。。。 三下就WA。。。
又观察了一下数据。。。。
大胆猜测两头取相同个数再到较小的一端取中位数。。。。 又拍还WA。。。于是弃疗。。。。
结果下午出成绩发现A了。。。。还莫名其妙成了Rank1。。。。。 瑟瑟发抖

下午是FFT和杂题选讲。。。。

xjk光速过ppt看得我一脸懵逼。。。。不现推一下感觉非常懵逼。。。。
还好有算导。。
大概就是求两个多项式的乘积可以先把这两个系数表达多项式换成等价的点值表达,然后点值表达就可以$O(n)$直接乘过去,乘出来的多项式次数是原来两个多项式次数的和,所以原来两个多项式都需要用$m+n$个点值对表示,乘完之后再把结果插成系数表达。
于是问题来了,怎么快速求点值表达以及插回系数表达

FFT通过恰当地选择x降低求值和插值的复杂度
首先引入单位复数根即满足$\omega^n=1$的复数$\omega$,对于$k=0,1,\dots,n-1$,这些根是$\mathrm{e}^{2\pi\mathrm{i}k/n}$
由复数的指数形式的定义 $$\mathrm{e}^{iu}=\cos(u)+\mathrm{i}\sin(u)$$
得 $$ω_n^k=\cos(2\pi k/n)+\mathrm{i}\sin(2\pi k/n)$$
这个东西有很多非常优雅的性质:

  • (消去引理)对任意整数$n \geq 0,k \geq 0,d \geq 0$,有
    $$\omega^{dk}_{dn}=(\mathrm{e}^{2\pi\mathrm{i}/dn})^{dk}=(\mathrm{e}^{2\pi\mathrm{i}/n})^{k}=\omega^{k}_{n}$$

  • (折半引理)如果$n>0$且$n$为偶数,那么$n$个$n$次单位根的平方的集合就是$n/2$个$n/2$次单位根的集合,且每个元素恰好出现两次。

  • (求和引理)对于任意整数$n\geq1$和不能被$n$整除的整数$k$,有$$\sum_{j=0}^{n-1}(\omega_n^k)^j=0$$

这个折半引理是坠重要的,有了它我们就可以像香港记者一样快了,它保证了递归子问题的规模只有递归调用前的一半。

我们希望计算次数为$n$的多项式 $$A(x)=\sum_{j=0}^{n-1}a_jx^j$$ 在$\omega_n^0,\omega_n^1,\omega_n^2,\dots,\omega_n^{n-1}$处的值,所以对$k=0,1,2,\dots,n-1$
$$y_k=A(\omega_n^k)=\sum_{j=0}^{n-1}a_j\omega_n^kj$$
我们可以把多项式 $$A(x)=\sum_{j=0}^{n-1}a_jx^j$$ 拆成两个$n/2$次的新多项式 $$A^{[0]}=a_0+a_2x+a_4x^2+\dots +a_{n-2}x^{n/2-1}$$ $$A^{[1]}=a_1+a_3x+a_5x^2+\dots +a_{n-1}x^{n/2-1}$$ 则 $$A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$$ 于是把问题转化为了求$A^{[0]}(x)$和$A^{[1]}(x)$在$(\omega_n^0)^2,(\omega_n^1)^2,\dots,(\omega_n^{n-1})^2$处的值
由折半引理可知$x^2$的取值只有$n/2$个
所以成功的缩小了子问题的规模,复杂度$O(n \lg n)$ 至于插值有(详见算导)
$$a_j=\frac{1}{n}\sum_{j=0}^{n-1}y_k\omega_n^{-kj}$$
然后再观察找规律法实现迭代计算
cpp

发表在 未分类 | 留下评论

交易一中集训Day[3]

自习一天!!!

WA的一声就哭了
TLE的一声就哭了
RE的一声就哭了

早上调了两个小时的费用流。。。。。结果发现S加错了。。。。
下午还是接着切费用流。。。。
然后越改越怀疑人生。。。
哇不会是我板子的问题吧(
交道洛谷模板题压压惊
我擦怎么是70。。。。。
后三个点还是输出0 0。。。。
一条增广路都没找到。。。。。 吓得我又交了一发Dinic。。。。。。还是0。。。。
最后发现我只读了n条边。。。。。。
这都能有70。。。。卡卡常切掉(
然后接着测poi的题。。。。
研究了会对拍怎么写。。。。
然后拍了2K组N=10也没挂。。。。
感觉害怕。。。。。
拍了一组N=1发现我居然用N去建线段树。。。。。
逗号运算符重载在Debug的时候很好用((

Description
有n个强盗,其中第i个强盗会在$a[i],a[i]+1],[a[i]+1,a[i]+2],...,[b[i]-1,b[i]]$这么多段长度为1时间中选出一个时间进行抢劫,并计划抢走\(c[i]\)元。作为保安,你在每一段长度为1的时间内最多只能制止一个强盗,那么你最多可以挽回多少损失呢?
Input 第一行包含一个正整数n(1<=n<=5000),表示强盗的个数。
接下来n行,每行包含三个正整数a[i],b[i],ci,依次描述每一个强盗。
Output
输出一个整数,即可以挽回的损失的最大值。
Sample Input
4
1 4 40
2 4 10
2 3 30
1 3 20
Sample Output
90
Source
By Claris

发表在 未分类 | 留下评论

交易一中集训Day[2]

玄学网络流!!!
做模板题教辅的组成忘记拆书。。。。

二食堂东边这个窗口真可怕。。。。各种乱七八糟的菜全堆在一起。。。。那味道。。。。这地方本来口味也偏重。。。。
啊~
到了外面,才知道我校的食堂原来辣么棒。。。。

教工食堂的WiFi是假的!
人与人之间最基本的信任呢 搞到了密码显示WAN口未插♂
啊~

Q:如何减少bug?
A:提高1A率
Q:如何提高1A率?
A:减少bug
Q:1A率受bug率影响,bug率又收1A率影响,这样岂不是成环了啊
A:不是啊,是你bug率减少的结果是你1A率增加啊,你提升1A率是给减少bug一个明确的目标
Q:那如何提高1A率呢
A:减少bug啊

杂题选讲听着听着就CONNECTION_RESET了。。。。。。。尝试重连失败。。。。。。
然后就刷模板题。。。。。。
花式WA花式RE花式TLE花式CE。。。。
我好菜啊。。。

回去一起颓了一会Duck Game。。。。
利用信息不对等成功虐人(x
他们都说我打游戏看起来超认真。。。。。
我。。。。
瑟瑟发抖。。。
我一句话也不说是坠吼的啊。。。。。 怎么就。。。认真了。。。。

发表在 未分类 | 留下评论

交易一中集训Day[1]

起来之后感到瑟瑟发抖。。。。昨天晚上和小伙伴们挤一挤果然不冷了。。。。。然而起来的时候。。。啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 简直要死。。回想起了那些年没有暖气的日子。。。。
食堂里饼好多的样子。。。感觉有点咸。。。。
上午T1T2看起来很可做的样子。。。。。基本就是裸的逆元。。。exgcd乱搞一下就可以了。。。然后发现map时间会被卡。。。map里也忘记开long long。。 炸成75。。T1想出了正解。。。就是一个奇怪的01序列的线段树。。。不过标记炸了。。。挂成8分。。。gg。。。。
中午发现可能是顶到了AP的Reset恢复了出厂设置。。。。还以为它也gg了。。。。wireshark抓了一下包get到IP就能愉快的进管理页面了。。。。。
下午讲博弈。。。。经典的Nim游戏。。。。异或乱搞一下。。。。。
阶梯博弈。。a[0]是没有用的。。。可以归纳地证明所有偶数层的石子也是没有用的。。。奇数层的拿出来玩Nim游戏就可以了。。。。
然后就讲sg函数。。。
啊,然后sg函数值也可以当Nim玩的样子。。。每个sg(x)都可以转移到0~sg(x)-1。。。。然后异或乱搞一下。。。。。
然后又是一堆奇奇怪怪的东西。。。。
数据发下来都是些奇奇怪怪的东西。。。。
[5,5)
(5,5)
这都是什么鬼区间啊(╯‵□′)╯︵┻━┻
然而dalao们的鲁棒性都好强啊qwq
晚上又是饼。。。。还是好咸。。。。柠檬水好甜。。。感觉这里口味偏重。。。。。
校园里随处可见游荡的doge。。。
写到这里想起来cdc同学说校园里会有校领导出没,在校园里游荡有可能会被抓起来(((
拿到了空调遥控器。。。可以睡个好觉了((((

发表在 未分类 | 留下评论

交易一中集训Day[0]

在车上睡了一觉醒来就到了,发现带的AP完全没啥卵用,距离太远还直视不到。。。基本不行。。。。感觉这破AP主板好像也被我搞炸了。。。晚上回去再看看。。。和HN的住在一块。。。ljt大佬真是太强辣!%%%
到机房戳开oj发现一个Judging赫然躺在那里。。。虽然说oj有多任务分布完全不用担心评测队列卡住。。。但是还是要看看发生了什么。。。。下好Sh ad ow so ck s准备fq结果发现闪退。。。gg。。。。自带SSTP证书错误。。。gg。。。。Sothether UDP模式会被深度包检测。。。。(好像所有大流量UDP都会被封。。gg)。。最后强制禁用UDP才连上。。。



处理CE的代码有个地方改炸了没发现。。。。单元测试很重要(然而并没有时间写)。。。。gg。。。。。。
晚上回去和其他SX小伙伴们拼床在一起(((啊(
挤一挤就不冷了(( 然后收到我爸消息我才惊讶的发现我没有带电脑的电源。。。。 电池还能撑会的样子。。。。 AP大约的确是炸了。。。。

发表在 未分类 | 留下评论