一、BD1 罪犯转移
描述：
C市现在要转移一批罪犯到D市，C市有n名罪犯，按照入狱时间有顺序，另外每个罪犯有一个罪行值，值越大罪越重。现在为了方便管理，市长决定转移入狱时间连续的c名犯人，同时要求转移犯人的罪行值之和不超过t，问有多少种选择的方式（一组测试用例可能包含多组数据，请注意处理）？
输入描述：
第一行数据三个整数:n，t，c(1≤n≤2e5,0≤t≤1e9,1≤c≤n)，第二行按入狱时间给出每个犯人的罪行值ai(0≤ai≤1e9)
输出描述：
一行输出答案。
示例1
输入：3 100 2
1 2 3
输出：2
题解示例：
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int t = in.nextInt(); int c = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int left = 0, right = left + c - 1; long res = 0; long temp = 0; while (right < n) { //虽然是滑动窗口，但是每次滑动都是重新计算窗口内的犯罪值 for (int i = left; i <= right; i++) { temp += arr[i]; } if (temp <= t) res++; right++; left++; temp = 0; } System.out.println(res); } } }
二、BD2 裁减网格纸
描述
度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
输入描述：
第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点
输出描述：
一行输出最小面积
示例1
输入：2
0 0
0 3
输出：9
题解示例：
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while(in.hasNext()){ int n = in.nextInt(); int maxX = Integer.MIN_VALUE; int maxY = Integer.MIN_VALUE; int minX = Integer.MAX_VALUE; int minY = Integer.MAX_VALUE; for(int i = 0;i<n;i++){ int x = in.nextInt(); int y = in.nextInt(); maxX = (int) Math.max(maxX,x); maxY = (int) Math.max(maxY,y); minX = (int) Math.min(minX,x); minY = (int) Math.min(minY,y); } int side = Math.max((maxX-minX),(maxY-minY)); System.out.println(side*side); } } }
三、BD3 钓鱼比赛
描述
ss请cc来家里钓鱼，鱼塘可划分为n＊m的格子，每个格子有不同的概率钓上鱼，cc一直在坐标(x,y)的格子钓鱼，而ss每分钟随机钓一个格子。问t分钟后他们谁至少钓到一条鱼的概率大？为多少？
输入描述：
对于每组数据，第一行五个整数n,m,x,y,t(1≤n,m,t≤1000,1≤x≤n,1≤y≤m);
接下来为一个n＊m的矩阵，每行m个一位小数，共n行，第i行第j个数代表坐标为(i,j)的格子钓到鱼的概率为p(0≤p≤1)
输出描述：
输出两行。第一行为概率大的人的名字(cc/ss/equal),第二行为这个概率(保留2位小数)
示例1
输入：2 2 1 1 1
0.2 0.1
0.1 0.4
输出：equal
0.20
题解示例：
import java.util.Scanner; public class Main { /** * 非要逐行读取才不超时! */ //思路:cc:固定某点概率;ss:所有点求平均概率,再由独立事件公式求t分钟后 public static void main(String[] args) { Scanner reader = new Scanner(System.in); while(reader.hasNext()){ String[] s1 = reader.nextLine().split(" "); int n = Integer.parseInt(s1[0]); int m = Integer.parseInt(s1[1]); int x = Integer.parseInt(s1[2]); int y = Integer.parseInt(s1[3]); int t = Integer.parseInt(s1[4]); double proCC = 0; double sumPro = 0; for(int i=1; i<=n; i++){ String[] s = reader.nextLine().split(" "); for(int j=1; j<=m; j++){ double p = Double.parseDouble(s[j-1]); sumPro += p; if((i == x) && (j == y)){ proCC = p; } } } sumPro /= (n*m); //!注意这里:t个独立事件:P(t1Ut2Ut3..Utn) = 1-P(非t1)P(非t2)...P(非t3) if(proCC == sumPro){ System.out.println("equal"); System.out.println(String.format("%.2f", 1 - Math.pow(1-proCC, t))); //保留小数点后两位 }else if(proCC > sumPro){ System.out.println("cc"); System.out.println(String.format("%.2f", 1 - Math.pow(1-proCC, t))); }else if(proCC < sumPro){ System.out.println("ss"); System.out.println(String.format("%.2f", 1 - Math.pow(1-sumPro, t))); } } } }
