#include #include #include #include using namespace std; typedef pair <double, int> dpr; const int maxn = 30009; const int maxl = 15; const int max_buf = maxn * maxl * 2; const double eps = 1e-7; const double finf = 1e20; int ibuf_arr[max_buf], *ibuf; double fbuf_arr[max_buf], *fbuf; struct edge { int t; edge *next; }; struct line { double k, b; inline double xCross(const line& a) { return (a. b - b) / (k - a....
自己出的题还要写题解。 就是化成可以二分的形式，然后发现是找凸壳上x=x0的时候的最大值的和，看它是否大于0。 于是就写呗。据说很难写。我觉得写起来还行啊。 其实主要是为了测试系统用的。
#include #include #include #include using namespace std; const int maxn = 100009; const int maxl = 19; typedef struct node { int t; node *next; } edge; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { sz += a....
<div class="post_brief"><p> 这回我是出题人。第一次出给这么多人做。</p> 好像是一个很有意思的故事。我猜看到的人会喷死我。不过反正已经身败名裂了。大概我能作为bc史上最逗逼的出题人被记录下来了。 还是记下来这个悲伤的故事吧。也许未来某天还可以愉快地回忆一下。 要从去年12月强行退役开始说。当时觉得生活太无聊了于是yy了四道题去找bestcoder。当时的四道题分别是高精加，现在的第三题数据弱化版，一道灭绝树的裸题，一道动态dfs序。然后审了一下说我题太难了。于是把灭绝树扔了把第三题换成第二题，把第二题改成单峰序列这个坑题。然后听说可以出数据了。 退役的日子，时间也不多，于是拖到wc之前才在宾馆里把数据出出来了。发过去了。然后让我等一个月。 于是就等到开学了。周二晚上快睡觉的时候，qq上发来消息说，“下周用你的题”。于是我就被拉进了一个验题组。 有人对我说：1001高精，即使b进制也可以强行用java水的。于是开始郁闷了。因为早上要考试所以比他们都睡得早，当然比平时睡得晚很多。比较开心的是某君说了一句“高中生的数据结构都好强”。 第二天早上起来，发现他们说1004在bzoj上有原题，我还是它的弱化版。那题我都没仔细看完过题啊- -b。不开心了。那既然是原题就得换。于是与某队友一起yy良久出了一道d。后来事实证明这是个悲剧。下午把题给验题组看，说是可以。于是去写std，造数据，不亦乐乎。最后发现std因为复杂度太高，所以得把数据出弱，会不会给暴力？不管嘛。扔hdoj服务器上好像还挺快的样子。然后就因为精度误差对拍出各种错。好郁闷。然后想起还有一套给高一的题？熬夜把数据造了。 第三天早上起来，看到有人说第三题数据范围可以加到30，用分两半的方法。想想的确可以。于是就去写了个分两半的东西。然后悲伤地发现已经搞忘之前的datamaker的参数是怎么设计的了。于是随便传了几个参数进去，发现能造出无解的数据。那就这样呗。然后发现第一题可以改一改让高精板废掉。于是就去改了呗。然后晚上的时候第三题又挑出bug了。用c++能过，而用g++怎么都是wa。去找了个cena的g++之后发现还真wa了。然后觉得大概那个方法是错的吧。于是先把数据范围改回16好喽。又是十二点。 第四天早上考试脑子都不清醒了。犯了一堆逗逼错自坑110分。感觉不太好。下午的时候看到有人批斗了我的1003，原来是我排序的关键字搞错了。又改回来吧。然后又有人提醒我1004可以用分数。赶紧改。晚上感觉好累。去跑了3000之后好了一些。 第五天也就是今天了。怎么感觉像是审判一样。早上很晚才起。然后就发现有人又告诉我1004的精度还是不够。然后提出可以换他的1004。决定任性一把，自立deadline。最后提出的解决方案是提高std的精度，同时把数据范围从1e6降到1e3。拍了上万组之后觉得无误了。虽然最后还是徒劳。 下午的时候传来消息说给高一出的数据里三道有两道有问题。不是个好兆头啊。 晚上比赛前怎么觉得比做题还紧张。从开始到等来第一个submission的五分钟感觉是我人生中最慢的五分钟了。 还好1001有人过了。然后1002有人过了。至少这两个题是没有事了。（其实有）然后发现1003怎么前几次都在wa？看看怎么都写的dfs！？然后居然有dfs就过了。郁闷ing。 然后另一项工作是答疑。有人说我中文第二题到底是两个都要满足还是只满足一个？根本没看想了一想说只要满足一个。我想成只要是峰或者谷就行了。然后还顺便发了一发通知。几分钟过后才意识过来发错了赶紧改。据说这一下坑了很多人。 然后就渐渐有人过题了。感觉1003数据给水了啊。好像还真是水。看来没有成功理解当时写的datamaker。 直到结束也没有人交最后一题。虽然听zhx说有人在写。 然后，code time结束。hack开始。然后服务器就崩了。之后的20多分钟没有成功打开网站。看到不同的群里吐槽颇多。 然后再打开网页的时候已经完了。好像很惨的样子。 然后有人开始说数据水了。第二题只有一组1 1，没有成功卡掉忘减1的人。第三题what鬼，暴力随便过。 好吧是疏忽了。 所以就身败名裂了呗。 估计当初想骗些出题费也是无望了。 估计不久之后出去的时候还会被狂吐槽。 所以说毕竟我还是太弱了。还是好好刷题去吧。不要天天想着骗钱。
<div class="post_brief"><p> 今天是强行把270吃成了160。</p> 第一题，水水的单调性。然后就以为只有小写字母。想想能得20分真是神奇。 第二题不是个暴搜题嘛。加个最优性剪枝就能过。然后就没有注意到顺子的长度是不小于5而不是等于5。再见。 第三题满分做法没看懂。自己想出来的dfs能过70分。然后就判素数的时候强行int了。不开心啊。 所以今天是太粗心了。也许昨天晚上睡眠不足也有关系吧。 毕竟我太弱了。
<div class="post_brief"><p> 题目名字好长。</p> 当年在考场上只会分块打表的题。 前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。 于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。 考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久） 然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。 然后还是没有原版跑得快。OTL。 #define PROC "shop" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 53; const int maxm = 509; const int mb = 253; dint l, r; int n, m, bs, a[maxn];...
<div class="post_brief"><p> 在一道usaco的题上wa了三次。我也是厉害。</p> 其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。 对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。 于是就是拿俩树状数组扫四遍就行了。 #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; struct point { int x, y, i; point() { x = -inf, y = -1; } point(int xo, int yo) { x = xo, y = yo; } inline void init(int ix) { scanf("%d%d", &x, &y); i = ix; } }; inline bool operator <(const point& a, const point& b) { return (a....
<div class="post_brief"><p> 继续傻。</p> 早上考试。因为事情比较多所以有些心不在焉。 第一题似乎很水？直接线段树搞定。拍都没拍。然后似乎有一堆人理解错题意了。 第二题是个最大权闭合子图一类的东西。前几天做过小m的作物，所以很快就反应出了建图的方法。 第三题是个数学题。打了几个小数据在oeis上找到了通项。不过这种行为搞出来的公式显然是不能拿出来用的。其实我也没细看。然后在各种郁闷下想了一会没想对，于是就交了个30分的暴力。 然后他们都把前两题中的至少一题写挂了。然后他们第三题都比我高。所以我还是太弱了。 然后花了这一天中剩下的所有时间来出题。 原来出题是这么郁闷的一件事情，尤其是出的题会涉及到很多的利益关系的时候。 感觉今天也没做什么。是我的效率太低了吧。
<div class="post_brief"><p> 今天比较傻嘛。写了个奇怪的东西还自以为能AK。</p> 第一题明明已经想到正确的结论了，然后又觉得它不太靠谱，于是就没敢写。晕。 第二题原题，虽然已经快忘了。 第三题原题。当年不太会，不过现在想一想就会了。然后他们暴力就过了，不开心。反正写线段树保不TLE，虽然考场上幸好随便对拍了一发不然就惨了。 下午讲课让我觉得有必要去补一些最近scoi的题。 所以我还是太弱了。
<div class="post_brief"><p> 晚上在家效率好低啊。什么都不想干。</p> 于是今天考试还是死得挺惨。 第一题没想。然后乱写得了20分。居然能得20分。然后正解比较神奇的感觉，虽然抄了一遍但是还是没有很好地理解跳的那一步。 第二题想了很久才发现比较简单。之前想复杂了。其实转到值域上之后就会好做许多。 第三题水水水水水水水水水水。然后题意。什么鬼。 所以我还是太弱啦。这个样子怎么省选TT。