Views

<div class="post_brief"><p> 毕竟uoj还是缺人么，比赛比较稀疏。</p>   然后觉得我在这种智商向的题面前无力了。   第一题， 一看，不就是a[i]*(26n-1)=26*h[i]-h[i+1]么，水，敲。然后就没有考虑到26n-1≡0(mod p)的情况。于是gg。   第二题，居然是构造矩阵的题？首先我连基尔霍夫矩阵都要忘了。手推了一下发现消元消出来不对？原来是这一行的系数不能变。晕。然后就这样也只会暴力枚举图。20分走人。   第三题，似乎见过？不对啊，只见过完全图的解法。好像有10分。随手写一个吧。怎么今天三道题都有modPow。不管了弃疗。   结局是50+10+20=80=一个很惨的rank。所以我还是太弱啊。   昨天打球的时候，教练说，这一年我打球就像在赶场，没有找到自己的节奏。想想，不只是打球吧。很多时候都是在被拖着走，很没有目标感。不知道自己要去哪里，也不知道怎么去。似乎好像也做了规划，不过也没有真正去实现。到底是世界太复杂，还是我太简单？   不论如何，既然选择了自己的路，那爬也要爬完。

<div class="post_brief"><p> 插头dp的练手题么。虽然之前还没写过哈密顿回路的题。</p>   学习了一下广义括号法。发现状态数比之前记连通性的方法要少。仔细想想发现，两个连通的插头的顺序有关。不能存在1212这种东西。所以连通性的方法记了很多废状态。那把连通性方法改进一下会不会变得更快呢？可以研究一下。我觉得应该是等效了吧。   今天的debug时间明显缩短了。虽然还是debug了老半天。然后怎么代码还是那么长。想起我每次都觉得把东西挤到一起看起来很不雅观，于是去写一堆找转移的函数。晕。   #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 = 15; const int maxst = 50009; #define mbit(x,y) ((x)<<((y)<<1)) #define gbit(x,y) (((x)>>((y)<<1))&3) #define cbit(x,y) ((x)&(~(3<<((y)<<1)))) int n, m, tots, slst[maxst]; bool mp[maxn][maxn]; dint f[2][maxst]; void dfsState(int l, int c, int z) { if (l == m + 1) { if (!...

<div class="post_brief"><p> orz mhy。看mhy的刷题记录成为了我成天的刷题方向了。</p>   其实最初也没有想清楚。然后看了一眼mhy写的题解写了凸壳，秒懂。   二分一个答案，设它是ans。如果ans≥realAns的话，那么就会存在yi-ans*xi+qj-ans*pj≥0。然后i和j就分开了。于是变成了求一条路径上yi-ans*xi的最大值。把xi看作k，把yi看作b，就变成半平面交了。于是开归并式线段树把凸壳给记录下来就好了。然后复杂度大约是单次询问O(lg3(n))的？链剖后每棵树单独建树，然后复杂度我就不会算了TT。   于是就硬着头皮写了，然后发现跑得还挺快。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 30009; const int maxl = 15; const int max_buf = maxn * maxl * 2; const double eps = 1e-6; const double finf = 1e10; int ibuf_arr[max_buf], *ibuf(ibuf_arr); double fbuf_arr[max_buf], *fbuf(fbuf_arr); struct edge { int t; edge *next; }; struct line { double k, b; inline double xCross(const line& a) { return (a....

<div class="post_brief"><p> 这么水的题居然还要写题解。要不要说我写了半个下午+半个晚上。</p>   丧心病狂想写一发zkw去抢速度rank。然后发现zkw怎么支持区间修改查询TT。课件根本没讲懂。而且max怎么区间加。   想了很久终于想出了来了。然后交上去发现常数巨大比普通线段树还要慢TT。到头来想想如果我直接写普通线段树说不定十多分钟就能过，而且代码量还会小一些。因为那个是可以直接通用的，但是这个比较麻烦。   其实写这个就题解就是想记录一下我yy出来的zkw区间修改区间查询的方法。   这道题是区间查询最大值+区间修改。如果是写一般的线段树，需要记录两个值a和v（至于为啥我用了这俩神奇的字母我也不知道），分别表示当前区间被完整覆盖的修改的最大值（又称lazy标记）和当前区间的最大值。然后所以zkw也要记这两个东西。   如果我们把zkw看作一棵树，那么每次修改和询问操作的时候都是对一些线段的a和v进行操作。（废话）   首先考虑修改。zkw经典的变为开区间取中间能处理a值的改变，但是不能处理v值的改变。因为v值改变的线段不一定会被当前区间包含。然后仔细考虑发现a值没有变但是v值变了的点只可能存在于两个端点到根的路径上。那就直接强行更新一发就好了啊。然后更新的区域就变成了一个有点像倒置漏斗的形状。   再考虑询问。a要覆盖当前区间，v要被当前区间覆盖。那不就是修改把a和v的做法反一下么。   然后好像也不是很麻烦的样子哈。   然后常数很大哈。   那还拿zkw做何用。   晕。   #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4567; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!...

<div class="post_brief"><p> 居然网上都没有找到程序来和我拍。好吧其实它是一道权限题而且过的人也不多。</p>   其实就是裸的插头DP。本来想学一下广义括号的然后被状态数吓到了于是只好还是写最小表示。连通性。   然后我发现最小表示连通性很容易写挂。而在findstate的时候检查一下是个不错的办法。至少这道题靠这个就可以直接debug出来问题了。   比上次写插头要好许多了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) #define mbit(x,y) ((_l x)<<((y)<<2)) #define gbit(x,y) (((x)>>((y)<<2))&0xf) const int maxn = 13; const int maxst = 570009; dint slst[maxst]; int n, m, v[maxn][maxn], tots, f[2][maxst], cnt[17]; bool av[2][maxst]; void dfsState(int l, int tot, dint z) { if (l == m) { for (int i = 1; i <= tot; ++ i) if (cnt[i] !...

<div class="post_brief"><p> 计算几何题。别人都用simpson搞。然后我决定不水一发，用hwd神犇在wc上讲的关键点法做。</p>   然后就搞到了12点半。发现坑数次。还专门用js写了个画圆的。当然我现在知道怎么画圆了。过两天去把oj7的统计图改一改。   思路是把所有圆的左右端点和所有圆的两两交的x提出来，unique一发（不然会tle显然的）。这样两个x之间的部分的圆弧是不会有交的。那么就可以视为一堆弓形和梯形了。然后扫描一下中位线的有效长度算梯形。每次新进入一个连通区域和出来的时候加相应弓形的面积。   需要注意按y排序的时候是按弓形与竖线的交点的y，而不是梯形的y，否则会有非常神奇的精度误差。另外算弓形面积必需要用反三角函数（至少我没研究出怎么不用）。如果用acos的话会暴精度暴得很惨。要用atan2来提高精度。   然后这样写连样例都会tle。仔细感受一下发现好像如果有一堆同心圆的话都会tle。然后考虑去掉包含的圆之后似乎就快了。然后就交了，然后居然跑过了。   然后来欣赏一下我的时间巨大，空间巨大，长度巨大。挤在一堆simpson里显得特别郁闷的代码。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const double eps = 1e-8; const double pi = acos(-1); inline int sgn(double x) { return (x > eps) - (x < -eps); } inline double sqr(double x) { return x * x; } typedef struct geo_obj { double x, y; geo_obj() {} geo_obj(double xo, double yo) { x = xo, y = yo; } inline void read() { scanf("%lf%lf", &x, &y); } inline geo_obj vertical() { return geo_obj(-y, x); } inline double len() { return sqrt(sqr(x) + sqr(y)); } } point, vect; inline geo_obj operator +(const geo_obj& a, const geo_obj& b) { return geo_obj(a....

<div class="post_brief"><p> 严重地被虐了。</p>   今天考试=一道奇怪题+一道普及题+一道无脑题。然后就挂了。   第一题直接就想到了上次的变异最小圆覆盖。然后那道题没有过。然后这道题也比较神奇。感觉是可以用那个题的方法搞的。不过粘过来std居然错了。无语。然后居然放过了很逗的写法。更无语。   第二题也比较无语。普及组题。   第三题想一想就知道只要贪心就完了。然后边权是可以为0的于是WA傻了。完全是自己加了一句没有用的话结果就100变60了。   所以我还是太弱了。

<div class="post_brief"><p> 比较神奇的数学题。首先你要知道这个函数的意思是把它的二进制flip。至于怎么来的我也是听说的。然后推一下发现的确是这么回事。</p>   于是就变成数位dp了。然后我发现数位dp常常可以用奇奇怪怪的方法水过去。然后又发现数组从0开始标号也会造成麻烦。+1-1啥的最讨厌了。   于是这题就变成高精度练习题了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 409; struct BigInt { int l, a[maxn], base; BigInt(int b = 10) { l = 0; base = b; } void push() { for (int i = 0; i < l - 1; ++ i) { a[i + 1] += a[i] / base; a[i] %= base; } for (; a[l - 1] >= base; ++ l) { a[l] = a[l - 1] / base; a[l - 1] %= base; } } void pull() { for (; l && !...

<div class="post_brief"><p> 第六百道题一定要不水！虽然离第一页还有几十道题的距离。</p>   很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦，更不要说这个了。   现在想想还行，因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的，那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来，其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量，写起来也比较明了。虽然还是比mhy长。   然后因为我在最后一步dp的时候写了一个static的f数组，所以光荣了。debug了好久。晕。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, av; edge *next, *rv; }; struct ball { int l, *a, h; }; const int maxn = 50009; const int maxm = 200009; const int maxarr = 400009; int n, m, cb, fb[maxn], d[maxn]; int f[maxn], ans, fd[maxn], fe[maxn]; int stc[maxn], tst; int ibuf_arr[maxarr], *ibuf(ibuf_arr); bool vis[maxn]; edge elst[maxm], *ep(elst), *head[maxn]; ball b[maxm];...

<div class="post_brief"><p> 最初感觉好多状态怎么做。</p>   然后发现（其实是瞟了一下题解）如果把一个数分成2a*3b*c，那么c只影响上界。2a*3b中a最大是16，b最大是10，列一张17*11的表出来，然后发现右下方还有很多空东西。于是直接像插头一样状压一下轮廓线呗。反正对一个数有影响的只有它的上面和左边。最近写插头写得有点疯啊。其实它的很多思想都是可以推广出来用的。比如最小表示啥的。   于是如果直接这样写的话大概要跑30000多次dp，还是比较悬。然后再想想发现只有表里能取的数的形状发生改变的时候才会改变dp的答案。表里面的数很少所以改变次数也应该很少。所以记一下上一次的形状是什么然后比较相不相同，相同就直接沿用。   然后跑得飞快。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) #define pow2(x) (1<<(x)) const int maxn = 19; const int maxm = 15; const int maxv = 100000; const int maxst = pow2(11) + 9; const int mod = 1e9 + 1; int f[2][maxst], vl[maxn][maxm], n, m, v; int dis[maxn], ldis[maxn], lans, ans; void pre() { for (int i = 0; i < maxn; ++ i) { vl[i][0] = (1 << i); if (vl[i][0] > maxv) vl[i][0] = -1; for (int j = 1; j < maxm; ++ j) if (vl[i][j - 1] > -1) { vl[i][j] = vl[i][j - 1] * 3; if (vl[i][j] > maxv) vl[i][j] = -1; } else vl[i][j] = -1; } }...