laekov

BZOJ2693 jzptab

多组询问,硬根号。yy了一下午,在去80MSWC的时候的病历上打了若干草稿,最后硬yy出来了。


其实拿LaTeX来当公式编辑器蛮好的。


然后d(a)函数可以线性筛,讨论一下是不是倍数就行了。


发现数论真的好神奇。


lofter的html源码好讨厌啊。


#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define _l (long long int)
 
const int maxn = 10000009;...

BZOJ2709 [Violet 1]迷宫花园

水水的二分+最短路么?


然后读入坑死了检查了好久的最短路。


没救了。


然后发现我好像进前100了,小小地开心一下。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef pair <double, int> dpr;


struct edge {

int v, t;

edge *next;

};


#define nid(_x_,_y_) ((_x_-1)*m+(_y_...

BZOJ1273 [BeiJingWc2008]序列

逃掉数学考试。感觉解几纯粹不给人希望。


这题还是比较有意思。做法是把每位分开预处当总共加了多少的时候这一位上是1的数字有多少个。然后每一层是线性的。询问是O(1)的。


然后发现自己的代码能力已经没救了。


#include <cstdio>

#include <cstring>


#define pow2(x) (1<<(x))


typedef long long dint;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "...

20150116

感觉自己坚持不下去了。


现在真不知道为什么要回去上课。好多次想跑掉然后还是没有跑。毕竟还是,唉。


物理十分钟够我想一道选择题还多半是错的。化学生物英语啥的基本就是不会。zhx告诉我回去可以拿数学RANK1然后发现解析根本做不了。想起初中的时候很自豪地认为我的解析几何很厉害。现在才学会做人。


上课还是那种走神的样子。也没有想OI的题,也不想听课。不知不觉就跑掉了。最后只有利用上课的时间做作业。然后,不会,不开心,担惊受怕。


每天唯一的娱乐就是晚上去码一下OJ。然后发现我的东西写得太丑,如果数据量一大根本就handle不了。当初做的时候也是边做边改,好多东西根本就不科学。但...

BZOJ2393 Cirno的完美算数教室

充分证明我已经学傻了。把ONLINE_JUDGE打成ONLINE_JUGE还WA了若干次。然后开了个10^10的数组直接CE还想了好久是怎么回事。


10^10大概会TLE,真正的数据大概只有10^9。


做法比较简单直接容斥+剪枝,反正凑起来的几个数不会很多。


#ifndef ONLINE_JUGE


#include <cstdio>

#include <algorithm>


using namespace std;


typedef long long dint;


#ifdef WIN32

#define lld...

BZOJ2813 奇妙的Fibonacci

的确比较奇妙。


有一个奇妙的玩意是fib[gcd(i, j)] == gcd(fib[i], fib[j])。(fib[1] = fib[2] = 1)


然后就比较可搞了。


线性筛处理每个数的因子个数和因子和。开一点变量然后推一下就出来了。


然后要注意fib[2]也可以整除所有奇数,包括1。表示在这上面坑了2次提交。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


#define...

BZOJ3522 [Poi2014]Hotel

水水的dp。拿pascal玩玩边表。然后莫名其妙地发现在main上先是ce然后全wa。下到数据一测就过了,交bzoj还是过了。不开心。


必定是一个中间点然后连三条出去。所以直接枚举中间点然后bfs就好了。相当于每条边被转移了两次所以还是O(n^2)的。最初想错了想成三方了把自己吓了一跳。


pascal啊。


type

edge = ^edger;

edger = record

t: longint;

next: edge;

end;


const

maxn = 5009;

//ONLINE_JUDGE = false;

ONLINE_JUDGE =...

BZOJ3851 2048

题号是3851,题目名称是2048。


比较厉害的DP。最初没有想到怎么表示状态。其实就是一个≤2048的自然数就可以表示状态了。


然后转移不能一个一个来,每个值要一起来, 然后拿组合数来算。然后就行了。


虽然hdu上还是过不到。好慢的说。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


#define _l (long long int)


const int maxn = 100009;

const...

BZOJ2527 [Poi2011]Meteors

全局二分+树状数组,其实还是比较水。


比较坑的一点是直接求和会暴long long。如果≥Pi了要直接break掉。好坑啊。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std; 


int _d_;

#define readInt(_x_) { \

int& _s_ = (_x_ = 0); \

while...

BZOJ1112 [POI2008]砖块

水一发。


本来可以直接拿主席树找中位数的,但是因为main上只有32MB,所以只好写了个splay。感觉现在是爱上指针了。然后kth的时候少打个等号又wa又re好爽。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef long long dint;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"...

BZOJ1097 [POI2007]旅游景点

比较简单易懂的状压。


最初想懒一下把起点和终点也压进来然后发现刚好会超一点空间。然后不压进来的话就是100MB左右,很好奇MAIN上面64MB的内存应该怎么做。拿MAP么?


代码各种难看啊郁闷。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


struct edge {

int t, v;

edge *next;

};


#define pow2(x) (1<<(x))


typedef...

BZOJ3858 Number Transformation

yy了一个sqrt的玩意,不过因为n在变所以没有保障啊。


肯定不是正解了。


1s的题跑了1.3s居然AC,好厉害。


#include <cstdio>


typedef long long dint;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif


dint calc(dint n, dint k) {

if (n <= 1)

return k;

for (dint i = 1, j; i...

BZOJ2870 最长道路

最初觉得挺麻烦的一道题没思路。有点像并查集直接搞但是不好维护直径。


然后发现树上到任意一点的最远点一定是直径的两个端点之一。于是直接把直径是哪俩点记下来就好了。然后按点权从大到小往树里插。


然后莫名其妙地抢到了第二快。这么老的题也是蛮欣慰的。大概是读入优化2333


#include <bits/stdc++.h>


using namespace std;


void setRand() {

FILE* pf = fopen(".rs", "r");

int hsv;

if (pf) ...

BZOJ3834 [Poi2014]Solar Panels

orz jason_yu提醒了我一句“最简单的优化”,才想起来。


如果d合法的话那么b/d-(a-1)/d>0。然后用整除优化到sqrt就可过。虽然比较慢。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


int main() {

int t, a, b, c, d, s, e;

scanf("%d", &t);

while (t --) {...

BZOJ3829 [Poi2014]FarmCraft

树型贪心orz


写丑了。调了半个晚上,然后发现是起点最耗时的时候的情况搞错了,只用走n-1条路而不是n条。晕。


对于每个节点贪心按f[p]-2*sz[p]排序或者用原式也行。不过巨慢。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


int _d_; 

#define readInt(_x_) { \

int& _s_ = ...

BZOJ3831 [Poi2014]Little Bird

一血yeah yeah。


第一眼觉得是比较麻烦的单调队列。


然后发现转移的时候只会加1或者不加。


那么取的时候只用取队首,队里首先fi单不降然后hi单减。那么一定没有方案比取队首差。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


int _d_; 

#define readInt(_x_) { \

int& _s_ =...

BZOJ3401 [Usaco2009 Mar]Look Up 仰望

签到题。表示今天虽然废了一天但是还是坚持写了题的。


单调栈搞定。


因为打球把小指头打残了所以不想敲include所以写了pascal,然后发现include不用小指。


const

maxn = 100009;


var

n, i, t: longint;

a, st, ans: array[0 .. maxn] of longint;


begin

readln(n);

for i := 1 to n do

readln(a[i]);

t := 0;

for i := n downto 1 do begin

while (t > 0)...

BZOJ3825 [Usaco2014 Nov]Marathon

英语阅读题。做完去翻译题面然后写英语作业了。


就维护一下区间里的距离和and忽略一个点的收益的最大值。完了。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


struct seg {

int l, r;

int s, v;

seg *ls, *rs;

};


const int maxn = 100009;


int n, m, x[maxn], y[maxn], d[maxn], v[maxn]...

BZOJ3826 [Usaco2014 Nov]Cow Jog

新题么。略水。


就一个序列,如果起点单增的话只要终点单增就不会冲突。


然后最少单增子序列覆盖=最长不降子序。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef long long dint;


#define _l (long long int)


const int maxn = 100009;


int n, m, a[maxn], t[maxn], s;

dint v[maxn],...

20150101

2015,嗯,还习惯性地敲2014。一年就过去了,好快。


2014年1月1号已经是一年前的事情了,略恐怖。


感觉不只过了一年啊。


这一年我都在干啥?


寒假的时候去wc打个酱油,骗分的结果还不错。然后感觉讲课完全像在冬眠。好多课根本听不懂没法听。是我太弱吧。


开学之后就一直在教室和机房两边跑。对省队还怀有一丝幻想。直到,见到省选题。然后就以能拿的分没拿到不能拿的分也没拿到的分再见了。当时安慰自己太年轻,现在想来,也真是。


然后看到学长们填thu的自招表,也去跟着填了一个表。然后,当然肯定被毫无疑问地打了回来。令人触目惊心的是要填各次大考的成绩。半期缺考+垫底的...

BZOJ3301 [USACO2011 Feb] Cow Line

新年第一题哈哈。虽然没有成功拿到fb。


所谓阶乘进制数么。略水。只不过加一减一啥的得小心些。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef long long dint;


#define pow2(x) (1<<(x))

#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"...

BZOJ3823 定情信物

解锁成就:半夜过题。(其实是因为在搞bsd)


仔细看下题推一下发现第n维中m维元素的个数为2^(n-m)*C(n,m)。


然后组合数好像得nlogn用逆元?恭喜tle。


然后yy了一个用线性筛的办法,只是素数用快速幂,这样大约可以降低复杂度,然后就能过了。好神奇。


代码好长TT。


#include <cstdio>

#include <cstring>


#define _l (long long int)


const int maxn = 10000009;


int tp, pn[maxn], inv[maxn...

BZOJ1367 [Baltic2004]sequence

退役了之后智商下降严重啊。今天bc死惨了。这比较水的题也是去看了题解才反应过来的。


先把序列改成不降。


然后把原来的序列分成一些段,每段的中位数递增。


  考虑新加入一个ai,如果它比前一段的中位数小,那么就把它和前一段合并,再拿合并之后的段去和再前一段比较一下。其实我也不能证明为啥是这样,只是感觉比较有道理。我肯定是没救了。


中位数的话用可合并的堆来维护比较方便。orz各种神级堆,然后我还是用的左偏树。


以后树要拿指针写所以代码巨长。


#include <cstdio>

#include <cctype>

#...

BZOJ1171 大sz的游戏

大概是今天不宜刷题来着。应该好好做作业。


用线段树套单调队列可以把复杂度降到O(nlogn)。然后deque严重不靠谱,得用list才行。


然后还是跑得巨慢。前面的人是排序搞定的么?表示不明觉厉。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <deque>

#include <list>

#include <algorithm>


using namespace std;


int _d_;

#define...

BZOJ3821 玄学

zhx+主席出的题,恐怖至极。


写此题需要极高的常数优化技巧+耐心。


本地跑到50s才在bzoj上压80s跑过。


其实思路就是拿线段树套AVL把询问的时间复杂度优化到O(logn)。


然后首先用treap会t爽+mle爽。


然后avl需要各种常数优化。


然后要在xxxxx地方优化。


加上zhx牌读入优化+块状内存+抄std的AVL+.....终于在81s过了。


orz比我快一倍的wangyisong神犇。


#include <cstdio>

#include <cstdlib>

#include <cctype...

BZOJ2738 矩阵乘法

全局二分的经典题。


最初试图用持久化线段树和分块,然后欢快地tle+mle了。看到jason_yu和mhy过了,只能说自己的常数优化还不过关啊。


第一次写这种二分。就是把所有东西扔进来快速排序,顺便考虑每个询问应该被扔到哪边。然后加树状数组来统计就好了。


代码巨丑。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


struct query {

int x1,...

BZOJ1633 [Usaco2007 Feb]The Cow Lexicon 牛的词典

本来想做点英语作业的。想10分钟把这题搞定的。结果傻了去写trie树dp又傻了没有考虑终点也可以有子结点。


我真是无药可救了。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


int tcnt;

struct trie_node {

int d, e, t[26];

inline trie_node(int d0 = 0) {

e = 0;

d = d0 + 1;

memset(t, 0, sizeof...

© laekov | Powered by LOFTER