JZYshuraK

未归档

/ 注册

全部文章 / 未归档（共392篇）

[poj2406]Power Strings_hash

Power Strings poj-2406 　　　　题目大意：询问一个字符串最多几个相同且连续的字符串构成(Eg：abababab由4个构成，abcd由1个构成)。　　　　注释：字符串长度为n，$1\le n\le 10^6$. 　　　　　　想法：hash裸题，通过Hash求出单个字符串的...

2018-03-19

0 305

[poj3904]Sky Code_状态压缩_容斥原理

Sky Code poj-3904 　　　　题目大意：给你n个数，问能选出多少满足题意的组数。　　　　注释：如果一个组数满足题意当且仅当这个组中有且只有4个数，且这4个数的最大公约数是1，$1\le n\le 10^4$。　　　　　　想法：我们显然可以知道4个数是可以不用两两互质的，所以正...

2018-03-19

0 257

[luogu2831][noip d2t3]愤怒的小鸟_状压dp

愤怒的小鸟 noip-d2t3 luogu-2831 　　　　题目大意：给你n个点，问最少需要多少条经过原点的抛物线将其覆盖。　　　　注释：1<=点数<=18，1<=数据组数<=30。且规定抛物线是开口向下的。　　　　　　想法：其实一开始的想法是很偏的，就是设dp[...

2018-03-19

0 389

[poj3740]Easy Finding_状态压缩_dfs

Easy Finding poj-3470 　　　　题目大意：给你一个01矩阵，问能否选出一些行，使得这些行所新组成的01矩阵每列中有且只有1个1。　　　　注释：1<=行数<=16，1<=列数<=300. 　　　　　　想法：对于一个单独的01矩阵来讲，我们可以用一个数...

2018-03-19

0 325

[bzoj1565][NOI2009]植物大战僵尸_网络流_拓扑排序

植物大战僵尸 bzoj1565 　　　　题目大意：给你一张网格图，上面种着一些植物。你从网格的最右侧开始进攻。每个植物可以对僵尸提供能量或者消耗僵尸的能量。每个植物可以保护一个特定网格内的植物，如果一个植物被保护，那么如果僵尸想吃掉该植物就必须先吃掉保护它的植物。问：僵尸最多能获得多少能量。　...

2018-03-17

0 351

[bzoj1497][NOI2006]最大获利_网络流_最小割

最大获利 bzoj-1497 　　　　题目大意：可以建立一个点，花费一定的代价；将已经建立的两个点之间连边，得到一定收益。有些节点之间是不允许连边的。　　　　注释：1<=点数<=5,000，1<=允许连边的边数<=50,000。　　　　　　想法：将每个可以相连的点之...

2018-03-16

0 271

[luogu1402]酒店之王_网络流

酒店之王 luogu-1402 　　　　题目大意：有n个人，p道菜，q个房间，每个人喜欢吃一些菜、喜欢住一些房间，如果一个人即住到了他喜欢的房间有吃到了他喜欢的菜，就对答案贡献++，求最大贡献。　　　　注释：1<=n,p,q<=100. 　　　　　　想法：网络流第二题，和上一题相...

2018-03-16

0 350

[jdoj1817]Drainage Ditches_网络流

Drainage Ditches jdoj-1817 　　　　题目大意：网络流裸求最大流　　　　注释：n(点数)，m(边数)<=200. 　　　　　　想法：裸的网络流求最大流，用bfs+dfs，美其名曰dinic。　　　　没有开始？何来最后... ...代码... ... ...

2018-03-16

0 311

[poj2923]Relocation_状压dp_01背包

Relocation poj-2923 　　　　题目大意：给出n个物品，有两辆车，两辆车必须一起出动并且每辆车有单独的容量。问最少需要运输多少次才能运走所有货物。　　　　注释：n<=10，容量，物品代价<=1000且物品代价<=max(两车容量)。　　　　　　想法：这题的...

2018-03-15

0 465

[poj3254]Corn Fields_状压dp

Corn Fields poj3254 　　　　题目大意：给你一个n*m的地，每一块地可以种或不种，两块种过的地不能挨着，可以一块都不种，问所有的种地方案数。　　　　注释：读入用0和1，1<=n,m<=12. 　　　　　　想法：这题和炮兵阵地特别像，比炮兵更简单。我们再度入的时候...

2018-03-14

0 319