HNOI 2016题解
NOI2016 D1T2题解

JLOI2016题解

HJWJBSR posted @ 2016年4月28日 14:28 in 题解 , 807 阅读
贵省的题目好鬼畜。。
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]:为什么这个坑在这里了呢？虽然就这么两道题不过不是很想管了所以就让它坑在这里吧。牛顿等幂和公式已经怎么样都好了，反正感觉就差不多那个意思了。分类讨论怎么样都好了，反正过的人那么多。于是这篇博客感觉也是怎么样都好了，最近已经懒得动了= =
Small_feed 评论 (1)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter