随便搞点什么吧2
shinbokuow
posted @ Jun 16, 2015 06:10:59 PM
in water
, 1144 阅读
弱省胡策Round6 A
大意:首先注意到就是求出一个最大的循环串集合,使得集合中的任意两个循环串在模$a$意义下相等或者模$b$意义下相等.
思路:首先找出哪些循环串是模$a$相等的,哪些循环串是模$b$相等的,然后找出模$a$相等的最大集合,再找出模$b$相等的最大集合,取个最大值.
利用反证法易证这样是对的.
利用hash很容易实现,时间$O(n)$.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define N 1000010
int A[N<<1],B[N<<1];
struct Hash_system{
static const int mod1=1000000007;
static const int mod2=1000000009;
static const int seed1=200019;
static const int seed2=13131;
int f1[N<<1],f2[N<<1],pow1[N<<1],pow2[N<<1];
inline void init(){
int i;
for(pow1[0]=1,i=1;i<=2000000;++i)
pow1[i]=(ll)pow1[i-1]*seed1%mod1;
for(pow2[0]=1,i=1;i<=2000000;++i)
pow2[i]=(ll)pow2[i-1]*seed2%mod2;
}
inline void input(int A[],int n){
f1[n+1]=f2[n+1]=0;
for(int i=n;i>=1;--i){
f1[i]=((ll)f1[i+1]*seed1+A[i])%mod1;
f2[i]=((ll)f2[i+1]*seed2+A[i])%mod2;
}
}
pii gethash(int l,int r){
int h1=(f1[l]-(ll)f1[r+1]*pow1[r-l+1]%mod1+mod1)%mod1;
int h2=(f2[l]-(ll)f2[r+1]*pow2[r-l+1]%mod2+mod2)%mod2;
return make_pair(h1,h2);
}
}H;
pii seq[N];
int main(){
int T;
cin>>T;
int i,j;
H.init();
while(T--){
int n,a,b;
cin>>n>>a>>b;
for(i=1;i<=n;++i)
scanf("%d",&A[i]);
for(i=n+1;i<2*n;++i)
A[i]=A[i-n];
int ans=0;
for(i=1;i<2*n;++i)
B[i]=A[i]%a;
H.input(B,2*n-1);
for(i=1;i<=n;++i)
seq[i]=H.gethash(i,i+n-1);
sort(seq+1,seq+n);
for(i=1;i<=n;){
for(j=i;j!=n&&seq[j]==seq[j+1];++j);
ans=max(ans,j-i+1);
i=j+1;
}
for(i=1;i<2*n;++i)
B[i]=A[i]%b;
H.input(B,2*n-1);
for(i=1;i<=n;++i)
seq[i]=H.gethash(i,i+n-1);
sort(seq+1,seq+n);
for(i=1;i<=n;){
for(j=i;j!=n&&seq[j]==seq[j+1];++j);
ans=max(ans,j-i+1);
i=j+1;
}
cout<<(ans==1?0:ans)<<endl;
}
return 0;
}
弱省胡策Round6 B
思路:首先将树树链剖分,则任何一颗联通的子树都必定可以用一条链上的一段作为主链来表示,主链上的每个点会向下连出一些子链,我们仅需考虑子链的最大前缀和,若其$>0$,则加到这个点的点权中.然后再搞出这个链的最大子段和更新答案.
维护一个全局堆记录所有重链的最大子段和.
考虑修改,只需要修改这个点的权值,更新链的最大子段和,在堆中修改,然后更新父亲重链的点权,并以此类推就行了.
时间复杂度$O(log^2n)$.
我的代码在ch上不明所以的RE,本地可以AC.
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>s;
#define N 100010
#define l(x) S[x].l
#define r(x) S[x].r
struct Ans{
int lm,rm,sum,mx;
inline void add(int x){
lm+=x;
rm+=x;
sum+=x;
mx+=x;
}
};
struct Node{
int l,r;
Ans v;
}S[N<<1];
Ans merge(const Ans&l,const Ans&r){
Ans re;
re.lm=max(l.lm,l.sum+max(0,r.lm));
re.rm=max(r.rm,r.sum+max(0,l.rm));
re.sum=l.sum+r.sum;
re.mx=max(max(l.mx,r.mx),l.rm+r.lm);
return re;
}
int cnt;
inline int build(int tl,int tr){
int q=++cnt;
if(tl==tr)
return q;
int mid=(tl+tr)>>1;
l(q)=build(tl,mid);
r(q)=build(mid+1,tr);
return q;
}
inline void up(int x){
S[x].v=merge(S[l(x)].v,S[r(x)].v);
}
inline void add(int q,int tl,int tr,int ins,int v){
if(tl==tr){
S[q].v.add(v);
return;
}
int mid=(tl+tr)>>1;
if(ins<=mid)
add(l(q),tl,mid,ins,v);
else
add(r(q),mid+1,tr,ins,v);
up(q);
}
inline Ans Query(int q,int tl,int tr,int dl,int dr){
if(dl<=tl&&tr<=dr)
return S[q].v;
int mid=(tl+tr)>>1;
if(dr<=mid)
return Query(l(q),tl,mid,dl,dr);
else if(dl>mid)
return Query(r(q),mid+1,tr,dl,dr);
else
return merge(Query(l(q),tl,mid,dl,mid),Query(r(q),mid+1,tr,mid+1,dr));
}
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q++;
}
inline void make(int a,int b){
addedge(a,b);
addedge(b,a);
}
int v[N],_v[N];
int siz[N],son[N],id,p_id[N],id_p[N],dep[N],top[N],pa[N];
inline void dfs(int x,int fa){
siz[x]=1;
int Max_siz=0;
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
pa[end[j]]=x;
dfs(end[j],x);
siz[x]+=siz[end[j]];
if(siz[end[j]]>Max_siz){
Max_siz=siz[end[j]];
son[x]=end[j];
}
}
}
}
int lab[N],num=1,_begin[N],_end[N];
inline void create(int x,int Top){
top[x]=Top;
p_id[x]=++id;
id_p[id]=x;
lab[id]=num;
if(son[x])
create(son[x],Top);
else
++num;
for(int j=head[x];j;j=next[j])
if(end[j]!=pa[x]&&end[j]!=son[x])
create(end[j],end[j]);
}
int n,m;
inline void Modify(int x,int y){
Ans tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]);
int lastlm=tmp.lm,lastmx=tmp.mx,_lastlm,_lastmx;
int nowlm,nowmx;
add(1,1,n,p_id[x],-v[x]+y);
v[x]=y;
while(1){
tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]);
nowlm=tmp.lm,nowmx=tmp.mx;
s.erase(s.find(lastmx)),s.insert(nowmx);
if(pa[top[x]]){
tmp=Query(1,1,n,_begin[p_id[pa[top[x]]]],_end[p_id[pa[top[x]]]]);
_lastlm=tmp.lm,_lastmx=tmp.mx;
if(lastlm<=0&&nowlm>0)
add(1,1,n,p_id[pa[top[x]]],nowlm);
else if(lastlm>0&&nowlm<=0)
add(1,1,n,p_id[pa[top[x]]],-lastlm);
else if(lastlm>0&&nowlm>0)
add(1,1,n,p_id[pa[top[x]]],-lastlm+nowlm);
x=pa[top[x]];
lastlm=_lastlm;
lastmx=_lastmx;
}
else
break;
}
}
int main(){
//freopen("tt.in","r",stdin);
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;++i)
scanf("%d",&_v[i]);
int a,b;
for(i=1;i<n;++i){
scanf("%d%d",&a,&b);
make(a,b);
}
dep[1]=1;
dfs(1,-1);
create(1,1);
for(i=1;i<=n;){
for(j=i;j!=n&&lab[j]==lab[j+1];++j);
for(k=i;k<=j;++k)
_begin[k]=i,_end[k]=j;
i=j+1;
}
for(i=1;i<=num-1;++i)
s.insert(0);
build(1,n);
for(i=1;i<=n;++i)
Modify(i,_v[i]);
int qte,x,y;
while(m--){
scanf("%d",&qte);
if(qte==2){
multiset<int>::iterator it=s.end();
printf("%d\n",max(0,*(--it)));
}
else{
scanf("%d%d",&x,&y);
Modify(x,y);
}
}
return 0;
}
弱省胡策Round6 C
想了好长时间的性质,结果发现是暴力题,稍微加了一点可行性剪枝就过了.
出题人我@$#^$%&$%#@^%#$&$%&...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>s;
#define N 2010
int a[N];
int main(){
//freopen("tt.in","r",stdin);
int T;
cin>>T;
int n,m,i,j;
while(T--){
cin>>n>>m;
int sum=0,Max=0;
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
sum+=a[i];
Max=max(Max,a[i]);
}
int ans;
for(ans=max(Max,sum/m);ans<=sum;++ans){
int tim=0,last;
for(i=1;i<=n;++i)
s.insert(a[i]);
while(!(s.begin()==s.end())){
++tim;
last=ans;
while(1){
if(s.begin()==s.end())
break;
multiset<int>::iterator it=s.upper_bound(last);
if(it==s.begin()||last<*(--it))
break;
last-=*it;
s.erase(s.find(*it));
//for(multiset<int>::iterator it=s.begin();it!=s.end();++it)printf("%d ",*it);puts("");
}
}
//printf("%d ",tim);
if(tim<=m)
break;
}
cout<<ans<<endl;
}
return 0;
}
WC2014紫荆花之恋
orz jkxing!orz orz orz!
我现在终于明白正确的动态树分治是什么鬼啦...
我们并不是对于每个分治结构在里面维护每个子树的信息,而是直接把每个子树的信息维护到对应的子结构里面去就行啦!
还有,求每个点在分治结构中的贡献,用一个全局的lca倍增就行了,也不用单独在分治结构中维护!
一般来说,这种路径信息全局的lca应该都足以解决了.
于是我现在又要开动啦!
upd:现在一些恶心的点爆栈,剩下的还是都能过的,80分.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
#define ls ch[0]
#define rs ch[1]
#define N 100010
namespace Treap{
struct Node{
Node*ch[2];
int v,p,s;
Node():s(0){}
inline void up(){
s=ls->s+rs->s+1;
}
}mem[N*50],*G=mem,Tnull,*null=&Tnull;
stack<Node*>bin;
inline Node*newnode(int _v){
Node*re;
if(!bin.empty()){
re=bin.top();
bin.pop();
}
else
re=G++;
re->ls=re->rs=null;
re->v=_v;
re->p=rand();
re->s=1;
return re;
}
inline void Rot(Node*&p,bool d){
Node*q=p->ch[!d];
p->ch[!d]=q->ch[d];
q->ch[d]=p;
p->up();
q->up();
p=q;
}
inline void insert(Node*&p,int v){
if(p==null)
p=newnode(v);
else if(v<p->v){
insert(p->ls,v);
if(p->ls->p<p->p)
Rot(p,1);
}
else{
insert(p->rs,v);
if(p->rs->p<p->p)
Rot(p,0);
}
p->up();
}
inline int query(Node*p,int v){
if(p==null)
return 0;
if(v<p->v)
return 1+p->rs->s+query(p->ls,v);
else
return query(p->rs,v)+(p->v>=v);
}
inline void recover(Node*p){
if(p==null)
return;
if(p->ls!=null)
recover(p->ls);
if(p->rs!=null)
recover(p->rs);
bin.push(p);
}
void dfs(Node*p){
if(p->ls!=null)
dfs(p->ls);
printf("%d ",p->v);
if(p->rs!=null)
dfs(p->rs);
}
}
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int l){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=l;
}
inline void make(int a,int b,int l){
addedge(a,b,l);
addedge(b,a,l);
}
int dep[N],_dep[N],pa[N][21];
inline int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;--i)
if(dep[pa[x][i]]>=dep[y])
x=pa[x][i];
if(x==y)
return x;
for(int i=20;i>=0;--i)
if(pa[x][i]!=pa[y][i])
x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
inline int getdist(int x,int y){
return _dep[x]+_dep[y]-(_dep[lca(x,y)]<<1);
}
ll ans;
int r[N];
struct Array{
int t[N],a[N],tclock;
inline int operator[](const int&x){
if(t[x]!=tclock){
t[x]=tclock;
a[x]=0;
}
return a[x];
}
inline void ch(int x,int d){
t[x]=tclock;
a[x]=d;
}
}in;
namespace Dynamic_System{
struct Tnode{
Tnode*pa;
Treap::Node*root,*_root;
set<Tnode*>son;
int up,g,siz;
}mem[N],*G=mem,Tnull,*null=&Tnull,*ins[N];
stack<Tnode*>bin;
inline Tnode*newnode(){
Tnode*re;
if(!bin.empty()){
re=bin.top();
bin.pop();
}
else
re=G++;
re->pa=null;
re->root=Treap::null;
re->_root=Treap::null;
re->son.clear();
return re;
}
inline Tnode*sNode(int x){
Tnode*re=newnode();
re->g=re->up=x;
re->siz=1;
Treap::insert(re->root,r[x]);
return re;
}
inline void recover(Tnode*p){
for(set<Tnode*>::iterator it=p->son.begin();it!=p->son.end();++it)
recover(*it);
in.ch(p->g,1);
Treap::recover(p->root);
Treap::recover(p->_root);
p->son.clear();
bin.push(p);
}
inline Tnode*divide(int x,int pdis){
static int q[N],_pa[N],ms[N],siz[N],d[N];
//static int g,mins;
//static Tnode*re,*tmp;
static int fr,ta,g,mins;
int i,j;
static Tnode*tmp;
Tnode*re;
_pa[x]=0;
d[x]=0;
fr=ta=0;
q[ta++]=x;
re=newnode();
re->up=x;
while(fr!=ta){
i=q[fr++];
Treap::insert(re->_root,r[i]-(d[i]+pdis));
for(j=head[i];j;j=next[j])
if(end[j]!=_pa[i]&&in[end[j]]){
_pa[end[j]]=i;
d[end[j]]=d[i]+len[j];
q[ta++]=end[j];
}
}
mins=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
ms[q[i]]=max(ms[q[i]],ta-siz[q[i]]);
if(mins>ms[q[i]]){
mins=ms[q[i]];
g=q[i];
}
ms[_pa[q[i]]]=max(ms[_pa[q[i]]],siz[q[i]]);
siz[_pa[q[i]]]+=siz[q[i]];
}
ins[re->g=g]=re;
re->siz=ta;
_pa[g]=0;
d[g]=0;
fr=ta=0;
q[ta++]=g;
while(fr!=ta){
i=q[fr++];
Treap::insert(re->root,r[i]-d[i]);
for(j=head[i];j;j=next[j])
if(end[j]!=_pa[i]&&in[end[j]]){
_pa[end[j]]=i;
d[end[j]]=d[i]+len[j];
q[ta++]=end[j];
}
}
if(ta==1)
return re;
in.ch(g,0);
for(j=head[g];j;j=next[j])
if(in[end[j]]){
tmp=divide(end[j],len[j]);
tmp->pa=re;
re->son.insert(tmp);
}
return re;
}
inline void rebuild(Tnode*p){
Tnode*fa=p->pa;
if(fa!=null)
fa->son.erase(p);
++in.tclock;
recover(p);
Tnode*get=divide(p->up,fa==null?0:getdist(p->up,fa->g));
if(fa!=null){
get->pa=fa;
fa->son.insert(get);
}
}
inline void addnode(int x,int fa,int pdis){
dep[x]=dep[fa]+1;
_dep[x]=_dep[fa]+pdis;
pa[x][0]=fa;
for(int j=1;j<=20;++j)
pa[x][j]=pa[pa[x][j-1]][j-1];
make(x,fa,pdis);
ins[x]=sNode(x);
ins[x]->pa=ins[fa];
ins[fa]->son.insert(ins[x]);
Tnode*last=ins[x],*node=null;
for(Tnode*t=ins[fa];t!=null;t=t->pa){
int dis=getdist(t->g,x);
Treap::insert(t->root,r[x]-dis);
Treap::insert(last->_root,r[x]-dis);
ans+=Treap::query(t->root,dis-r[x])-Treap::query(last->_root,dis-r[x]);
if(last->siz/(double)(++t->siz)>0.75)
node=t;
last=t;
}
if(node!=null)
rebuild(node);
}
}
int main(){
//freopen("tt.in","r",stdin);
int n;
scanf("%*d%d",&n);
//scanf("%d",&n);
int pa,pdis;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&pa,&pdis,&r[i]);
pa^=(ans%1000000000);
if(i==1){
dep[1]=1;
_dep[1]=0;
Dynamic_System::ins[1]=Dynamic_System::sNode(1);
}
else
Dynamic_System::addnode(i,pa,pdis);
//printf("%I64d\n",ans);
printf("%lld\n",ans);
}
return 0;
}
BZOJ3924
一样的动态树分治,对于每个分治结构维护所有点到根的加权距离以及所有点到父分治结构的根的加权距离,以及分治结构内部所有点的权值和.
计算答案时,每次向着答案更小的地方走就好了.
#include<cstdio>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
#define mp make_pair
#define N 100010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=c;
}
inline void make(int a,int b,int c){
addedge(a,b,c);
addedge(b,a,c);
}
int seq[N<<1],in[N<<1],tclock,dep[N];
ll _dep[N];
int ans[N<<1][21],_log[N<<1];
inline int Min(int x,int y){
return dep[x]>dep[y]?y:x;
}
inline void dfs(int x,int fa){
seq[in[x]=++tclock]=x;
for(int j=head[x];j;j=next[j])
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
_dep[end[j]]=_dep[x]+len[j];
dfs(end[j],x);
seq[++tclock]=x;
}
}
inline void rmq_init(){
for(int i=1;i<=tclock;++i)
ans[i][0]=seq[i];
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=tclock;++i)
ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]);
for(int i=2;i<=tclock;++i)
_log[i]=_log[i>>1]+1;
}
inline int lca(int x,int y){
x=in[x],y=in[y];
if(x>y)
swap(x,y);
int d=_log[y-x+1];
return Min(ans[x][d],ans[y-(1<<d)+1][d]);
}
inline ll dist(int x,int y){
return _dep[x]+_dep[y]-2ll*_dep[lca(x,y)];
}
struct Node{
Node*pa;
ll sum,_sum,siz;
int up,g;
vector<Node*>son;
}mem[N],*P=mem,Tnull,*null=&Tnull,*ins[N];
inline Node*newnode(){
P->pa=null;
return P++;
}
bool vis[N];
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
inline Node*divide(int x){
static int q[N],pa[N],siz[N],ms[N],fr,ta;
static Node*tmp;
int i,j;
Node*re=newnode();
re->up=x;
fr=ta=pa[x]=0;
q[ta++]=x;
while(fr!=ta){
i=q[fr++];
for(j=head[i];j;j=next[j])
if(end[j]!=pa[i]&&!vis[end[j]])
pa[q[ta++]=end[j]]=i;
}
int g,Min_siz=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
maxi(ms[q[i]],ta-siz[q[i]]);
if(ms[q[i]]<Min_siz){
Min_siz=ms[q[i]];
g=q[i];
}
maxi(ms[pa[q[i]]],siz[q[i]]);
siz[pa[q[i]]]+=siz[q[i]];
}
ins[(re->g=g)]=re;
vis[g]=1;
for(j=head[g];j;j=next[j])
if(!vis[end[j]]){
tmp=divide(end[j]);
tmp->pa=re;
re->son.push_back(tmp);
}
return re;
}
inline void up(int x,int y){
ins[x]->siz+=y;
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){
t->siz+=y;
t->sum+=(ll)dist(t->g,x)*y;
last->_sum+=(ll)dist(t->g,x)*y;
}
}
inline ll getans(int x){
ll ans=ins[x]->sum;
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa)
ans+=t->sum-last->_sum+(ll)dist(t->g,x)*(t->siz-last->siz);
return ans;
}
inline ll solve(Node*root){
ll res=getans(root->g);
for(int j=0;j<root->son.size();++j)
if(getans(root->son[j]->up)<res)
return solve(root->son[j]);
return res;
}
int main(){
//freopen("tt.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int i,a,b,c;
for(i=1;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
make(a,b,c);
}
dfs(1,-1);
rmq_init();
Node*root=divide(1);
while(m--){
scanf("%d%d",&a,&b);
up(a,b);
printf("%lld\n",solve(root));
}
return 0;
}
WJMZBMR模拟赛的某题
我们有一个树，大小为n。考虑树上的一条路径，如果一个边的两个点都在这路径
上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们
称这个边与这个路径相邻。现在每个边要么是黑色的要么是白色的，一开始所有
边都是白色的。
我们有3个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径
上黑边的总数。
上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们
称这个边与这个路径相邻。现在每个边要么是黑色的要么是白色的，一开始所有
边都是白色的。
我们有3个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径
上黑边的总数。
思路:给每个点和每条边(看做一个点)都维护一个颜色,那么每条边的真实颜色就是两个点和一条边的异或和.
路径反色只需要将路径上的所有点都打上取反的标记即可.
然后Access时随便维护一下?
算了,现在只管基本的思路.
BZOJ4012
每个分治结构维护所有版本的关键点到根的距离之和,以及所有版本关键点到父分治结构的距离之和,以及所有版本的关键点数.
然后按照年龄顺序添加版本,每添加一个点都只会增加$O(logn)$个版本,因此空间复杂度$O(nlogn)$.
时间$O(nlog^2n)$,自带大常数垫底辣!
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define pb push_back
#define inf 0x3f3f3f3f
#define N 150010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=c;
}
inline void make(int a,int b,int c){
addedge(a,b,c);
addedge(b,a,c);
}
int seq[N<<1],in[N],tclock,dep[N],_dep[N];
int ans[N<<1][21],_log[N<<1];
inline int Min(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline void dfs(int x,int fa){
seq[in[x]=++tclock]=x;
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
_dep[end[j]]=_dep[x]+len[j];
dfs(end[j],x);
seq[++tclock]=x;
}
}
}
inline void rmq_init(){
for(int i=2;i<=tclock;++i)
_log[i]=_log[i>>1]+1;
for(int i=1;i<=tclock;++i)
ans[i][0]=seq[i];
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=tclock;++i)
ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]);
}
inline int lca(int x,int y){
x=in[x],y=in[y];
if(x>y)
swap(x,y);
int d=_log[y-x+1];
return Min(ans[x][d],ans[y-(1<<d)+1][d]);
}
inline int getdist(int x,int y){
return _dep[x]+_dep[y]-(_dep[lca(x,y)]<<1);
}
struct Node{
Node*pa;
vector<ll>sum;
vector<ll>_sum;
vector<int>tim;
vector<int>_tim;
vector<int>siz;
vector<int>__tim;
int up,g;
inline ll qsum(int _time){
int d=upper_bound(tim.begin(),tim.end(),_time)-tim.begin()-1;
return sum[d];
}
inline ll q_sum(int _time){
int d=upper_bound(_tim.begin(),_tim.end(),_time)-_tim.begin()-1;
return _sum[d];
}
inline ll qsiz(int _time){
int d=upper_bound(__tim.begin(),__tim.end(),_time)-__tim.begin()-1;
return siz[d];
}
}mem[N],*P=mem,Tnull,*null=&Tnull,*ins[N];
inline Node*newnode(){
P->pa=null;
return P++;
}
bool vis[N];
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
inline Node*divide(int x){
static int q[N],siz[N],ms[N],pa[N],fr,ta;
int i,j;
Node*re=newnode();
re->up=x;
fr=ta=pa[x]=0;
q[ta++]=x;
while(fr!=ta){
i=q[fr++];
for(j=head[i];j;j=next[j])
if(end[j]!=pa[i]&&!vis[end[j]])
pa[q[ta++]=end[j]]=i;
}
int g,Min_siz=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
maxi(ms[q[i]],ta-siz[q[i]]);
if(ms[q[i]]<Min_siz){
Min_siz=ms[q[i]];
g=q[i];
}
maxi(ms[pa[q[i]]],siz[q[i]]);
siz[pa[q[i]]]+=siz[q[i]];
}
ins[re->g=g]=re;
vis[g]=1;
for(j=head[g];j;j=next[j])
if(!vis[end[j]])
(divide(end[j]))->pa=re;
re->tim.pb(0);
re->sum.pb(0ll);
re->_tim.pb(0);
re->_sum.pb(0ll);
re->__tim.pb(0);
re->siz.pb(0);
return re;
}
int a[N],w[N],sav[N];
int qu[N];
inline bool cmp(const int&x,const int&y){
return a[x]<a[y];
}
inline void up(int x,int _time){
ins[x]->tim.pb(_time);
ins[x]->sum.pb(ins[x]->sum.back());
ins[x]->__tim.pb(_time);
ins[x]->siz.pb(ins[x]->siz.back()+1);
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){
int _dis=getdist(t->g,x);
last->_tim.pb(_time);
last->_sum.pb(last->_sum.back()+_dis);
t->tim.pb(_time);
t->sum.pb(t->sum.back()+_dis);
t->__tim.pb(_time);
t->siz.pb(t->siz.back()+1);
}
}
inline ll query(int x,int _tim){
ll ans=ins[x]->qsum(_tim);
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa)
ans+=t->qsum(_tim)-last->q_sum(_tim)+(ll)(t->qsiz(_tim)-last->qsiz(_tim))*getdist(x,t->g);
return ans;
}
inline int getc(){
static const int L=1<<15;
static char buf[L],*S=buf,*T=buf;
if(S==T){
T=(S=buf)+fread(buf,1,L,stdin);
if(S==T)
return EOF;
}
return*S++;
}
inline int getint(){
int c;
while(!isdigit(c=getc()));
int x=c-'0';
while(isdigit(c=getc()))
x=(x<<1)+(x<<3)+c-'0';
return x;
}
int main(){
//freopen("tt.in","r",stdin);
int n,Q,A;
cin>>n>>Q>>A;
int i,j;
for(i=1;i<=n;++i)
a[i]=getint(),w[i]=a[i];
sort(w+1,w+n+1);
int id=0;
for(i=1;i<=n;){
for(j=i;j!=n&&w[j]==w[j+1];++j);
sav[++id]=w[i];
i=j+1;
}
sav[id+1]=inf;
for(i=1;i<=n;++i){
qu[i]=i;
a[i]=lower_bound(sav+1,sav+id+1,a[i])-sav;
}
sort(qu+1,qu+n+1,cmp);
int x,y,z;
for(i=1;i<n;++i){
x=getint();
y=getint();
z=getint();
make(x,y,z);
}
dfs(1,-1);
rmq_init();
divide(1);
for(i=1;i<=n;++i)
up(qu[i],a[qu[i]]);
for(i=1;i<=n;++i){
ins[i]->tim.pb(inf);
ins[i]->_tim.pb(inf);
ins[i]->__tim.pb(inf);
}
ll ans=0;
int u,l,r;
while(Q--){
u=getint();
l=getint();
r=getint();
l=(ans+l)%A,r=(ans+r)%A;
if(l>r)
swap(l,r);
--l;
ans=0;
if(l>=sav[1])
ans-=query(u,upper_bound(sav+1,sav+id+2,l)-sav-1);
if(r>=sav[1])
ans+=query(u,upper_bound(sav+1,sav+id+2,r)-sav-1);
//printf("%I64d\n",ans);
printf("%lld\n",ans);
}
return 0;
}
BZOJ1511
首先KMP,然后令$ans_i$表示前缀$i$的答案,然后依照我的代码分类讨论...就没了.
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
char s[1000010];
int next[1000010],ans[1000010];
int main(){
int n;
scanf("%d",&n);
int i,j=0;
scanf("%s",s+1);
long long res=0;
for(i=2;i<=n;++i){
for(;j&&s[j+1]!=s[i];j=next[j]);
if(s[j+1]==s[i])
++j;
next[i]=j;
if(next[i]){
if(i%(i-next[i])==0)
ans[i]=next[i]+ans[i-next[i]];
else
ans[i]=i-i%(i-next[i])+ans[i%(i-next[i])];
}
}
for(i=1;i<=n;++i)
res+=ans[i];
cout<<res<<endl;
return 0;
}
BZOJ2850
基本全是KDTree,我们考虑一种复杂度稳定的算法吧...
我们将点分块,分成$\sqrt{n}$块,每块$\sqrt{n}$个点,那么每个块都有$O(n)$个斜率,对于每个块,我们把所有的询问离线进去跟斜率一起排序,维护一个点的序列使得点到当前向量的有向距离是有序的,然后斜率每一次改变相当于只是交换了对应两个点在序列中的位置.
我们用一个树状数组维护一下就行了,询问的时候直接二分.
于是这样的复杂度是$O(\sqrt{n}\times((n+m)logn))$.
可是细节太多...
我决定写KDTree辣!
BZOJ2028
set随便玩...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int> pii;
set<pii>be,en;
#define mp make_pair
#define N 200010
char s[10];
int _be[N],_en[N];
int main(){
int n;
scanf("%d",&n);
int cnt=0,now=0,num,lab;
set<pii>::iterator it,next;
while(n--){
scanf("%s",s);
if(s[0]=='A'){
++cnt;
num=0;
++now;
scanf("%d%d",&_be[cnt],&_en[cnt]);
it=en.lower_bound(mp(_be[cnt],0));
while(1){
if(it==en.end()||_be[(*it).second]>_en[cnt])
break;
--now;
++num;
lab=(*it).second;
next=it,++next;
be.erase(be.find(mp(_be[lab],lab)));
en.erase(en.find(mp(_en[lab],lab)));
it=next;
}
be.insert(mp(_be[cnt],cnt));
en.insert(mp(_en[cnt],cnt));
printf("%d\n",num);
}
else
printf("%d\n",now);
}
return 0;
}
BZOJ4134
我忽略了一点,那就是Trie树是可以在$O(logn)$时间内求出mex的!
这样随便yy就是带标记Trie树合并啦?
如何求mex呢?首先考虑左子树,如果没有满就进入左子树,否则进入右子树.
又如何合并呢?我们类比线段树合并,首先下传这个点的标记,然后下去合并就行了.由于都是自顶向下,是不矛盾的.
我要写一写!
时间复杂度$O(nlogn)$,并不用启发式合并.
代码慢到死.
其实线段树合并为什么是$O(nlogn)$的呢...
感觉我现在还不十分理解.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define Log 29
struct Node{
Node*l,*r;
bool full;
int c;
Node():full(0),c(0){}
}mem[N*100],*P=mem,Tnull,*null=&Tnull;
inline Node*newnode(){
P->l=P->r=null;
P->full=0,P->c=0;
return P++;
}
inline void addit(Node*p,int _c,int d){
p->c^=_c;
if((_c>>d)&1)
swap(p->l,p->r);
}
inline void down(Node*p,int d){
if(p==null)
return;
if(p->c){
if(p->l!=null)
addit(p->l,p->c,d-1);
if(p->r!=null)
addit(p->r,p->c,d-1);
p->c=0;
}
}
inline void copy(Node*&x,Node*y){
if(y==null)
x=null;
else
*x=*y;
}
Node*Merge(Node*x,Node*y,int d){
down(x,d);
down(y,d);
Node*ret=newnode();
if(x==null||y==null){
copy(ret,x==null?y:x);
return ret;
}
else if(d==-1){
ret->full=x->full|y->full;
return ret;
}
else{
ret->l=Merge(x->l,y->l,d-1);
ret->r=Merge(x->r,y->r,d-1);
ret->full=ret->l->full&ret->r->full;
}
return ret;
}
inline void insert(Node*&p,int x,int d){
if(p==null)
p=newnode();
if(d==-1){
p->full=1;
return;
}
insert((x>>d)&1?p->r:p->l,x,d-1);
p->full=p->l->full&p->r->full;
}
inline int mex(Node*p,int d){
if(p==null)
return 0;
down(p,d);
if(d==-1)
return p->full?0:1;
if(p->l->full)
return (1<<d)+mex(p->r,d-1);
else
return mex(p->l,d-1);
}
int col[N];
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q++;
}
inline void make(int a,int b){
addedge(a,b);
addedge(b,a);
}
int pa[N];
inline void dfs(int x,int fa){
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
pa[end[j]]=x;
dfs(end[j],x);
}
}
}
inline int getpa(int x){
int t;
for(t=pa[x];t&&col[t];t=pa[t]);
return t;
}
vector<int>son[N];
int sg[N],sum[N];
Node*root[N];
inline void solve(int x){
if(son[x].size()==0){
sg[x]=1;
insert(root[x]=null,0,Log);
return;
}
int i,j;
for(i=0;i<son[x].size();++i){
solve(son[x][i]);
sum[x]^=sg[son[x][i]];
}
root[x]=null;
insert(root[x],sum[x],Log);
for(i=0;i<son[x].size();++i){
addit(root[son[x][i]],sum[x]^sg[son[x][i]],Log);
root[x]=Merge(root[x],root[son[x][i]],Log);
}
sg[x]=mex(root[x],Log);
}
int ans[N];
inline void getans(int x,int lastxor){
ans[x]=lastxor^sum[x];
for(int i=0;i<son[x].size();++i)
getans(son[x][i],ans[x]^sg[son[x][i]]);
}
vector<int>tot;
int main(){
//freopen("tt.in","r",stdin);
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&col[i]);
int a,b;
for(i=1;i<n;++i){
scanf("%d%d",&a,&b);
make(a,b);
}
dfs(1,-1);
int _pa;
for(i=1;i<=n;++i)
if(!col[i]){
_pa=getpa(i);
son[_pa].push_back(i);
}
solve(0);
getans(0,0);
for(i=1;i<=n;++i)
if(!col[i]&&!ans[i])
tot.push_back(i);
if(tot.size()==0)
puts("-1");
else
for(i=0;i<tot.size();++i)
printf("%d\n",tot[i]);
return 0;
}
BZOJ3294
令$f[i][j][k]$表示前$i$种颜色占据$j$行$k$列的方案数,令$g[i][j][k]$表示$i$个棋子占满$j$行$k$列的方案数.
则有:$f[i][j][k]=\sum_{_j}\sum_{_k}f[i-1][j-_j][k-_k]\times{C_{j}^{_j}\times{C_{k}^{_k}}\times{g[x_i][_j][_k]}}$
关键是$g$怎么求.
我们考虑,如果用更少的行数和列数就能够占满,那么剩下的行和列一定都是空的.
故而我们利用补集转化,具体看代码.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int mod=(1e9)+9;
inline void inc(int&x,int y){
if((x+=y)>=mod)
x-=mod;
}
inline void dec(int&x,int y){
if(x>=y)
x-=y;
else
x=x+mod-y;
}
int C[1510][1510];
int f[15][35][35],g[1010][35][35];
inline void getG(int x,int n,int m){
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
g[x][i][j]=C[i*j][x];
for(int _i=1;_i<=i;++_i)
for(int _j=1;_j<=j;++_j)
if(_i*_j<i*j)
dec(g[x][i][j],(long long)g[x][_i][_j]*C[i][_i]%mod*C[j][_j]%mod);
}
}
int main(){
//freopen("tt.in","r",stdin);
int n,m,c;
cin>>n>>m>>c;
int i,j,k;
for(C[0][0]=C[1][0]=C[1][1]=1,i=2;i<=n*m;++i){
C[i][0]=C[i][i]=1;
for(j=1;j<i;++j)
inc(C[i][j]=C[i-1][j],C[i-1][j-1]);
}
g[1][1][1]=1;
f[0][0][0]=1;
int x;
for(i=1;i<=c;++i){
scanf("%d",&x);
getG(x,n,m);
for(j=0;j<=n;++j)
for(k=0;k<=m;++k)
for(int _j=0;j+_j<=n;++_j)
for(int _k=0;k+_k<=m;++_k)
if(_j*_k>=x)
inc(f[i][j+_j][k+_k],(long long)f[i-1][j][k]*g[x][_j][_k]%mod*C[j+_j][_j]%mod*C[k+_k][_k]%mod);
}
int ans=0;
for(j=0;j<=n;++j)
for(k=0;k<=m;++k)
inc(ans,(long long)f[c][j][k]*C[n][j]%mod*C[m][k]%mod);
cout<<ans<<endl;
return 0;
}
弱省胡策Round7 A
我这个大傻叉只会$O(n^3)$,并且知道prufer序列之后也不会$O(n^2)$.
于是果断请教ZYF大爷.
首先肯定是要枚举环的长度$k$,关键的是剩下的怎么搞.
这个我现在还不是非常理解,等我稍微好一点了在进行解释...
弱省胡策Round7 B
对每个高度维护一颗线段树维护最长连续存在区间,注意到存在性是随着高度递减有包含关系的,所以直接用持久化线段树,空间复杂度$O(nlogn)$.
维护一个全局堆表示每个高度的答案,同时每次修改相当于对两个高度进行单点修改,直接改一下,然后在全局堆里面修改就行了.
于是时间复杂度$O((n+m)logn)$.
BZOJ4143
对于每一天分别维护最早结束的和最晚开始的.
BZOJ4144
首先spfa搞出对于每个点$x$到最近的加油站的距离$d[x]$.
然后对于原有的边$(x,y,w)$建立新边$(x,y,d[x]+d[y]+w)$.
然后将询问离线,每次插入所有权值不超过询问的边,并回答两个询问的点是否连通.
利用并查集维护即可.
正确性:我们考虑$(x,y)$如果在新边的意义下连通,那么脑补一下可以发现必定存在一个加油站序列使得两两之间的最短路不超限制.这样的话自然就是可达的了.
BZOJ4145
令$f[s]$表示在一家店购买集合$s$的最小值,令$g[s]$表示购买集合$s$的最小值.
枚举一遍更新出$f$,注意把到商店的费用也算上.
然后$O(3^n)$枚举子集状压dp.
BZOJ4146
令$f[i]$表示有多少数是$i$的倍数.
这个直接$O(nlogn)$求就行了.
然后枚举每个数作为约数的对即可.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2000010
int a[N];
int c[N],d[N];
int main(){
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&a[i]),++c[a[i]];
for(i=1;i<=2000000;++i)
for(j=i;j<=2000000;j+=i)
d[i]+=c[j];
long long ans=0;
for(i=1;i<=n;++i)
ans+=d[a[i]]-1;
cout<<ans<<endl;
return 0;
}
BZOJ4152
考虑每个点,以这个点为中心,在每个象限内,假设是代价为$delta_y$的那个象限,必定只有与这个点$y$的差的绝对值最小的点才有用.
于是这样只会有$O(n)$条边.
就可以做了.
BZOJ3608
个人以为和COT3并没有不同?
BZOJ2563
我们要从考虑答案的贡献入手.
假设现在有一个人要先手,我们考虑所有事情对先手-后手分数的贡献.
选择一个点:贡献$w_i$.
不选一个点:贡献$-w_i$.
一条边的两个端点都被选中:贡献$c_j$.
一条边只有一个端点被选中:贡献$0$.
一条边没有端点被选中:贡献$-c_j$.
我们发现这是一个等差数列,于是预先将答案加上$\sum{w_i}+\sum{c_j}$,于是现在的贡献分别变成:
$2w_i,0,2c_j,c_j,0$.
令每个点的贡献为$2w_i+c_j$,每个点的贡献都是独立的.
于是贪心从大到小选就行了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 10010
#define M 100010
int a[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
ll ans=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
ans-=a[i];
a[i]*=2;
}
int x,y,z;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
ans-=z;
a[x]+=z,a[y]+=z;
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i+=2)
ans+=a[i];
cout<<ans<<endl;
return 0;
}
2333
评论 (0)