NOIP模拟题 2015.8.2 T3
题解：有一个暴力是将r-l+1个数排序之后从小到大加，设已经加的数的和为s，当前要加ai，如果s<ai-1则不能加s（然而这个我在考场上面都没想到）于是正解就是优化一下，考虑每次加数把可以加的都加进来，于是s每次扩大一倍，至于加哪些数可以用主席树，复杂度为n log^2 n。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 1073741824
int gf[N],st=0,s[N*50],c[N*50][2],v[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int Set_up(int x,int y,int z,int o)
{
int i=x + y >> 1,j=++st;
if (x==y) {s[j]=s[z]+o;return j;}
if (o<=i) c[j][1]=c[z][1],c[j][0]=Set_up(x,i,c[z][0],o);else
c[j][0]=c[z][0],c[j][1]=Set_up(i+1,y,c[z][1],o);
s[j]=s[c[j][0]]+s[c[j][1]];
return j;
}
int Find(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=0;
if (x==p&&y==u) return s[o]-s[z];
if (p<=i) j=Find(x,i,c[z][0],c[o][0],p,min(u,i));
if (u>i) j+=Find(i+1,y,c[z][1],c[o][1],max(p,i+1),u);
return j;
}
int Solve(int y,int x)
{
int k=0,l=0,q=0;
do
{
l=Find(0,M-1,gf[x-1],gf[y],q+1,k+1);
if (!l) return k+1;
q=k+1;k=k+l;
} while (1);
}
int main()
{
freopen("hhsum.in","r",stdin);
freopen("hhsum.out","w",stdout);
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++)
gf[i]=Set_up(0,M-1,gf[i-1],v[i]);
m=Read();
while (m--)
printf("%d\n",Solve(Read(),Read()));
return 0;
}
NOIP模拟题 2015.8.1 T2
感觉题解还是要放的正常向一点，还是一题一题放吧= =
题意：给定一张无向图，每条边有通过这条边消耗的油量，有一些点是加油点，可以补满油，然后有q个询问从一个加油点往另外一个加油点走，油箱容量为v，问能否到达。
输入格式：第一行四个整数n m p k分别是点、边、询问和加油点数，第二行k个加油点的编号，接着m行每行三个整数u、v和d代表u和v之间有耗油为d的边相连，最后p行每行三个整数u、v、d询问u到v在容量只有d的时候能否到达
输出格式：q行“YES”或者“NO”
Sample Input:
题解：这题之前VFK讲课时讲过，不，应该说则就是VFK出的题。然而并忘（睡）了= =，而且T3是一道恶心的点分治/set启发式合并题，写的比较蛋痛，也没时间想这道题了。
然而这题有个结论：设点i的最近加油点为Ai，这两点的距离为Si，于是我们考虑重建一个只有加油点的图，原来的连i-j的边变成Ai-Aj，边权变成Si+Sj+Vi-j。由于脑补可以发现这样是不会使两点之间距离变大，如果有一条经过非加油点u、v的路径i->u->v->j并且i和j不是u、v的最近点的话画一画图可以发现在走去Ai和Aj一定是会更优的
于是设一个S连向所有加油点，SPFA一下求出所有点的Ai，然后就是最小生成树还有倍增了= =
话说在这里贴一张VFK题解：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
#define N 300050
#define M 1000050
#define fr first
#define sc second
#define INF 0x7f7f7f7f
pair <int,int> yz[M];
int ne[M*2][3],ln[M][3],fi[N],nr[N],sg[N],n,m,ff[N];
int ss=1,s[N],gf,qu,zy,fa[N][20],ma[N][20],h[N];
queue <int> li;
bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
ne[++ss][0]=y;ne[ss][1]=fi[x];ne[ss][2]=z;fi[x]=ss;
ne[++ss][0]=x;ne[ss][1]=fi[y];ne[ss][2]=z;fi[y]=ss;
}
void SPFA()
{
for (int i=1;i<=n;i++) s[i]=INF;
for (int i=1;i<=zy;i++)
s[sg[i]]=0,li.push(sg[i]),b[sg[i]]=1,nr[sg[i]]=sg[i];
while (!li.empty())
{
int k=li.front();li.pop();b[k]=0;
for (int i=fi[k];i;i=ne[i][1])
if (s[ne[i][0]]>s[k]+ne[i][2])
{
s[ne[i][0]]=s[k]+ne[i][2];nr[ne[i][0]]=nr[k];
if (!b[ne[i][0]])
b[ne[i][0]]=1,li.push(ne[i][0]);
}
}
return;
}
int Find(int x)
{return ff[x]==x?x:(ff[x]=Find(ff[x]));}
void Kruskal()
{
sort(yz+1,yz+m+1);
for (int i=1;i<=m;i++)
{
int k=nr[ln[yz[i].sc][0]],l=nr[ln[yz[i].sc][1]],
q=Find(k),w=Find(l);
if (q==w) continue;
ff[q]=w;Line(k,l,yz[i].fr);
}
return;
}
void Set_up()
{
memset(s,0,sizeof(s));
gf=sg[1];li.push(gf);s[gf]=1;
while (!li.empty())
{
int k=li.front();li.pop();
for (int i=fi[k];i;i=ne[i][1])
if (!s[ne[i][0]])
s[ne[i][0]]=s[k]+1,fa[ne[i][0]][0]=k,
ma[ne[i][0]][0]=ne[i][2],li.push(ne[i][0]);
}
for (int i=1;i<=18;i++)
{
for (int j=1;j<=zy;j++)
ma[sg[j]][i]=max(ma[sg[j]][i-1],
ma[fa[sg[j]][i-1]][i-1]),
fa[sg[j]][i]=fa[fa[sg[j]][i-1]][i-1];
}
return;
}
int Query(int x,int y)
{
int k=0;
if (s[x]<s[y]) swap(x,y);
for (int i=18;i>=0;i--)
if (s[x]-(1 << i)>=s[y])
k=max(k,ma[x][i]),x=fa[x][i];
for (int i=18;i>=0;i--)
if (fa[x][i]!=fa[y][i])
k=max(max(k,ma[x][i]),ma[y][i]),x=fa[x][i],y=fa[y][i];
if (x!=y)
k=max(max(k,ma[x][0]),ma[y][0]);
return k;
}
int main()
{
freopen("petrol.in","r",stdin);freopen("petrol.out","w",stdout);
n=Read();m=Read();zy=Read();qu=Read();
for (int i=1;i<=zy;i++) sg[i]=Read(),ff[sg[i]]=sg[i];
for (int i=1;i<=m;i++)
ln[i][0]=Read(),ln[i][1]=Read(),ln[i][2]=Read(),
Line(ln[i][0],ln[i][1],ln[i][2]);
SPFA();ss=1;
memset(fi,0,sizeof(fi));
for (int i=1;i<=m;i++)
yz[i].sc=i,yz[i].fr=ln[i][2]+s[ln[i][0]]+s[ln[i][1]];
Kruskal();Set_up();
while (qu--)
{
int q=Read(),w=Read(),e=Read();
if (e>=Query(q,w)) puts("YES");else
puts("NO");
}
return 0;
}
UOJ #134
题面：给定一张无向图，然后将其中一些边定向，要求将剩下的无向边也定向，使得原无向图中的连通块在变成有向图之后还是在同一个强连通分量。（n,m<=5000）
题解：好神啊，考场上面并没有想出来，连60分暴力都斜挂了= =
有一个性质：在当前还没定向完的图中对于每条边的两个点u和v要不就u不通过这条边可以到达v，要不就是v可以不通过这条边可以到达u。然后就可以暴力遍历整张图然后判断是哪种情况就可以定向了。
看完证明感觉还是很有道理，移步这♂里♂
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5050
int b[N][N],d[N],n,m,fi[N],c[N*2][2],ss=1,ln[N][3],now;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;b[x][y]++;}
void DFS(int x)
{
d[x]=now;
for (int i=fi[x];i;i=c[i][1])
if (b[x][c[i][0]]&&d[c[i][0]]!=now) DFS(c[i][0]);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
ln[i][0]=Read();ln[i][1]=Read();ln[i][2]=Read();
Line(ln[i][0],ln[i][1]);
if (!ln[i][2]) Line(ln[i][1],ln[i][0]);
}
for (int i=1;i<=m;i++)
if (!ln[i][2])
{
now++;b[ln[i][0]][ln[i][1]]--;
DFS(ln[i][0]);b[ln[i][0]][ln[i][1]]++;
if (d[ln[i][1]]==now)
b[ln[i][0]][ln[i][1]]--,puts("1");else
b[ln[i][1]][ln[i][0]]--,puts("0");
} else puts("0");
return 0;
}
最近的几次比赛
最近感觉RP好吼，打了场BC的Rank1，还有UOJ的rank12，之前还有场CF div1
CF那场第三题挂的莫名其妙，但还是涨了100+RT，真是不知道smg
BC那场T2纯暴力一开始不敢写，还naive以为要用什么回文自动机这种我不会的高端东西，想了很久没想出来。后来弃疗去看UOJ群发现暴力大法可以过，虽然知道肯定会被hack但是还是交了一发暴力= =然后构造了一个可以hack掉我这个数据的N/2-1个a+1个b+1个c+N/2-1个d，感觉可以卡的死死的。room还是第五。后来hack时间随便点开了几个跟我的代码长得比较面善的hack掉了，而且还有个人一开始准备hack我，但是并没有得逞。然而我感觉这种暴力并很好hack啊，但是至少我们房间没什么人屑于= =不知道为什么。于是非常愉快的hack了4个人之后就结束了，复测完之后发现几个三题爷都挂掉了，然后本来还坐等第二题挂掉结果没能如愿，uwi十分魔性的在10分钟之内切掉前两题（主要是看出了第二题暴力），但是不屑于hack于是我神奇的rank1了，拿68元真是感到喜闻乐见。
然后后面那场BC感觉就比较caodan了，第二题题面简直什么鬼，rating掉掉掉！！！（话说最近几场BC的质量都很拙计啊）
昨天还用我那个负rating的大号考了UOJ，前面半小时撸完第一题，第二题弃疗之后交了个理论60分暴力，第三题提答题sxbk，我还不会用终端，于是后面耗掉一个小时摸索+膜duyege怎么破，然后30分钟准备随机十个点，然而喜闻乐见的是由于时间分配只搞出了6个点，并且在最后被网速成功卡掉最后的交题，不过还好分本来就不多，名次也只会升一名。后来看到12名感觉非常吓人（虽然之前考过一次rank 7的Goodbye Jiawu）但是看到参加人数感觉又比较正常。复测粗来第二题成功写跪20分，但是还好第一题只跪了extra test，第三题爆两分了，感觉还是比没分好TATQAQ2333。后面的人虽然都不是很认识，然而发现yali的两个大爷好像在后面的样子，主要都是T1跪了。。。
所以感觉最近RP还有rating都涨的比较喜闻乐见，我自然也喜闻乐见。
最近的真．NOIP模拟题
最近考了小狗和李茂才的NOIP模拟题
让我第一次了解到原来树套树、动态点分治、费用流、LCT/树链剖分都在NOIP正常的考试范围内，这么看来我NOIP之后就要AFO了。
P.S.其实后来想想考这些也还算正常，NOIP考纲里面是有线段树、平衡树的，所以树套树就是前面两者的综合运用，点分治是分治思想的拓展运用，LCT是Splay的拓展，树链剖分就是线段树维护DFS序，所以考这些都没什么奇怪的说。【斜眼贼】
LMC1T2：对于一个排列，要删点，边删点边输出当前序列的逆序对数。
题解：将一个点的x坐标设为下标，y坐标设为权值，就变成了动态维护点集，还要查询一个点左上右下的点个数。于是可以用树套树做。我在考场上面写了线段树套平衡树，也算是过了。颓废着写了调了一个多小时，于是愉快地被duyegeD飞了。
考后我才知道有分块做法，然而感觉树套树也不难写，并且复杂度还是要优秀一些。总之没怎么多想了。膜一发考试的时候有这种思路但是没想出来的duyege
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
int n,m,sb=0,a[N],qu[N],li[N];ll ans[N];bool d[N];
struct Point
{
int s,v;Point *c[2],*fa;
} b[N*40],*c[N*3];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline Point* NewNode(int x)
{b[++sb].s=1;b[sb].v=x;return &b[sb];}
inline void Update(Point* x)
{
x->s=1;
if (x->c[0]!=NULL) x->s+=x->c[0]->s;
if (x->c[1]!=NULL) x->s+=x->c[1]->s;
return;
}
inline void Rotate(Point* x)
{
Point *i=x->fa,*j=i->fa;bool k=i->c[0]==x;
if (j!=NULL) j->c[j->c[1]==i]=x;
if (x->c[k]!=NULL) x->c[k]->fa=i;
i->c[!k]=x->c[k];i->fa=x;
x->c[k]=i;x->fa=j;
Update(i);
return;
}
void Splay(Point* x,int y)
{
while (x->fa!=NULL)
{
if (x->fa->fa!=NULL)
Rotate((x->fa->fa->c[0]==x->fa)^(x->fa->c[0]==x)?x:x->fa);
Rotate(x);
}
Update(c[y]=x);
return;
}
Point* Find(Point* x,int y,int z)
{
if (x==NULL) return x;
Point *k;
if ((!z&&x->v>=y)||(z&&x->v>y)) k=Find(x->c[0],y,z);else k=Find(x->c[1],y,z);
if (!z)
{
if (k!=NULL) return k;
if (x->v<y) return x;else return NULL;
}
if (k!=NULL) return k;
if (x->v>y) return x;else return NULL;
}
int Query(int x,int y,Point* z,int o)
{
Point *k=Find(z,x,0),*l=Find(z,y,1);
Splay(k,o);k->c[1]->fa=NULL;Splay(l,o);
l->fa=c[o]=k;k->c[1]=l;Update(k);
k=l->c[0];return k!=NULL?k->s:0;
}
int Query(int x,int y,int z,int o,int p,int e,int r)
{
int i=x + y >> 1,j=z << 1,k=0;
if (x==o&&y==p) return Query(e,r,c[z],z);
if (o<=i) k+=Query(x,i,j,o,min(i,p),e,r);
if (p>i) k+=Query(i+1,y,j+1,max(o,i+1),p,e,r);
return k;
}
void Insert(Point* x,int y)
{
bool i=x->v<y;
if (x->c[i]==NULL) x->c[i]=NewNode(y),x->c[i]->fa=x;else Insert(x->c[i],y);
x->s++;
return;
}
void Insert(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (c[z]==NULL) c[z]=NewNode(p);else Insert(c[z],p),Splay(&b[sb],z);
if (x!=y)
if (i>=o) Insert(x,i,j,o,p);else Insert(i+1,y,j+1,o,p);
return;
}
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
c[z]=NewNode(0);c[z]->c[1]=NewNode(n+1);c[z]->c[1]->fa=c[z];Update(c[z]);
if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
return;
}
int main()
{
n=Read();m=Read();
Set_up(1,n,1);
for (int i=1;i<=n;i++) li[a[i]=Read()]=i;
for (int i=1;i<=m;i++) d[qu[i]=Read()]=1;
for (int i=1;i<=n;i++)
if (!d[i]) ans[m+1]+=Query(1,n,1,1,li[i],i,n)+Query(1,n,1,li[i],n,1,i),Insert(1,n,1,li[i],i);
for (int i=m;i>=1;i--)
ans[i]+=Query(1,n,1,1,li[qu[i]],qu[i],n)+Query(1,n,1,li[qu[i]],n,1,qu[i]),
Insert(1,n,1,li[qu[i]],qu[i]),ans[i]+=ans[i+1];
for (int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
XG2T3：就是BZOJ1095，然而我想起来了的是QTREE4。由于论文上面的东西都不记得了，还是贼爷提醒才知道是点分治，一开始还一直在想分块做法= =真是羞耻。于是我还没写过点分治就开始写动态点分治了（虽然我现在还不知道到底算不算动态点分治），反正就是记录每次点分治的重心、每个点到重心的距离、每个点是重心的哪个子树，用n log n个set维护重心的每棵子树的点到重心距离、维护每个重心的每棵子树的最大距离以及每次点分治的答案。然后写了2个小时写出来了，调了一个小时，但是没发现一个不会对小数据造成多大影响的答案，于是过了样例交了之后还是挂了= =。后来发现把一个地方的j打成i了，改过来之后发现时间上面常数好大，2s时限在渣渣本机上根本跑不出来。然后这道题输入输出与1095稍有不同，还是贴上来代码好了= =（话说其实我们的考试可以考到4H，于是还算是有时间写这题）
当然，我考后才知道原来还有括号序列相关的线段树做法，膜一发考场上面有这种思路然后并没有想出来的duyege。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
multiset <int> a[N*2];
set <int> :: iterator it,ti;
int as=0,n,m,c[N*2][2],fi[N],sg[N][20],sn[N],ag[N],rt[N][20];
int s[N],ss=1,li[N],h[N][20],la[N],sgg[N][20],sz[N];
bool t[N];char yy;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
int BFS(int x)
{
int le=1,ri=1;
li[1]=x;la[x]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (c[i][0]!=la[li[le]]&&!sn[c[i][0]])
li[++ri]=c[i][0],la[c[i][0]]=li[le];
return ri;
}
void Set_up(int x,int y)
{
int ls=BFS(x),rf,ma=0,mx=0;
if (ls==1) {sn[x]=y-1;return;}
for (int i=ls;i>=1;i--)
{
sz[li[i]]=1;
for (int j=fi[li[i]];j;j=c[j][1])
if (c[j][0]!=la[li[i]]&&!sn[c[j][0]]) sz[li[i]]+=sz[c[j][0]];
}
for (int i=ls;i>=1;i--)
{
int k=0,l=0;
for (int j=fi[li[i]];j;j=c[j][1])
if (c[j][0]!=la[li[i]]&&!sn[c[j][0]]) k=max(k,sz[c[j][0]]),l+=sz[c[j][0]];
k=max(k,ls-1-l);
if (k<=ls/2) {rf=li[i];break;}
}
sn[rf]=y;BFS(rt[rf][y]=rf);ag[rf]=++as;a[as].insert(0);
for (int i=fi[rf];i;i=c[i][1])
if (!sn[c[i][0]]) sg[c[i][0]][y]=c[i][0],sgg[c[i][0]][y]=++as,
a[as].insert(h[c[i][0]][y]=1),rt[c[i][0]][y]=rf;
for (int i=2;i<=ls;i++)
for (int j=fi[li[i]];j;j=c[j][1])
if (!sg[c[j][0]][y]&&!sn[c[j][0]])
a[sgg[sg[c[j][0]][y]=sg[li[i]][y]][y]].insert(h[c[j][0]][y]=h[li[i]][y]+1),
rt[c[j][0]][y]=rf;
for (int i=fi[rf];i;i=c[i][1])
if (!sn[c[i][0]])
{
it=a[sgg[c[i][0]][y]].end();a[ag[rf]].insert(*(--it));
if (*it>ma) mx=ma,ma=*it;else if (*it>mx) mx=*it;
}
if (mx) a[0].insert(mx+ma);else a[0].insert(ma);
for (int i=fi[rf];i;i=c[i][1])
if (!sn[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
void Insert(int x)
{
for (int i=1;i<=sn[x];i++)
if (rt[x][i]==x)
{
a[ag[x]].insert(0);
if (a[ag[x]].size()==2) it=a[ag[x]].begin(),a[0].insert(*(++it));
}else
{
int k=0,l=0;ti=a[sgg[sg[x][i]][i]].end();bool e=0;
if (ti==a[sgg[sg[x][i]][i]].begin()) e=1;else ti--;a[sgg[sg[x][i]][i]].insert(h[x][i]);
if (!e&&h[x][i]<=*ti) continue;
if (a[ag[rt[x][i]]].size()>1)
it=a[ag[rt[x][i]]].end(),l=*(--it)+*(--it),it=a[0].lower_bound(*it),a[0].erase(it);
if (!e) it=a[ag[rt[x][i]]].lower_bound(*ti),a[ag[rt[x][i]]].erase(it);
a[ag[rt[x][i]]].insert(h[x][i]);
if (a[ag[rt[x][i]]].size()>1) it=a[ag[rt[x][i]]].end(),k=*(--it)+*(--it),a[0].insert(k);
}
return;
}
void Delete(int x)
{
for (int i=1;i<=sn[x];i++)
if (rt[x][i]==x)
{
a[ag[x]].erase(0);
if (a[ag[x]].size()==1) it=a[ag[x]].begin(),it=a[0].lower_bound(*it),a[0].erase(it);
}else
{
int k=0,l=0,q=0,w=0,e=0;it=a[sgg[sg[x][i]][i]].end();k=*(--it);
it=a[sgg[sg[x][i]][i]].lower_bound(h[x][i]);
a[sgg[sg[x][i]][i]].erase(it);
if (h[x][i]<k) continue;
if (a[ag[rt[x][i]]].size()>1)
it=a[ag[rt[x][i]]].end(),q=*(--it)+*(--it),
it=a[0].lower_bound(q),a[0].erase(it);
it=a[ag[rt[x][i]]].lower_bound(k);a[ag[rt[x][i]]].erase(it);
if (a[sgg[sg[x][i]][i]].size())
it=a[sgg[sg[x][i]][i]].end(),a[ag[rt[x][i]]].insert(*(--it));
if (a[ag[rt[x][i]]].size()>1)
it=a[ag[rt[x][i]]].end(),q=*(--it)+*(--it),a[0].insert(q);
}
return;
}
int main()
{
t[n=Read()]=1;m=Read();
for (int i=1;i<n;i++) Line(Read(),Read()),t[i]=1;
Set_up(1,1);
for (int i=1;i<=m;i++)
{
int k=Read();if (t[k]) Delete(k);else Insert(k);
t[k]=!t[k];it=a[0].end();printf("%d\n",*(--it));
}
return 0;
}
感觉最近真是被正解的duyegeD肥了
