HNOI2015填坑
HJWJBSR
posted @ 2015年9月17日 23:17
in 题解
, 656 阅读
UPD 9.20 我真心想吐槽这东西我交了3遍重写了两遍刷了一个小时这篇题解才交上去TATQAQ2333
HNOI滚粗半年之后才来填坑= =
主要是当时姿势水平不够，现在回去看题目应该会好些了
至少现在不会一道都不会只能打暴力了
亚瑟王：
想了很久TM就是想不出来，后来Orzei题解。
原来是设的第i个卡牌有j个机会的时候的概率，因为不会用LaTeX之类的东西放公式太丑了还是点链接里的看好了
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
long double ans,p[N],v[N],f[N][N];int n,m,t;
inline long double s(int x,int y)
{return pow(1-p[x],y);}
int main()
{
cin >>t;
while (t--)
{
memset(f,0,sizeof(f));
cin >>n>>m;ans=0;f[0][m]=1;
for (int i=1;i<=n;i++)
{
double k,l;
scanf("%lf%lf",&k,&l);
p[i]=k;v[i]=l;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j]=f[i-1][j]*s(i-1,j)+f[i-1][j+1]*(1-s(i-1,j+1)),
ans+=f[i][j]*(1-s(i,j))*v[i];
printf("%.10lf\n",(double)ans);
}
return 0;
}
接水果：
maya我一直以为这个是树套树，YY了一下感觉一般二分答案的搞法还是n log^3 n的，感觉要线段树套线段树然后先找出第一层的log n的节点然后边比较log n个节点的子树大小边往左右走才能搞到n log^2 n的，但是空间复杂度也是O(n log^2 n)的真是好虚啊
所以果断就弃坑了
后来感觉不行还是要来填坑，结果NM发现*利的代码只有100h缩行比我还屌，才知道这题要用整体二分。
一开始刚看到这东西感觉还是非常玄幻的
但是在二分的同时不仅减小了答案范围的大小，同时询问的规模还有盘子的个数也是同时在减小的
所以就不虚了。
具体来说就是先搞出DFS序，然后分两种情况讨论，
对于每个盘子如果两个点没有祖先关系它所能接到的水果的两点的DFS序分别在两个子树里面
否则的话设较深的那个点为v，另外一个点为u，v的比u深1的祖先为k，这个倍增求一下
则水果上两个点的DFS序分别在v的子树里面
另外一个要不就比k的DFS序小要不就比k子树内的最大DFS序大
所以每个盘子就相当于最多两个矩形
然后每个询问也对应了一个点
问题就变成了求每个点被覆盖的矩形里面的第k小值
这东西就整体二分搞了
首先对于当前二分的区间，我们弄出其中值小于等于mid的盘子
然后排个序，询问也排个序，然后扫一遍，球当前所有点分别被多少盘子覆盖，线段树明显可以搞
最后比较涉及的所有询问和求得的个数
如果个数小于询问的k则询问的k减去求得个数然后把这个询问放到b序列
否则这个询问放到a序列
a序列的答案就在[L,mid]里面，b序列的答案就在[mid+1,R]里面
并且盘子中值小于mid的都可以归到a里面，其余的都归到b里面。
所以询问规模每次都是减半的
算上线段树还有排序的复杂度这东西就是O(n log^2 n)的了，而且空间也顶多有一个倍增数组的O(n log n)
感觉理清思路之后其实也还好写
然而一开始开的线段树的空间是3n的挂掉了，虽然一般说是3n就够用了但是空间还够用的时候还是开4n比较保险
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50050
#define INF 0x7f7f7f7f
struct Point
{int tp,x,y,z,v;} li[N*5];
int fi[N],c[N*2][2],n,m,sg[N][2],ss=1,st,St,p,t[N],fa[N][20];
int s[N*4],ad[N*4],ans[N],h[N],S[N*5];
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)
{
sg[x][0]=++st;h[x]=h[fa[x][0]]+1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,DFS(c[i][0]);
sg[x][1]=st;
}
int Find(int x,int y)
{
for (int i=16;i>=0&&fa[x][0]!=y;i--)
if (h[fa[x][i]]>h[y]) x=fa[x][i];
return x;
}
inline void Push(int x,int y,int z,int o,int p)
{li[++st].tp=x;li[st].x=y;li[st].y=z;li[st].z=o;li[st].v=p;}
inline bool cmp(Point x,Point y)
{return x.x<y.x;}
inline void adj(int x,int y,int z)
{
if (!ad[z]) return;
if (x!=y) ad[z*2]+=ad[z],ad[z*2+1]+=ad[z];else
s[z]+=ad[z];
ad[z]=0;
}
void Insert(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;
if (x==o&&y==p) {ad[z]+=u;return;}
if (o<=i) Insert(x,i,j,o,min(p,i),u);
if (p>i) Insert(i+1,y,j+1,max(o,i+1),p,u);
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
adj(x,y,z);if (x==y) return s[z];
return o<=i?Query(x,i,j,o):Query(i+1,y,j+1,o);
}
void Half_Find(int x,int y,int z,int o,int p,int u)
{
if (x>y||z>o||p>u) return;
if (x==y)
{
for (int i=p;i<=u;i++) ans[li[i].v]=t[x];
return;
}
int mid=x + y >> 1,ri=z-1,r1=z,r2=p;
for (int i=z;i<=o;i++)
if (li[i].v<=t[mid]) swap(li[i],li[++ri]);
sort(li+z,li+ri+1,cmp);sort(li+p,li+u+1,cmp);
while (r1<=ri||r2<=u)
if (r1<=ri&&(r2>u||(li[r1].x<=li[r2].x)))
Insert(1,n,1,li[r1].y,li[r1].z,li[r1].tp==1?1:-1),r1++;else
S[r2]=Query(1,n,1,li[r2].y),r2++;
r2=p-1;
for (int i=p;i<=u;i++)
if (S[i]>=li[i].z)
swap(li[++r2],li[i]);else
li[i].z-=S[i];
Half_Find(x,mid,z,ri,p,r2);
Half_Find(mid+1,y,ri+1,o,r2+1,u);
}
int main()
{
n=Read();m=Read();p=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);st=0;
for (int i=1;i<=16;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for (int i=1;i<=m;i++)
{
int q=Read(),w=Read(),e=Read();t[i]=e;
if (sg[q][0]>sg[w][0]) swap(q,w);
if (sg[q][1]<sg[w][0])
Push(1,sg[q][0],sg[w][0],sg[w][1],e),
Push(2,sg[q][1]+1,sg[w][0],sg[w][1],e);else
{
q=Find(w,q);
Push(1,1,sg[w][0],sg[w][1],e);
Push(2,sg[q][0],sg[w][0],sg[w][1],e);
if (sg[q][1]!=n)
Push(1,sg[w][0],sg[q][1]+1,n,e),
Push(2,sg[w][1]+1,sg[q][1]+1,n,e);
}
}
sort(t+1,t+m+1);St=st;
for (int i=1;i<=p;i++)
{
int q=Read(),w=Read(),e=Read();
if (sg[q][0]>sg[w][0]) swap(q,w);
Push(3,sg[q][0],sg[w][0],e,i);ans[i]=INF;
}
Half_Find(1,m,1,St,St+1,st);
for (int i=1;i<=p;i++)
printf("%d\n",ans[i]);
return 0;
}
菜肴制作：
建图，j->i，然后每次选出入度为0的最大点，倒序输出就是答案。
YY一下感觉是对的，泥要问我怎么证这东西我怎么会知道。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
int a[N],n,m,fi[N],c[N][2],s[N],li[N],ri;
inline void Insert(int x)
{
int i=++ri;
li[i]=x;
while (i!=1&&li[i]>li[i/2])
swap(li[i],li[i/2]),i/=2;
return;
}
inline void Delete()
{
int i=1,k;
li[1]=li[ri--];
while (i*2<=ri)
{
k=i*2+(i*2<ri&&li[i*2+1]>li[i*2]);
if (li[k]<li[i])
break;
swap(li[k],li[i]);i=k;
}
return;
}
int main()
{
int i,j,k,l,q,w,e,ss;
scanf("%d",&ss);
while (ss--)
{
memset(fi,0,sizeof(fi));memset(c,0,sizeof(c));
memset(s,0,sizeof(s));memset(li,0,sizeof(li));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&k,&l);
c[i][0]=k;c[i][1]=fi[l];fi[l]=i;s[k]++;
}
ri=0;
for (i=n;i>=1;i--)
if (!s[i])
li[++ri]=i;
w=0;
while (ri&&w!=n)
{
e=li[1];Delete();
for (i=fi[e];i;i=c[i][1])
{
s[c[i][0]]--;
if (!s[c[i][0]])
Insert(c[i][0]);
}
a[++w]=e;
}
if (w!=n)
{
printf("Impossible!\n");
continue;
}
for (i=n;i>=1;i--)
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
落忆枫音
madan记得看题面的时候当场就喷了，这还是我第一次推的galgame，而且当时被虐的要死，虽然说原画是有点崩的，不过当时感觉是很不错啊，如果TM不是某个素质低下的人剧透感觉会推起来更带感。顺便一提个人是比较萌海音的。话说好像扯远了= =
感觉吧如果没有多出来的那条边就是直接把除1之外所有点的出边个数乘起来，然而当时我这都没想出来= =
多了一条边就是拓扑图DP了，先把原图反过来建，然后拓扑排序一下，然后从多出来的那条边的终点开始更新它的出边上的点j的答案就是当前的Si*Multi(i+1,j-1)，Multi是从i+1到j-1的所有点的出边个数之积，这东西前缀和处理下然后逆个元什么的就好了。终点的S值是1~T-1的乘积，最后得到起点的答案之后还要乘以Multi(S+1,n)，最后得到的这个东西cnt，答案就是加上那条多余的边之后的所有点出度乘积-cnt。感觉并没有讲人话，反正就是按照原来的方法统计答案会出现问题，也就是会有包含了那个多余边的环也算进了答案，所以我们拓扑图DP统计这东西并减去就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 1000000007
#define ll long long
int fi[N],c[N*2][2],fa[N],S,T,n,m,ss=1,cnt[N],li[N],sg[N];
ll ans,s[N][2],tot[N];queue <int> a;
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;fa[x]++;cnt[y]++;}
ll Quick_Power(ll x,int y,ll z)
{ll k=1;while (y) k=y&1?k*x%z:k,x=x*x%z,y >>= 1;return k;}
inline ll Query(int x,int y)
{return s[y][0]*s[x-1][1]%M;}
void Top_Sort()
{
for (int i=1;i<=n;i++)
if (!cnt[i]) a.push(i);
s[0][0]=s[0][1]=1;
for (int i=1;i<=n;i++)
{
sg[li[i]=a.front()]=i;a.pop();
s[i][0]=s[i-1][0]*fa[li[i]]%M;
s[i][1]=Quick_Power(s[i][0],M-2,M);
for (int j=fi[li[i]];j;j=c[j][1])
{
cnt[c[j][0]]--;
if (!cnt[c[j][0]])
a.push(c[j][0]);
}
}
for (int i=1;i<=n;i++)
{
if (li[i]==S)
tot[S]=Query(1,i-1);else
if (li[i]==T)
ans=(ans-tot[T]*Query(i+1,n)%M+M)%M;
for (int j=fi[li[i]];j;j=c[j][1])
tot[c[j][0]]=(tot[c[j][0]]+Query(i+1,sg[c[j][0]]-1)*tot[li[i]]%M)%M;
}
return;
}
int main()
{
n=Read();m=Read();S=Read();T=Read();
for (int i=1;i<=m;i++) Line(Read(),Read());
if (S==T) S=T=0;ans=1;
for (int i=2;i<=n;i++)
ans=ans*(fa[i]+(i==T))%M;
if (T!=1)
fa[1]=1,Top_Sort();
cout <<ans<<endl;
return 0;
}
开店
一眼点分治，一开始还准备用线段树，但是空间怎么算都是会爆炸的，于是前缀和就好了。
如果真在考场上面碰到这题真心写起来需要勇气啊
1A（主要是样例数据良心），正好卡时过= =时间常数这么大肯定是人丑没办法
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 8000050
#define ll long long
int fi[N],c[N*2][3],gf[N][21],n,m,p,ss=1,sg[N][21],st=0;ll ans;
int h[N][21],sum[N],li[N],s[N],t[N],cnt[N],la[N],Rt[N][20];
struct Point {int x,y,z;} a[N];
inline ll max(ll x,ll y)
{return x<y?y:x;}
struct ST
{
ll s[M*3];int t[M][2],cnt;
inline void Push(int x,int y,int z)
{t[++cnt][0]=x;t[cnt][1]=y;s[cnt]=z;}
void Set_up()
{for (int i=2;i<=cnt;i++) s[i]+=s[i-1];}
ll Query(int x,int y,int z,int o,ll p)
{
int i=x + y >> 1;
if (x>y) return -1;
if (t[i][0]<z||(t[i][0]==z&&t[i][1]<=o))
return max(Query(i+1,y,z,o,p),i*p+s[i]);else
return Query(x,i-1,z,o,p);
}
} A;
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 z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
inline void Calc(int* x,int* y)
{
int k=(*x+ans)%p,l=(*y+ans)%p;
*x=min(k,l);*y=max(k,l);
}
inline bool cmp(Point x,Point y)
{return x.x<y.x||(x.x==y.x&&x.y<y.y);}
inline bool cpm(Point x,Point y)
{return x.y<y.y;}
int BFS(int x,int y)
{
int le=1,ri=1;li[1]=x;h[x][y]=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]]&&!cnt[c[i][0]])
h[c[i][0]][y]=h[li[le]][y]+c[i][2],
li[++ri]=c[i][0],la[c[i][0]]=li[le];
return ri;
}
int Find(int x,int y)
{
for (int i=1;i<=y;i++) sum[li[i]]=0;
for (int i=y;i>=1;i--) sum[la[li[i]]]+=++sum[li[i]];
while (1)
{
int k=0;
for (int i=fi[x];i;i=c[i][1])
if (!cnt[c[i][0]]&&c[i][0]!=la[x]&&sum[c[i][0]]*2>y)
{x=c[i][0];k=1;break;}
if (!k) return x;
}
}
void Set_up(int x,int y)
{
int tot=BFS(x,y),rt=Find(x,tot),ri=1;BFS(rt,y);
sg[rt][cnt[rt]=y]=++st;
for (int i=2;i<=tot;i++)
if (la[li[i]]==rt)
gf[li[i]][y]=li[i],sg[li[i]][y]=++st;else
gf[li[i]][y]=gf[la[li[i]]][y];
for (int i=1;i<=tot;i++)
a[i].x=sg[gf[li[i]][y]][y],a[i].y=t[li[i]],a[i].z=h[li[i]][y],
Rt[li[i]][y]=rt;
sort(a+1,a+tot+1,cpm);
for (int i=1;i<=tot;i++)
A.Push(sg[rt][y],a[i].y,a[i].z);
sort(a+1,a+tot+1,cmp);
for (int i=2;i<=tot;i++)
A.Push(a[i].x,a[i].y,a[i].z);
for (int i=fi[rt];i;i=c[i][1])
if (!cnt[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
ll query(int x,int y,int z,int o)
{
ll k=A.Query(1,A.cnt,x,z,o),l=A.Query(1,A.cnt,x,y-1,o);
if (k==-1) k++;if (l==-1) l++;
return k-l;
}
ll Query(int x,int y,int z)
{
ans=query(sg[x][cnt[x]],y,z,0);
for (int i=cnt[x]-1;i>=1;i--)
ans+=query(sg[Rt[x][i]][i],y,z,h[x][i])-
query(sg[gf[x][i]][i],y,z,h[x][i]);
return ans;
}
int main()
{
n=Read();m=Read();p=Read();A.cnt=0;
for (int i=1;i<=n;i++) t[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
Set_up(1,1);A.Set_up();
while (m--)
{
int q=Read(),w=Read(),e=Read();
Calc(&w,&e);
printf("%lld\n",Query(q,w,e));
}
return 0;
}
实验比较
感觉思路还是比较好想的，就是优化一个DP
首先设Ai,j,k代表我们合并两个长为i和j的只有小于的链成一个长为k的链的方案数
就等于Σ(b=0 to j) Ai-1,b,k-j+b-1 + Σ (b=0 to j-1) Ai-1,b,k-j+b
分别是枚举的i链第一个点在哪个位置和第一个点和哪个点合并。这东西是n^4的
所以考虑前缀和优化，可以观察到Σ里面的Ai,j,k里面的k-j都是一定的
所以我们再设一个Si,j,k代表Σ(b=0 to k) Ai,k,k+j 这东西边求Ai,j,k的时候就可以边处理出这个数组
最后就是树形DP，可以设个超级根连掉所有的根，然后DFS一遍就好了。
合并的时候就是枚举两条链的长度以及生成链的长度用A转移
这东西看上去是n^4的，虽然实际上我也不知道它复杂度多少但是我们可以记录每个子树所生成的链最大最小的长度多少来优化
所以就非常愉快了
还要注意的是狗哔题面并没有说会有环但是是有这种情况的
所以要特判掉环的情况输出0
建边就是并查集搞一搞
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
#define M 1000000007
#define ll long long
int s[N][N][N],a[N][N][N],fa[N],len[N][2],S[N][N],n,m,ans;
int fi[N],c[N*2][2],ss=1,ln[N][3],li[N];char b[20];bool d[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 bool cmp(int x,int y)
{return ln[x][2]<ln[y][2];}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[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 Set_up()
{
n++;
for (int i=0;i<=n;i++)
a[0][i][i]=1,s[0][0][i]=i+1;
for (int i=1;i<=n;i++)
for (int j=0;j<=n-i;j++)
for (int k=max(i,j);k<=i+j;k++)
a[i][j][k]=((k==j?0:s[i-1][k-j-1][j])+s[i-1][k-j][j-1])%M,
s[i][k-j][j]=(s[i][k-j][j-1]+a[i][j][k])%M;
n--;
}
void Merge(int x,int y)
{
ll Aha[N];memset(Aha,0,sizeof(Aha));
for (int i=len[x][0];i<=len[x][1];i++)
for (int j=len[y][0];j<=len[y][1];j++)
for (int k=max(i,j);k<=i+j;k++)
Aha[k]=(Aha[k]+(ll)(S[x][i])*S[y][j]%M*a[i][j][k]%M)%M;
len[x][0]=max(len[x][0],len[y][0]);
len[x][1]=len[x][1]+len[y][1];
for (int i=len[x][0];i<=len[x][1];i++)
S[x][i]=Aha[i];
}
void DFS(int x)
{
d[x]=S[x][0]=1;
for (int i=fi[x];i;i=c[i][1])
if (!d[c[i][0]])
DFS(c[i][0]),Merge(x,c[i][0]);
len[x][0]++;len[x][1]++;
for (int i=len[x][1];i>=len[x][0];i--)
S[x][i]=S[x][i-1];
}
bool DSF(int x,int y)
{
d[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (d[c[i][0]]&&c[i][0]!=y) return 1;else
if (!d[c[i][0]]&&DSF(c[i][0],x)) return 1;
return 0;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
int k=Read();scanf("%s",b);int l=Read();
ln[i][0]=k;ln[i][1]=l;ln[i][2]=b[0]=='<';li[i]=i;
}
sort(li+1,li+m+1,cmp);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++)
if (ln[li[i]][2])
Line(Find(ln[li[i]][0]),Find(ln[li[i]][1])),
d[Find(ln[li[i]][1])]=1; else
fa[Find(ln[li[i]][1])]=Find(ln[li[i]][0]);
for (int i=1;i<=n;i++)
if (!d[i]&&Find(i)==i) Line(n+1,i);
memset(d,0,sizeof(d));
int check=DSF(n+1,0);
for (int i=1;i<=n;i++)
if (!d[i]&&Find(i)==i) check=1;
if (check) {puts("0");return 0;}
memset(d,0,sizeof(d));
Set_up();DFS(n+1);
for (int i=len[n+1][0];i<=len[n+1][1];i++)
ans=(ans+S[n+1][i])%M;
cout <<ans<<endl;
return 0;
}
相比Day1的题感觉Day2的题良心多了
评论 (0)
