广联达笔试8-19
单选题
30道单选和三道编程题总分一样，都是60分。
30道单选做了45分钟左右，里面求程序执行结果的题有不少，考的也比较全面。
记录一题懵逼的题：思路先回到大一学的《离散数学》，又回到研一学的《凸优化》，但还是没有头绪，怒抄之。
在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题（）
A. 有多重最优解
B. 有无界解
C. 有唯一最优解
D. 无可行解
第一题
思路：双指针
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s1 = input.nextLine();
String s2 = input.nextLine();
int res = 0, len = s1.length();
int idx1 = 0, idx2 = 0;
while (idx1 < len && idx2 < len) {
if (s1.charAt(idx1) == s2.charAt(idx2))
res += 20;
if (s1.charAt(idx1) != s2.charAt(idx2)) {
if (res >= 10)
res -= 10;
else res = 0;
}
idx1++;
idx2++;
}
System.out.println(res);
}
}
第二题
草草读了一下题就返回第一题，然后接着第三题去了。现在也不知道第二题讲的什么，只模模糊糊地记得魔法士，真正的粉丝，看到魔法士就第三题
典型的背包问题。
思路：动态规划。
难点：在于 dp 数组中下标为浮点数时的转化。
考虑到最后求的是 最大取悦值，跟另一个变量，也就是电量关系不太大，猜测测试用例可能都是两位小数，索性直接乘了一百全当成整数算，没想到竟然过了。
有点投机取巧。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int C = input.nextInt() * 100;
float[] c = new float[n];
int[] w = new int[n];
int[] tmp = new int[n];
for (int i = 0; i < n; i++) {
c[i] = input.nextFloat();
w[i] = input.nextInt();
tmp[i] = (int) (c[i] * 100);
}
int[] dp = new int[C + 1];
for (int i = 0; i < n; i++)
for (int j = C; j >= tmp[i]; j--)
dp[j] = Math.max(dp[j - tmp[i]] + w [i], dp[j]);
System.out.println(dp[C]);
}
}
