从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 .........................
•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 ...