2
25
2016
0

[bzoj]3944: Sum

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3944

本来想留着给初三爷出题。。然而都没几个会欧拉函数的,所以就写个题解等我忘了看……

最开始给我灵感的是codevs月赛的一道题,它的一个子问题是求

$\sum_{i=1}^{n}\sigma \left ( i \right )$,其中$\sigma \left ( n \right )= \sum_{d|n}d$

介个东西怎么做呢,当然并不能直接做喽,当时比利直接秒出%%%,he said :"This is a foolish thing." 他是考虑每个数对答案的贡献,我还是暴力推了推公式

$\sum_{i=1}^{n} \sigma \left ( i \right )= \sum_{i=1}^{n}\sum_{j=1}^{n}[j|i]\cdot j= \sum_{i=1}^{n}i\cdot [\frac{n}{i}]$

2
25
2016
0

[bzoj]3545: [ONTAK2010]Peaks

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3545

sb题

离线做,把边和询问都排序,然后一条条加边,维护连通块,于是这就是个平衡树合并裸题。。然而只有我这种都比被卡了辣么久- =

一发5s,感觉跑好慢……,一看榜,发现rank3而且代码也很短2333

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,k,m,n,x,y,Q,h[N],cnt,fa[N],pp[N],ans[N*5],top;
struct edge{
	int x,y,z;
	inline void in(){x=read(),y=read(),z=read();}
	bool operator <(const edge&a)const{return z<a.z;}	
}e[N*5];
struct ques{
	int v,x,k,id;
	inline void in(){v=read(),x=read(),k=read(),id=i;}
	bool operator <(const ques&a)const{return x<a.x;}
}q[N*5];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct node{
	node*ch[2];int r,sz,h,id;inline void up(){sz=ch[0]->sz+ch[1]->sz+1;}
	inline int cmp(int x)const{return x>h;}
}C[N],Null,*null=&Null;
inline void rotate(node*&o,int d){node*k=o->ch[d^1];o->ch[d^1]=k->ch[d],k->ch[d]=o,k->sz=o->sz,o->up(),o=k;}
int insert(node*&o,int x,int id){
	if(o==null)o=&C[id],o->id=id,o->h=x,o->ch[0]=o->ch[1]=null,o->sz=1,o->r=rand();
	else{
		int d=o->cmp(x);++o->sz;
		insert(o->ch[d],x,id);if(o->ch[d]->r>o->r)rotate(o,d^1);
	}
	return o->id;
}
void Add(node*x,node*y){if(x==null)return;Add(x->ch[0],y),Add(x->ch[1],y),top=insert(y=&(C[top]),x->h,x->id);}
inline void link(int u,int v){
	if(u==v)return;
	if((C+u)->sz<(C+v)->sz)swap(u,v);
	fa[v]=u,top=pp[u],Add(C+pp[v],C+pp[u]),pp[u]=top;
}
int kth(node*o,int k){
	if(o==null||k<=0||k>o->sz)return 0x7f7f7f7f;
	if(k<=o->ch[0]->sz)return kth(o->ch[0],k);
	if(k>o->ch[0]->sz+1)return kth(o->ch[1],k-o->ch[0]->sz-1);
	return o->h;
}
int main(){
	for(n=read(),m=read(),Q=read(),i=1;i<=n;++i)h[i]=read(),fa[i]=i,pp[i]=i,(C+i)->id=i,(C+i)->h=h[i],(C+i)->sz=1,(C+i)->ch[0]=(C+i)->ch[1]=null,(C+i)->r=rand();
	for(i=1;i<=m;++i)e[i].in();for(i=1;i<=Q;++i)q[i].in();
	for(cnt=1,sort(e+1,e+m+1),sort(q+1,q+Q+1),i=1;i<=Q;++i){
		while(e[cnt].z<=q[i].x&&cnt<=m)link(find(e[cnt].x),find(e[cnt].y)),++cnt;
		ans[q[i].id]=kth(C+pp[find(q[i].v)],(C+pp[find(q[i].v)])->sz-q[i].k+1);
	}
	for(i=1;i<=Q;++i)if(ans[i]==0x7f7f7f7f)puts("-1");else printf("%d\n",ans[i]);
}

Category: bzoj | Tags: 平衡树 启发式合并
2
23
2016
2

(持续更新)[bzoj][黑科技]一些题

有人问我为什么有些题那么快_(:зゝ∠)_

所以我来解释一下我加的黑科技,题目编号是乱的= =,有想要我解释的题请评论


首先是fastio,bzoj上有了这个就可以轻易rank1吧。。

#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:*p1++)
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
char pf[S],*o1=pf,*o2=pf+S;
#define ot(x) (o1==o2?fwrite(pf,1,S,stdout),*(o1=pf)++=x:*o1++=x)
inline void print(int x){static char s[15],*b;b=s;if(!x)*b++=48;for(;x;*b++=x%10+48,x/=10);for(;b--!=s;ot(*b));}
fwrite(pf,1,o1-pf,stdout);
//for(i=1;i<=m;++i)print(ans[i]),ot('\n');

所以在这里我就不解释用fastio艹上去的题了

Category: bzoj | Tags: 黑科技
1
13
2016
7

[题解]缅怀逝去的木吉♂初三爷欢乐模拟赛

这个题解我是在你们做这套题的时候写的♪(^∇^*)



先讲第二题吧-。- 原题是bzoj4080

首先如果有人这题没分。。

。。。。。。。。。。。。。。

好,我们来看前60%的数据,$n<=15$,这个东西只要$2^{15}$枚举就行了我不多说

对于100%的数据,有很多种做法-。-,不知道你们认不认识我给你们的关怀里的那个 “大力”

Category: 日常 | Tags: 模拟赛
12
28
2015
1

[bzoj]4373: 算术天才⑨与等差数列

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373

强制在线。。只能想到数据结构-。-

标算表示想不到-。-||| %Claris

我的做法是,用线段树维护区间最小值,区间哈希值,哈希采用平方和的方法(from 比利),对于一个知道了首项和公差的等差数列,其数列

$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$

然后。。

Category: bzoj | Tags: hash gcd 线段树
12
25
2015
0

[bzoj]2657: [Zjoi2012]旅游(journey)

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2657

 

嘛,两个三角形最多只有一条公共边-。-,然后以每个三角形为顶点与相邻的三角形连边,这样构成一棵树。。然后跑直径就好了

$O(N)$

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
int i,j,k,m,n,x,y,cnt,last[N],z,who,dep[N],Dep;
struct edge{int to,next;}e[N<<1];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt,e[++cnt]=(edge){u,last[v]},last[v]=cnt;}
struct Edge{int l,r;bool operator <(const Edge&b)const{return(l<b.l)||(l==b.l)&&(r<b.r);}};
map<Edge,int>mp;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa)dfs(y,x);
	if(Dep<dep[x])Dep=dep[x],who=x;
}
inline void Add(int x,int y){
	if(mp[(Edge){x,y}]!=0)add(mp[(Edge){x,y}],i),mp[(Edge){x,y}]=0,mp[(Edge){y,x}]=0;
	else mp[(Edge){x,y}]=i,mp[(Edge){y,x}]=i;
}
int main(){
	for(n=read(),i=1;i<n-1;++i){
		x=read(),y=read(),z=read();
		Add(x,y),Add(x,z),Add(y,z);
	}
	dfs(1,0),Dep=0,dep[0]=0,dfs(who,0);
	printf("%d",Dep);
}

 

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