- 博客(23)
- 收藏
- 关注
RSS订阅
原创 WC2019 酱油记
Day 0早上六点四十五起床去赶火车，坐了一上午+一中午的高铁终于到广州南站了，而且因为没准备车上的午餐饿的两眼发绿，一下车就吃了个肯德基。然后在大巴上颠簸了一个小时到了广州二中。路上还吃了把鸡。来宿舍后和其他湖北OIer面基，发现大家长得都很帅都很成熟，除了xqy还是个孩子的模样。其他人都是第一次见面，还记不住长相，同寝室有一个华一的，也记不住长相。晚上在学校食堂吃，觉得炸鱼块很好吃，...
2019-01-24 20:11:18
538
3
原创 NOIP2018酱油记
第一次写酱油记好激动哦～Day -365一年前的 NOIP2017 我爆零了QWQ但是人家只会 DFS，能指望个啥嘛～Day -10今天打 slay.one 的时候偶遇 WGSZ 的 Edgration 大佬，然后切磋了几把技术，加了 QQ话说 Edgration 在今年九月份来过我的 QQ 空间，可能是因为我们都在 NOI2018 HB 交流群吧 233（不过我们都是...
2018-11-11 19:07:00
212
原创 CF 1039D You Are Given a Tree && CF1059E Split the Tree 的贪心解法
CF 1039D You Are Given a Tree && CF1059E Split the Tree 的贪心解法 1039D 题意：给你一棵树，要求对给定链长于 k = 1, 2, 3, ..., n，求出最大的链剖分。1059E 题意：给你一棵带权树，要求对于一组给定的 L, W 求出最小完全竖链...
2018-10-11 20:15:00
153
原创 最大异或子序列问题
问题是这样的：给定一个整数序列，要求出其最大异或子序列受到最大和子序列的启发，我首先就尝试 DP然而 WA 掉了。。。很明显，这个问题没有最优子结构异或可以抵消，因此最大的可以抵消成最小的，非常不好 :(然后我尝试贪心先给数字排序，然后从大到小选取使当前答案变大的加入进去也 WA 掉了 :(很显然，每次我们都是取到第 i 位为 1 的最大的数字这样能保证答案...
2018-09-12 23:38:00
1572
原创 UVa 10615 - Rooks
这题我想了两个小时却没有发现要做 K 次匹配。。。我好笨啊。。。不过即使想到了要做 K 次匹配，我也想不到要加边加边的充分性是很好证明的（用 Hall 定理）但是为什么直接算 K 次最大匹配就不对了呢？我先交了一份不加边的代码，并且用 assert 做一遍检查果然就 RE 了边没有被匹配完为啥呢？有反例吗？有！hack 数据：**..** （为了...
2018-09-07 22:59:00
117
原创 UVa 1057 - Routing
先声明一下：这篇题解纯粹是对原题解的翻译与修复，并非原创。解法是 DP + 最短路。这个思想并不是很少见，而这题强化了 DP 的思维难度。设 f[i][j] 为 1~i，2~j 所经过的点数最少的路径的点数（考虑了重复点）。给出转移方程：f[i2][j] = min(f[i][j] + [i2 != j] | g[i][i2] = 1)f[i][j2] = min(f[i][j...
2018-09-04 20:21:00
265
原创 用树状数组代替平衡树
那天我在做 USACO 的某道题的时候突发奇想用树状数组代替平衡树（但是这似乎不是我首创的 idea）（不过貌似用的人很少）大体做法就是靠二分+树状数组，单次操作复杂度 \( O( log^2 n ) \)虽然复杂度比 Treap 高了一点，但是代码短呀！（但是我不打算贴代码了 QWQ 因为我懒）对于不超过 \( 10^5 \) 的长度还是很轻松的时间宽松的话 \( 5...
2018-08-17 18:09:00
393
原创 [CTSC2008]图腾totem
（图腾这题做的我头疼 233）记 f(xxxx) 为 xxxx 出现的次数，那么题目就是要求 f(1324) - f(1243) - f(1432)最有难度的是把上面的式子转化一下，变成 f(1x2x) - f(14xx) - f(12xx) + f(1234)这点除非对 f 的求法能一眼看出来，否则很难想到后两个比较简单一点f(1234) 可以想到用动规求具体来讲，设 d...
2018-07-13 12:40:00
209
原创 POI2009 题解
POI2009 完结撒花！Kam为了满足题目条件，我们可以做差分把差分后的序列当作石子堆，这样原序列中拿走一颗石子相当于差分序列里把一颗石子推到后面一堆去那么就是阶梯博弈了（阶梯博弈就是谁先把石子全部推下去谁赢）阶梯博弈的策略是：先手若把偶数堆的石子推到奇数堆，后手就把这些石子推到下一个偶数堆（这样奇数堆状态不会变） 先手若把奇数堆的石子推到偶数堆，这时根据 SG 函...
2018-07-11 17:51:00
242
原创 POI2008 题解
POI2008 完结(´･_･`)撒花！海报PLA单调栈裸题！激光发射器SZK光路可逆？然后证一下发射器与接收器两两对应？砖块Klo区间中值！可用树状数组水过。。。将高度 \( h \) 的值域作为树状数组维护的序列，维护一下前缀数量与前缀和即可。BLO求割点裸题！Staso easy 的树上DP！CLO蜜汁构造。。。Tro草稿题...
2018-07-07 17:05:00
105
原创 POI2007 题解
POI2007 完结撒花！旅游景点atr很简单的一道 dp 题，不说了。有意思的是官网上的标程把空间复杂度压成了 \( 2^k \)，而我不知道这是怎么搞的，所以官网上提交会 \( MLE \)办公楼biu很容易想到求补图的联通块，然后随便敲了个 \( BFS \)，果断 \( WA \) 考虑用并查集把相同联通块的点圈起来，类似缩点的思想，这样一边枚举点一边减少点，可以卡着过...
2018-07-04 22:33:00
183
原创 BZOJ 1080: [SCOI2008]劣质编码
这题我会暴力。。。如果时限 1e9 的话就可以 AC 啦这题 clj 也会暴力。。。然后他就秒切了。。。（果然是蒟蒻 vs 大神）大神的暴力简直不可用语言来描述了。。。#include <bits/stdc++.h>using namespace std;const int N = 55;string str[N];int n;vector<int...
2018-06-30 20:25:00
136
原创 BZOJ 1018: [SHOI2008]堵塞的交通traffic
正解是线段树。。。可惜我不会这么高级的操作。。。（实际上是我抄学长的代码，结果TLE了）然后过了一个月，在CF上学到了rollback 这种灵活处理动态图的方法，于是就秒了。简单来说 rollback 就是暴力记录每个变量过去的值，就可以随时退回到原来的某个状态了。当然必须要求每次对变量的修改要少，至于少多少得看题目，并查集几乎是常数，所以最后的复杂度接近线性。非常劲。下面...
2018-06-30 20:23:00
96
原创 BZOJ 2125: 最短路
这是仙人掌第二题。正解是用圆方树，没毛病。然后为了表示我没有无脑抄答案，就敲了一份暴力的，调试两个多小时后光荣TLE（但是在学校的OJ上AC了，难道是BZOJ的CPU真的是来自上个世纪？）在写暴力的时候我就觉得圆方树真是个好东西。首先可以方便的确定LCA所在的环，这样两个后代往上跳就很有目的性。暴力的话得分一堆情况，非常的没有美感。其次可以方便的记录每个环的相关信息。如果是暴力的话是没有很...
2018-06-15 19:21:00
174
原创 BZOJ 1022: [SHOI2008]小约翰的游戏John Nim游戏简要笔记
按照现在的OI科技发达程度，这题只能当作NOIP普及组考考了。很简单的Nim游戏模板题，但是仍然需要知道Nim游戏的策略，否则无法想象怎样在考试的时候自己YY出正解来（也可能是本蒟蒻理解不了大佬们的思维吧^_^）基础的Nim游戏分两种，一种是拿到最后一颗石子的人赢，另一种就是拿到最后一颗石子的人输。Nim的策略是这样的：先手要让自己行动后每一堆石子大小的异或和为0。怎样保证下一步的...
2018-06-13 10:06:00
103
原创 BZOJ 1019: [SHOI2008]汉诺塔 简要证明
先安利一发Sengxian的题解。我看了好几篇博客，几乎就两种做法：一种是跟Sengxian的做法类似的或一样的，用递推关系求^o^另一种比较玄学的是猜通项公式(￣▽￣)（其实是待定系数啦）当然我比较喜欢递推的做法，毕竟通项公式不好证明正确性（也可能是我没有多想想(´▽｀)）这里先多扯一句，汉诺塔又叫河内塔，而河内是越南首都，然而河内塔问题源于一个印度传说(´･_･`)这篇文章就是...
2018-06-12 13:43:00
122
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人