最近的真．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肥了
SGU乱做
虽然比较晚了
但是听说SGU质量都比较好，所以开刷了。P.S.感觉SGU的乱搞题比较多啊，真是开心。
upd:en没错这东西已经坑掉了。。
101：maya第二题劳资就不会做，一开始想到了是要搞成若干个环加一条链，但是不知道怎么找无向图中的环。然后发现网上都使用了一个神奇的DFS，因为DFS未走过的边，从起点开始第一次无法继续递归只会是到另外一个奇度数点或者自己，所以递归时先递归所到达的点再记录边，这样记录的边回是连续的。然后判断有没有解就是连通性和点度数判断。具体看代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2005
int c[N][2],fi[N],n,m=-1,li[N],ss=1,cnt=0,s[N];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 y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;s[x]++;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;s[y]++;
}
void DFF(int x)
{
b[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (!b[c[i][0]]) DFF(c[i][0]);
return;
}
bool Check()
{
for (int i=0;i<=6;i++)
if (fi[i]&&!b[i]) {DFF(i);break;}
for (int i=0;i<=6;i++)
if (fi[i]&&!b[i]) return 1;
for (int i=0,j=0;i<=6;i++)
{
j+=s[i]&1;
if (s[i]&1) m=i;
if (m==-1&&s[i]) m=i;
if (j>2) return 1;
}
memset(b,0,sizeof(b));
return 0;
}
void DFS(int x)
{
for (int i=fi[x];i;i=c[i][1])
if (!b[i])
b[i]=b[i^1]=1,DFS(c[i][0]),li[++cnt]=i;
return;
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) Line(Read(),Read());
if (Check()) puts("No solution");else
{
DFS(m);
for (int i=1;i<=cnt;i++)
printf("%d ",li[i] >> 1),
putchar(li[i]&1?'+':'-'),putchar('\n');
}
return 0;
}
108：本来以为O(n)会挂，都想要分块打表了，没想到筛是可以过的。话说内存卡的丧心病狂
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5050
#define M 150
#define fr first
#define sc second
pair <int,int> b[N];
int n,m,s=0,v=0,cnt=0,c[N],d[N];bool a[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 main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++) b[i].fr=Read(),b[i].sc=i;
sort(b+1,b+m+1);
for (int i=1;i<=n;i++)
{
int j=0,k=i,l=i%64;
while (k) j+=k%10,k/=10;
a[(j+i)%64]=1;
if (!a[l]) s++;
while (!a[l]&&s==b[v+1].fr) c[++v]=i;
a[l]=0;
}
cout <<s<<endl;
for (int i=1;i<=m;i++) d[b[i].sc]=c[i];
for (int i=1;i<m;i++)
printf("%d ",d[i]);
printf("%d\n",d[m]);
return 0;
}
SGU109：构造，乱搞。
SGU110：反正是一堆向量在乱搞，可以推出来。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
#define eps 1e-6
#define INF 0x7f7f7f7f
struct Point
{
double x,y,z;
} a[N],S,T;
double r[N];
int n,m;
Point operator+ (const Point &x,const Point &y)
{return (Point){x.x+y.x,x.y+y.y,x.z+y.z};}
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y,x.z-y.z};}
Point operator* (const Point &x,const double &y)
{return (Point){x.x*y,x.y*y,x.z*y};}
inline double min(double x,double y)
{return x<y?x:y;}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y)+sqr(x.z-y.z));}
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
Point Vertical(Point x,Point y,Point z)
{
double q=dis(x,y),w=dis(y,z),e;
e=(sqr(q)+sqr(w)-sqr(dis(x,z)))/(2*q*w);
return y+(z-y)*(q*e/w);
}
Point Intersect(Point x,Point y,Point z,double u)
{
double q=dis(x,y),w=dis(y,z),e=q-sqrt(sqr(u)-sqr(w));
return x+(y-x)*(e/q);
}
int main()
{
n=Read();
for (int i=1;i<=n;i++)
a[i].x=Read(),a[i].y=Read(),a[i].z=Read(),r[i]=Read();
scanf("%lf%lf%lf%lf%lf%lf",&S.x,&S.y,&S.z,&T.x,&T.y,&T.z);
for (int i=1;i<=11;i++)
{
Point s,t;double mi=INF;int q=0;
for (int j=1;j<=n;j++)
{
Point k=Vertical(a[j],S,T),l;
if (dis(k,a[j])>r[j]+eps||
abs(dis(T,k)-dis(S,T)-dis(k,S))<eps) continue;
l=Intersect(S,k,a[j],r[j]);
if (dis(l,S)>mi) continue;
mi=dis(l,S);s=l;t=S+(Vertical(S,l,a[j])-S)*2;q=j;
}
if (mi==INF) {printf("\n");break;}
if (i!=11) printf("%d ",q);else
puts("etc.");
S=s;T=t;
}
return 0;
}
SGU111：之前在codevs做过，让人感觉丧心病狂（很久以前写的太丑了还是不贴代码的好）
SGU118：打表发现f就是123456789的循环，然后直接做了，发现结论之后证明是很容易的。
SGU119：一眼感觉就是所有(A0*k)%N*X+(B0*k)%N*Y，证明都没证明直接交了= =
SGU120：恶心的计算几何。旋转二维向量有公式的（@baidu向量旋转矩阵），然而我之前的笔记都记得我看不清了，结果wa了n久= =
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 150
#define eps 1e-10
const double pi=acos(-1.0);
struct Point
{double x,y;} a[N],S,T;
int n,m,s1,s2;double r,d,p;
Point operator+ (const Point &x,const Point &y)
{return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
Point operator* (const Point &x,const double &y)
{return (Point){x.x*y,x.y*y};}
inline Point Rotate(Point x,double y)
{double i=cos(y),j=sin(y);return (Point){x.x*i-x.y*j,x.x*j+x.y*i};}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline Point Zoom(Point x,double y)
{return x*(y/(sqrt(sqr(x.x)+sqr(x.y))));}
int main()
{
cin >>n>>s1>>s2;
scanf("%lf%lf%lf%lf",&a[s1].x,&a[s1].y,&a[s2].x,&a[s2].y);
r=2*pi*min(abs(s1-s2),n-abs(s1-s2))/n;p=(pi-r)/2;
r=dis(a[s1],a[s2])/sqrt(2*(1-cos(r)));
d=2*pi/n;r*=sqrt(2-2*cos(d));
if (s2!=s1%n+1)
{
if ((n+s2-s1)%n<=n/2)
p=(pi-d)/2-p,a[s1%n+1]=a[s1]+Zoom(Rotate(a[s2]-a[s1],p),r);else
p=p+(pi-d)/2,a[s1%n+1]=a[s1]+Zoom(Rotate(a[s2]-a[s1],p),r);
}
for (int i=(s1+1)%n+1;i!=s1;i=i%n+1)
{
Point k=a[(i+n-2)%n+1],l=a[(i+n-3)%n+1];
a[i]=k+Rotate(k-l,2*pi-d);
}
for (int i=1;i<=n;i++)
printf("%.6lf %.6lf\n",a[i].x+eps,a[i].y+eps);
return 0;
}
SGU121：感觉这道题真是莫名其妙啊，题解也都是造的出反例的乱搞，真是不知道什么鬼。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
int a[N][N],c[N][N],sz[N],n,m;bool b[N][2];
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;
}
void DFS(int x,int y)
{
for (int i=1;i<=sz[x];i++)
{
int k=a[x][i];
if (!c[x][k])
c[x][k]=c[k][x]=y,b[x][2-y]=b[k][2-y]=1,DFS(k,y=3-y);
}
}
int main()
{
n=Read();
for (int i=1,k;i<=n;i++)
while (k=Read()) a[i][++sz[i]]=k;
for (int i=1;i<=n;i++)
if (sz[i]&1) DFS(i,1);
for (int i=1;i<=n;i++)
if (!(sz[i]&1)) DFS(i,1);
for (int i=1;i<=n;i++)
if ((!b[i][0]||!b[i][1])&&sz[i]>1) m=-1;
if (m) {puts("No solution");return 0;}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=sz[i];j++)
printf("%d ",c[i][a[i][j]]);
puts("0");
}
return 0;
}
SGU122：组合数学原题，感觉也是比较诡异= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
bool a[N][N],b[N];
int n,m,s[N],S,T,ne[N][2],ans=0,li[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 y=='\n'||y==EOF?-x:x;
}
void Ins(int x)
{
for (int i=1;i<=n;i++)
if (a[x][i]&&!b[i]) s[i]++;
ans++;b[x]=1;
}
int DFS(int x,bool y)
{
for (int i=1;i<=n;i++)
if (a[x][i]&&!b[i])
{Ins(i);ne[x][y]=i;ne[i][!y]=x;return DFS(i,y);}
return x;
}
void Reverse(int x,int y)
{
int cnt=0;
for (int i=ne[x][1];i;i=ne[i][1])
li[++cnt]=i;
for (int i=cnt;i>=1;i--)
ne[x][1]=li[i],ne[li[i]][0]=x,x=li[i];
ne[T=li[1]][1]=S;ne[S][0]=T;
}
int main()
{
n=Read();n=-n;
for (int i=1;i<=n;i++)
do
{
int k=Read();a[i][abs(k)]=1;
if (k<0) break;
} while (true);
Ins(S=T=b[1]=1);ne[1][1]=ne[1][0]=1;
while (ans!=n)
{
int t=0;
for (int i=1;i<=n;i++)
if (!b[i]&&s[i])
{
for (int j=1;j<=n;j++)
if (a[i][j]&&b[j])
{
S=i;ne[i][1]=j;T=ne[j][0];
ne[T][1]=0;ne[j][0]=i;Ins(i);break;
}
break;
}
S=DFS(S,0);T=DFS(T,1);
for (int i=S;i!=T;i=ne[i][1])
if (a[i][T]&&a[ne[i][1]][S])
{Reverse(i,T);break;}
}
cout <<1<<' ';
for (int i=ne[1][1];i!=1;i=ne[i][1])
printf("%d ",i);
cout <<1<<endl;
return 0;
}
SGU124：本来以为是凸多边形，然后就想用叉积什么的直接搞，然后果wa。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 20050
#define eps 1e-8
struct Point
{int x,y;} Edge[N][2],li[N],S;
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
int n,m,ss=1,ln[N][2],s;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline double Cha(Point x,Point y)
{return x.x*y.y-x.y*y.x;}
int main()
{
n=Read();
for (int i=1;i<=n;i++)
Edge[i][0].x=li[i*2-1].x=Read(),
Edge[i][0].y=li[i*2-1].y=Read(),
Edge[i][1].x=li[i*2].x=Read(),
Edge[i][1].y=li[i*2].y=Read();
S.x=Read();S.y=Read();
for (int i=1;i<=n;i++)
if (fabs(dis(Edge[i][0],Edge[i][1])-dis(Edge[i][0],S)-
dis(Edge[i][1],S))<=eps)
{puts("BORDER");return 0;}
for (int i=1;i<=n;i++)
{
if (Edge[i][0].y>Edge[i][1].y)
swap(Edge[i][0],Edge[i][1]);
if (Cha(Edge[i][0]-S,Edge[i][1]-S)<0&&
Edge[i][0].y<=S.y&&Edge[i][1].y>S.y)
s++;
}
if (s&1) puts("INSIDE");else puts("OUTSIDE");
return 0;
}
NOI2015流水账
Day0：
Wulala上火车前身份证失踪，据说晚上10点多钟到，真是喜闻乐见
进寝室感觉XJ真是爽爆了，没网没电，晚上电子阅览室还不开门，我的电脑充电还只能用1个半小时，真是要报警了。
出去上个厕所听到各个寝室都传出膜大男神的声音，大男神果然神。
结果找到一个电动车棚可以充电的，蹲了一个小时脚上全是包，学军的蚊子果然热情。
Day1：
睡了一上午开幕式，下午笔试差点不记得关程序是Ctrl+C还是D，如果不是用NOI Linux考还可以试一下真的要ydcydc了【捂脸贼】。然后练习赛一开始没调出T1吓得要死，调出来之后果断滚去阅览室占座颓颓颓4个+小时。晚上大男神各种MF出题人，熄灯半个小时突然给出题人打电话，已吓傻。
Day2：
没带餐票，一大早就在门口坐着，感觉实在是好虚啊好虚啊好虚啊，各种思想斗争，然后就进考场了。真是日了zei左上角又是毛爷爷，最右边还有qmqmqm大爷，更神的是左边的左边是德爷！默默膜了一发之后就开考了，也不知道单数年会难一些是不是真的。一抬头看到了喜闻乐见的杜宇飞，感觉应该会sxbk。然后T1娱乐题一眼了。T2第一眼看上去像Top Tree，感觉很神啊，不敢写。。T3也比较hehe，然后T1写完之后感觉状态还是很虚，然后看T2，总感觉出题人不会出Top Tree这种sxbk的东西，然后想了一(hen)下(jiu)发现其实就是树链剖分SB题，然后马上撸了一发。。然后时间还有200min啊。于是果断转第三题。。第三题果断没想出来（状态还是太萎了TATQAQ2333），其实当时有相关思路至少不是最裸的30分的，但是最近的思路都一直比较乱，第二题的思路都那么萎。然后决定30分打表大法好，一直打到了n=48。然后回去看第二题了，然后发现用GUIDE测T2肉眼无法在一秒以内出解！！！然后好虚好虚，发现fa[i]不一定比i小，而且两个DFS可能会爆栈，然后果断改了，但是发现这个跟超时并没有任何卵关系，于是一直在看代码没看出来到底是有什么问题，然后一直虚到了最后，还想写一发动态树，但是后来没时间了。于是估分100+20+30=150。出考场的时候毛爷爷说检查了2个半小时，中午听说230以上有100+，没有听任何人说第二题树链剖分会挂，感觉实在可以滚粗了TATQAQ2333。中午一直也都没睡着。总算敢去看成绩了，发现第二题没挂！！！！！而且没一个超过0.2s的，感觉GUIDE实在是再也不会爱了，但是第三题WA*9实在不知道什么鬼，难道我又打错表了？！大男神果玩一玩，成绩都不屑于看。貌似鸿太阳、破太阳玩脱了？！很消沉的样子。。也不知道该说些什么。鸿少这已经是倒数第三场比赛了。我这种分数既不算挂，也没什么希望，Dyzerjet甩我70，wulala甩我40，感觉实在不会再爱。（其实我已经被虐习惯了）嘛，由于数据水大家都没拉开与我的分差，day2还有大幅度甩我分的机会，总之day2加油吧。
下午讲题杜宇飞说不会LCT吓傻，说好的ACM选手呢？！第一题的五种姿势也是跪傻。。真是Day3一定要颓一天！！！！！
后来吃饭的时候破神问我第三题怎么做到只有10分，我说我尚不知，他问你有没有一个111、333的点，我说我怎么可能会有！……所以就ydcydc了，打表都打错这已经是第二次了，第一次是有一次考鸿少的考试。
Day3：
上午把LSP的12道作业做的只剩下一道了，下午晚上颓颓颓！！！达成键盘扫雷成就，而且还算进了200秒。然后补了恶魔高校DXD，不枉我特地下那个BD。【斜眼贼】
Day4：
上午就有种不祥的预感，感觉没有前天那么虚，但是反而状态变差了。貌似状态从来没好过啊。拿题之后看了一遍，第一题看完马上想起去年这个时候问李茂才的Haffman树，而且有40分好像都是这个东西，于是m叉Haffman怎么求啊，不会啊。于是我猜可能都一样的吧，不过就是每次选最小的m个。然而有的叉没有m个儿子，那我猜可以补0吧。然后还要求最小高度，于是我猜可以选最小的同时要选最矮的。然后虚了一发就完了。然后继续虚第二题，感觉后缀数组可以乱搞搞？然而我还是太萎了，并没有倒着搞，于是维护区间信息删点操作，我非常神奇的用了两个set还有一个splay，以我的代码长度都到了170+行。然而这些其实倒着搞只有加点操作便是并查集维护就没了。后来只有一个小时写第三题暴力，结果4分。考完之后一直虚，虚了一中午，据说第一题是P神出的，并且很多人第一题都没做出来。。真是忧伤，于是我抱着200+的美好愿想看成绩，TM原来只有139，第二题以我的代码能力这么搞果然出事了。成绩出来我们学校甚至我们省的很多人都退役了，湖南一共只有4人进队。我们学校、雅礼、一中高二全灭，据说基本上全跪在今天第一题，尤其是段哥只差12分进队。但是浙江据说只有几个人没做出第一题，也不好说什么。感觉明年省选会很严峻，都说不知道北大还会不会有这么好雅兴签湖南。看银牌线好像是高我10分是smg，不过就算Ag也没用了。
后来讲题的时候发现第一题是PTY出的，已傻。
总之一切都差不多结束了。我们学校的情况可以说是每况愈下，我们这一届也很萎。但是我还有一年，实在不好意思也不能说出“希望就全部寄托在下一届了”这种话了。来年NOI劳资要笑着回去！
Day5：
今天果然是用来颓废的！寝室里面的两位衡八大爷上午去了“快乐大本营”，下午还去了开幕式。不过那位进队了也确实会有这种雅兴。包括昨天晚上，今天一天都没心情吃饭，食堂里面的饭菜也感觉实在吃够了。今天果然都有人找我谈人生了，确实除了我之外我们学校的人都好萎。就我觉得duyege如果从一开始就认真搞是一定有实力的，他的思维不比我差，有的时候会想到一些我没想到的东西，一开始也基础算很不错的。但是我们这一届都没什么斗志，甚至有种他们都没想过NOIP之后的事情的感觉。当然也说不定，但是为什么从来没怎么看过他们努力过，当然就我看来有少数人是在努力的，但是为什么一直都没看到进步。现在的风气我感觉也很奇怪，明明一直都在D别人怎么怎么神，明明考试有的时候都成这个样子，为什么自己却一直在那里摆，难道就一点都不会不甘心么。可能都已经麻木了吧。当然我也没什么资格D别人太摆了，但是我觉得我还是在进取的，我还是会努力的。其实我们学校也是，一直都管的不严，LSP这一年难道没发现我们根本就没什么很大进步吗。反正都比较晚了，希望下一届高一不要是这样吧。
我这一年吧，算是有收获吧，但是也走了很多弯路。我一直以来都没什么自信，初中的时候也发生过一些事情，导致心态也比较奇怪，感觉人一直都是蛮迷茫的。但是整个信息组都比较奇怪，包括贼爷的很多事情。我常常先跟着他们做，然后尝试去解释一些事情。我也不会和别人交流。当然我对一些事情还是会有自己的判断，也还是保留了自己的态度，一直撑到了今天。还是蛮羡慕其他学校的氛围的，至少还是有能好好交流的人吧。总之一年就这么过去了，还是往前看吧。今年这一年吧，反正我也别管那么多认真搞就是了，明年我们学校实在不能再没成绩了，不然信息组以后还不知道有没有人。当然我们学校的条件确实不如其他学校，虽然没去过长郡雅礼看，但是感觉一是风气肯定没他们好、二是水平高的人他们肯定多一些、三是老师也管的严一些。感觉唯一的好处就是我们学校省选绝对不会出现卡名额的情况。。虽然这样了，但是还是希望下一届高一能够加油吧，高三的都走了，也只有我能做些什么了。
现在都不是什么我能不能做好的问题了，我有实力去做，我TM一定要做好。明年再战加油吧。
Day6：
然后就这么滚回长沙了。。。回来数了下左腿上有40+个包，身上也总共有80+了吧，杭州真是不会再爱了。总之总算回来了。
暑假计划
要认真搞了
暑假里面还是要先提升姿势水平，首先是多项式运算的姿势，还有单纯性，斯坦纳树，数据结构要补一补，QTREE推完，什么爬山算法，模拟退火，后缀自动机，K-D Tree，回文自动机，插头DP，朱刘算法什么的。
没事的时候推推高数什么的
没事打打CF，TCO，SGU要开刷了，希望能补救拙计的智商。之前攒下来的资料感觉要过一遍了。
BZOJ1016最小生成树计数
本来是Matrix-Tree裸题，然后不知道怎么写挂了，然后再网上看到了一种奇怪的做法：
首先处理出一棵最小生成树，然后统计不同权值在树上的出现的次数，
有个性质是显然的：最小生成树上的不同权值的个数一定是上面那样子的（虽然不会证但是总感觉很有道理）
然后就按权值从小到大，处理出权值为v的所有边的不会使当前图有环的方案s，然后选择其中一种方案的边加入当前图中，最后把所有s乘起来。
至于证明：数学归纳法假设前i种权值选择好了之后的图联通情况都是相同的，然后加入k条边，如果有两种方案使得处理后联通情况不同那么两种方案的并一定会更优，所以是可以这么搞的。然后这么看所有权值的边选择独立，所以可以乘法原理乘起来。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
#define M 31011
struct Line
{
int x,y,v;
} a[N*10];
int n,m,ss=1,fa[N],s[N*10],cnt=0,h[N*10],ans=1;
bool b[N*10];
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 Find(int x)
{return x==fa[x]?x:(fa[x]=Find(fa[x]));}
inline bool cmp(Line x,Line y)
{return x.v<y.v;}
int find(int x)
{return x==fa[x]?x:find(fa[x]);}
int DFS(int x,int y,int z)
{
int i=find(a[x].x),j=find(a[x].y),k=0;
if (x==z) return y==0;
if (i!=j&&y) {fa[i]=j;k=DFS(x+1,y-1,z);fa[i]=i;}
k+=DFS(x+1,y,z);
return k;
}
int main()
{
int i,j,k,l,q,w,e=0;
n=Read();m=Read();
for (i=1;i<=m;i++)
a[i].x=Read(),a[i].y=Read(),a[i].v=Read();
sort(a+1,a+m+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
k=Find(a[i].x);l=Find(a[i].y);
if (k!=l)
fa[k]=l,e++,b[i]=1;
}
if (e!=n-1)
{printf("0\n");return 0;}
for (i=1;i<=m;i++)
{
if (a[i].v!=a[i-1].v) h[++cnt]=i;
s[cnt]+=b[i];
}
h[cnt+1]=m+1;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=cnt;i++)
{
ans=(ans*DFS(h[i],s[i],h[i+1]))%M;
for (j=h[i];j<h[i+1];j++)
if (b[j])
q=find(a[j].x),w=find(a[j].y),fa[q]=w;
}
cout <<ans<<endl;
return 0;
}
