NOI2016 D1T2题解
考场上面写的东西。因为我不会求割点，然后可能常数比较大。
就是离散化之后把所有的轮廓线都拿出来，然后轮廓线就是很多环，给环上每个线段定个向，方向指向没有格子的那一边。
比如一行一列有个格子，它下方是一个轮廓线的一部分，那么这个这部分的方向就是往下的。
做这个的办法就是画个图出来发现可以每次找到一个没有提过的线段然后逆时针找下一个线段是哪一个。这东西需要用map存。
判掉无解的情况：最多只有两个空格子
判掉不用的情况：轮廓线顶部的线条是往下的环个数就是连通块个数。
判掉只用一个格子的情况：枚举黑格子，然后在它旁边8个格子试着放一个黑格子，然后用之前的方法去判断能不能把一个环切成两部分。
最后那个情况我在考场上面处理的比较naive，所以跪了。而且我一直以为是对的，到后面才拍出来。
现在想想如果考场上面能够一次想清楚不浪费时间的话说不定还是刚的出来的。
这方法止增笑耳。
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题的吧。。我这种渣渣暴力完全不能同台竞技啊。。
教训是能做的题还是要尽量做，考试的时候不要方就是干。纯暴力选手没有好下场。现在想想考试的时候自己明明写得出来但是没有写正解还是非常不爽的。
51nod 部分题解
POI20填坑计划
感觉是至今推过的最神的一届。。而且还有交互题简直厉害。。
惯例先口胡：
[ByteComputer]：一眼DP
[Tower Defense Game]：直接随便删就好。为了保证复杂度标记哪些点是所连的所有点都被删除的
[Polarization]：详见15年论文“启发式思想”。知道了结论之后就直接背包就好。多重背包我用了倍增+bitset。虽然带个log但是跑的飞起。贪心搞法好神啊。
[Take-out]：直接维护一个栈然后如果最后k+1个可以删除就删除。合法性显然。最后也肯定不会有剩余，这个也可以证明。
[Tales of seafaring]：直接每个点为起点BFS一遍就好
[Taxis]：写个式子很容易发现出租车在左边的时候明显先放大的车更优。于是只要分两种情况：要留一个刚好大于等于右边距离的车和不要留取个答案最大值就好。
[Triumphal arch]：一眼二分答案+树形DP
[Multidrink]：很明显一棵子树只能跳进去一次。然后我觉得树形DP+分类讨论就好。但是分类讨论好麻烦的样子不知道还有没有更加优美的姿势啊。
[Inspector]：二分答案显然，然后我觉得应该就差分搞搞，然后贪心一下就好？Tn log n的
[Walk]：只会在每个点搜一下连通块，然后调下阀值什么的能不能过啊？好虚啊。
[Tapestries]：JB几何题直接弃疗了
[Maze]：这题海瑞斯特说他一眼秒！感觉其实也就是拿个栈维护一下哪些东西可以被提出来，比如LR、RL之类的东西。
[Colorful Chain]：水题。。
[Laser]：波兰文不能看
[Watering can]：水题。。每次删除就好。。
[Watering can]：有点意义不明。。不知道那个M(n)到底是干什么的。。
