6
23
2015
0

BZOJ3653: 谈笑风生

题意(一开始理解错了的版本)
Q个询问、n个点
 
每个询问是p k
 
求 p的子树中(不包括p)有多少个二元组 (b,c) 满足:
b,c互不相等
b为c的祖先
p和b的距离不超过k
 
n<=3*10^5 Q<=3*10^5
 
 
简单思考一下可以发现如下性质:
  1. 对于任何一个满足8的b,满足条件的c的个数就是b的子树大小(不包括b)
  2. 对于任何一个在p的子树中的c,满足条件的b的个数是min(dep[c] - dep[p], k)
 
  哪个更好用?
  性质1的子树大小不变,但是b的范围是不好处理的
  性质2的k的大小是不确定的每个点的贡献不方便确定
 
难点集中在对k的处理上
 
p的子树中距离小于等于k的b?注意这里p是b的祖先,dis(p,b) 不就是dep[p] - dep[b] ?
也就是子树中dep[b] <= dep[p] + k的b
 
然后我们每次询问的就是在[pre[p] + 1, last[p]] 这段内dep[b] <= dep[p] + k的
而dep[p] + k又是可以确定的,那么我们就可以离线询问、按照dep加入一个BIT
就不用写主席树了
 
 
写完才发现上面理解错了题意,b不一定在p的子树中,但是它和p都是c的祖先
所以如果它不在p的子树中,那么它就是p的祖先,而此时c只能是sz[p] - 1个,修正一下把这块加上即可
 
所以误打误撞学会了一种分析题目的办法,按照它在p的子树内,还是子树外分类
这里这么分类是因为这两种情况的贡献一个是sz[b] - 1 一个是sz[p] - 1,是一道明显的界限
 
 
http://www.cnblogs.com/zyfzyf/p/4252291.html另外一种办法(慢一点)
 
第一次在数据结构相关的题上时间rank1 好开心
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
using namespace std;
const int N = 300010;
typedef long long LL;
struct edge{
	int to,pre;
}e[N * 2];
int l = 0, u[N];
inline void ins(int a,int b){
	e[++l] = (edge){b, u[a]}, u[a] = l;
}
int pre[N], dep[N], dfs_clock = 0, last[N], sz[N];
void dfs(int x,int f){
	pre[x] = ++dfs_clock, sz[x] = 1;
	reg(i,x) if (v != f){
		dep[v] = dep[x] + 1, dfs(v,x), sz[x] += sz[v];
	}
	last[x] = dfs_clock;
}
#define mp(a,b) make_pair(a,b)
pair<int,int> y[N];
struct query{
	int l,r,t,pos,szp,dep,k;//(l,r]
}q[N];
LL ans[N];
inline bool cmp(const query &a, const query &b){
	return a.t < b.t;
}
inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}

    return x*f;

}
int n;
struct BIT{
	LL s[N];
	inline void add(int x, int d){
		while (x <= n){
			s[x] += d;
			x += (-x) & x;
		}
	}
	inline LL sum(int x){
		LL ans = 0;
		while (x > 0){
			ans += s[x];
			x -= (-x) & x;
		}
		return ans;
	}
}b;
#undef v
int main(){
	int Q;n = read(); Q= read();
	rep(i,1,n-1){
	    int u,v;
	    u = read(),v = read();
		ins(u,v), ins(v,u);
	}
	dep[1] = 1;dfs(1,0);
	rep(i,1,n) y[i] = mp(dep[i],i);
	sort(y+1, y+n+1);
	rep(i,1,Q){
		int p, k;p = read(), k =read();
		q[i] = (query){pre[p], last[p], dep[p] + k, i, sz[p], dep[p], k};
	}
	sort(q+1, q+Q+1, cmp);

	int j = 1;
	rep(i,1,Q){
		for(;y[j].first <= q[i].t && j <= n; j++) {
			int x = y[j].second;
			b.add(pre[x], sz[x] - 1);
		}
		ans[q[i].pos] = b.sum(q[i].r) - b.sum(q[i].l) +1LL * min(q[i].k, q[i].dep - 1) * (q[i].szp - 1);
	}
	rep(i,1,Q) printf("%lld\n", ans[i]);
}

 

Category: oi题解 | Tags:
4
23
2015
0

ahoi2015 (jsoi round2) 滚粗记

Day1之前学习了怎么配置gedit和对拍,在比赛里帮了自己大忙……

 

比赛的时候就用gedit的经典蓝色配色写的代码……自己配置了一键编译

 

Day1

    早上随便吃了一点就上了考场,想多带点水,最后还是只带了两瓶

    于是最后没水喝好难受啊……

    t1使劲画了画样例,怎么都画不对……就弃疗了

    结果大家最后直接找规律A了……真是遗憾

    回来之后我一直在抱怨自己……直到看见神犇说“自己技不如人啊”才反应过来……我是不该抱怨的

   只能说自己在考场上放弃t1去写t3一个没有把握的做法是轻率的

   同时t3的做法似乎写挂了,只有40,说明自己的代(mo)(ban)能力还是要提高啊……

   然后二分答案做了t2正解,对拍找到了一个错误之后,拍了好几下都过了,然后居然乱调,浪费了很长时间。感觉心态有两个“诶呀,对拍调参又轻松又好玩,还是在干正事”呵呵……省选是去玩的吗……感觉这个心态和自己做作业偷偷玩手机的心态差不多啊 ……就是偷懒安慰自己罢了。另外一个心态就是“只要A了一题就差不多了吧,反正js的题一向很难”,呵呵,你会做 别人就不会?怎么可能!你必须自己尽力拿分啊。

 

最后知道Day1成绩的时候十分悲伤……埋怨自己……

Day2

Day1的教训之后态度认真了不少

但是早上起来早了好困啊……好困好困好困啊……

bkq等学长说“数学差”……很是不服

打开t1之后,发现是期望题……有了“证明自己数学不差”的想法

然后注意到其实某个女孩子选择某个男孩的概率是确定的,等比数列求之……

之后期望可加就直接做了……

写了个暴力和BIT拍……似乎一次就拍过了

       拍过了不敢耽误就去看t2

又有了“诶呀A了一题就行了吧”的想法……真是可恶!

然后发现t2首先可以费用流,感觉数据范围像是贪心……于是yy了一个靠谱的,脑补了下大致证明……

然后和费用流拍过了……但是复杂度比较高……(但是已经有70分了)

感觉脑子不清醒了,发现t3 40分似乎可写,t2剩下的30就算了吧(以为是要写个splay或者是用set什么的)……

纠结了一会三角函数把t3 40分写出来了……发现好像没处理y1<0的情况……又纠结半天,写出来了……

手动画数据调了调就不管了

仔细想想,发现t230分一个priority_queue就搞定了,然后愉快的写了,对拍出一个错误

然后拍过了……怕有问题,于是

   if (n<=200) work1(); else if (n<=1000) work2(); else work3();

我把三个版本并到一起了……

然后特意留意了一下空间,确定不会MLE

最后对拍的时候不小心弄错了版本,结果WA半天,虚惊一场

 

然后比赛就结束了,十分惋惜的说,如果d1t1做出来了就无悬念A队了吧

 

最后省队肯定是进了,但是不知道能不能进A

 

第一天拿着手机在qq上找别人帮我看成绩,结果是0+100+40=140……跪的很惨……3位芜湖大爷ak

 

第二天打电话问老师也没有,最后还是day1 ak的芜湖大爷罗教帮我看的……100+100+40=240 也算没有失误了 和芜湖大爷并列rank2

 

最后总结:

    1.比赛心态很重要,时刻记得保证基本分,多想想,所有题都要看懂,都要想……

    2.比赛的时候千万不能有懒惰的想法,对拍的时候可以看题,不要偷懒

    3.尽人事,听天命。

 

 

Update:

Day1t3我是树链剖分+主席树的……树链剖分是为了提取出一条路径……然而……taorunz大爷告诉我……这个信息是支持加法减法的,也就是可以s(u)+s(v)-2*s(lca)……多显然的结论啊……我居然注意到…看来考场上还是要多想想啊……TAT

Category: 未分类 | Tags: 比赛经验
4
14
2015
0

Tmp

#!/bin/bash
name="jzt"
make ${name}
make ${name}_bf
 
t=0
while[$t ‐lt 100]
do
let "t=$t+1"
./gen>${name}.in
./${name}<${name}.in>${name}.out
./${name}_bf<${name}.in>${name}.ans
diff ${name}.out ${name}.ans
done
Category: 未分类 | Tags:
4
13
2015
0

我的线段树模板的一个坑点

我就是不听老人言……自己yy的模板果然出了问题……

这样的,我的写法里面必须push之后节点内的信息才是正确的

但是在modify中

注:#define lcq lc,l,mid             #define rcq rc,mid+1,r

if (a <= mid) modify(lcq,wq,d);

if (b >   mid) modify(rcq,wq,d);

upd(x);

碉堡了!可能只是递归到一边,然后另外一边没有push!真可怕!

所以应该改成

if (a <= mid) modify(lcq,wq,d); else push(lcq);

if (b >   mid) modify(rcq,wq,d); else push(rcq);

upd(x);

或者在upd里面加上push(lcq);push(rcq); 反正都一样,这样大概常数小一些

一定不要忘啦

Category: 未分类 | Tags:
4
11
2015
1

gedit的配置

配置gedit编译和运行:(shell)
编译
#!/bin/sh
fullname=$GEDIT_CURRENT_DOCUMENT_NAME
name=`echo $fullname | cut -d. -f1`
g++ $fullname -o $name -Wall -g

其中fullname=$GEDIT_CURRENT_DOCUMENT_NAME 显然是文件名
cut -d. -f1是啥呢? 从.分割成两端 取第一段
注意:所有UNIX命令,要取结果或输出,都要用$( )或反引号` `
不能少了``

 

Category: linux使用 | Tags:
1
8
2015
0

写题的时候debug出的错误

 

  1. 【bzoj1798】sb的线段树居然在update的时候忘记mod p

  2. 【bzoj1293】在增加右边界r的时候没有考虑到r<=n

  3. 【bzoj1854】写数组模拟链表的时候(尤其是存图和hash)可以记录当前这个点最后的一个后继,这样插入就是O(1)的了

         

    procedure add_edge(a,b:longint);

    var

     i:longint;

    begin

     inc(l);v[l]:=b;next[l]:=0; 

     i:=ut[a];if i=0 then begin u[a]:=l;ut[a]:=l;exit;end; 

     next[i]:=l;ut[a]:=l;

    end;

     

  4. 【bzoj3631】倍增LCA调整到同一深度的时候不!要!暴!力!要用倍增数组调整……

               u,v是双向的,边是2n的……傻逼就开了n的数组是闹咋样啊……(论跑随机大数据的重要性

5.  【bzoj1406】这题最后对答案排序可能无解……然后如果无解快排看起来就是这个样子sort(1,0)一定会死循环!所以小心                    sort(l,r) 一定要有l<=r

                还有开始枚举约数的时候n mod j<>0没有continue掉时什么心态……

6.【bzoj1857】 囧掉了囧掉了囧掉了!注意1.向量a,b的a b顺序很重要,所以swap了l r之后就不能用a b了 要用l r

               前后继的两个红色特的特判也很重要,总之斜率就是小心delta x=3或者dealta x=0 & delta y=0的

               

 

function next(x,a,b:dot):dot;

begin

 if check(a,b) then exit(x);

 if b.x-a.x<eps then begin 

     x.y:=x.y+eps;exit(x);

 end;

 x.x:=x.x+eps;

 x.y:=x.y+((b.y-a.y)*eps)/(b.x-a.x);

 exit(x); 

end;

7.【bzoj1986】喷头是向两边喷的囧……所以要把奇数过滤掉

8.【bzoj1856】注意费马小定理算乘法逆是p-2次方

9.【bzoj2440】注意在线性筛法计算欧拉函数的时候特殊处理i mod p[j]=0的情况(其实也不用太特殊啦)

              10^9二分就要开int64了

10.【bzoj1610】由于x y都是1000的范围的,eps取10^(-8)才行

11.【bzoj1614】无向图当做双向的有向图来存的时候原本边数是n,那么现在就要变成2n,数组要开够!

               (要跑随机大数据……&

12.【bzoj1046】在函数里返回一个值一定要记得写exit

13.【bzoj2007】swap居然没加var……感受一下……太傻逼了

               嗯……i j两个变量不要打反了

               (其实这次的堆的写法我从以前繁琐的写法稍微修改了一下,感觉好多了

14.【bzoj2957】写线段树的时候要 先判断是否到了叶子(别忘了exit) 然后再递归

               这道题在update的时候相当有讲究

15.【bzoj2115】写1 shl 60会爆longint 要写成int64(1) shl 60

16.【bzoj2242】:

  1. a的逆元在 mod质数p意义下是a^(p-2)而非a^(p-1)

  2. 小心,所有东西重复使用之前都要清0,比如hash

  3. 不要混用halt exit break(多傻逼的错误)

  4.  注意特判,0是没有逆元的。所以 a mod p=0 的情况要特殊处理

  5. 小心代码的常数 能用mod p搞定 坚决不 while x<0 do inc(x,p) 改过之后一下子快了3s+

17.【bzoj3144】最大流的s和t是全局定义的,之后在main()里千万不能写成int s=,t= 而应该写成s=;t=;

18.【bzoj2154】: 分块的时候做了前缀和,在统计的时候就不用*(r-l+1)了

19.【bzoj1014】:

    1.o->upd() in insert() && build();
    2.char数组 scanf("%c");的时候是从0开始的 所以build的时候应该用s[l-1]
    3.insert之后记得n++
    4.l1 r1比较之前应该把负数变成正的并% Mod 过程中关键的地方应该使用long long 避免溢出
Category: 未分类 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com