bzoj刷题总结列表.pdf

1293:[SCOI2009]生日礼物队列，排序。按位置排序，依次加入队列。加入一个元素后判断，保证队首颜色只有一种。1083:[SCOI2005]繁忙的都市最小生成树，水题。1237:[SCOI2008]配对1015:[JSOI2008]星球大战starwar离线倒着做并查集。把星球一个个的加入图中。一开始没过是因为有一个i写成x了。。。1602:[Usaco2008Oct]牧场行走Lca。用len[i,k]记录距离：len[i,j]:=len[i,j-1]+len[p[i,j-1],j-1];求lca时顺便求一下距离。最后不要忘了求完lca后a与b同时再往上提一次提到根。1854:[Scoi2010]游戏二分图匹配。属性向装备连边。比较特殊的是做到某一次不能匹配时就立刻停止。注意fori:=1tom+1do因为是输出i-1所以要到m+1。wa了好几次。。。。1497:[NOI2006]最大获利最大权封闭子图。站点权为负值，若两点间有收益则新建一个点，权为正收益，向两点连边。最后求一遍最大权封闭子图就是答案。因为建图时弄成了long[other[ee]]:=c；而不是0所以调了好半天。。。1565:[NOI2009]植物大战僵尸最大权封闭子图。由被保护的向保护者连有向边。注意因为可能有环，环上的都不可能被吃掉，所以要先用拓扑排序消环。先把所有的边反向，每次选入度为1的点删除，最后被访问过的点加入图中。由于可能有一个环保护一个点的情况，所以强连通分量是不对的（坑）。1088:[SCOI2005]扫雷Mine数学，水题。因为发现前两个格子确定后，后面的都可以确定，所以枚举第一个格子就行了。1051:[HAOI2006]受欢迎的牛强连通分量。缩点后，若有一个出度为0的点，则输出点集中点个数。若有多个则impossible。1189:[HNOI2007]紧急疏散evacuate网络流，spfa，二分答案。1296:[SCOI2009]粉刷匠动态规划,前缀和。sum[i,j,1],sum[i,j,0]维护前缀和f[i,j,k]表示第i行前j个格子刷k次能正确粉刷的最大格子数。ans[i,j]表示前i行刷j次所能正确刷的最大格子数。f[i,j,k]=max(f[i,j,k],f[i,l,k-1]+max(sum[i,j,1]-sum[i,l,1],sum[i,j,0]-sum[i,l,0]));ans[i,j]=max(ans[i,j],ans[i-1,j-k]+f[i,m,k]);L要从0开始循环，wa了2次。1230:[Usaco2008Nov]lites开关灯线段树。区间修改，xor1。1193:[HNOI2006]马步距离1103:[POI2007]大都市meg线段树维护dfs序。dfs序中一棵子树对应的区间是连续的一段，我们可以区间修改。1050:[HAOI2006]旅行comf枚举最小边，然后由小到大向里面加边。直到s，t连通。1005:[HNOI2008]明明的烦恼树的prufer数列，数学设没有度数限制的点有m个，有度数限制的点度数为d[i]，t:=∑(d[i]-1)。答案为m^(n-2-t)*C(n-2,t)*t!/∏(du[i]−1)!用高精度乘法，除数与被除数每个数分解质因数，排序后相同的消除。1003:[ZJOI2006]物流运输trans动规，spfaf[i]表示从第一天到第i天最少总成本。cost[x,y]表示第x天到第y天只用同一运输方案所用的最少成本,spfa预处理得到。f[i]=min(f[i],f[j]+cost[j+1][i]+k);1607:[Usaco2008Dec]PattingHeadsp[i]表示i出现了几次。forj:=1to[√n]doans:=ans+p[j]+p[a[i]divj](a[i]modj=0)加p[a[i]divj]条件是j*j<>a[i]。1934:[Shoi2007]Vote善意的投票最大流。建立S，T，同意的向S连边，不同意的向T连边，朋友之间连边，流量都是1.跑最小割。2783:[JLOI2012]树树上倍增。枚举每个点i，if(now+sum[a,i]<=s)then<倍增>2761:[JLOI2011]不重复数字平衡树。水题，先查找有没有这个数，没有就加入。2431:[HAOI2009]逆序对数列动规，前缀和。用f[i][j]表示用1~i这些自然数组成的逆序对数为j的数列个数。f[i][j]=Σf[i-1][j-k](0<=k<i)前缀和优化一下sum[i,j]=Σf[i][k](0<=k<=j)2748:[HAOI2012]音量调节大水题。Bool型动规。1026:[SCOI2009]windy数令f[i][j]为有i位，且第i位(从右数,下同)为j的w数