BZOJ 1006
膜了一上午CDQ的弦图课件
真尼玛一堆性质/定理
不过基本上懂了
这题就是直接用，首先用MCS求完美消除序列。然后有一个性质：最大团=最小染色数。
看网上一堆人写的好长贪心求染色的都是没看到这个性质就弃坑了么= =。
然后就直接求个最大团就可以了。还有个性质就是最大团为每个点跟其完美消除序列位置后面相连的点的导出子图是一个团
所以只要枚举每个点看其连的点里面有多少个在其前面就可以了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 1000050
#define fr first
#define sc second
int c[M*2][2],ss=1,fi[N],n,m,ans,sg[N],s[N];bool b[N];
priority_queue <pair<int,int> > li;
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 Solve()
{
for (int i=1;i<=n;i++)
li.push(make_pair(0,i));
for (int t=n;t>=1;t--)
{
do sg[t]=li.top().sc,li.pop(); while (b[sg[t]]);
b[sg[t]]=1;
for (int i=fi[sg[t]];i;i=c[i][1])
if (!b[c[i][0]])
li.push(make_pair(++s[c[i][0]],c[i][0]));
}
for (int i=n;i>=1;i--)
{
int k=0;b[sg[i]]=0;
for (int j=fi[sg[i]];j;j=c[j][1])
if (!b[c[j][0]]) k++;
ans=max(ans,k+1);
}
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
Line(Read(),Read());
Solve();
cout <<ans<<endl;
return 0;
}
HNOI2015填坑
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的题良心多了
NOI2015填坑
Day1
T1 签到题
T2 树剖裸题
T3 神题：
考场上面就没想出来
重新往状压DP方向想了一（hen）下（jiu）发现依旧没想出来
因为每个数大于sqrt(n)的质因数最多只有1个，所以可以状压前8个质数，然后把每个数依次加进来计算方案。
设f(S,T)为第一个人的状态为S且第二个人状态为T的时候的当前方案个数，然后还设个g0/g1(S,T)分别是两个人选择当前这个质因数的时候的方案数，最后处理完这个质因数就把f处理成g0+g1-f，因为两个都不选算了两遍。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 256
#define M 505
#define fr first
#define sc second
#define ll long long
pair <int,int> li[M];
int f[N][N],g[2][N][N],n,m,ans;
const int Prime[]={2,3,5,7,11,13,17,19};
inline int Mod(ll x)
{return (x+m)%m;}
int main()
{
cin >>n>>m;
for (int i=2;i<=500;i++)
{
int k=i;
for (int j=0;j<8&&k-1;j++)
while (k%Prime[j]==0)
k/=Prime[j],li[i-1].sc|=1 << j;
li[i-1].fr=k;
}
sort(li+1,li+n);
f[0][0]=1;
for (int i=1;i<n;i++)
{
if (li[i].fr==1||li[i].fr!=li[i-1].fr)
memcpy(g[0],f,sizeof f),memcpy(g[1],f,sizeof f);
for (int k=N-1;k>=0;k--)
for (int l=N-1;l>=0;l--)
if ((l&li[i].sc)==0)
g[0][k|li[i].sc][l]=Mod(g[0][k|li[i].sc][l]+g[0][k][l]);
for (int k=N-1;k>=0;k--)
if ((k&li[i].sc)==0)
for (int l=N-1;l>=0;l--)
g[1][k][l|li[i].sc]=Mod(g[1][k][l|li[i].sc]+g[1][k][l]);
if (li[i].fr!=li[i+1].fr||li[i].fr==1)
for (int k=0;k<N;k++)
for (int l=0;l<N;l++)
f[k][l]=Mod(g[0][k][l]+g[1][k][l]-f[k][l]);
}
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
ans=Mod(ans+f[i][j]);
cout <<ans<<endl;
return 0;
}
Day2
T1：按哈弗曼树那样贪心，只不过一次选取最小的k个，并且高度也要贪心选取。如果n%k!=0就补位。
由于是考场上面A的就懒得放代码了= =
T2：后缀排序+并查集，后缀排序之后就求出了两两相邻字典序后缀之间的相似程度，就可以从n-1到0扫一遍，每次用相似程度为i的两对更新答案。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 600050
#define fr first
#define sc second
#define ll long long
pair <int,int> a[N];ll ans,Ans[N][2],s[N],ma[N],mi[N],tot,INF;
int n,m,fa[N],c[N],d[N],sx[N],sy[N],li[N];char b[N];
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;
}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
inline ll max(ll x,ll y)
{return x<y?y:x;}
inline ll min(ll x,ll y)
{return x<y?x:y;}
void aa(int x)
{
memset(c,0,sizeof(c));memset(d,0,sizeof(d));
memset(sy,0,sizeof(sy));int ri=x;
for (int i=0;i<x;i++) sy[i]=n-i-1;
for (int i=0;i<n;i++)
if (sx[i]>=x) sy[ri++]=sx[i]-x;
for (int i=0;i<n;i++) c[li[i]]++;
for (int i=1;i<=n;i++) c[i]+=c[i-1];
for (int i=0;i<n;i++)
sx[c[li[sy[i]]-1]++]=sy[i];
d[sx[0]]=1;
for (int i=1;i<n;i++)
d[sx[i]]=d[sx[i-1]]+1-(li[sx[i]]==li[sx[i-1]]&&
li[sx[i]+x]==li[sx[i-1]+x]);
for (int i=0;i<n;i++) li[i]=d[i];
}
int main()
{
n=Read();
scanf("%s",b);
for (int i=1;i<=n;i++) ma[i]=mi[i]=Read(),fa[i]=i,s[i]=1;
for (int i=0;i<n;i++) c[b[i]]++;
for (int i=1;i<=256;i++) c[i]+=c[i-1];
for (int i=0;i<n;i++)
sx[c[b[i]-1]+(d[b[i]]++)]=i,
li[i]=c[b[i]];
for (int i=1;i<n;i <<= 1) aa(i);
int now=0,ri=0;ans=INF=-(ll)(1e18);
for (int i=0;i<n;i++)
{
now-=now>0;
if (li[i]==1) continue;
while (i+now<n&&sx[li[i]-2]+now<n&&b[i+now]==b[sx[li[i]-2]+now]) now++;
a[++ri].fr=now;a[ri].sc=i+1;
}
sort(a+1,a+n);ri=n-1;
for (int i=n-1;i>=0;i--)
{
while (ri&&a[ri].fr==i)
{
int k=Find(a[ri].sc),l=Find(sx[li[a[ri].sc-1]-2]+1);
if (k!=l)
fa[k]=l,ans=max(ans,ma[k]*ma[l]),
ans=max(ans,mi[k]*mi[l]),
ma[l]=max(ma[l],ma[k]),mi[l]=min(mi[k],mi[l]),
tot+=s[l]*s[k],s[l]+=s[k];
ri--;
}
Ans[i][0]=tot;Ans[i][1]=ans;
}
for (int i=0;i<n;i++)
printf("%lld %lld\n",Ans[i][0],!Ans[i][0]?0:Ans[i][1]);
return 0;
}
T3这种凶残的题还是不准备现在填坑了= =
BZOJ 2716/2648
膜了一发K-D Tree这种高端东西
感觉比想象中好写。
但是不用指针就会T，用了指针就跑的飞起只有10+s感觉实在不科学= =
这个版本并没有套上暴力重建，也懒得套暴力重建了= =
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000050
#define INF 0x7f7f7f7f
struct Point
{int x,y,x1,y1,x2,y2;Point *c[2];};
int n,m;
bool cmp(const Point &x,const Point &y)
{return x.x<y.x;}
bool cpm(const Point &x,const Point &y)
{return x.y<y.y;}
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;
}
struct KD_Tree
{
int st,ans;Point now,*gf,t[N];
inline int Minimum(Point *x,Point y)
{
int k=0;
if (y.x<x->x1) k+=x->x1-y.x;else
if (y.x>x->x2) k+=y.x-x->x2;
if (y.y<x->y1) k+=x->y1-y.y;else
if (y.y>x->y2) k+=y.y-x->y2;
return k;
}
inline int Dis(Point *x,Point y)
{return abs(x->x-y.x)+abs(x->y-y.y);}
inline void Get(int x)
{
t[x].x=t[x].x1=t[x].x2=Read();
t[x].y=t[x].y1=t[x].y2=Read();
}
inline void Update(Point *x,Point *y)
{
x->x1=min(x->x1,y->x1);
x->x2=max(x->x2,y->x2);
x->y1=min(x->y1,y->y1);
x->y2=max(x->y2,y->y2);
}
Point *Build(int x,int y,int z)
{
int k=x + y >> 1;
if (x>=y) return x==y?&t[x]:NULL;
nth_element(t+x,t+k,t+y+1,z?cmp:cpm);
t[k].c[0]=Build(x,k-1,!z);
t[k].c[1]=Build(k+1,y,!z);
if (t[k].c[0]!=NULL) Update(&t[k],t[k].c[0]);
if (t[k].c[1]!=NULL) Update(&t[k],t[k].c[1]);
return &t[k];
}
void Insert(Point *x,int y,int z)
{
int k=(z&&x->x<=t[y].x)||(!z&&x->y<=t[y].y);
if (x->c[k]==NULL)
x->c[k]=&t[y];else
Insert(x->c[k],y,!z);
Update(x,x->c[k]);
}
void query(Point *x,int y)
{
int k=(y&&x->x<=now.x)||(!y&&x->y<=now.y);
ans=min(ans,Dis(x,now));
if (x->c[k]!=NULL&&Minimum(x->c[k],now)<ans)
query(x->c[k],!y);
if (x->c[!k]!=NULL&&Minimum(x->c[!k],now)<ans)
query(x->c[!k],!y);
}
int Query(int y,int x)
{
ans=INF;now.x=x;now.y=y;
query(gf,0);return ans;
}
} A;
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
A.Get(i);
A.gf=A.Build(1,n,0);A.st=n;
while (m--)
if (Read()-1)
printf("%d\n",A.Query(Read(),Read()));else
A.Get(++A.st),A.Insert(A.gf,A.st,0);
return 0;
}
USACO Gold题填（bei）坑（nue）计划
做起来果然比Silver带感多了，更能体现我智商癌的本质。
感觉自己还真是萎废，这种题还做得一卡一卡的
BZOJ1230 线段树
BZOJ1231 一开始没想出来，后来发现是状压DP
BZOJ1233 好神的贪心+DP，首先一个草堆要最高必须要底层最瘦。证明好像其它地方有，然后就可以DP了，记录第i个到第n个最优情况下有多瘦、有多高。一开始没注意底层宽度不一定具有单调性，然后就wa了，后来看了一下式子发现要用单调队列优化。
BZOJ1571 直接DP
BZOJ1572 首先把工作按照截止日期排个序，然后从后往前枚举时间点用个set什么的每个时间点选取最大价值的。
BZOJ1574 贪心，把跟那些点相邻的点都打上标记，最后从起点DFS能到达多少没打标记的点，最后用n-cnt就是答案了
BZOJ1575 预处理出每个区间的误差值和，最后DP一下
BZOJ1577 按照右端点排序，然后依次放就好了。
BZOJ1578 一个东西第i天买进第j天卖出相当于每天都买入卖出，所以直接算出每天最多有多少钱，也就是每天背包一下。
BZOJ1581 DP，设ai,j代表前i+j位放了i个0和j个1，有多少种方案。算第k大也是扫一遍什么的就好了
BZOJ1583 直接算，只不过题意是真的艹蛋
BZOJ1584 发现k最大只能是200，所以直接DP好了
BZOJ1585 好久没做网络流的题目了裸的最小割没看出来TAT
BZOJ1589 BFS
BZOJ1590 trie
BZOJ1592 离散化+DP
BZOJ1593 我写的splay,调起来极其带感
BZOJ1596 贪心
BZOJ1597 斜率优化
BZOJ1692 后缀数组
BZOJ1694 DP，算的是这段距离对答案的总贡献所以并没有后效性
BZOJ1697 想到了正解一开始并不敢写= = 对于每个置换环要不就用其中最小的节点在上面移，要不就把全局最小的移进来。
BZOJ1699 重题了
BZOJ1702 前缀和一下然后差分一下然后排个序
BZOJ1703 猜了个结论就是不能确认的关系的对数
BZOJ1704 乱搞
BZOJ1705 DP，因为增加的高度不会太大，但是不能只开到10，我反正开到20才过
BZOJ1706 矩阵快速幂
BZOJ1707 乱搞
BZOJ1708 背包
BZOJ1709 首先找到一个有对手的格子，答案就只能放在它的八个方向的格子上
BZOJ1710 DP
BZOJ1711 TAT果然网络流荒废太久了都不记得了，建图S->F->N->D->T
BZOJ1712 乱搞+快速幂
BZOJ1690 分数规划+二分答案+找负环，感觉好神啊。一开始还没看到路线是个环，感觉无论如何都不能理解= =
BZOJ1604 好神的规律题啊，可以看这里。
BZOJ1598 K短路，然而因为是拓扑图所以可以用A*算法。记得我以前是看过鼎爷的论文的然而已经忘得差不多了= =
