JSOI2017滚粗记

今年JSOI感觉换了出题人,与往年风格相比变得极为鬼畜,最后0+80+60+120=260分滚粗ORZ。

Round 1

Day1一眼望去,只有第一题可做,我的思路是先对树上的每个点做一遍nlgn的Dijkstra,然后在环上二分,判断环上的点到其他点是走中心点还是不走中心点,然后使用线段树/打标记的方式把环上的距离和求出,最后DFS一遍树求出结果,可惜到九点半才开始写代码,又因为代码实在太繁琐,一直到考结束也没调对,第两题暴力匆忙之中忘了给scanf里面加上&,华丽爆炸,0分滚粗。

Day2第一题就是一道提交答案,构造骗了50分,还有30分因check不力挂了,第二……

阅读全文 »

[HDU 4348]To the moon | 可持久化线段树学习笔记

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4348

给定一个长度为N的数组,要求对数组执行M次指定的区间修改、区间和查询、查询历史版本的区间和、回滚到历史版本。

因为输入数据并没有进行加密,所以完全可以读入所有的数据后进行离线操作(但这样就没意思了,手动滑稽),但如果数据需要前一个查询的结果进行解密,强制在线,那就只能用可持久化线段树,即主席树进行维护。

可持久化数据结构的核心思想就是最大限度地利用之前版本的信息,减少增加记录的空间消耗。对线段树而言,就是将所有未修改的节点指针指向上一个版本的节点。

这一题还有一个要注……

阅读全文 »

[Codeforces 555E]Case of Computer Network

题目链接:http://codeforces.com/problemset/problem/555/E

给定N个节点和M条无向边,再给出Q对(u,v),问能否给每条边标上方向,使Q中的u节点都能到达v节点。

很明显,一个强连通分量中的点只要连成一个点,就一定可以相互到达,tarjan缩点之后整张图就变成了一棵树或者森林。然后可以拿树链剖分对每对(u,v)需要标记的边做线段覆盖,如果一条线段被两个方向的线段树同时覆盖,就说明不存在方案。

[sourcecode lang="cpp"]
#include <cstdio>
#include <cstring&……

阅读全文 »

Hello World | 终于把博客建好了

折腾了一个周末,晚上又被同学玩坏了,只能推倒重来Orz。本博客为一个OI蒟篛的博客,搭VPS翻墙是主要目的,建博客反而是次要的huaji_little,不保证内容准确性,因参考本博客中的代码造成的Wrong Answer本人概不负责。

阅读全文 »