问某个日期后N天是几月几号星期几,我脑子里已经模拟的思路了。。但是懒得写,就用想python里面是否有现成的函数,没想到还真找到了。
代码十分简单,易读,唉,好方便,要是比赛中能用多好。。
(更多…)
问某个日期后N天是几月几号星期几,我脑子里已经模拟的思路了。。但是懒得写,就用想python里面是否有现成的函数,没想到还真找到了。
代码十分简单,易读,唉,好方便,要是比赛中能用多好。。
(更多…)
昨天下午新人比赛,我想找个模拟题,然后从大黄的题解上随便找了一个,比赛中途,我想敲敲试试,没想到光看题就用了20分钟,敲题用了半个多小时,最后到吃饭时候也没把样例给过了,心情十分郁闷。晚上回去,突然发现那些候选数字是以0为结尾的,于是我就换个结束的方法while( scanf(“%d”,&n) && n );然后他就华丽丽地在我的眼前AC了。
模拟对对碰,不过规则改了改,他不是交换两个相邻的格子,而是移动一行或一列,如果存在三个颜色相同的在一行或者一列,消去。说实话,难度不大。需要注意的两点:1.把k个操作保存起来再进行模拟,2. 候选格子是以0结尾的,不一样都放在一行输入上。我的代码用类把各种操作封装了。。
alsomagic 想给女朋友送宝石,但是gf不希望某种颜色太多,alsomagic 也不希望留在手中的宝石某种形状的太多(这个在刚开始看题时候理解不清楚,哎),还好alsomagic 有超能力,能让A形状B颜色的转换成C形状D颜色的,问能不能产生合适的分配。
题目中给出一个无向图,需要判断mst是否唯一。
本题用prim算法来做比较简单,具体来说,当一个节点被两个边更新的时候,如果他被选为下一个放入树中的点,那么连接他的边我们就不能确定了,也就是可能有多个最小生成树。上图,当a点确定的时候,b点更新为8,c点更新为12,然后b被加入树中,然后要更新c点,这时c的值12已经被两条边更新了,所以就可能产生多棵树。
城市宽带网络,由于不够用,所以需要扩大某些线路的容量,这样就可以增大网络的流量,你的任务就是寻找到这些边使得这些边容量一扩充就能增大流量。
每个城市都是源点,所以建立超级源点S,然后求S到T的最大流,从S开始dfs把点染色为1,再从T开始dfs把点染色成2,如果我们能找到一条边u,v一边是1,一边是2的话,这条边就是关键割边。注意割边不一定是关键的,因为对它扩容之后,与他临接的可能还是满流。。
(更多…)
我有种DP的感觉,也有种最短路的感觉,然后我就无语了。。
每个加油的地方要分拆成(c+1)个点,然后求最短路,但是我实在是太土了,真的是把点弄成了N(C+1)个,还建图了好多次,TLE到无语。。
后来看了题解,各种不明白,因为对所给图形的理解不是很好,这个题硬是搞了一天。
以前做过几个bfs优先队列的,但是对他的理解不是很深刻,现在慢慢了解,他跟dijkstra非常神似,也是一个贪心的过程,每次弹出最小量,然后他对应的那个值就确定了,因为他之后的不可能被更改。赶紧去找几个类似题目练练手~~~
(更多…)
乍看是带点权的最短路,实际上最短路再加上最大点权最小的时候才是最短,即min{ path(S,T) + min{w[i]|i on path from S to T}}.我表示没有思路,看的题解做的。。比如说我们要求出S,T的“最短路”,我们可以枚举最大中间节点,因为这条路必经经过一个最大中间节点,比如说我们找到点U的时候,就假设U是S到T路径上点权最大的点,可以把图上点权大于U的点去掉然后d[ S, U ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”,每给出一个询问,查询即可。
破坏一个棵树的,就是把他的所有边都删掉,现在有两种方式就是删掉i点的所有入边,还有就是删掉i点的所有出边,所需要的费用为Wi+,Wi-,每一条边<u,v>要被销掉,要么删除u的所有出边,要么删除v的所有入边,每条边都至少与一种操作相关联,我们可以联想到二分图的最小点集覆盖,求最小的点集,让所有的边都与之关联。对于这个题来说就是典型的模型了。二分图的最小点权覆盖,AMBER的论文第30页有讲,不再赘述,注意不要把边权选错了,入度的权在右边。。。我因为这个搞了一个下午。
还有,我的最大流模板已经十分完善了,就在blog上放我的模板,以后会填上费用流,强连通等的并且不断改进:
题目就不在赘述,很裸的最大点权闭合集,在《最小割模型在信息学竞赛中的应用》有证明,但是呢,我看的不是很懂,今天早上看了一早上,下午又看了一会,还不是很明白,真坑跌,我怎么就理解不了最小割呢?哎,路漫漫,网络流的各种模型我什么时候才能搞懂啊 = =
虽然我不懂,,,但是AC还是没有问题的。。。
(更多…)
以前刚开始看网络流的时候,下载过一个文档,《网络流建模汇总 by Edelweiss》,里面第一个模型就是这个题,当时看了好长时间,没看懂= =b,这两天重新看过之后,思路清晰了许多。网络流难的不是dinic,sap呀什么的,是建图,搞死人呢。。。
经过一番搜题解之后,我发现最详细的解释出自这里,凑活着看吧,上面的文档中也有(不过我打印出来是黑白的,图示不清)。
(更多…)