从N个三元组{matches, red, blue}取出尽量多的组,使得取出的{matches}的任何非空子集的异或都不为0,也就是两个人用来玩NIM游戏,先手必赢。在必赢的情况下,求出最小的sum{red} * sum{blue}..
问题1:取出的{matches}任何非空子集都是先手必赢,可以采用贪心的方法,利用|{matches}| == 矩阵的质。
问题2:使得sum{red} * sum{blue}最小,我们定出贪心的顺序。
对于问题2,
对于每个最优解OPT, 定义: sigma{OPT.red[i]} = R and sigma{OPT.blue[i]} = B.
定义: w[i] = red[i] + t * blue[i] (t = R / B)
所以: sigma{OPT.w[i]} = 2 * R.
对于其他解 S, 定义: sigma{S.red[i]} = r ,sigma{S.blue[i]} = b.
那么 sigma{S.w[i]} = r + b * t >= 2 * sqrt(r * b * t) >= 2 * sqrt(R * B * t) = 2 * R
所以: sigma{S.w[i]} >= sigma{OPT.w[i]}. 而且当且仅当S是最优解,等号成立。
由于有N个数,最多会有(N*N) 个t,枚举之。
补充:
有N个二元组{a,b},选出M个使得sum{a} * sum{b} 最小。
用堆可以在N * N * logN的时间内解决。
分享到:
相关推荐
*padding:2px 5px 0 5px;margin-left:8px;overflow:hidden}.tools{position:absolute;right:-75px}#mHolder{width:62px;position:relative;z-index:296;display:none}#mCon{height:18px;line-height:18px;position:...
Section 1-1: Early History .............................................................................................................5 The Early Years: Telegraph to Telephone .........................
第5章 用visual basic进行声明式编程 255 5.1 声明式编程与visual basic 256 5.2 使用xaml创建窗口 257 5.3 xaml语法 260 5.3.1 xaml语言基础 261 5.3.2 使用xaml声明工作流 264 5.4 小结 265 第6章 ...
•NETGEAR WGT624, WGR614v9, WNR1000v3, WNR3500L, and possibly other models. •NETGEAR DEVG2020 •ASUS WL-520g, WL-600g, and possibly similar models. •ASUS RT-N10+ , and possibly similar models. ...
1.1.3 一维数组的高级应用 5 范例1-3 一维数组的高级应用 5 1.1.4 显示杨辉三角 7 范例1-4 显示杨辉三角 7 ∷相关函数:c函数 8 1.1.5 魔方阵 9 范例1-5 魔方阵 9 1.1.6 三维数组的表示 14 范例1-6 三维数组...
1.1.3 一维数组的高级应用 5 范例1-3 一维数组的高级应用 5 1.1.4 显示杨辉三角 7 范例1-4 显示杨辉三角 7 ∷相关函数:c函数 8 1.1.5 魔方阵 9 范例1-5 魔方阵 9 1.1.6 三维数组的表示 14 范例1-6 三维数组...
G1 Z-5. F200. X-62.939 C4.827 F16.1 F值可以输出G99格式 X-61.649 C7.514 X-60.51 C10.281 X-59.526 C13.12 X-58.699 C16.024 X-58.031 C18.983 X-57.523 C21.985 X-57.177 C25.019 X-56.994 C28.073 X-56.973 C31...
" " " "自由选择电信,网通,铁通,联通 " " " "多线路 " " "526元/3年 " " " "878元/5年 " " "200M 多线虚拟主机空 "312元/年 "1. 不限流量,IIS并发数200个 " "间 " "2. 赠送企业邮箱5用户,500M容量 " "支持...
1.1.3 一维数组的高级应用 5 范例1-3 一维数组的高级应用 5 1.1.4 显示杨辉三角 7 范例1-4 显示杨辉三角 7 ∷相关函数:c函数 8 1.1.5 魔方阵 9 范例1-5 魔方阵 9 1.1.6 三维数组的表示 14 范例1-6 三维数组...
062 统计月销售量1000以下、利润2000元以上商品数 138 063 统计特色商品数量 139 064 统计各部门职工的学历情况 140 065 统计销售部总人数 142 066 自动生成员工编号 143 067 统计学生缺考总次数 144 ...
T2E_WRE526(T) 已知温度T,求WRE-526型热电偶热电势(单位:mV) E2T_S(E) 已知热电势E,求S型热电偶温度(单位:℃) E2T_N(E) 已知热电势E,求N型热电偶温度(单位:℃) E2T_R(E) 已知热电势E,求R型热电偶温度(单位:℃) E2T_...
1000+声音效果,您可以直接导入到您的项目高科技武器机械,设计科幻装药,和数百个武器射击 各种武器射击类型,包括翘曲,霞弹枪,重型,激光,爆能枪,小型,等等 100多个武器的多样性增加声音的多样性 超过900MB的...
* NETGEAR WGT624, WGR614v9, WNR1000v3, WNR3500L, and possibly other models. * NETGEAR DEVG2020 * ASUS WL-520g, WL-600g, and possibly similar models. * ASUS RT-N10+ , and possibly similar models. * ...
4 <br>0008 为程序设置版本和帮助信息 4 <br>0009 设置Windows应用程序启动窗体 5 <br>0010 设置Web应用程序起始页 5 <br>0011 如何设置程序的出错窗口 5 <br>0012 如何进行程序调试 6 ...