本文共 11437 字,大约阅读时间需要 38 分钟。
题目描述
输入
输出
样例输入 Copy
231 34 56 721 33 4
样例输出 Copy
YESNO
代码:
import java.util.Scanner;public class Main { static int n; static void swap(int i,int k,int []start,int []end) { int t1 = start[i]; start[i] = start[k]; start[k] = t1; int t2 = end[i]; end[i] = end[k]; end[k] = t2; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int T = sc.nextInt();//两组案例 for(int i=1;i<=T;i++) { n = sc.nextInt();//n组数据 int start[] = new int[n];//活动开始时间 int end[] = new int[n];//活动结束时间 for(int j=0;jend[k]) swap(j,k,start,end); boolean flag = true; for(int j=1;j
题目描述
输入
输出
样例输入 Copy
2000
样例输出 Copy
8
代码:
【第一种方法容易溢出,我班大佬建议打表】
import java.util.Comparator;import java.util.Map;import java.util.Scanner;import java.util.TreeMap;public class Main { // static boolean judge(int n ) { // int m = n;//输入的数// int ping = n * n;//平方// while(n != 0) {//循环判断// if(n % 10 != ping % 10) {//两个数的尾数不相等// return false;// }// n = n / 10;//除去尾数剩余的数// ping = ping / 10;// }// return true;// }// // static int solve(int n) { // int count = 0;//用来统计有多少个自守数// while(n >= 0) { // if(judge(n)) { // count++;// }// n--;// }// return count;// } static void solve(long T) { Mapmap = new TreeMap<>(new Comparator () { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); map.put(0, 1); map.put(1, 2); map.put(5, 3); map.put(6, 4); map.put(25, 5); map.put(76, 6); map.put(376, 7); map.put(625, 8); map.put(9376, 9); map.put(90625, 10); map.put(109376, 11); map.put(890625, 12); map.put(2890625, 13); map.put(7109376, 14); map.put(12890625, 15); map.put(87109376, 16); map.put(212890625, 17); map.put(787109376, 18); map.put(1787109376, 19); for (Map.Entry m : map.entrySet()) { if (T >= m.getKey()) { System.out.println(m.getValue()); break; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { long T = sc.nextInt(); solve(T); } }}
题目描述
输入
输出
样例输入 Copy
5 410 65 23 67 805 15 60 90
样例输出 Copy
4
代码:
【这个代码是我自己写的嗷!但是也是提交了两遍,第一遍是因为没有做好判断的内容,第二遍是没有排序】
import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int m = sc.nextInt();//男同学的数量 int n = sc.nextInt();//女同学的数量 int man[] = new int[m];//男同学的颜值 for(int i=0;i
题目描述
输入
输出
样例输入 Copy
56 3 6 5 42 2 4 6 58
样例输出 Copy
15 1 2 3
代码:
import java.util.Scanner;public class Main{ static int n, C,cw,cv,bestv; static int v[],w[],way[],bestway[]; static void backtrack(int i) { if(i>n){ //如果放到最后一个物品,那一定是最佳方案 if(cv>bestv){ //判断当前的最佳和之前的最佳方案 bestv=cv;//交換 for (int j = 1; j <=n; j++) bestway[j] = way[j];//交換 } } else { //第一种选 if(cw>=w[i]){ //当前剩余容量 cw-=w[i];//更新剩余容量 cv+=v[i];//更新当前最佳容量 way[i]=1;//将选中的物品标志更改为 backtrack(i+1);//继续回溯 cw+=w[i]; cv-=v[i]; way[i]=0; }//第二种不选 if(bound(i+1)+cv>bestv) backtrack(i+1);//当前物品大于剩余容量,但是除了他不放,把之后的物品都放入还可以得到一个优于现有解 //当前物品不选继续递归下一个 } } static int bound(int k) { int bound=0; for(int j=k;j<=n;j++) bound+=v[j]; return bound; } static void print() { System.out.print(bestv+" "); for (int i=1;i<=n;i++) if(bestway[i]==1) System.out.print(i+" "); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ n = sc.nextInt();//物品数量 v = new int[n+1];//价值背包 w = new int[n+1];//重量背包 way = new int[n+1];//当前背包 bestway = new int[n+1];//最好背包 for(int i=1;i<=n;i++) v[i] = sc.nextInt();//依次放价值 for(int i=1;i<=n;i++) w[i] = sc.nextInt();//依次放价值 C = sc.nextInt();//最大背包容量 cw = C;//背包容量赋值 cv = 0;//当前最佳 bestv = 0;//最终最佳 backtrack(1); print(); } } }
题目描述
输入
输出
样例输入 Copy
4 61 2 301 3 61 4 42 3 52 4 103 4 20
样例输出 Copy
1 3 2 4 125
代码:
【大佬地文章,】
import java.util.Scanner;public class Main { static int n,m;//n城市数量,m边数量 static int graph[][]; static int cd,bd;//当前距离,最短距离 static int x[],bestx[];//当前路线,最好的路线 static int MAX = Integer.MAX_VALUE; static void swap(int t, int i) { int temp=x[t]; x[t]=x[i]; x[i]=temp; } static void backtrace(int t) { if(t==n) { if(graph[x[n-1]][x[n]]!=MAX && //准备去第n个城市 判断当前售货员与第n个点有没有路线,没路线剪掉 graph[x[n]][1]!=MAX && //判断第n个点与起点1有没有路线,没有剪掉 (cd+graph[x[n-1]][x[n]]+graph[x[n]][1]
题目描述
输入
输出
样例输入 Copy
12
样例输出 Copy
1-2
代码:
【第一个没用到递归~,第二个用到了递归】
import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); int sum = 0; for(int i=1,count=1;count<=n;i+=2,count++) { //1 3 5 7... if(count%2==1) sum+=i; else sum-=i; } System.out.println(sum); } }}//递归求和import java.util.Scanner;public class Main { static int solve(int n) { if(n==0) return 0; if(n==1) return 1; return (int) (Math.pow(-1,n-1)*(2*n-1)+solve(n-1)); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); System.out.println(solve(n)); } }}
题目描述
输入
输出
样例输入 Copy
10000 52000 1000 5000 3000 4000
样例输出 Copy
4
代码:
【仔细看,这其实是一个最优装载的问题】
import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int M = sc.nextInt(); int n = sc.nextInt(); int a[] = new int[n]; for(int i=0;i=0;i++) if(a[i]<=M) { count++; M-=a[i]; } System.out.println(count); } }}
题目描述
输入
输出
样例输入 Copy
3
样例输出 Copy
40
代码:
import java.util.Scanner;public class Main { //S(n) = 1*4 + 4*9 + 9*16 + 16*25 + ... + ((n-1)^2)*n^2 static int solve(int n) { if(n==0) return 0; if(n==1) return 0; return (int) (((Math.pow(n-1,2))*Math.pow(n,2))+solve(n-1)); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); System.out.println(solve(n)); } }}
题目描述
输入
输出
样例输入 Copy
100 450 10 20 10 40 10 50 20
样例输出 Copy
37.50
代码:
import java.util.Arrays;import java.util.Comparator;import java.util.Scanner; //结构体class Element{ double w; double v; double p;//单位重量价值};//自定义以单位重量价值排序排序class cmp implements Comparator{ public int compare(Element a, Element b) { if(a.p 0){ //余下重量大于0 x[i]=(1.0)*weight/bag[i].w; //将物品i的一部分装入 bestv+=x[i]*bag[i].v; //累计总价值 } System.out.println(String.format("%.2f", bestv)); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ c = sc.nextInt(); n = sc.nextInt(); bag = new Element[n+1]; for(int i=1; i<=n; i++){ bag[i] = new Element(); bag[i].w = sc.nextDouble();//第N个项目的总投资额 bag[i].v = sc.nextDouble();//第N个项目的总收益 } for(int i=1; i<=n; i++) bag[i].p = bag[i].v/bag[i].w;//单位重量价值 Arrays.sort(bag,1,n+1,new cmp());//排序// // for(int i=1;i<=n;i++) { // System.out.println(bag[i].w+" "+bag[i].v);// } knapsack(); } }}
题目描述
输入
输出
样例输入 Copy
515 18 17 11 12
样例输出 Copy
2
代码:
【这是一个最长递减子序列的变形】
import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); int a[] = new int[n+1]; int b[] = new int[n+1];//存储对应的上升子序列 for(int i=0;ia[i] && k maxlen) maxlen = b[i]; System.out.println(n-maxlen); } }}
【在大佬的帮助下,万幸做完了,周末还要期末考试,我还没复习,难受,哭唧唧~,还是先做课设吧】
“当你烦恼的时候,想想人生就是减法,见一面少一面,活一天就少一天,还有什么好烦恼的呢,不忘人恩,不念人过,不思人非,不计人怨。不缺谁,不少谁,对得起良心就好。”
转载地址:http://yfcki.baihongyu.com/