NOI2015网络同步赛总结与反思

  • 内容
  • 评论
  • 相关

嘛,其实我这个同步赛狗没什么好些的,不过既然做了,就写一下好了... 超人熊

Day x(x<=0)

    做了几套弱省胡策,感觉自己弱爆了
    然后又去被xjoi的题虐...
    考试前一天码了几个模板,还有+Rp的程序...

Day 1

【比赛前】:
    貌似有延时了?
    标准开场,貌似8:50左右比赛开始
【比赛过程】
T1:
【题目大意】:
    给出一对等式或不等式,判断是否成立
【题目解法】:
    签到题?
    显然并查集,不过要离散化
    我们先把等式弄出来,用并查集维护即可
    然后在并查集里判断不等式是否成立,复杂度O(N)
    大概写了20min+对拍10min
【FSF noip模拟赛 T1】:
    这题需要在线做法
    考虑启发式合并
    对每个点维护与其有关的不等式,合并时利用启发式合并
    然后暴力判断不等式是否成立,由于启发式合并,每个等式做多被判断log次
    所以复杂度就是O(nlogn)
    我不会告诉你我用了二分+cheat乱搞过了...
T2:
【题目大意】:
    给出一棵树,设计数据结构维护:
    1.子树求和
    2.子树修改
    3.链上求和
    4.链上修改
【题目解法】:
    原题?bzoj 4034: [HAOI2015]T2
    按照树链剖分的顺序弄出dfs序
    既可以维护链也可以维护子树,复杂度O(N log N)
    写了40min+对拍10min
T3:
【题目大意】:
    有n-1个数2....n,两个人任意选若干个,求两个人取得数两两都互质的方案数
【题目解法】:
    一开始想容斥dp来着,后来发现太复杂,果断放弃
    考虑暴力O(4^N)还是算了吧
    然后我们在考虑(x,y)=1,满足没有一样的质因数
    考虑N<=30,质数只有10个左右,状压dp即可,复杂度O(2^20*N)
    然后...就不会了
    标解出发点跟我想的一样...
    我们发现每个数分解质因数最多只有1个是>根号N的,因此对于小于根号N那10个数状压dp,大于根号N的枚举即可
【成绩】:
    于是嘛,就100+100+30=230,感觉大众分数?
    不过今天ccf成绩出的也太快了吧,比赛结束1h后就有成绩了...
    据说25个AK...

Day2

    跟我有个毛线关系啊...

Day3

【比赛前】:
    今天比赛比较准时,8:30开始
T1:
【题目大意】:
    求K叉哈夫曼树
【题目解法】:
    似乎不是签到题了?
    考虑贪心解2叉哈夫曼树
    仿照那个即可,每次选取权值最小的K个即可
    有两个细节:
    1.题目要求深度最小,每次合并时,如果权值一样要比较深度
    2.由于如果给出的结点不能弄满K叉树,答案可能不会最优。比如最后剩下不到K的点组成哈夫曼树,我们显然可以把最深的结点拉若干个上来补满根结点的儿子,这样答案会更优,所以我们可以考虑补权值为0的结点即可。我们考虑补多少个?每次取K个,放回去一个,等于减去k-1个,我们令t=n%(k-1),那么如果t=0,说明存在一个时刻有(k-1)个,这个时候选不出k个,因此补一个点;如果t=1,那么最后剩下1个,显然合法;如果t>1,那么不k-t个即可,注意特判k=2,此时不能补结点
    写了1h+对拍10min
T2:
【题目大意】:
    给出字符串,如果两个子串lcp>=r,则称他们为“r相似”的
    每个子串的权值为第一个位置的字母的权值a[i],一对“r相似”子串的权值为他们两者的权值乘积
    统计对于r=1..n-1,r相似子串的个数,以及r相似子串中的最大权值
【题目解法】:
    原题?bzoj 3238: [Ahoi2013]差异  题目不同,但是做法相似
    当然似乎比较大众的做法是SAM+treedp...我表示太长时间没写SAM了,就写了一发SA
    考虑求出SA后,求出height,考虑暴力枚举做法是O(n^2)
    再来考虑对于某个height[i],他的有效区域[l,r]怎么求?
    有效区域的意思即为:在height[l..r]中height[i]最小,此时人选x<i y>=i,满足x开头的子串和y开头的子串的lcp为height[i]
    因此任选的x y都是[1..height[i]]相似的(显然相似具有包含性),第一问解决。用线段树维护区间最大次大,最小次小即可解决第二问
    考虑如何求出[l,r],显然单调栈即可,复杂度O(N)
    然后就是要解决重复问题,由于有些height[i]相同,可能会有重复
    我们定义[l,i]不重复,[i+1,r]可重复即可(感觉好抽象...)
【吐槽】:
    然而只有70pt...
    原因是最大值可能小到-1e18,然而我的INF只开到了-1e12...
    手贱啊!!!
T3:
【题目大意】:
    有一些点,每个点只能向左边,右边,上边,左上,右上到达第一个未访问过的点
    第一问:求最多访问几个点 20%
    第二问:输出任意一种最优解的便利方法 20%
    第三问:没仔细看... 60%
【题目解法】:
    第三问貌似是最小路径覆盖模型,没时间写了
    考虑前两问
    显然的想法是构图跑spfa或直接dp
    考虑如何构图,我们建3*N个set把每一列,每一左斜线,每一右斜线上的点串起来,查询即可,复杂度O(nlogn)
    然而同一行之间的边有正环...
    没关系,题目有限制,同一行的点最多不超过1000
    于是同一行直接枚举起点终点dp即可,其它的dp转移即可
    考虑复杂度:O(N/1000*1000^2)=O(1000N),挺科学的
    然而方案不好弄,因为同一行的转移比较烦,最后一刻调出来了,可惜没时间了
【总结】:
    Day1:100+100+30=230
    Day2:100+70+20=190
    总分:230+190=420
    貌似Ag?然而并没有进省队...
    只能说还是太弱了...
    orz chenjb 浙大一本  xqf复旦一本  ljh北大一本,祝高考顺利!

又是一年NOI 超人熊

(首尾呼应一下嘛)

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.