2016年12月

BZOJ 2958&3269: 序列染色

December 26, 2016

###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1<=a<=b<c<=d<=N Sa,Sa+1,...,Sb均为B Sc,Sc+1,...,Sd均为W 其中b=a+K-1,d=c+K-1 由于方法可能很多，因此只需要输出最后的答案对109+7取模的结果。 ###Input 第一行两个正整数N,K 第二行一个长度为N的字符串S ###Output 一行一个整数表示答案%(109+7)。 ###Sample Input 5 2 XXXXX ###Sample Output 4 ###Solution 首先搞出B和W的前缀个数，那么可以O(1)判某段区间能否为B或W 然而这样对于超过K个的会算重 对于连续的B和W，考虑用最后K个计算，则不会算重（可以在序列最后加一个X，更好写） 状态可以设计成f[i][j][k]表示考虑前i位，状态为j，这一位选了k，j为0,1,2分别代表BW都没有，只有B，BW都有 转移看代码 ###Code ```c++ #include<bits/stdc++.h> #define mod 1000000007 int n,k,bp[1000010],wp[1000010],f[1000010][3][2]; char s[1000010]; int main() { scanf("%d%d%s",&n,&k,s+1); s[++n]='X'; for(int i=1;i<=n;i++) { bp[i]=bp[i-1]+(s[i]=='B'); wp[i]=wp[i-1]+(s[i]=='W'); } f[0][0][0]=1; for(int i=1;i<=n;i++) { if(s[i]=='B'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(s[i]=='W'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(i<=k)continue; if((s[i]=='B'||s[i]=='X')&&!(bp[i-1]-bp[i-k-1])) { f[i][2][0]=(f[i][2][0]+f[i-k][1][1])%mod; f[i][1][0]=(f[i][1][0]-f[i-k][1][1])%mod; } if((s[i]=='W'||s[i]=='X')&&!(wp[i-1]-wp[i-k-1])) { f[i][1][1]=(f[i][1][1]+f[i-k][0][0])%mod; f[i][0][1]=(f[i][0][1]-f[i-k][0][0])%mod; } } int ans=f[n][2][0]; if(ans<0)ans+=mod; printf("%d\n",ans); } ```

BZOJ 4398: 福慧双修

December 26, 2016

###Description 菩萨为行，福慧双修，智人得果，不忘其本。 ——唐朠立《大慈恩寺三藏法师传》 有才而知进退，福慧双修，这才难得。 ——乌雅氏 如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有N块区域，M条小路，两块区域之间可通过小路连接起来。现在甄嬛站在1号区域，而她需要在御花园中绕一绕，且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到1号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。 ###Input 第一行仅2个正整数n,m，意义如题。 接下来m行每行4个正整数s,t,v,w，其中s,t为小路所连接的两个区域的编号，v为甄嬛从s到t所需的时间，w为甄嬛从t到s所需的时间。数据保证无重边。 ###Output 仅一行，为甄嬛回到1号区域所需的最短时间，若方案不存在，则输出-1 ###Sample Input 3 3 1 2 2 3 2 3 1 4 3 1 5 2 ###Sample Output 8 ###Solution 一条合法路径一定是1->a->...->b->1这样的 考虑a和b一定有至少一个二进制位不同 所以按二进制分组，每次新建一个源点和汇点，分别连向某位为1和0的点，然后跑最短路 ###Code ```c++ #include<bits/stdc++.h> #define mp(a,b) std::make_pair(a,b) int n,p[40001],dis[40001]; bool vis[40001]; std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >, std::greater<std::pair<int,int> > >q; struct edge { int to,ne,w; }e[200001]; inline void add(int i,int a,int b,int w) { e[i].to=b,e[i].ne=p[a],e[i].w=w,p[a]=i; } inline void yjq(int andv,int anda,int &ans) { memset(dis,0x7f,sizeof(dis)); memset(vis,0,sizeof(vis)); for(int j=p[1];j;j=e[j].ne) if((e[j].to&andv)==anda) q.push(mp(dis[e[j].to]=e[j].w,e[j].to)); while(!q.empty()) { int k=q.top().second;q.pop(); if(vis[k])continue; vis[k]=1; for(int j=p[k];j;j=e[j].ne) if(e[j].to==1) { if((k&andv)!=anda&&ans>dis[k]+e[j].w)ans=std::min(ans,dis[k]+e[j].w); } else if(dis[e[j].to]>dis[k]+e[j].w) { q.push(mp(dis[e[j].to]=dis[k]+e[j].w,e[j].to)); } } } int main() { int m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); add(i*2+1,a,b,c); add(i*2+2,b,a,d); } int ans=0x7fffffff; for(int i=1;i<=n;i<<=1) { yjq(i,i,ans); yjq(i,0,ans); } printf("%d",ans); } ```

BZOJ 2432: [Noi2011]兔农

December 20, 2016

###Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？ 聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。 ###Input 输入一行，包含三个正整数n, k, p。 ###Output 输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。 ###Sample Input 6 7 100 ###Sample Output 7 ###Solution 按模k余数写出数列，则为 1,1,...,a,0, a,a,...,b,0, b,b,...,c,0, ... 这个数列最后有可能每一排首项循环，也有可能不再出现0 每次求a的逆元，则其在fib数列中首次出现位置就是a后面下一个0的位置，如果没有0特判 ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) void exgcd(int a,int b,int &x,int &y){if(b)exgcd(b,a%b,y,x),y-=(a/b)*x;else x=1,y=0;} ll n; int k,p,pos[1000000],f[6000010]={0,1,1},p2[1000000]; struct mat { int a[3][3]; inline void operator *=(mat x) { ll t[3][3];memset(t,0,sizeof(t)); fo0(i,3)fo0(j,3)fo0(k,3)t[i][k]+=(ll)a[i][j]*x.a[j][k]; fo0(i,3)fo0(j,3)a[i][j]=t[i][j]%p; } inline mat operator *(mat x) { mat r=*this;r*=x;return r; } }; mat pow(mat a,ll p) { mat r=(mat){1,0,0,0,1,0,0,0,1}; for(;p;p>>=1,a*=a)if(p&1)r*=a; return r; } struct data { int st,len;mat x; }s[1000001]; inline mat get(ll n,int tt) { mat r=(mat){1,0,0,0,1,0,0,0,1}; if(!n)return r; for(;n>=s[tt].len;n-=s[tt++].len)r*=s[tt].x; return r*pow((mat){0,1,0,1,1,0,0,0,1},n); } int main() { scanf("%lld%d%d",&n,&k,&p); for(int i=3;;i++) { f[i]=f[i-1]+f[i-2]; if(f[i]>=k)f[i]-=k; if(!pos[f[i]])pos[f[i]]=i; if(f[i]==1&&f[i-1]==0)break; } int ns=1,sc=1; for(;!p2[ns];sc++) { s[sc].st=ns; p2[ns]=sc; int t1,t2; exgcd(k,ns,t1,t2); if(t2<0)t2+=k; t1=pos[t2]; if((ll)ns*t2%k!=1||!t1)break; s[sc].len=t1; s[sc].x=pow((mat){0,1,0,1,1,0,0,0,1},t1-1)*(mat){0,1,0,1,1,0,0,-1,1}; ns=(ll)ns*f[t1-1]%k; } mat bfm=(mat){1,0,0,0,1,0,0,0,1},lpm=(mat){1,0,0,0,1,0,0,0,1},ans=(mat){1,0,0,0,1,0,0,0,1}; ll bf=0,lp=0; fo1(i,p2[ns]-1)bf+=s[i].len,bfm*=s[i].x; fo(i,p2[ns],sc-1)lp+=s[i].len,lpm*=s[i].x; if(!lp)lp=1,lpm=(mat){0,1,0,1,1,0,0,0,1}; if(n<bf) { ans*=get(n,1); } else { ans*=bfm;n-=bf; ans*=pow(lpm,n/lp); ans*=get(n%lp,p2[ns]); } int a1=ans.a[0][1]+ans.a[2][1]; while(a1>=p)a1-=p;while(a1<0)a1+=p; printf("%d\n",a1); } ```

BZOJ 3552: 最右非零的数

December 16, 2016

###Description 给出正整数N（可能有前导0），请求出N!最右非零的数位的值。 ###Input 第一行一个数T表示数据组数 下接T行每行一个数N表示一组数据 ###Output 对于每组数据，输出一行一个数表示这组数据的答案 ###Sample Input 2 5 4 ###Sample Output 2 4 ###Solution 随便lucas一下就好了，然而懒得写高精，就用了python，于是实力rank last ###Code ```python T=int(raw_input()) for I in range(T): n=int(raw_input());t=n;a=0;b=0;c=1 while t>0:t/=2;a+=t while n>0:c=c*[1,1,2,1,4,4,4,3,4,1][n%10]%5;n/=5;b+=n a=a-b+1 if a>1:a=0 t=3 while b>0: if b&1:c=c*t%5 t=t*t%5 b/=2 print (a*5+c*6)%10 ```

BZOJ 4539: [Hnoi2016]树

December 16, 2016

###Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图： ![11(4).png][1] 根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示 ![22(2).png][2] 现在他想问你，树中一些结点对的距离是多少。 ###Input 第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000 ###Output 输出Q行，每行一个整数，第 i行是第 i个询问的答案。 ###Sample Input 5 2 3 1 4 1 3 4 2 4 5 4 3 3 2 6 9 1 8 5 3 ###Sample Output 6 3 3 ###Solution 先对模板树求lca，并按dfs序建一棵主席树 每次向大树上加子树时，先二分查找他的父亲在哪一块，然后在主席树上查接到哪个节点下面 对于每一块，存它的根节点与根节点的父亲在模板树中的编号 然后把每一块视做节点，可以得到一棵大树，对大树也求lca 处理查询时，需要分3种情况：在同一块中，两块在一条链上，两块不在一条链上 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define N 100000 namespace zx { struct node { int lc,rc,cnt; }s[2000000]; int sm=1; int modify(int x,int l,int r,int p) { int t=sm++; s[t]=s[x]; s[t].cnt++; if(l^r) { int f=(l+r)>>1; if(p<=f) s[t].lc=modify(s[x].lc,l,f,p); else s[t].rc=modify(s[x].rc,f+1,r,p); } return t; } int kth(int a,int b,int l,int r,int k) { if(l==r)return l; int t=s[s[a].lc].cnt-s[s[b].lc].cnt,f=(l+r)>>1; if(t>=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int n,m,q; namespace t1 { int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1]; struct edge { int to,ne; }e[N<<1]; inline void add(int x,int a,int b) { e[x].to=b,e[x].ne=p[a],p[a]=x; } void dfs(int x) { sz[x]=1; id[x]=++idm; zx::root[id[x]]=zx::modify(zx::root[id[x]-1],1,n,x); for(int i=p[x];i;i=e[i].ne) if(e[i].to^fa[x][0]) fa[e[i].to][0]=x,dep[e[i].to]=dep[x]+1,dfs(e[i].to),sz[x]+=sz[e[i].to]; idr[x]=idm; } inline int dis(int x,int y) { int a=x,b=y,ret=0; if(dep[a]<dep[b]) { for(int i=16;~i;i--) if((dep[b]-dep[a])&(1<<i)) ret+=1<<i,b=fa[b][i]; } else if(dep[a]>dep[b]) { for(int i=16;~i;i--) if((dep[a]-dep[b])&(1<<i)) ret+=1<<i,a=fa[a][i]; } if(a==b)return ret; for(int i=16;~i;i--) if(fa[a][i]^fa[b][i]) a=fa[a][i],b=fa[b][i],ret+=1<<i+1; return ret+2; } } namespace t2 { int cnt=1; ll id[N+1],nid; struct data { int a,b,dep,fa[17],di[17]; }s[N+1]; inline void link(int a,ll b) { int c=std::upper_bound(id,id+cnt,b)-id-1; int cf=s[c].a,d=zx::kth(zx::root[t1::idr[cf]],zx::root[t1::id[cf]-1],1,n,b-id[c]+1); s[cnt].a=a; s[cnt].b=d; s[cnt].dep=s[c].dep+1; s[cnt].fa[0]=c; s[cnt].di[0]=t1::dis(cf,d)+1; id[cnt]=nid; nid+=t1::sz[a]; cnt++; } inline void init() { for(int i=0;i<16;i++) for(int j=0;j<cnt;j++) s[j].fa[i+1]=s[s[j].fa[i]].fa[i],s[j].di[i+1]=s[j].di[i]+s[s[j].fa[i]].di[i]; } inline int lca(int x,int y) { int a=x,b=y; if(s[a].dep<s[b].dep) { for(int i=16;~i;i--) if((s[b].dep-s[a].dep)&(1<<i)) b=s[b].fa[i]; } else if(s[a].dep>s[b].dep) { for(int i=16;~i;i--) if((s[a].dep-s[b].dep)&(1<<i)) a=s[a].fa[i]; } if(a==b)return a; for(int i=16;~i;i--) if(s[a].fa[i]^s[b].fa[i]) a=s[a].fa[i],b=s[b].fa[i]; return s[a].fa[0]; } inline ll linkdis(int p,int q,int x,int y) { ll ret=t1::dis(x,s[p].a)+1; for(int i=16;~i;i--) if((s[p].dep-s[q].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; return ret+t1::dis(s[p].b,y); } inline ll dis(ll x,ll y) { int p=std::upper_bound(id,id+cnt,x)-id-1,q=std::upper_bound(id,id+cnt,y)-id-1; int xid=zx::kth(zx::root[t1::idr[s[p].a]],zx::root[t1::id[s[p].a]-1],1,n,x-id[p]+1); int yid=zx::kth(zx::root[t1::idr[s[q].a]],zx::root[t1::id[s[q].a]-1],1,n,y-id[q]+1); if(p==q)return t1::dis(xid,yid); int t=lca(p,q); if(t==p)return linkdis(q,p,yid,xid); if(t==q)return linkdis(p,q,xid,yid); ll ret=t1::dis(xid,s[p].a)+t1::dis(yid,s[q].a)+2; for(int i=16;~i;i--) if((s[p].dep-s[t].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; for(int i=16;~i;i--) if((s[q].dep-s[t].dep-1)&(1<<i)) ret+=s[q].di[i],q=s[q].fa[i]; return ret+t1::dis(s[p].b,s[q].b); } } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); t1::add(i<<1,a,b); t1::add(i<<1|1,b,a); } zx::root[0]=zx::sm++; t1::fa[1][0]=1; t1::dfs(1); for(int i=0;i<16;i++) for(int j=1;j<=n;j++) t1::fa[j][i+1]=t1::fa[t1::fa[j][i]][i]; t2::s[0].a=1; t2::id[0]=1; t2::nid=n+1; while(m--) { int a; ll b; scanf("%d%lld",&a,&b); t2::link(a,b); } t2::init(); while(q--) { ll a,b; scanf("%lld%lld",&a,&b); printf("%lld\n",t2::dis(a,b)); } } ``` [1]: /usr/uploads/2016/12/1348856476.png [2]: /usr/uploads/2016/12/2791822739.png

BZOJ 1176&2683&4066

December 11, 2016

[传送门][1] [传送门][2] [传送门][3] 题目大意：单点加，矩阵查询 直接上kdtree就好了，定期暴力重构 1176题代码： ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} template<typename T> T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) namespace kd { const int D=2,inf=1000000000; char dnow; struct point { int d[D],val; int operator[](int x){return d[x];} }; inline bool operator<(point a,point b) { return a[dnow]<b[dnow]; } inline int dis(point a,point b){int ret=0;for(int i=0;i<D;i++)ret+=abs(a[i]-b[i]);return ret;} struct kdnode { point p; int sum,l[D],r[D],lc,rc; }; int ans,tm=2; point q1,q2,Q,*P; kdnode t[200010]; inline void update(int k) { for(int i=0;i<D;i++) { if(t[k].lc)repl(t[k].l[i],t[t[k].lc].l[i]),repr(t[k].r[i],t[t[k].lc].r[i]); if(t[k].rc)repl(t[k].l[i],t[t[k].rc].l[i]),repr(t[k].r[i],t[t[k].rc].r[i]); } t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum; } inline void init(int x) { for(int i=0;i<D;i++)t[x].l[i]=t[x].r[i]=t[x].p[i];t[x].sum=t[x].p.val; } int build(int l,int r,char now) { if(now==D)now=0; dnow=now; int mid=(l+r)>>1,x=tm++; std::nth_element(P+l,P+mid,P+r+1); t[x].p=P[mid]; t[x].lc=t[x].rc=0; init(x); if(l<mid)t[x].lc=build(l,mid-1,now+1); if(r>mid)t[x].rc=build(mid+1,r,now+1); update(x);return x; } void insert(int k,char now) { if(now==D)now=0; if(Q[now]>=t[k].p[now]) { if(t[k].rc) insert(t[k].rc,now+1); else { t[k].rc=tm++;t[t[k].rc].p=Q; init(t[k].rc); } } else { if(t[k].lc) insert(t[k].lc,now+1); else { t[k].lc=tm++;t[t[k].lc].p=Q; init(t[k].lc); } } update(k); } void query(int k,char now) { if(now==D)now=0; bool tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i]) tag=0; if(tag){ans+=t[k].sum;return;} tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i]) tag=0; if(tag)ans+=t[k].p.val; tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].lc)query(t[k].lc,now+1); tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].rc)query(t[k].rc,now+1); } inline void build(point *p,int n){P=p;build(0,n-1,0);} inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;} inline void insert(point p){Q=p;insert(1,0);} } kd::point pp[200000]; int main() { int cx,n=0,opt; kd::point a,b; scanf("%d%*d",&cx); while(1) { scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val); kd::insert(pp[n++]); } else if(opt==2) { scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]); printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1)); } else return 0; if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n); } } ``` 过不了就适当调参 [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=1176 [2]: http://www.lydsy.com/JudgeOnline/problem.php?id=2683 [3]: http://www.lydsy.com/JudgeOnline/problem.php?id=4066

BZOJ 3697: 采药人的路径

December 5, 2016

###Description 采药人的药田是一个树状结构，每条路径上都种植着同种药材。 采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。 采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。 ###Input 第1行包含一个整数N。 接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。 ###Output 输出符合采药人要求的路径数目。 ###Sample Input 7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1 ###Sample Output 1 ###HINT 对于100%的数据，N ≤ 100,000。 ###Solution 点分治，边权为0变成-1，dfs时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2]; ll ans; bool vis[100001]; struct edge { int to,ne,w; }e[200000]; inline void add(int a,int b,int w) { e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++; } void dfs1(int x,int fa) { sz[x]=1; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs1(e[i].to,x),sz[x]+=sz[e[i].to]; } void dfs2(int x,int fa) { bool ok=sz[ro]<=2*sz[x]; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) { dfs2(e[i].to,x); if(sz[e[i].to]*2>sz[ro])ok=0; } if(ok)nro=x; } void dfs3(int x,int fa,int len) { if(len) { if(apr[len+n]) ans+=cnt[n-len][0]; else ans+=cnt[n-len][1]; } else { if(apr[len+n]) ans+=cnt[n][0]+1; else ans+=cnt[n][0]; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs3(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs4(int x,int fa,int len) { if(len) { if(apr[len+n]) cnt[n+len][0]++,cnt[n+len][1]++; else cnt[n+len][0]++; } else { cnt[n][0]++; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs4(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs5(int x,int fa,int len) { cnt[n+len][0]=cnt[n+len][1]=0; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs5(e[i].to,x,len+e[i].w); } void solve(int x) { dfs1(x,0); ro=x; dfs2(x,0); vis[nro]=1; for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w); dfs5(nro,0,0); for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])solve(e[i].to); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c?c:-1),add(b,a,c?c:-1); } solve(1); printf("%lld\n",ans); } ```

BZOJ 4700: 适者

December 1, 2016

###Description 敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制， 每回合进程如下： ·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值<0则被破坏。 ·2 敌方每台未被破坏的人形兵器攻击我方基地造成Ai点损失。 但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损 失。 ###Input 第一行两个数n，ATK，表示敌方人形兵器数量和我方人形兵器攻击力。 接下来n行，每行两个数A，Di，表示对方第i台人形兵器的攻击力和护甲值。 3<=n<=3×10^5，Ai，Di<=10^4，ATK<10^4 ###Output 只一行，一个数，表示最好情况下我方基地会受到的损失总和。 ###Sample Input 3 7 30 8 7 35 1 209 ###Sample Output 28 ###Solution 每个敌人被杀所需时间为 Ti=Di/atk+1 设T的前缀和为P，A的后缀和为S 假设没有秒杀，按Ti/Ai排序后依次杀即可，每个敌人对答案的贡献为Si\*Ti-Ai 假设（排序后）秒杀了i和j（假设i<j） 那么我方损失会减少 Si\*Ti + P(i-1)\*Ai - Ai + Sj\*Tj + P(j-1)\*Aj - Aj - Ti\*Aj 注意最后 -Ti\*Aj 是因为算了两次 由于只有 Ti\*Aj 与 i,j 均有关，这个表达式可以看成一个以Ti为变量的一次函数 若从后往前扫，就可以看成动态维护一些直线的凸包 这个用线段树就可以维护，每个节点存一条直线，标记永久化 修改时，找到两直线交点，把距端点更短的一部分pushdown 查询时把路径上所有节点取max ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct line { ll k,b; }s[35000]; void modify(int x,int l,int r,line p) { if(s[x].k==p.k) { repr(s[x].b,p.b); return; } int t=(l+r)>>1; db f=(db)(p.b-s[x].b)/(s[x].k-p.k); if(f<l||f>r||l==r) { if(p.k*t+p.b>s[x].k*t+s[x].b)s[x]=p; return; } if(f<t+0.5) { if(p.k*r+p.b>s[x].k*r+s[x].b)std::swap(s[x],p); modify(x<<1,l,t,p); } else { if(p.k*l+p.b>s[x].k*l+s[x].b)std::swap(s[x],p); modify(x<<1|1,t+1,r,p); } } ll query(int x,int l,int r,int p) { ll ret=s[x].k*p+s[x].b; if(l!=r) { int t=(l+r)>>1; if(p<=t) repr(ret,query(x<<1,l,t,p)); else repr(ret,query(x<<1|1,t+1,r,p)); } return ret; } struct yjq { int a,t; ll as,tp; inline bool operator <(const yjq &x)const { return (ll)x.a*t<(ll)a*x.t; } }p[300000]; int n,atk; int main() { scanf("%d%d",&n,&atk); for(int i=0;i<n;i++) scanf("%d%d",&p[i].a,&p[i].t),p[i].t=(p[i].t-1)/atk+1; std::sort(p,p+n); for(int i=1;i<n;i++) p[i].tp=p[i-1].tp+p[i-1].t; p[n-1].as=p[n-1].a; for(int i=n-2;i>=0;i--) p[i].as=p[i+1].as+p[i].a; for(int i=0;i<35000;i++) s[i].b=-1e18; ll ta=0; for(int i=n-1;i>=0;i--) { ll tmp=p[i].as*p[i].t+p[i].tp*p[i].a-p[i].a; repr(ta,query(1,1,10000,p[i].t)+tmp); modify(1,1,10000,(line){-p[i].a,tmp}); } ll ans=0; for(int i=0;i<n;i++) ans+=p[i].as*p[i].t-p[i].a; ans-=ta; printf("%lld\n",ans); } ```