TZOJ 挑战题库随机训练10（JAVA）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了TZOJ 挑战题库随机训练10（JAVA），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5910字，纯文字阅读大概需要9分钟。
内容图文
点击题号跳转
A.矩形嵌套回到顶部
题意
题解
代码
B.Introspective Caching回到顶部
题意
题解
代码
C.C实验：复读机回到顶部
题意
输入一行文本s，输出s，在输出s wsl，要求用给定函数实现
题解
char* p = (char*)malloc(105*sizeof(char));复杂度O(105)
PS：可能有空格，需要gets读入
代码
1 char *GetText(){
2 char *p=(char*)malloc(105*sizeof(char));
3 gets(p);
4 return p;
5 }
C
D.Robot Navigation回到顶部
题意
题解
代码
E.Rectangles回到顶部
题意
n个矩形嵌套，跟A题类似，求最多嵌套，n<=2000
题解
求最长路，分析一下可以知道是单向边和无环图，那么最长路就是放负权值的最短路，复杂度O(n^2)
代码
1 import java.util.*;
2
3 public class Main {
4
5 public static void main(String[] args) {
6 Solution solver = new Solution();
7 solver.solve();
8 }
9
10 }
11
12 class Solution {
13
14 private final int N = 1005;
15
16 private List<List<Integer>> list = new ArrayList<>();
17 private int[] d = new int[N];
18 private Point[] p1 = new Point[N];
19 private Point[] p2 = new Point[N];
20 private Queue<Integer> q = new LinkedList<>();
21 private int n;
22
23 class Point {
24 int x, y;
25 Point(int x, int y) {
26 this.x = x;
27 this.y = y;
28 }
29 }
30
31 public void solve() {
32 Scanner sc = new Scanner(System.in);
33 while (sc.hasNext()) {
34 n = sc.nextInt();
35 if (n == 0) break;
36 list.clear();
37 list.add(new ArrayList<>());
38 for (int i = 1;i <= n; i++) {
39 p1[i] = new Point(sc.nextInt(), sc.nextInt());
40 p2[i] = new Point(sc.nextInt(), sc.nextInt());
41 list.add(new ArrayList<>());
42 }
43
44 for (int i = 1;i <= n; i++) {
45 for (int j = 1; j <= n; j++) {
46 if (check(i, j))
47 list.get(i).add(j);
48 }
49 }
50 for (int i = 1; i <= n; i++) list.get(0).add(i);
51
52 System.out.println(dij());
53 }
54 }
55
56 private boolean check(int i, int j) {
57 return p2[i].x < p1[j].x && p2[i].y < p1[j].y;
58 }
59
60 private int dij() {
61 d[0] = 0;
62 for (int i = 1; i <= n; i++) d[i] = 1000000000;
63 q.clear(); q.add(0);
64 while (!q.isEmpty()) {
65 int u = q.poll();
66 for (int i = 0; i < list.get(u).size(); i++) {
67 int v = list.get(u).get(i);
68 if (d[v] > d[u] - 1) {
69 q.add(v);
70 d[v] = d[u] - 1;
71 }
72 }
73 }
74 int ans = 0;
75 for (int i = 1; i <= n; i++) ans = Math.max(ans, -d[i]);
76 return ans;
77 }
78 }
E
F.悼念512汶川大地震遇难同胞――选拔志愿者回到顶部
题意
AB轮流捐钱，单次不超过m，总共捐到n结束，A开始
题解
简单博弈，如果n%(m+1)==0，由于A最多拿m，比如A拿了a，那么B只需要拿m+1-a，就可以让B赢，复杂度O(1)
代码
1 import java.util.*;
2
3 public class Main {
4
5 public static void main(String[] args) {
6 Solution solver = new Solution();
7 solver.solve();
8 }
9
10 }
11
12 class Solution {
13
14 public void solve() {
15 Scanner sc = new Scanner(System.in);
16 int c = sc.nextInt();
17 for (int i = 0; i < c; i++) {
18 int n = sc.nextInt();
19 int m = sc.nextInt();
20 if (n % (m + 1) == 0) System.out.println("Rabbit");
21 else System.out.println("Grass");
22 }
23 }
24
25 }
F
G.小强的Linux回到顶部
题意
给一个图，每个点需要时间，有依赖关系，问安装完n个点需要最小时间，n<=1000
题解
拓扑排序，首先取出时间最小的，把度数为0的所有点减掉最小时间，如果安装完就把这个点从图上去掉，并更新度数，复杂度O(n^2)
代码
1 import java.util.*;
2
3 public class Main {
4
5 public static void main(String[] args) {
6 Solution solver = new Solution();
7 solver.solve();
8 }
9
10 }
11
12 class Solution {
13
14 private final int N = 1005;
15
16 private int[] d = new int[N];
17 private int[] t = new int[N];
18 private int[] vec = new int[N];
19 private boolean[][] G = new boolean[N][N];
20 private boolean[] vis = new boolean[N];
21
22 public void solve() {
23 Scanner sc = new Scanner(System.in);
24 int n = sc.nextInt();
25 for (int i = 1; i <= n; i++) t[i] = sc.nextInt();
26 int m = sc.nextInt();
27 for (int i = 1; i <= m; i++) {
28 int u = sc.nextInt();
29 int v = sc.nextInt();
30 if (!G[v][u]) {
31 G[v][u] = true;
32 d[u]++;
33 }
34 }
35
36 int sum = 0;
37 for (int i = 1; i <= n; i++) {
38 int minn = 1000000000;
39 int tot = 0;
40 for (int j = 1; j <= n; j++) {
41 if (!vis[j] && d[j] == 0) {
42 vec[tot++] = j;
43 minn = Math.min(minn, t[j]);
44 }
45 }
46 if (minn == 1000000000) break;
47 for (int j = 0; j < tot; j++) {
48 t[vec[j]] -= minn;
49 if (t[vec[j]] == 0) {
50 vis[vec[j]] = true;
51 for (int k = 1; k <= n; k++) {
52 if (!vis[k] && G[vec[j]][k]) {
53 G[vec[j]][k] = false;
54 d[k]--;
55 }
56 }
57 }
58 }
59 sum += minn;
60 }
61
62 System.out.println(sum);
63 }
64 }
G
H.Unique Snowflakes回到顶部
题意
题解
代码
I.Draw Something Cheat回到顶部
题意
题解
代码
J.教堂回到顶部
题意
题解
代码
内容总结
以上是互联网集市为您收集整理的TZOJ 挑战题库随机训练10（JAVA）全部内容，希望文章能够帮你解决TZOJ 挑战题库随机训练10（JAVA）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。