Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

05/17
20:49
杂题

[bzoj 4874] 筐子放球

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

小N最近在研究NP完全问题,小O看小N研究得热火朝天,便给他出了一道这样的题目:
有 n 个球,用整数 1 到 n 编号。还有 m 个筐子,用整数1到m编号。
每个球只能放进特定的两个筐子之一,第 i 个球可以放进的筐子记为 Ai 和 Bi 。
每个球都必须放进一个筐子中。
如果一个筐子内有奇数个球,那么我们称这样的筐子为半空的。
求半空的筐子最少有多少个。
小N看到题目后瞬间没了思路,站在旁边看热闹的小I嘿嘿一笑:"水题!"
然后三言两语道出了一个多项式算法。
小N瞬间就惊呆了,三秒钟后他回过神来一拍桌子:
"不对!这个问题显然是NP完全问题,你算法肯定有错!"
小I浅笑:"所以,等我领图灵奖吧!"
小O只会出题不会做题,所以找到了你--请你对这个问题进行探究,并写一个程序解决此题。

Read More →

[bzoj 4874] 筐子放球

@krydom3月前

05/17
20:46
杂题

[bzoj 4895] 项链分赃(增强版)

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

你和你的1个同伙偷了一串长度为n的项链,它上面有m种颜色的珠子,我们假设项链为链状的,并且每一颗珠子都是随机分布,现在我想知道,对于给定的n,m你在最坏情况下最少需要切多少刀 才能使得你们可以通过每人获得一些切完之后的项链,并且满足每个人得到的每种宝石的数量刚好相同,我们假设珠子的数目一定是偶数。也就是说对于每种情况都一定存在一种解决方案。然而这才是这个问题的真正形式。

Read More →

[bzoj 4895] 项链分赃(增强版)

@krydom3月前

05/17
20:26
杂题

[bzoj 4878] [Lydsy2017年5月月赛]挑战NP-Hard

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

天才大学生quailty热衷于解决NP-Hard问题,你如果AC 了这道题,就可以成为他真正的粉丝。图染色问题:给定无向图G和一个正整数k。对于图中的每个点,选择一个在[1,k]之间的整数作为其颜色。你需要保证对于每条边,其两端点的颜色均不相同。简单k路径问题:给定无向图G和一个正整数k。请找到一条经过了恰好k条边的简单路径。即,你需要找到一个长度为k+1的序列v_1,v_2,...,v_{k+1},满足1<=v_i<=n,且任意两个v均不相同,同时v_i与v_{i+1}之间存在一条边。现在给定无向图G和一个正整数k,quailty知道你没有他的水平,所以你只需解决上面的任意一个问题就可以成为他的粉丝。

Read More →

[bzoj 4878] [Lydsy2017年5月月赛]挑战NP-Hard

@krydom3月前

05/17
20:02
杂题

[bzoj 4893] 项链分赃

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有一串长度为n的项链,上面有红绿蓝三种颜色的珠子,每种颜色的珠子数目都是偶数,现在要你把它切几刀分成若干段,把其中一些段分给海盗1,剩余的段分给海盗2,要求两个海盗分得的每种颜色的珠子数量都相同,请输出最少需要切多少刀。

Read More →

[bzoj 4893] 项链分赃