Problem Statement for MixingColors | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
SRM621 1000分 第3题算法解答_____________________________________________________________________________
看了算法解释,真心佩服,自己数学融汇贯通的能力差啊。当时怎么也想不出来。
数学原理:求rank,即通过最大线性无关组获得,计算机解法,高斯消元法(Gauss Elimination)
矩阵A的秩=rank(A) = rank({A1,A2, .... Am});
每一个数字,都可以表示为一个二进制向量,如3={0,1,1},向量的纬度 m = 最大数的位数(直接用32也可以)
以{3,5,6}为例:
于是:矩阵A = {3,5,6} =
0 1 1
1 0 1
1 1 0
采用高斯消元法:注,这个时候的消元不是通过线性加减,而是异或准则
0 1 1
1 0 1
1 1 0
选择主行(即第A(0,0)!=0即可)交换
1 1 0
0 1 1
1 0 1
第0行与第2行异或——》第2行
1 1 0
0 1 1
0 1 1
第1行与第二行异或
1 1 0
0 1 1
0 0 0
于是,对角线上不为0的个数= rank(A)=2,所以答案为2
import java.util.*; /** * User: Free * Date: 14-5-20 * Time: 下午11:51 */ public class MixingColors { public int minColors(int[] colors) { int len = colors.length; Arrays.sort(colors); int max = 1; int maxCount = 31; maxCount = Integer.toBinaryString(colors[colors.length - 1]).length(); int i = 0; byte[][] A = new byte[colors.length][maxCount]; for (; i < colors.length; i++) { String bits = Integer.toBinaryString(colors[i]); for (int j = 0; j < bits.length(); j++) { A[i][maxCount - bits.length() + j] = (byte) (bits.charAt(j) - '0'); } for (int j = 0; j < maxCount - bits.length(); j++) { A[i][j] = 0; } } //gauss elimination // process Row =r,Col=c,A[r][c]==0 int r = 0; int c = 0; int pivot; for (r = 0; r < colors.length; r++) { do { if (c >= maxCount) break; for (pivot = r; pivot < colors.length; pivot++) { if (A[pivot][c] == 1) { break; } } if (pivot < colors.length) { //swap ROW pivot,r if (pivot != r) { for (int j = c; j < maxCount; j++) { byte t = A[pivot][j]; A[pivot][j] = A[r][j]; A[r][j] = t; } } //eliminate; for (int curRow = r + 1; curRow < colors.length; curRow++) { if (A[curRow][c] != 0) { //XOR for (int j = c; j < maxCount; j++) { A[curRow][j] ^= A[r][j]; } } } c++; break; } else { c++; } } while (true); } //calc rank(A) int rankRow = 0; for (int row = 0; row < A.length; row++) { for (int col = 0; col < A[0].length; col++) { if (A[row][col] != 0) { rankRow++; break; } } } return rankRow; } public static void main(String args[]) { MixingColors mix = new MixingColors(); System.out.println(mix.minColors(new int[]{4, 8, 16, 32, 64, 128, 256, 512, 1024})); // System.out.println(mix.minColors(new int[]{3, 5, 6})); // System.out.println(mix.minColors(new int[]{1, 3, 4, 5, 6, 8})); // System.out.println(mix.minColors(new int[]{534, 251, 76, 468, 909, 410, 264, 387, 102, 982, 199, 111, 659, 386, 151})); // // System.out.println(mix.minColors(new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912})); } }
相关推荐
一种SRM仿真,其中采用了CCC方法对SRM进行控制,后续可以添加转速环进行转速控制。
Hasp SRM 32bit usb virtual driver source code.
基于SIMULINK对开关磁阻电机做的仿真工作,内容非常详细。
开启式螺杆水源热泵机组-中文
Driver HASP SRM emulator (x86)
ERP项目实施方法论--调研阶段--SRM调研提纲
G-SRM-SP-布局与策略.pptx
G-SRM-SP-布局与策略.zip
不错的VMware SRM资料,可以看看
蓝牙HC-05 主从机一体蓝牙模块 无线蓝牙串口透传模块 无线模块
基于改进的RIU-LBP和SRM的高分辨率遥感影像分割
Installation Documentation - SAP SRM 2007
NGOD的边缘服务器子架构定义:点播系统的最后一公里...
srm-wol SRM-WoL的测试仓库
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
执行部分代码M-SRM 用于预测智利北部中部融雪的修正融雪径流模型。 该存储库是作为 2013/2014 DEVELOP 项目的一部分创建的,该项目用于对智利北部中部融雪造成的可用水量进行粗略预测。 希望使用 M-SRM 的用户可以以...
G-SRM-SLM-生命周 期-01培训手册.pptx G-SRM-SP-供应商考核.pptx G-SRM-SP-布局与策略.pptx G-SRM-SP-综合绩效.pptx G-SRM-SR-供货比例-01培训手册.pptx G-SRM-SR-合同管理-01培训手册_.ppt G-SRM系统供应商绩效及...
SAP-SRM系统概览介绍
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
exam srm sample questions These questions and solutions are representative of the types of questions that might be asked of candidates sitting for Exam SRM. These questions are intended to represent ...