JLOI2016题解
贵省的题目好鬼畜。。
D1T1：
貌似见过这题。反正就是设dpi,j代表i这个点子树内的状态都确定，对上面点的影响为j的最小值。j为负数代表需要上面有守卫覆盖到往下j深度的点。否则是可以覆盖到上面j距离的点。然后转移可以枚举对上面的影响，然后枚举是哪个子树造成了这样的影响，其它的就是大于等于这个的影响随便取了。正确性显然。O(n*d)
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define M 50
#define INF 0x3f7f7f7f
#define mi(x,y) Mi[x][y+25]
int val[N],fi[N],c[N*2][2],Mi[N][M],n,m,ss=1,ans;bool col[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)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
return;
}
void DFS(int x,int y)
{
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y) DFS(c[i][0],x);
int Cnt=false;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y) Cnt+=mi(c[i][0],-m);
mi(x,m)=Cnt+val[x];
for (int j=-m;j<0;j++)
{
Cnt=false;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y)
Cnt+=mi(c[i][0],j+1);
if (j!=-1) mi(x,j)=Cnt; else
if (col[x]) mi(x,0)=INF,mi(x,-1)=Cnt; else
mi(x,0)=mi(x,-1)=Cnt;
}
for (int j=0;j<m;j++)
{
Cnt=false;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y)
Cnt+=mi(c[i][0],-j);
if (j) mi(x,j)=INF;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y)
mi(x,j)=min(mi(x,j),Cnt-mi(c[i][0],-j)
+mi(c[i][0],j+1));
}
for (int i=m-1;i>=-m;i--)
mi(x,i)=min(mi(x,i),mi(x,i+1));
return;
}
int main()
{
//freopen("input.txt","r",stdin);
n=Read();m=Read();
for (int i=1;i<=n;i++) val[i]=Read();
int p=Read();
while (p--) col[Read()]=true;
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1,0);cout <<mi(1,0)<<endl;
return 0;
}
D1T2：
BZOJ上面这几题里面过的人数最多的。。有点不知所措。。反正非常暴力地推一下然后上大分类讨论好像就可以算出来了。外面再套一下4个点的容斥公式就好了的样子。
D1T3：
dp显然。设dpi,j代表前i科考试之后还有j个人被碾压，转移明显是dpi,j=dpi-1,k*C(k,j)*Σ(t = 1 to Ui) t^(n - Ri)*(Ui-t)^Ri。主要是后面那个东西算起来代价太大。考虑能不能倍增算。Su代表Ui取u的时候的答案。当Ui变成2Ui那么后面那个式子变成Σ(t = 1 to 2Ui) t^(n - Ri)*(Ui+(Ui-t))^Ri=Σ(t = 1 to Ui) t^(n-Ri)*(Ui+(Ui-t))^Ri+……。这东西明显可以将后面的东西拆开来算贡献，于是多一维状态表示(Ui-t)的幂是多少。就变成了n^2求这个了。还有Σ(t = 1 to Ui) (t+Ui)^(n-Ri)*(Ui-t)^Ri。前面的东西也要拆开来算贡献，也是n^2。然后就变成了O(n^3 log n+n^3)。。应该能过吧。。
UPD：后来感觉还是太不优美了，主要是我把所有这个东西的所有幂的组合都求出来了。考虑直接对原式下手：拆掉那个(ui-t)^Ri所以就变成了若干个Σ(t = 1 to ui) t^j*ui^?*组合数。后面两个东西是个常数所以只要考虑前面的东西怎么求就好了。前面那个东西貌似是冬令营的提答考过的科技，可以手推化式子，也可以用组合数学里面的一种方法：Σi^t-Σ(i-1)^t=i^t=将前面那个式子化出来得到的一个最高项t-1的一个多项式。然后那个多项式里面可以提出Σi^(t-1)，并且i^t可以快速幂算，所以就可以得出Σi^(t-1)。这是n^3的。
还有没有其它思路呢？我们在这里接上之前我们提到的倍增是不是毫无违和感。连复杂度都是一样的真是2333
最后我翻到了一个叫做牛顿等幂和公式的一个东西好像比较厉害。我看到这东西的第一反应就是这东西很厉害啊一定可以用来出题。然后找不到证明之类的东西。。【待续】
D2T1：
预处理子串出现的开始位置，然后枚举相对位置，然后按照从左到右的顺序扫一遍。然后我还naive地想用线段树维护这些东西。。直接对于每个点记录当这个点是之前取的所有子串里面最右边的端点的时候的的最小值当然也要分子串是哪一个记录。转移就是分类讨论一下，对于当前子串不经过之前那个右节点就直接取前缀最大值就好了。否则就是如果相交就是取Ansx+Now-x的最优解，这个前缀最优值搞一搞就好。还有被那东西包含也是直接用个单调队列搞就好。然后这里因为长度都不一样所以可能不满足枚举的相对位置但是并不要紧，因为答案不会变优所以这里只需要考虑最右边是谁就好。然后答案也有一个序列，所以也肯定会在一次被枚举到所以最优性也是有的。单调栈那东西本来还想用线段树搞，但是发现复杂度有问题。现在变成了O(T*n!*n*|A|)就没有问题了。细节写的人要精分了。真心瘠薄细节题，不想清楚真心GG。。（要我考场上面只有4h绝对不会来刚这狗哔东西。。细节题死ね。
最后调了一堆错还是调出来了。搞了好久。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 30050
#define M 6
#define INF 0x3f7f7f7f
int li[N],_li[N],sg[M],fail[N],ma[2][M][N],mi[2][M][N],len[M];
char a[N],b[N];bool vis[M],_vis[M],mch[M][N];int n,m,t,ans0,ans1;
void Match(int x,int &len)
{
len=strlen(b+1);int Now=false;
for (int i=1;i<=len;i++)
{
fail[i]=fail[i-1];
while (fail[i]&&b[fail[i]+1]!=b[i])
fail[i]=fail[fail[i]];
if (i!=1) fail[i]+=b[fail[i]+1]==b[i];
}
for (int i=1;i<=n;i++)
{
while (Now&&a[i]!=b[Now+1]) Now=fail[Now];
Now+=a[i]==b[Now+1];mch[x][i]=Now==len;
if (Now==len) Now=fail[Now];
}
return;
}
void Clear(int x)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
ma[x][j][i]=-INF,mi[x][j][i]=INF;
return;
}
inline void Ma(int &x,int y)
{x=max(x,y);return;}
inline void Mi(int &x,int y)
{x=min(x,y);}
void Solve()
{
memset(_vis,false,sizeof _vis);
Clear(true);_vis[sg[1]]=true;
for (int i=1;i<=n;i++)
if (mch[sg[1]][i])
ma[1][sg[1]][i]=mi[1][sg[1]][i]=len[sg[1]];
for (int j=2;j<=m;j++)
{
bool flag=j&true;Clear(flag);
int _ma=-INF,_mi=INF;
for (int k=1;k<=m;k++)
if (_vis[k]&&len[k]>=len[sg[j]])
{
int ri=false;
for (int i=1;i<=n;i++)
{
if (mch[sg[j]][i]) ri=i;
if (mch[k][i]&&ri>=i-len[k]+len[sg[j]])
ma[flag][k][i]=ma[!flag][k][i],
mi[flag][k][i]=mi[!flag][k][i];
}
}
for (int i=len[sg[j]]+1;i<=n;i++)
{
for (int k=1;k<=m;k++)
Ma(_ma,ma[!flag][k][i-len[sg[j]]]),
Mi(_mi,mi[!flag][k][i-len[sg[j]]]);
if (mch[sg[j]][i])
Ma(ma[flag][sg[j]][i],_ma+len[sg[j]]),
Mi(mi[flag][sg[j]][i],_mi+len[sg[j]]);
}
for (int k=1;k<=m;k++)
if (_vis[k])
{
int le=true,ri=false;
int _le=true,_ri=false;
for (int i=1;i<=n;i++)
{
int e=min(i-len[sg[j]]+len[k],i);
if (le<=ri&&li[le]+len[sg[j]]<i) le++;
if (_le<=_ri&&_li[_le]+len[sg[j]]<i) _le++;
if (e>0&&e<=n&&mch[k][e])
{
while (_le<=_ri&&i+mi[!flag][k][e]-e<=
mi[!flag][k][_li[_ri]]-_li[_ri]+i) _ri--;
_li[++_ri]=e;
while (le<=ri&&i+ma[!flag][k][e]-e>=
ma[!flag][k][li[ri]]-li[ri]+i) ri--;
li[++ri]=e;
}
if (_le<=_ri&&mch[sg[j]][i])
Mi(mi[flag][sg[j]][i],i-_li[_le]+mi[!flag][k][_li[_le]]);
if (le<=ri&&mch[sg[j]][i])
Ma(ma[flag][sg[j]][i],i-li[le]+ma[!flag][k][li[le]]);
}
}
_vis[sg[j]]=true;
}
bool flag=m&true;
for (int i=1;i<=n;i++)
for (int k=1;k<=m;k++)
Ma(ans0,ma[flag][k][i]),Mi(ans1,mi[flag][k][i]);
return;
}
void DFS(int x)
{
if (x==m+1) Solve();
for (int i=1;i<=m;i++)
if (!vis[i])
sg[x]=i,vis[i]=true,DFS(x+1),vis[i]=false;
return;
}
int main()
{
//freopen("input.txt","r",stdin);
cin >>t;
while (t--)
{
scanf("%s",a+1);n=strlen(a+1);
cin >>m;ans0=-INF;ans1=INF;
for (int i=1;i<=m;i++)
scanf("%s",b+1),Match(i,len[i]);
DFS(1);cout <<ans1<<' '<<ans0<<endl;
}
return 0;
}
D2T2：
一开始感觉不会弃疗，后来想想好像是见过的思路，就直接扫描线+平衡树。用一条直线穿过一些圆，这些圆的上下边界看成括号会变成一个括号序列，所以扫描线从左到右扫一遍，每次加入一个圆就二分出应该插在哪里，同时维护括号区间和可以询问出第一个包含这个圆的圆是哪一个。用这个造出一棵树就可以。直接搞了。复杂度O(n log n)。写一发发现带删除的平衡树不能用不记录父亲的Treap写，shit！感觉平时都不怎么写平衡树现在写起来还是没那么顺了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define eps 1e-9
#define INF 0x3f7f7f7f
#define ld double
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
#define ld double
#define ll long long
PII li[N*2];ll ans;
int wz[N][2],fa[N],r[N],c[N*2][2],fi[N],ss=1,n,m;
inline ld sqr(ld x) {return x*x;}
struct Node
{
Node *c[2],*fa;int sg,val,suf,Cnt;
ld Get(ld x)
{return wz[sg][1]-val*sqrt(sqr(r[sg])-sqr(x-wz[sg][0]));}
} a[N][2],*emp,Emp,*root;
inline int Read()
{
int x=0;char y;bool z=false;
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 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;
return;
}
void DFS(int x,bool flag)
{
if (flag) ans+=1LL*r[x]*r[x]; else
ans-=1LL*r[x]*r[x];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]) DFS(c[i][0],!flag);
return;
}
inline Node* GetNew(int x,bool flag)
{
a[x][flag].val=a[x][flag].Cnt=flag?-true:true;
a[x][flag].suf=max(a[x][flag].Cnt,0);
a[x][flag].c[0]=a[x][flag].c[1]=a[x][flag].fa=emp;
a[x][flag].sg=x;
return &a[x][flag];
}
inline void Update(Node* x)
{
x->Cnt=x->val+x->c[1]->Cnt+x->c[0]->Cnt;
x->suf=max(x->c[1]->suf,x->c[1]->Cnt+x->val+x->c[0]->suf);
return;
}
inline void Rotate(Node* x)
{
Node *i=x->fa,*j=i->fa;bool flag=i->c[0]==x;
if (j!=emp) j->c[j->c[1]==i]=x;
if (x->c[flag]!=emp) x->c[flag]->fa=i;
i->c[!flag]=x->c[flag];i->fa=x;
x->c[flag]=i;x->fa=j;Update(i);
return;
}
void Splay(Node* x)
{
while (x->fa!=emp)
{
if (x->fa->fa!=emp)
Rotate((x->fa->fa->c[0]==x->fa)^(x->fa->c[0]==x)?
x:x->fa);
Rotate(x);
}
root=x;Update(x);
return;
}
int Find(Node* x,int y)
{
if (x->c[1]->suf+y>0) return Find(x->c[1],y); else
if (x->c[1]->Cnt+y+x->val==1) return x->sg+INF; else
return Find(x->c[0],y+x->val+x->c[1]->Cnt);
}
int Insert(Node* x,int _x,int y,bool z)
{
double k=x->Get(_x);bool flag=k<wz[y][1];int _k=false;
if (y==x->sg) flag=true;
if (x==emp) return root=GetNew(y,z),INF;
if (x->c[flag]==emp)
x->c[flag]=GetNew(y,z),x->c[flag]->fa=x,_k=false; else
_k=Insert(x->c[flag],_x,y,z);
Update(x);
if (_k<INF&&flag)
if (_k+x->val==1) _k=INF+x->sg; else
if (_k+x->val+x->c[0]->suf>0) _k=Find(x->c[0],x->val+_k); else
_k+=x->val+x->c[0]->Cnt;
if (_k<INF&&x->fa==emp) _k=INF;
return _k;
}
Node* Merge(Node* x,Node* y)
{
if (x==emp) return y; else
if (y==emp) return x;
if (abs(x->Cnt)>abs(y->Cnt))
x->c[1]=Merge(x->c[1],y),x->c[1]->fa=x; else
y->c[0]=Merge(x,y->c[0]),x=y,x->c[0]->fa=x;
emp->fa=emp;Update(x);
return x;
}
void Delete(Node* x)
{Splay(x);root=Merge(x->c[0],x->c[1]);root->fa=emp;return;}
void Solve()
{
for (int i=1;i<=n*2;i++)
if (li[i].sc<0)
Delete(&a[-li[i].sc][0]),
Delete(&a[-li[i].sc][1]); else
fa[li[i].sc]=Insert(root,li[i].fr,li[i].sc,false)-INF,
Insert(root,li[i].fr,li[i].sc,true),
Splay(&a[li[i].sc][0]);
return;
}
int main()
{
//freopen("input.txt","r",stdin);
n=Read();
emp=&Emp;root=emp->c[0]=emp->c[1]=emp->fa=emp;
for (int i=1;i<=n;i++)
wz[i][0]=Read(),wz[i][1]=Read(),r[i]=Read();
for (int i=1;i<=n;i++)
li[i*2-1]=mp(wz[i][0]-r[i],i),
li[i*2]=mp(wz[i][0]+r[i],-i);
sort(li+1,li+n*2+1);Solve();
for (int i=1;i<=n;i++)
if (fa[i]) Line(fa[i],i);
for (int i=1;i<=n;i++)
if (!fa[i]) DFS(i,true);
cout <<ans<<endl;
return 0;
}
D2T3：提答题。。
口胡完了开始补代码了
[UPD]:为什么这个坑在这里了呢？虽然就这么两道题不过不是很想管了所以就让它坑在这里吧。牛顿等幂和公式已经怎么样都好了，反正感觉就差不多那个意思了。分类讨论怎么样都好了，反正过的人那么多。于是这篇博客感觉也是怎么样都好了，最近已经懒得动了= =
HNOI 2016题解
感觉这次省选确实出的比较蛋疼。就这样6个DS对待HN选手感觉是很不妥。
D1T1：
做法一：对所有操作询问按a排序后分块，先把1~i-1块的内容和第i块的询问按照b排序，然后再扫一遍，每次加边用并查集维护连通块的maxa和maxb。
然后扫到一个块内询问的时候就暴力加入当前块的符合条件的边，用一个新的数组搞并查集就可以了。复杂度O(m*sqrt(m)*log(n))。细节好像非常厉害，想清楚之后写比较好。尤其是我最近比较喜闻乐见的入了下划线坑然后这种代码就比较容易混乱。。写过了之后没有判掉那些询问点对是相等的情况，所以后来是面向数据调代码的。然后写丑了，我的要加点优化才能勉强过。
考场上面并没有花时间去想。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
int sg[N],_sg[N],cz[N][4],fa[N],ma[N][2],_fa[N],_ma[N][2];
int Now[N],Nep[N],qu[N][4],wz[N],_wz[N],n,m,p,rt,st;
bool Ans[N],flag=false;
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 fa[x]==x?x:(fa[x]=Find(fa[x]));}
int _Find(int x)
{
if (Now[x]!=st)
{
Now[x]=st;_ma[x][0]=ma[x][0];
_ma[x][1]=ma[x][1];_fa[x]=fa[x];
}
return _fa[x]==x?x:(_fa[x]=_Find(_fa[x]));
}
inline int Get(int x,int y)
{return x<0?qu[-x][y]:cz[x][y];}
inline bool cmp(int x,int y)
{return Get(x,3)<Get(y,3)||(Get(x,3)==Get(y,3)&&
(Get(x,2)<Get(y,2)||(Get(x,2)==Get(y,2)&&x>y)));}
inline bool _cmp(int x,int y)
{return Get(x,2)<Get(y,2)||(Get(x,2)==Get(y,2)&&
(Get(x,3)<Get(y,3)||(Get(x,3)==Get(y,3)&&x>y)));}
int main()
{
freopen("multiple.in","r",stdin);
freopen("multiple.out","w",stdout);
n=Read();m=Read();
for (int i=1;i<=m;i++)
for (int j=0;j<4;j++) cz[i][j]=Read();
for (int i=1;i<=m;i++) sg[i]=_sg[i]=i;
p=Read();
for (int i=1;i<=p;i++)
for (int j=0;j<4;j++) qu[i][j]=Read();
for (int i=1;i<=p;i++) _sg[i+m]=sg[i+m]=-i;
sort(_sg+1,_sg+m+p+1,_cmp);sort(sg+1,sg+m+p+1,cmp);
rt=(int)(sqrt(m+p));
if (m+p>10000) rt <<= true;
for (int i=1;i<=m+p;i++)
if (_sg[i]>0) wz[_sg[i]]=i; else _wz[-_sg[i]]=i;
for (int i=1;i<=m+p;i++) Nep[i]=(i-1)/rt;
for (int i=1;i<=m+p;)
{
int ri=i;while (ri<m+p&&Nep[ri+1]==Nep[ri]) ri++;
for (int j=1;j<=n;j++) fa[j]=j,ma[j][0]=ma[j][1]=false;
for (int j=1;j<=m+p;j++)
if (sg[j]>0&&wz[sg[j]]<i)
{
int k=Find(cz[sg[j]][0]),l=Find(cz[sg[j]][1]);
if (k!=l)
fa[l]=k,ma[k][0]=max(ma[k][0],ma[l][0]),
ma[k][1]=max(ma[k][1],ma[l][1]);
ma[k][0]=max(ma[k][0],cz[sg[j]][2]);
ma[k][1]=max(ma[k][1],cz[sg[j]][3]);
} else
if (sg[j]<0&&_wz[-sg[j]]>=i&&_wz[-sg[j]]<=ri)
{
st++;
for (int e=i;e<=ri;e++)
if (_sg[e]>0&&cz[_sg[e]][2]<=qu[-sg[j]][2]&&
cz[_sg[e]][3]<=qu[-sg[j]][3])
{
int k=_Find(cz[_sg[e]][0]);
int l=_Find(cz[_sg[e]][1]);
if (k!=l)
{
_fa[l]=k;
_ma[k][0]=max(_ma[k][0],_ma[l][0]);
_ma[k][1]=max(_ma[k][1],_ma[l][1]);
}
_ma[k][0]=max(_ma[k][0],cz[_sg[e]][2]);
_ma[k][1]=max(_ma[k][1],cz[_sg[e]][3]);
}
int k=_Find(qu[-sg[j]][0]),l=_Find(qu[-sg[j]][1]);
if (k==l&&_ma[k][0]==qu[-sg[j]][2]&&
_ma[k][1]==qu[-sg[j]][3]) Ans[-sg[j]]=true;
if (qu[-sg[j]][0]==qu[-sg[j]][1]&&!_ma[k][0]&&
!_ma[k][1]) Ans[-sg[j]]=false;
}
i=ri+1;
}
for (int i=1;i<=p;i++) puts(Ans[i]?"Yes":"No");
return 0;
}
做法二：UOJ群里面搞来的：
确实比较厉害。至于怎么维护黑点到根的max的min这明显可以用LCT上的splay直接维护每个点虚边上的最小值就好辣。还有因为有翻转操作所以要维护平衡树上从左到右和从右到左两个最小值。然后这东西看起来常数也很大。。（后来突然发现一个问题：怎么维护虚边上面的最小值，这东西我们不是有个叫做TopTree的很方便的东西吗，这样就是n log n辣（逃。。我们用个set就是n log^2 n的。。反正我不写。。
D1T2：
听说根号做法可以过。我的做法是点分治+平衡树。将操作拆到包含它的每个分治子树内，然后顶多只会有log个。每次询问在分治树上走。
假如当前走到的点是i，询问点为j，询问点在i的k子树内。分成两种情况：
1.操作的两个端点都不在i的k子树内。这种情况又分两种：第一种两个端点都在i的同一子树内，这个可以用set搞。第二种操作经过i点，这个用一棵平衡树维护i子树内的所有操作，按照权值维护，然后还维护平衡树子树内所有操作的公共端点。然后就可以在上面二分出第一个不经过k的操作了。
2.操作有一个端点在i的k子树内，有一个不在。这种情况再对于i的每个子树维护一个平衡树。维护的是满足(2)条件的所有操作。操作按照在k子树内的端点的dfs序维护，然后只要按照j和i的位置情况分类讨论一下可能的dfs区间就好了。
然后也是n log^2 n的。因为有两棵带删除的平衡树所以写起来非常蛋疼。。写到300h还没写完就弃坑了。。
网上找到了有人用n log^3 n强行艹过去了orz。是强行树套优先队列的所以常数比较小可能。总共跑了7s单点测试也没超时，随便过TAT。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 105
priority_queue <int> ad[N*4],del[N*4];
int fi[N],c[N*2][2],dfn[N][2],fa[N],h[N],rf[N],wei[N];
int cz[N*2][3],bd[M][2],sg[M],n,m,ss=1;
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;
}
void DFS(int x)
{
h[x]=h[fa[x]]+1;wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void DSF(int x,int y)
{
static int st=false;dfn[x][0]=++st;
rf[x]=y;int k=false;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&wei[c[i][0]]>wei[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
dfn[x][1]=st;
return;
}
inline int Query(int x,int y,int z,int o)
{
int mid = x + y >> 1 , j = z << 1 , k = -1;
while (!ad[z].empty()&&!del[z].empty()&&ad[z].top()==del[z].top())
ad[z].pop(),del[z].pop();
if (!ad[z].empty()) k=ad[z].top();
if (x!=y) if (o<=mid) k=max(k,Query(x,mid,j,o)); else
k=max(k,Query(mid+1,y,j+1,o));
return k;
}
inline bool cmp(int x,int y)
{return bd[x][0]<bd[y][0];}
void Modify(int x,int y,int z,int o,int p,int u,bool flag)
{
int mid = x + y >> 1 , j = z << 1;
if (x==o&&y==p)
{
if (flag) ad[z].push(u); else
del[z].push(u);
return;
}
if (p<=mid) Modify(x,mid,j,o,p,u,flag); else
if (o>mid) Modify(mid+1,y,j+1,o,p,u,flag); else
Modify(x,mid,j,o,mid,u,flag),
Modify(mid+1,y,j+1,mid+1,p,u,flag);
return;
}
void Insert(int x,int y,int z,bool flag)
{
int st=false;
while (rf[x]!=rf[y])
{
if (h[rf[x]]<h[rf[y]]) swap(x,y);
bd[++st][0]=dfn[rf[x]][0];bd[st][1]=dfn[x][0];
sg[st]=st;x=fa[rf[x]];
}
if (h[x]>h[y]) swap(x,y);
bd[++st][0]=dfn[x][0];bd[st][1]=dfn[y][0];sg[st]=st;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=st;i++)
if (bd[sg[i-1]][1]+1!=bd[sg[i]][0])
Modify(1,n,1,bd[sg[i-1]][1]+1,bd[sg[i]][0]-1,z,flag);
if (bd[sg[st]][1]!=n)
Modify(1,n,1,bd[sg[st]][1]+1,n,z,flag);
return;
}
int main()
{
freopen("network.in","r",stdin);freopen("network.out","w",stdout);
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);
for (int t=1;t<=m;t++)
{
int e=Read();
if (!e)
{
cz[t][0]=Read();cz[t][1]=Read();cz[t][2]=Read();
Insert(cz[t][0],cz[t][1],cz[t][2],true);
} else
if (e==1)
{
int k=Read();
Insert(cz[k][0],cz[k][1],cz[k][2],false);
} else
printf("%d\n",Query(1,n,1,dfn[Read()][0]));
}
return 0;
}
D1T3：最一眼的题：直接缩点然后树剖就好了。细节非常艹蛋。。不过想清楚之后也不用调很久。。编译完只调了三四个错就A了。。貌似跑的飞起。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 20
#define ll long long
ll bg[N],pre[N];int qu[N][4],rf[N],_rf[N],_fa[N],n,m,p,ss=true;
int wei[N],fi[N],c[N*2][2],h[N],sg[N],dfn[N][2],fa[N][3],rt[N];
int _dfn[N][2],li[N];
inline ll Read()
{
ll 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;
}
void _DFS(int x)
{
h[x]=h[_fa[x]]+1;wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x])
_fa[c[i][0]]=x,_DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void _DSF(int x,int y)
{
static int st=false;int k=false;
_rf[x]=y;dfn[x][0]=++st;sg[st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x]&&wei[c[i][0]]>wei[k])
k=c[i][0];
if (k) _DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x]&&c[i][0]!=k)
_DSF(c[i][0],c[i][0]);
dfn[x][1]=st;
return;
}
int LCA(int x,int y)
{
while (_rf[x]!=_rf[y])
{
if (h[_rf[x]]<h[_rf[y]]) swap(x,y);
x=_fa[_rf[x]];
}
return h[x]<h[y]?x:y;
}
struct Node
{
Node* c[2];int Cnt;
} statePool[N*M],*_rt[N],*cur,*emp,Emp;
inline Node* GetNew()
{return cur->c[0]=cur->c[1]=emp,cur++;}
Node* Insert(int x,int y,Node* z,int o)
{
int mid = x + y >> 1;Node* j=GetNew();
j->Cnt=z->Cnt+1;
if (x!=y) if (o<=mid)
j->c[1]=z->c[1],j->c[0]=Insert(x,mid,z->c[0],o); else
j->c[0]=z->c[0],j->c[1]=Insert(mid+1,y,z->c[1],o);
return j;
}
int Query(int x,int y,Node* z,Node* o,int p)
{
int mid = x + y >> 1,k=z->c[0]->Cnt-o->c[0]->Cnt;
if (x==y) return x;
if (k<p) return Query(mid+1,y,z->c[1],o->c[1],p-k); else
return Query(x,mid,z->c[0],o->c[0],p);
}
int Half_Find(int x,int y,ll z)
{
if (x>y) return false;
int mid = x + y >> 1;
if (z>=bg[mid]) return max(Half_Find(mid+1,y,z),mid); else
return Half_Find(x,mid-1,z);
}
void DFS(int x)
{
pre[x]=pre[fa[x][0]]+fa[x][2];wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void DSF(int x,int y)
{
static int st=false;_dfn[x][0]=++st;li[st]=x;
int k=false;rf[x]=y;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0]&&wei[c[i][0]]>wei[k])
k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
_dfn[x][1]=st;
return;
}
ll GetAns(int x)
{
if (qu[x][0]==qu[x][2])
return h[qu[x][1]]+h[qu[x][3]]-2*h[LCA(qu[x][1],qu[x][3])];
ll ans=false;
if (pre[qu[x][0]]<pre[qu[x][2]])
swap(qu[x][0],qu[x][2]),swap(qu[x][1],qu[x][3]);
if (_dfn[qu[x][0]][0]>=_dfn[qu[x][2]][0]&&
_dfn[qu[x][0]][1]<=_dfn[qu[x][2]][1])
{
int la=qu[x][0];
ans=h[qu[x][1]]-h[rt[qu[x][0]]]+
h[qu[x][3]]-h[rt[qu[x][2]]]+
pre[qu[x][0]]-pre[qu[x][2]];
while (rf[qu[x][0]]!=rf[qu[x][2]])
la=rf[qu[x][0]],qu[x][0]=fa[rf[qu[x][0]]][0];
if (qu[x][0]==qu[x][2])
qu[x][0]=la; else
qu[x][0]=li[_dfn[qu[x][2]][0]+1];
ans-=2*h[LCA(fa[qu[x][0]][1],qu[x][3])]-
2*h[rt[qu[x][2]]];
} else
{
int la0=false,la1=false;
ans=pre[qu[x][0]]+pre[qu[x][2]]+
h[qu[x][1]]+h[qu[x][3]]-
h[rt[qu[x][0]]]-h[rt[qu[x][2]]];
while (rf[qu[x][0]]!=rf[qu[x][2]])
{
if (pre[rf[qu[x][0]]]<pre[rf[qu[x][2]]])
swap(qu[x][0],qu[x][2]),swap(la0,la1);
la0=rf[qu[x][0]];
qu[x][0]=fa[rf[qu[x][0]]][0];
}
int e=pre[qu[x][0]]<pre[qu[x][2]]?qu[x][0]:qu[x][2];
ans-=2*pre[e];
for (int j=0;j<3;j+=2)
if (qu[x][j]!=e) qu[x][j]=li[_dfn[e][0]+1]; else
qu[x][j]=0;
if (!qu[x][0]) qu[x][0]=la0;
if (!qu[x][2]) qu[x][2]=la1;
ans-=2*h[LCA(fa[qu[x][0]][1],fa[qu[x][2]][1])]-
2*h[rt[e]];
}
return ans;
}
int main()
{
freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
n=Read();m=Read();p=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
cur=statePool;emp=&Emp;emp->c[0]=emp->c[1]=emp;
_DFS(1);_DSF(1,1);_rt[0]=emp;
for (int i=1;i<=n;i++)
_rt[i]=Insert(1,n,_rt[i-1],sg[i]);
memset(fi,0,sizeof fi);ss=bg[true]=rt[true]=true;
for (int i=2;i<=m+1;i++)
{
rt[i]=Read();ll l=Read();
fa[i][0]=Half_Find(1,i-1,l);
fa[i][1]=Query(1,n,_rt[dfn[rt[fa[i][0]]][1]],
_rt[dfn[rt[fa[i][0]]][0]-1],l-bg[fa[i][0]]+1);
fa[i][2]=1+h[fa[i][1]]-h[rt[fa[i][0]]];
bg[i]=bg[i-1]+wei[rt[i-1]];Line(i,fa[i][0]);
}
for (int i=1;i<=p;i++)
{
ll k=Read(),l=Read();
qu[i][0]=Half_Find(1,m+1,k);
qu[i][1]=Query(1,n,_rt[dfn[rt[qu[i][0]]][1]],
_rt[dfn[rt[qu[i][0]]][0]-1],k-bg[qu[i][0]]+1);
qu[i][2]=Half_Find(1,m+1,l);
qu[i][3]=Query(1,n,_rt[dfn[rt[qu[i][2]]][1]],
_rt[dfn[rt[qu[i][2]]][0]-1],l-bg[qu[i][2]]+1);
}
DFS(1);DSF(1,1);
for (int i=1;i<=p;i++) printf("%lld\n",GetAns(i));
return 0;
}
D2T1：如果询问一组我们直接元素排序之后一个一个加进来就好了。询问多组我们考虑维护答案。
设询问左端点右端点分别为x和y。那么当前我们加入坐标为i，i左边可以延伸到le，i右边可以延伸到ri，那么我们分类讨论x与le的大小关系还有ri与y的大小关系可以搞出不同的四个式子，这四个式子都可以看成a0xy+a1x+a2y+a3的形式，这个东西是可以看成4种不同的标记用线段树维护的。然后其影响的询问也就是转换成二维问题之后的一个矩形，所以我们直接扫描线+线段树就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
ll ad[N*4][4],Ans[N],cz[N*9][5],wz[N*9][3];
int sg[N*9],fa[N],bd[N][2],v[N],st,n,m;PII li[N];
inline int Read()
{
int x=0;char y;bool z=false;
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;
}
int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x]));}
inline void Get(int x,int y,int z,int o,ll _x,ll _y,ll _z,ll _o)
{
wz[++st][0]=x;wz[st][1]=z;wz[st][2]=o;
cz[st][0]=true;cz[st][1]=_x;cz[st][2]=_y;cz[st][3]=_z;cz[st][4]=_o;
wz[++st][0]=y;wz[st][1]=z;wz[st][2]=o;
cz[st][0]=false;cz[st][1]=-_x;cz[st][2]=-_y;cz[st][3]=-_z;cz[st][4]=-_o;
}
void Pretreat()
{
for (int i=1;i<=n;i++) li[i]=mp(-v[i],i);
sort(li+1,li+n+1);
for (int i=1;i<=n;i++)
{
int k=li[i].sc;fa[k]=bd[k][0]=bd[k][1]=k;
if (fa[k-1]) bd[k][0]=bd[Find(k-1)][0],fa[Find(k-1)]=k;
if (fa[k+1]) bd[k][1]=bd[Find(k+1)][1],fa[Find(k+1)]=k;
int bg=bd[k][0],ed=bd[k][1];
Get(bg,k+1,k,ed,-v[k],v[k]*(k-1LL),v[k]*(k+1LL),(1-1LL*k*k)*v[k]);
if (bg-1)
Get(1,bg,k,ed,0,0,(k-bg+1LL)*v[k],(k-bg+1LL)*(1LL-k)*v[k]);
if (ed<n)
Get(bg,k+1,ed+1,n,0,-(ed-k+1LL)*v[k],0,(k+1LL)*(ed-k+1LL)*v[k]);
if (bg-1&&ed<n)
Get(1,bg,ed+1,n,0,0,0,(k-bg+1LL)*(ed-k+1)*v[k]);
}
return;
}
inline bool cmp(int x,int y)
{return wz[x][0]<wz[y][0]||(wz[x][0]==wz[y][0]&&cz[x][0]<cz[y][0]);}
inline void Down(int z)
{
int j = z << 1;
for (int i=0;i<2;i++)
for (int k=0;k<4;k++) ad[j+i][k]+=ad[z][k];
for (int k=0;k<4;k++) ad[z][k]=false;
return;
}
inline void Modify(int x,int y,int z,int o,int p,ll _x,ll _y,ll _z,ll _o)
{
int mid = x + y >> 1, j = z << 1;
if (x==o&&y==p)
{
ad[z][0]+=_x;ad[z][1]+=_y;ad[z][2]+=_z;ad[z][3]+=_o;
return;
}
if (p<=mid) Modify(x,mid,j,o,p,_x,_y,_z,_o); else
if (o>mid) Modify(mid+1,y,j+1,o,p,_x,_y,_z,_o); else
Modify(x,mid,j,o,mid,_x,_y,_z,_o),
Modify(mid+1,y,j+1,mid+1,p,_x,_y,_z,_o);
return;
}
ll Query(int x,int y,int z,int o,int p)
{
if (x==y)
return 1LL*ad[z][0]*o*p+1LL*p*ad[z][1]+1LL*o*ad[z][2]+ad[z][3];
int mid = x + y >> 1, j = z << 1;Down(z);
if (o<=mid) return Query(x,mid,j,o,p); else
return Query(mid+1,y,j+1,o,p);
}
int main()
{
freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
n=Read();m=Read();st=m;
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=m;i++) wz[i][0]=Read(),wz[i][1]=Read(),cz[i][0]=2;
Pretreat();
for (int i=1;i<=st;i++) sg[i]=i;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=st;i++)
if (cz[sg[i]][0]!=2)
Modify(1,n,1,wz[sg[i]][1],wz[sg[i]][2],cz[sg[i]][1],cz[sg[i]][2],
cz[sg[i]][3],cz[sg[i]][4]); else
Ans[sg[i]]=Query(1,n,1,wz[sg[i]][1],wz[sg[i]][0]);
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return 0;
}
D2T2：不懂平面图那套理论。。
D2T3：设1~i所形成的十进制数字为Prei，则当P!=2&&P!=5,i<j时，我们要求(Prej-Prei*10^(j-i))%P==0的个数。
化一下式子两遍都除以10^-j则Prej*10^(-j)==Prei*10^(-i) %P，然后就可以直接变成小z的袜子了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
#define PII pair <ll,int>
#define fr first
#define sc second
#define mp make_pair
int n,m,val[N];char ch[N];ll P,ans;
inline ll Read()
{
ll 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;
}
ll Q_Multi(ll x,ll y)
{
ll z=false;
while (y) z=y&1?(z+x)%P:z,x=(x+x)%P,y >>= true;
return z;
}
ll Q_Power(ll x,ll y)
{
ll z=true;
while (y) z=y&1?Q_Multi(z,x):z,x=Q_Multi(x,x),y >>= true;
return z;
}
namespace Solve0
{
PII li[N];ll Inv,Pre,pre[N],_pre[N],Ans[N],ans;
int rt,st,_sg[N],Cnt[N],sg[N],qu[N][2];
void Pretreat()
{
for (int i=0;i<=n;i++) li[i]=mp(pre[i],i);
sort(li,li+n+1);pre[li[0].sc]=st=1;
for (int i=1;i<=n;i++)
pre[li[i].sc]=(st+=li[i].fr!=li[i-1].fr);
return;
}
inline bool cmp(int x,int y)
{return _sg[qu[x][0]]<_sg[qu[y][0]]||(_sg[qu[x][0]]==_sg[qu[y][0]]&&
qu[x][1]<qu[y][1]);}
inline void Add(int x) {ans+=Cnt[x]++;}
inline void Del(int x) {ans-=--Cnt[x];}
void Solve()
{
Inv=Pre=Q_Power(10,P-2);
for (int i=1;i<=n;i++)
_pre[i]=(10LL*_pre[i-1]+val[i])%P,
pre[i]=Q_Multi(Pre,_pre[i]),Pre=Q_Multi(Pre,Inv);
Pretreat();rt=(int)sqrt(n);
for (int i=1;i<=n;i++) _sg[i]=(i-1)/rt;
for (int i=1;i<=m;i++) qu[i][0]=Read(),qu[i][1]=Read();
for (int i=1;i<=m;i++) sg[i]=i;
sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=m;)
{
memset(Cnt,false,sizeof Cnt);ans=false;int ri=i;
while (ri<m&&_sg[qu[sg[ri+1]][0]]==_sg[qu[sg[i]][0]]) ri++;
int bg=qu[sg[i]][0]-1,ed=qu[sg[i]][1];
for (int j=bg;j<=ed;j++) Add(pre[j]);
Ans[sg[i]]=ans;
for (;i<=ri;i++)
{
int _bg=qu[sg[i]][0]-1,_ed=qu[sg[i]][1];
while (bg>_bg) Add(pre[--bg]);
while (ed<_ed) Add(pre[++ed]);
while (bg<_bg) Del(pre[bg++]);
while (ed>_ed) Del(pre[ed--]);
Ans[sg[i]]=ans;
}
}
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return;
}
}
namespace Solve1
{
ll pre[N],_pre[N];
void Solve()
{
for (int i=1;i<=n;i++)
{
pre[i]=pre[i-1];_pre[i]=_pre[i-1];
if (val[i]%P==0)
pre[i]+=i,_pre[i]++;
}
while (m--)
{
int k=Read(),l=Read();
printf("%lld\n",pre[l]-pre[k-1]+(_pre[l]-_pre[k-1])*(1-k));
}
return;
}
}
int main()
{
freopen("number.in","r",stdin);freopen("number.out","w",stdout);
P=Read();scanf("%s",ch+1);n=strlen(ch+1);
for (int i=1;i<=n;i++) val[i]=ch[i]-'0';
m=Read();
if (P==2||P==5) Solve1::Solve(); else
Solve0::Solve();
return 0;
}
总之完结了。。感觉day1还是太naive。。T2知道log^2不可写就要去想log^3的。。T3明明可以写出来但是对自己代码能力太没自信了。。不过我也不知道在考场那样的氛围下能不能写出来。。
但是还是感觉很虚啊。。day1好像有13、4个人A题的吧。。我这种渣渣暴力完全不能同台竞技啊。。
教训是能做的题还是要尽量做，考试的时候不要方就是干。纯暴力选手没有好下场。现在想想考试的时候自己明明写得出来但是没有写正解还是非常不爽的。
hnoi 2016 游记
省选前找了找状态。。感觉还是很虚。。
Day0：中午就过去了。家里面都来了所以感觉除了写题目有点不知所措。。
晚上背了板子然后就感觉一阵发虚。。然后就着Gromah博客的BGM把学长们还有VFK、Claris一些人的退役文还有省选游记等一些乱七八糟的东西看了一遍思考了一些东西感觉非常感慨。。
晚上睡觉的时候隐隐约约感觉这次我会坐到mx和yyt中间。。
Day1：虚的很。。7:20+来考场发现什么人都没有。。然后陆陆续续来了一群大爷。后来看到了策爷吉利。。脑袋上插了一堆家长们加持的flag就这么进考场了。然后发现woc真尼玛坐在myy和yyt中间。。感觉虚的要死。。开考前打FFT板子的手都是抖的。。开考看题woc数据结构专场真是sxbk。。后面两道题比较一眼。。第一题不怎么看得出是一个分块，觉得后面两题都写不完应该T1弃疗en。。然后作死开T3倍增巨坑。写了一个小时8、9k吧。。感觉脑袋都是炸的代码不能调。于是想了想就弃疗了。。第二题点分治+线段树好像比较良心但是时间感觉也不一定够就没开了。三题暴力打起。。最后暴力都没打完只打了120分。结束前一个小时myy一直在考场上骂街调不出来感觉也应该是第三题。出考场本来还感觉说不定暴力选手是有希望的但是听说一堆人A题都是估分100+myy200+估分就虚的要死。。我本来就是暴力再挂上一些岂不GG。。感觉明天还是这个样子是要滚粗的。。后来也确实发现总分前面那些人就我一个SB没有写一题正解。而且事后去写这些题，发现也不是那么不可做。。
出来吃饭大家都是一副喜闻乐见的样子感觉就我一个sb药丸。。后来也确实比较虚。等到成绩下来发现还是没有丢掉什么奇怪的分数。听说myy220果然还是不能同台竞技。不过感觉今天题目也是很不科学。。不知道为什么hn要搞出一个数据结构队。
期间dns还发来了短信的祝福加持。感觉药丸。。
day1就这么结束了。我这SB平时也没有加什么代码能力的技能点也就只能得这么多分。
Day2：晚上莫名感觉没有第一天这么虚了。感觉还是紧张一点好，不然总感觉会出现一些奇怪的错误。还想起了之前所有比赛的被线踩的flag不知道这次会不会灵验。。进去之前家长们的flag更大了，而且讲的那么大声感觉非常羞耻play。【捂脸】开考前我打NTT板子的手还是抖的。开题我发现我误会了省选组织单位，他们不是排错题了，因为他们不管怎么排都是每天3道数据结构。不过感觉今天的题没有那么大码农。。T1一眼扫描线+线段树维护4种标记en，T3一眼搞一搞逆元变成了莫队。enT2smg的平面图不知所措。码暴力三道题，然后就一个小时了。T1T3码码码拍拍拍分别一个小时。后来就不知所措了。各种暴力一暴力二正解互相拍，肉眼调T3的各种坑点爆long long什么的。。还有将近两个小时不知所措。然后还是很虚所以一直在那里拍拍拍虽然并没有什么卵用。。最后一个小时围观前排CJ小哥也是打完两题不知所措。。旁边的myy和yyt都一直在码码码T2orz。。
考完跑出来感觉很不错然而想起那个神奇的被线卡flag就虚的要死。毕竟成绩出来之前什么都有可能发生。中饭的时候zy还一直给我洗脑“yali的大爷们都写了50分平面图”、“yali的大爷们day1都是150、160”真是虚的要死。坐在一个大机房里面等成绩。如果在一些奇怪地方挂了就真的完蛋了。。期间出数据出代码。测出来发现175吓得要死，最后发现这题数据范围写错了。。成绩出来之后除了前面乱入的策爷之外好像就win了。。想想这两天都没有写挂什么分数。然后就神奇Rank5了。。之前以为Rank4终于尼玛可以破掉被线卡flag然而zhangzj大爷day1高10分联赛也高一点。。感觉真是心里发虚，这样下去NOI如果没破掉的话已经没有什么其它的线了感觉是药丸。。不过我们学校也没有出过A类所以这次就当做是学校的锅了en。我们学校没有发生什么奇迹。duyege好像考的还可以但是day1太浪自信写T2而不是暴力所以跪成50不然也差不多可以卡线进队orz。不过还能够买C吧可能，有人能够陪我继续下去还是挺好的。感觉也有些认识的人挂了比较伤感。。。毕竟总有人考得好也总有人会考挂。。
回来之后很久都没有缓过劲来，感觉一直都是紧张而懵逼的状态。吃饭这几天都吃不下什么东西。除了结果之外其它感受都是不太好的。这样决定性的比赛也还好只会有一次了。
总结一下的话感觉调试能力还是太弱所以day1就算有时间也不一定敢写T2。day2基本上还是正常。所以分数还是比较理想。但是如果这次崩掉了哪怕一题都会直接进不了了。（简直废话）想想感觉我个SB基本上什么题都没有什么特殊的优势，代码能力弱姿势水平低也就只能够靠稳了。
虽然之前说过这段时间没什么干劲，但是既然都进队了还是尽量拼一把吧。反正也只有三个月了。感觉都搞到这个时候了最后NOI滚粗了回去搞高考会非常不爽。后段时间多打比赛多写题。开些51nod和UOJ还有BZOJ的坑吧，对了此后各省省选题会陆续补口胡报告。补姿势的话虽然这次补的板子一个都没用上但是还是补一些之前没有搞过的常用的姿势比如FWT什么的一直都没有搞，还有高数相关的有些东西如果不是特别麻烦感觉也是可以去补一补。
搞到这个时候后面一些奇怪的比赛比如THUSC等一些东西都会出来了。依旧bless all吧。
最后引用我校学长的一句话吧：命运下的蝼蚁？
写在省选之前
省选还有一星期。。
这段时间浑浑噩噩。。OI已经失去了动力。博客也没有更了。以后也估计只会有滚粗文或者退役文了。
只不过在摸索了一段时间考试策略之后终于啃上了拼命攒的老本考试成绩翻上来了。
只不过对很多事情都比较消极。整个人心态经常不好又敏感。
考试的时候也不是注意一些细节。经常会在一些奇怪的地方滚粗。
最近几次集训之后对自己终于有了一些奇怪的自信，因为没那么容易滚粗了所以分数虚在半空中。于是在省选前一星期心态开始浪的时候天天爆炸。。
又一次开始思考人生。觉得我这种样子肯定是药丸的。好在还有一个星期。自己多做几场考试调整一下吧。
平时已经够浪了。考试再浪就真的只能滚粗了。。
en最后一次省选了。。求不滚粗不退役吧。。
[UPD 4.15]省选前一天了，求不跪。。
