zijunhz

  • 首页

  • 关于

  • 标签

  • 归档

  • 搜索

luoguP2845 [USACO15DEC]Switching on the Lights 开关灯

发表于 2018-11-05
题目 函数1:用于点亮(x,y)能开的灯,假设能开(xx,yy),将(xx,yy)交至函数2 函数2:判断(x,y)是否能被走到(即4个方向有被访问到的点相邻),如果能,将(x,y)交至函数1,遍历(x,y)的4个方向,如果有亮着灯但没有被访问的点(xx,yy),将(xx,yy)交至函数2 主程序 ...
阅读全文 »

luoguP3932 浮游大陆的68号岛

发表于 2018-11-05 | 更新于 2018-11-06
题目 开四个数组: $lcnt[i]$记录仓库i左边(不包括i)共有多少物品 $rcnt[i]$记录仓库i右边(不包括i)共有多少物品 $lcost[i]$记录将仓库i左边的所有物品移到仓库i所需的代价 $rcost[i]$记录将仓库i右边的所有物品移到仓库i所需的代价。 $lcnt[i]$和$ ...
阅读全文 »

luoguP4047 [JSOI2010]部落划分

发表于 2018-11-05
题目 考虑将两两点之间的距离算出来并从小到大排序。 显然,应该优先合并距离小且不在一个部落中点对。因为如果不合并,则最小距离就是这两个点间的距离了。 code1234567891011121314151617181920212223242526272829303132333435363738394 ...
阅读全文 »

luoguU50590 数字

发表于 2018-11-05
题目(num) 我们可有用DP很快地求出用x个数字构成y的方案数 1f[i][j]=f[i-1][m-a[k]] 其中a()为数字集合S中的数。 主要难点在于题目中条件3:前后和相等或奇偶和相等。考虑容斥。 我们可以很快地求出前后和相等+奇偶和相等的方案数,再减去既是前后和相等又是奇偶和相等的方 ...
阅读全文 »

luoguP2967 [USACO09DEC]视频游戏的麻烦Video Game Troubles

发表于 2018-11-05
题目 f(i,j)表示前i个游戏平台花费j的最大愉悦值。 难点在于保证买该平台游戏,则游戏平台一定要买。 如果按照金明的预算方案那样对于每个附属品选/不选肯定要T。 考虑f(i,j)=max( f(i-1,j-x)+y , f(i-1,j) ),这里x和y是一个附属物品的体积和价值。 如果直接这么 ...
阅读全文 »

luoguP3034 [USACO11DEC]牛摄影Cow Photography

发表于 2018-11-04
题目 考虑对于任意两头牛a和b,假设a在b前面。 他们在5张照片中,至少有3张照片,a在b前面,剩下一张可能是a移到了后面,还有一张可能是b移到了前面,但无论如何,至少有3张照片他们的相对位置保持不变。 这样就可以排序了。 p.s.还需要离散化。 code123456789101112131415 ...
阅读全文 »

luoguP3621 [APIO2007]风铃

发表于 2018-11-04
题目 什么时候不合法:最大玩具深度(下文记为mx)比最小玩具深度(下文记为mn)大至少2。 对于一根木棍,木棍左边连接有深度为mx、mn的玩具,木棍右边也连接有深度为mx,mn的玩具,这时候交换左右,仍然不可能满足题目的第二个要求。 计算ans在合法的前提下,对于一根木棍,如果左边有深度为mn的玩 ...
阅读全文 »

luoguP1291 [SHOI2002]百事世界杯之旅

发表于 2018-11-02
题目 假设有n个不同名字 先抽一次,必定抽出一个新的——ans+1 再抽第二次,这时有(n-1)/n的概率能抽到新的,所以期望抽n/(n-1)次能抽到新的——ans+n/(n-1) 再抽第三次,这时有(n-2)/n的概率能抽到新的,所以期望抽n/(n-2)次能抽到新的——ans+n/(n-2) … ...
阅读全文 »

luoguP3946 ことりのおやつ(小鸟的点心)

发表于 2018-11-02
题目 跑出每个点被雪覆盖的时间 跑dijk,如果到这个点的最短时间超过限制,就置为不连通。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#inclu ...
阅读全文 »

luoguP1875 佳佳的魔法药水

发表于 2018-11-01
题目 这道题目有点奇怪。 我交堆优化dijk,怎么样都A不掉,都只有10分。 检查了7个小时,重构过,依然不行。 然后放下尊严写邻接矩阵写堆优化,一遍A…. why???? 大致是这么做的: 每种药是一个点,假设a+b合成c,那么建一条a到c的边,边权为得到b的代价,建一条b到c的边,边权为得到 ...
阅读全文 »
123
zijunhz

zijunhz

30 日志
29 标签
© 2019 zijunhz