踩方格
描述
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
输入
允许在方格上行走的步数n
输出
计算出的方案数量
对于小数据1 <= n <= 20; 对于大数据1 <= n <= 100.
2
7
import java.math.BigInteger;
import java.util.Scanner;
//走方格，利用了动态规划
public class Test3 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
int n=scanner.nextInt();
BigInteger up=new BigInteger("1");
BigInteger left=new BigInteger("1");
BigInteger right=new BigInteger("1");
BigInteger up_pre=new BigInteger("1");
BigInteger left_pre=new BigInteger("1");
BigInteger right_pre=new BigInteger("1");
for(int i=2;i<=n;++i){
up=up_pre.add(left_pre).add(right_pre);
left=up_pre.add(left_pre);
right=up_pre.add(right_pre);
up_pre=up;
left_pre=left;
right_pre=right;
}
System.out.println(up.add(left).add(right));
}
}
}
传话游戏
时间限制: 1000ms 内存限制: 256MB
描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。
由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。
输出
对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。
数据范围
1 ≤ T ≤ 100
小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100
2 4 3 ship sheep sinking thinking thinking sinking the ship is sinking 10 5 tidy tiny tiger liar tired tire tire bear liar bear a tidy tiger is tired
Case #1: the sheep is thinking Case #2: a tiny bear is bear
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Qualification1 {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int t=Integer.parseInt(s.nextLine());
String string="";
Map<String, String> map;
StringBuilder[] sbs=new StringBuilder[t];
for(int i=0;i<t;++i){
string=s.nextLine();
//改进1：要尽量避免字符串匹配
int n=Integer.parseInt(string.split(" ")[0]);
int m=Integer.parseInt(string.split(" ")[1]);
map=new HashMap<String, String>();
for(int j=0;j<m;++j){
string=s.nextLine();
map.put(string.split(" ")[0], string.split(" ")[1]);
}
string=s.nextLine();
String[] sentence=string.split(" ");
for(int j=0;j<n-1;++j){
for(int k=0;k<sentence.length;++k){
if(map.containsKey(sentence[k])){
sentence[k]=map.get(sentence[k]);
}
}
}
sbs[i]=new StringBuilder();
for(int j=0;j<sentence.length;++j){
sbs[i].append(sentence[j]);
if(j!=sentence.length-1)
sbs[i].append(" ");
}
}
for(int i=0;i<t;++i){
System.out.println("Case #"+(i+1)+": "+sbs[i].toString());
}
}
}
长方形
时间限制: 1000ms 内存限制: 256MB
描述
在 N 条水平线与 M 条竖直线构成的网格中，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。
输入
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N，M，K。
输出
对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。
数据范围
1 ≤ T ≤ 100
0 ≤ K ≤ N * M
小数据：0 < N, M ≤ 30
大数据：0 < N, M ≤ 30000
3 3 3 8 4 5 13 7 14 86
Case #1: 5 Case #2: 18 Case #3: 1398
import java.util.Scanner;
public class Qualification2 {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
String string="";
int T=Integer.parseInt(s.nextLine());
int[] max=new int[T];
for(int t=0;t<T;++t){
string=s.nextLine();
int M = Integer.parseInt(string.split(" ")[0]);
int N = Integer.parseInt(string.split(" ")[1]);
int K = Integer.parseInt(string.split(" ")[2]);
int maxProduct=0;
int m=0,n=0;
//M>N
if(M<N){
int temp=M;M=N;N=temp;
}
for(int i=M;i>=1;--i){
if((K%i==0&&K/i<=N)||(K/i+1<=N)){
int rect=K%i==0?K:(K/i+1)*i;
m=i;
n=K%i==0?K/i:K/i+1;
int gap=rect-K;//gap + K % n|m = n|m;
int all=n*(n-1)/2*m*(m-1)/2;
int lack=0;
//保证m<=n
if(m>=n){
int temp=m;m=n;n=temp;
//无论怎样，紧着大边填可以保证只有最后一条大边有gap
//lack = C(1,m-1) * ( C(1,n-gap)*C(1,gap)+C(2,gap) )
lack=(m-1)*((n-gap)*gap+gap*(gap-1)/2);
if(all-lack>maxProduct) maxProduct=all-lack;
if(gap<m){
//只有gap比小边小才能紧着小边填，然后会出现有多条小边出现gap
lack=(n-1)*((m-gap)*gap+gap*(gap-1)/2);
if(all-lack>maxProduct) maxProduct=all-lack;
}
}
}
}
max[t]=maxProduct;
}
for(int t=0;t<T;++t){
System.out.println("Case #"+(t+1)+": "+max[t]);
}
}
}
树上的三角形
时间限制: 2000ms 内存限制: 256MB
描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？
输入
输入数据的第一行包含一个整数 T，表示数据组数。
接下来有 T 组数据，每组数据中：
第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。
接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。
接下来一行包含一个整数 M，表示询问数。
接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。
输出
对于每组数据，先输出一行"Case #X:",其中X为数据组数编号，从 1 开始。
接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
数据范围
1 ≤ T ≤ 5
小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000
大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
2 5 1 2 5 1 3 20 2 4 30 4 5 15 2 3 4 3 5 5 1 4 32 2 3 100 3 5 45 4 5 60 2 1 4 1 3
Case #1: No Yes Case #2: No Yes
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Quanlification3 {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int T=Integer.parseInt(s.nextLine());
String string="";
int[][] W;
boolean[][] hasTriangle=new boolean[T][];
for(int i=0;i<T;++i){
int N=Integer.parseInt(s.nextLine());
W=new int[N][N];
for(int j=0;j<N;++j){
W[j]=new int[N];
for(int k=0;k<N;++k){
W[j][k]=-1;
}
W[j][j]=0;
}
for(int j=0;j<N-1;++j){
string=s.nextLine();
int f=Integer.parseInt(string.split(" ")[0]);
int t=Integer.parseInt(string.split(" ")[1]);
W[f-1][t-1]=Integer.parseInt(string.split(" ")[2]);
W[t-1][f-1]=Integer.parseInt(string.split(" ")[2]);
}
int M=Integer.parseInt(s.nextLine());
hasTriangle[i]=new boolean[M];
for(int j=0;j<M;++j){
string=s.nextLine();
int f=Integer.parseInt(string.split(" ")[0]);
int t=Integer.parseInt(string.split(" ")[1]);
ArrayList<Integer> path=dijkstra(W, f-1, t-1);
int l=path.size();
if(l<3){
hasTriangle[i][j]=false;
}else{
Collections.sort(path);
boolean has=false;
for(int c=2;c<=l-1;++c){
if(path.get(c-2)+path.get(c-1)>path.get(c)){
has=true;
break;
}
}
if(has)
hasTriangle[i][j]=true;
else {
hasTriangle[i][j]=false;
}
}
}
}
for(int i=0;i<T;++i){
System.out.println("Case #"+(i+1)+":");
for(int j=0;j<hasTriangle[i].length;++j){
System.out.println(hasTriangle[i][j]?"Yes":"No");
}
}
}
public static boolean isTriangle(int a, int b, int c) {
if (a + b <= c || a + c <= b || b + c <= a)
return false;
else
return true;
}
@SuppressWarnings("unchecked")
public static ArrayList<Integer> dijkstra(int[][] W1, int start, int end) {
if(start==end) return new ArrayList<Integer>();
boolean[] isLabel = new boolean[W1[0].length];// 是否标号
int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合，以标号的先后顺序进行存储，实际上是一个以数组表示的栈
int i_count = -1;// 栈的顶点
int[] distance = W1[start].clone();// v0到各点的最短距离的初始值
int index = start;// 从初始点开始
int presentShortest = 0;// 当前临时最短距离
ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < W1.length; ++i) {
ArrayList<Integer> ini = new ArrayList<Integer>();
if (W1[start][i] > 0)
ini.add(W1[start][i]);
path.add(ini);
}
ArrayList<Integer> presentPath = new ArrayList<Integer>();
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
isLabel[index] = true;
while (i_count < W1[0].length) {
// 第一步：标号v0,即w[0][0]找到距离v0最近的点
int min = Integer.MAX_VALUE;
for (int i = 0; i < distance.length; i++) {
if (!isLabel[i] && distance[i] != -1 && i != index) {
// 如果到这个点有边,并且没有被标号
if (distance[i] < min) {
min = distance[i];
index = i;// 把下标改为当前下标
}
}
}
if (index == end) {// 已经找到当前点了，就结束程序
break;
}
isLabel[index] = true;// 对点进行标号
indexs[++i_count] = index;// 把已经标号的下标存入下标集中
if (W1[indexs[i_count - 1]][index] == -1
|| presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {
// 如果两个点没有直接相连，或者两个点的路径大于最短路径
presentShortest = distance[index];
presentPath = path.get(index);
} else {
presentShortest += W1[indexs[i_count - 1]][index];
presentPath = path.get(indexs[i_count - 1]);
presentPath.add(W1[indexs[i_count - 1]][index]);
}
// 第二步：将distance中的距离加入vi
for (int i = 0; i < distance.length; i++) {
// 如果vi到那个点有边，则v0到后面点的距离加
if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达，则现在可达了
distance[i] = presentShortest + W1[index][i];
ArrayList<Integer> temp = (ArrayList<Integer>) presentPath
.clone();
temp.add(W1[index][i]);
path.set(i, temp);
} else if (W1[index][i] != -1
&& presentShortest + W1[index][i] < distance[i]) {
// 如果以前可达，但现在的路径比以前更短，则更换成更短的路径
distance[i] = presentShortest + W1[index][i];
ArrayList<Integer> temp = (ArrayList<Integer>) presentPath
.clone();
temp.add(W1[index][i]);
path.set(i, temp);
}
}
}
return path.get(end);//就是路径长度数组
}
}
相似字符串
时间限制: 4000ms 内存限制: 256MB
描述
对于两个长度相等的字符串，我们定义其距离为对应位置不同的字符数量，同时我们认为距离越近的字符串越相似。例如，“0123”和“0000”的距离为 3，“0123”和“0213”的距离则为 2，所以与“0000”相比，“0213”和“0123”最相似。
现在给定两个字符串 S1 和 S2，其中 S2 的长度不大于 S1。请在 S1 中寻找一个与 S2 长度相同的子串，使得距离最小。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组测试数据恰好占两行，第一行为字符串 S1，第二行为 S2。所有字符串都只包括“0”到“9”的字符。
输出
对于每组测试数据，单独输出一行“Case #c: d”。其中，c 表示测试数据的编号（从 1 开始），d 表示找到的子串的最小距离。
数据范围
1 ≤ T ≤ 100
小数据：字符串长度不超过 1000
大数据：字符串长度不超过 50000
3 0123456789 321 010203040506070809 404 20121221 211
Case #1: 2 Case #2: 1 Case #3: 1
package BOP;
import java.util.Scanner;
public class Preliminary1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T=scanner.nextInt();
//改进1：可以用byte[] s1=scanner.next().getBytes() 数字和字母占1byte,汉字占2byte
char[] s1,s2;
int distance=0;
int minDistance=0;
for(int t=1;t<=T;++t){
s1=scanner.next().toCharArray();
s2=scanner.next().toCharArray();
minDistance=s2.length;
//改进2：尽量使用l1=s1.length保存，以免多次求值
for(int i=0;i<=s1.length-s2.length;++i){
distance=s2.length;
for(int j=0;j<s2.length;++j){
if(s1[i+j]==s2[j])
--distance;
}
if(distance<minDistance)
minDistance=distance;
}
System.out.println("Case #"+t+": "+minDistance);
}
}
}
竞价
时间限制: 1000ms 内存限制: 256MB
描述
Alice和Bob都要向同一个商人购买钻石。商人手中有 N 颗钻石，他会将它们一颗颗地卖给他们，Alice和Bob通过竞价的方式来决定钻石的归属。具体的过程如下：商人首先指定其中一个人开始报价，之后两人轮流报价，要求是一定要比对方报的价格更高。任何时候，如果一个人不愿出价或者出不起价钱时，可以宣布弃权，则对手以最后一次报的价格将钻石买下。当然，如果两人都没钱，商人是不会卖钻石的。首次报价至少为 1，并且只能报整数的价钱。
Alice和Bob特别爱攀比，因此他们都希望能比对方买到更多的钻石。Alice和Bob各自带了 CA 和 CB 的钱用于竞拍钻石。此外，Alice和商人有很不错的私人关系，因此商人总是会让Alice先报价。现在请问，在Alice和Bob都用最优策略的情况下，谁能买到更多钻石？假设双方都知道对方手中的现金数量，以及商人将要拍卖的钻石数量 N。
输入
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N，CA，CB，表示钻石的数量，以及双方带的现金数量。
输出
对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y的取值为{-1, 0, 1}，-1表示Alice买到的钻石会比Bob少，0表示两人能买到一样多，1表示Alice能买到更多钻石。所有数据按读入顺序从1开始编号。
数据范围
1 ≤ T ≤ 1000
小数据：0 ≤ N ≤ 10; 0 < CA, CB ≤ 10
大数据：0 ≤ N ≤ 105; 0 < CA, CB ≤ 106
2 4 3 5 7 4 7
Case #1: 0 Case #2: 1
package BOP;
import java.util.Scanner;
public class Preliminary2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T=scanner.nextInt();
int n,ca,cb;
for(int t=1;t<=T;++t){
n=scanner.nextInt();
ca=scanner.nextInt();
cb=scanner.nextInt();
int gap=getResult(n, ca, cb);
System.out.println("Case #"+t+": "+gap);
}
}
//别人用的寻找规律的方法
private static int getResult(int n, int ca, int cb){
int result = 0;
if (n == 0) {
result = 0;
}
if (n >= ca + cb) {
result = ca < cb ? -1 : (ca > cb ? 1 : 0);
} else {
if (n % 2 == 1) {
int x = (n + 1) / 2;
result = ca / x < cb / x ? -1 : 1;
} else {
int x = n / 2;
if (ca / (x + 1) >= cb / x)
result =1;
else if (ca / x < cb / (x + 1))
result =-1;
else
result =0;
}
}
return result;
}
//本来准备用穷举的方式，未果。。。
public static int gap(int N, int Ca, int Cb) {
if (N == 0)
return 0;
if (N == 1 && Ca >= Cb)
return 1;
else if(N == 1 && Ca < Cb){
return -1;
}
int max=Integer.MIN_VALUE;
//int min=0;
for(int i=1;i<=Ca;++i){
int left=gap(N-1, Ca-i, Cb)+1;
int right=gap(N-1, Ca, Cb-i-1)-1;
int m=left>right?left:right;
if(left>0&&right>0){
if(max<m)
max=m;
}
}
return max;
}
}
无尽的编号
时间限制: 1000ms 内存限制: 256MB
描述
在一条公路上，将要依次建造N座建筑。在每个建筑建成之后，都会用一个01串来给它编号。整条公路从起点到终点，所有建筑的编号都严格按照字典序递增的顺序来排列，而每在一个新的地方建起一个建筑时，它的编号会按以下规则确定：
1) 编号要比前一个建筑（起点方向）的字典序大，比后一个建筑（终点方向）的字典序小
3) 编号一定以1结尾
2) 编号要尽可能短，满足该条件时，字典序尽可能小
最开始时，公路的起点和终点上各有一个建筑，编号分别是0和1。接下来依次给出N个坐标 a1, a2, ..., aN，依次表示下一个建筑将要建造的位置，最后要问，当所有建筑建成时，这些建筑的编号总长度是多少，其中又出现了多少个字符1。所有建筑都在公路起点和终点之间，并且没有两个建筑建在同一个位置。
输入
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据中第一行为一个整数 N，表示将要建造的建筑数量，第二行是用单个空格隔开的N个互不相同的整数 a1, a2, ..., aN，表示依次将要建造的建筑所在的坐标。
输出
对于每组测试数据，输出一行"Case #X: Y Z"，其中X表示测试数据编号，Y表示所有建筑编号总长，Z表示所有编号中字符1的数量。所有建筑包括起点和终点的这两个建筑。所有数据按读入顺序从1开始编号。
数据范围
小数据：T ≤ 100, 0 < N ≤ 100, 0 ≤ ai ≤ 1000
大数据：T ≤ 10, 0 < N ≤ 50000, 0 ≤ ai ≤ 500000
1 5 1 2 3 4 5
Case #1: 22 16
package BOP;
import java.util.Scanner;
public class SemiFinal1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Building b;
int oneCount;
int codeLength;
int T=scanner.nextInt();
for(int t=1;t<=T;++t){
oneCount=0;
codeLength=0;
b=new Building(-1);
b.nextBuilding=new Building(600000);
int N=scanner.nextInt();
for(int n=0;n<N;++n){
int a=scanner.nextInt();
addBuilding(b,a);
}
while(b!=null){
oneCount+=b.oneCount;
codeLength+=b.codeLength;
b=b.nextBuilding;
}
System.out.println("Case #"+t+": "+codeLength+" "+oneCount);
}
}
private static void addBuilding(Building b, int a) {
Building cur=b;
while(cur!=null){
if(cur.nextBuilding.value<a){
cur=cur.nextBuilding;
}else{
break;
}
}
Building tmp=new Building(a);
char[] tmpCode;
if(cur.code.length>=cur.nextBuilding.code.length){
tmpCode=new char[cur.code.length+1];
//tmpCode=cur.code.clone();
for(int i=0;i<cur.code.length;++i)
tmpCode[i]=cur.code[i];
tmpCode[cur.code.length]='1';
tmp.oneCount=cur.oneCount+1;
tmp.codeLength=cur.codeLength+1;
}else {
tmpCode=new char[cur.nextBuilding.code.length+1];
for(int i=0;i<cur.nextBuilding.code.length-1;++i)
tmpCode[i]=cur.nextBuilding.code[i];
tmpCode[cur.nextBuilding.code.length-1]='0';
tmpCode[cur.nextBuilding.code.length]='1';
tmp.oneCount=cur.nextBuilding.oneCount;
tmp.codeLength=cur.nextBuilding.codeLength+1;
}
tmp.code=tmpCode;
tmp.nextBuilding=cur.nextBuilding;
cur.nextBuilding=tmp;
}
}
class Building{
public int value;
public char[] code=new char[1];
public Building nextBuilding=null;
public int codeLength;
public int oneCount;
public Building(int value) {
this.value=value;
if(value==-1){
code[0]='0';
oneCount=0;
codeLength=1;
}else if(value==600000){
code[0]='1';
oneCount=1;
codeLength=1;
}
}
}
招聘
时间限制: 3000ms 内存限制: 256MB
描述
Alice新开了一家公司，它的下面有两个项目，分别需要N1和N2个人来完成。现在有N个人前来应聘，于是Alice通过面试来决定他们中的哪些人会被录用。
Alice在面试中，会仔细考察他们能如何为公司的项目带来收益。她给每个人打了两个分值Q1和Q2，表示他加入第一个和第二项目分别能带来的收益值。同时，她也会仔细考察他们每个人的缺点，并且给每人打了另两个分值C1和C2，表示他们进入每个项目可能带来的负面效应。Alice心目中的最优决策是，在决定好录用哪些人以及每个人在哪个项目下工作之后，他们为公司带来的收益总和，除以他们为项目带来的负面效应总和，这个比值要最大。你能帮他计算出在最优决策下，这个比值为多少吗？
前来应聘的人数总是大于等于两个项目需求人数的总和，因此Alice一定会恰好招N1+N2个人，分配给第一个项目N1个人，分配给第二个项目N2个人，没有人会同时属于两个项目。
输入
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据第一行为三个用空格隔开的整数N，N1，N2，表示前来应聘的人数，以及两个项目分别需要的人数。
接下来N行，每行是用空格隔开的四个整数Q1，C1，Q2，C2，依次表示每个人在第一个项目下的价值和负面效应，以及第二个项目下的价值和负面效应。
输出
对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最优决策下招募的人的价值总和与负面效应总和的比值，与正确答案的绝对误差不应超过10-6。所有数据按读入顺序从1开始编号。
数据范围
T ≤ 100
1 ≤ Q1, Q2 ≤ 2000
1 ≤ C1, C2 ≤ 50
小数据：0 < N1 + N2 ≤ N ≤ 50,
大数据：0 < N1 + N2 ≤ N ≤ 500
1 5 2 2 12 5 8 3 9 4 9 4 7 3 16 6 11 5 7 5 18 10 6 3
Case #1: 2.444444
//提交成功者的代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 510
using namespace std;
struct ppp{
double x,y;
} a[N];
double f[N][N],l,r,mid;
int q1[N],q2[N],c1[N],c2[N],i,j,k,n,m,tim,T,n1,n2;
bool cmp(const ppp&a,const ppp&b){
return a.x>b.x||a.x==b.x&&a.y>b.y;
}
bool check(double mid){
for(i=1;i<=n;++i)a[i].x=q1[i]-mid*c1[i],a[i].y=q2[i]-mid*c2[i];
sort(a+1,a+n+1,cmp);
for(i=0;i<=n;++i)
for(j=0;j<=n;++j)f[i][j]=-100000000;
f[0][0]=0;
for(i=0;i<n;++i)
for(j=0;j<=i;++j){
if((i-j)<n1)f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1].x);
else f[i+1][j]=max(f[i+1][j],f[i][j]);
if(j<n2)f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+a[i+1].y);
}
return f[n][n2]>0;
}
int main(){
for(scanf("%d",&T),tim=1;tim<=T;++tim){
scanf("%d%d%d",&n,&n1,&n2);
for(i=1;i<=n;++i)scanf("%d%d%d%d",&q1[i],&c1[i],&q2[i],&c2[i]);
l=0; r=2100;
while(l+1e-8<=r){
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("Case #%d: %.8lf\n",tim,(l+r)/2);
}
}
相关推荐
【编程大赛概述】 编程大赛是IT行业内一种常见的技术竞赛形式，旨在检验参赛者的编程技能、逻辑思维能力以及问题解决能力。此类比赛通常涵盖多种编程语言和技术领域，如算法设计、数据结构、网络编程、数据库管理等...
【标题】"2021年世界编程大赛64K作品.zip" 提供了一个深入了解现代编程技巧和优化技术的机会。这个压缩包包含了2021年4月举行的世界编程大赛中排名前五的作品，特别是第三名，是一个使用WebGL技术创作的项目。这是一...
在编程界，编程大赛是检验开发者技能和创新能力的重要平台，这些比赛经常吸引全球各地的顶尖程序员参与。"编程大赛获奖作品.rar"这个压缩包文件，显然包含了一次名为"64K世界编程大赛"的赛事中，历年获奖的优秀程序...
《2019年世界编程大赛64K作品》是一个极具技术挑战性的竞赛集合，它展示了全球顶尖程序员在有限的存储空间内实现高效代码的精湛技艺。这些作品的大小限制在64KB，这意味着开发者必须在极度紧凑的环境中创造出功能...
64k编程大赛，顾名思义，是一种挑战程序员在仅64KB内存限制下创造出最精彩、最具创新性的程序的竞赛。这个压缩包包含了23个来自不同参赛者的64k编程大赛作品，每一份作品都展示了作者的卓越技艺和编程智慧。在这里，...
【标题】"2018年世界编程大赛一等奖作品-地球巨大灾难之前的宁静"揭示了在编程领域中的一项杰出成就，这个项目很可能是一款基于计算机的模拟或游戏，它以地球面临灾难为背景，通过编程技术呈现出灾变前的宁静场景。...
64K编程大赛，顾名思义，是一种挑战程序员在仅64KB的内存限制下创造出最复杂、最具创新性的程序的比赛。这种大赛通常聚焦于效率、算法优化和内存管理等核心技能，对于参赛者来说，它不仅是技术实力的展现，也是对...
【标题】"2018年世界编程大赛64KB作品"揭示了这是一次全球性的编程竞技活动，其中参赛者需要在极小的代码空间限制下，展示他们的编程技巧和创新思维。64KB的限制是比赛的核心挑战，意味着程序员必须极其精简和高效地...
在华为编程大赛中，参赛者需要遵循一系列严格的规范和标准，以确保代码的质量、可读性和可维护性。这些规范不仅有助于提升团队间的协作效率，还能帮助评委更好地理解和评估参赛作品。以下是一些核心的编程规范和注意...
【标题】"世界编程大赛前三名作品"揭示了全球顶尖程序员的卓越技能和创新思维，这些作品不仅是技术的结晶，更是人类智慧的体现。在这样的比赛中，参赛者们需要展示他们在算法设计、代码优化、软件工程等多个领域的...
在Google编程大赛中，参赛者通常会面临一系列挑战性的题目，旨在测试他们的编程技能、算法理解和问题解决能力。这些题目通常涉及计算机科学的基础知识，包括数据结构、算法、数学、逻辑推理以及特定领域的应用，例如...
【世界编程大赛作品收集】是全球范围内的一项编程竞赛的优秀作品集合，汇聚了来自世界各地的顶尖程序员们的创新思维和技术实力。这些作品不仅展现了参赛者们扎实的编程基础，还体现了他们在算法设计、软件工程、问题...
【标题】"2016全球编程大赛作品 极乐世界.rar" 提供的信息主要是一个在2016年举办的编程大赛中的参赛作品，该作品的名称为“极乐世界”。这个标题暗示了这个项目可能是一个创新的、具有挑战性的编程项目，它可能是...
【世界编程大赛作品下载】 在信息技术领域，编程竞赛已经成为检验开发者技能、创新能力及团队协作能力的重要平台。"世界编程大赛"作为一个全球性的盛事，吸引了众多编程爱好者参与，旨在推动技术的发展，发掘潜力...
标题中的“1997年世界编程大赛冠军作品 (.com格式)”揭示了这是一款在当年获得编程大赛最高荣誉的程序，其特别之处在于它是一个.com文件，这是DOS操作系统下的可执行程序格式。这种格式的程序通常体积小巧，但却能...
标题中的“2016年全球编程大赛作品 高原.rar”揭示了这是一个参与2016年全球编程大赛的作品，主题为“高原”。在编程领域，这样的比赛通常要求参赛者展示他们的创新能力和技术实力，将复杂的算法或视觉效果封装在极...
【编程大赛概述】 编程大赛是检验程序员技能和创新能力的重要平台，尤其像“华为杯”这样的比赛，更是业界具有高度影响力的赛事。2009年的华为杯编程大赛，旨在选拔和培养优秀的软件开发人才，推动信息技术领域的...
【世界编程大赛】是全球范围内的一项重要编程竞赛，旨在挑战程序员在极其有限的资源下创造出功能完备、创新的软件。这里的“64k组”指的是参赛作品必须在内存限制为64KB的情况下进行开发，这是一个极具挑战性的任务...