TZOJ 挑战题库随机训练08（JAVA）

点击题号跳转

A2441 B2293 C1724 D3462 E1608

F5065 G2427 H5466 I5603 J3299

A.Work Reduction回到顶部

题意

n变成m，两种操作，减1花费A，整除2花费B，问最小花费

题解

n变成n/2，操作1需要花费(n-n/2)*A，操作2需要花费B，比大小决定，复杂度O(logn)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         Solution solver = new Solution();
 9         int t = sc.nextInt();
10         for (int ca = 1; ca <= t; ca++) {
11             System.out.println("Case " + ca);
12             solver.solve(sc);
13         }
14     }
15 
16 }
17 
18 class Solution {
19 
20     class Node {
21         String name;
22         int sumCost;
23 
24         Node(String name, int sumCost) {
25             this.name = name;
26             this.sumCost = sumCost;
27         }
28     }
29 
30     public void solve(Scanner sc) {
31         int n = sc.nextInt();
32         int m = sc.nextInt();
33         int agencies = sc.nextInt();
34         sc.nextLine();// 读回车
35         List<Node> list = new ArrayList<Node>();
36         for (int i = 0; i < agencies; i++) {
37             String s = sc.nextLine();
38             String[] str = s.split(":");
39             String[] str1 = str[1].split(",");
40             int aCost = Integer.valueOf(str1[0]);
41             int bCost = Integer.valueOf(str1[1]);
42             int val = n;
43             int sumCost = 0;
44             while (val > m) {
45                 int updateTo = val / 2;
46                 int aSumCost = aCost * (val - updateTo);
47                 if (updateTo >= m && aSumCost > bCost) {
48                     sumCost += bCost;
49                     val = updateTo;
50                 } else {
51                     // 剩下一段全A
52                     sumCost += (val - m) * aCost;
53                     break;
54                 }
55             }
56             list.add(new Node(str[0], sumCost));
57         }
58 
59         Collections.sort(list, new Comparator<Node>() {
60             public int compare(Node o1, Node o2) {
61                 if (o1.sumCost > o2.sumCost)
62                     return 1;
63                 else if (o1.sumCost == o2.sumCost) {
64                     if (o1.name.compareTo(o2.name) > 0)
65                         return 1;
66                     else
67                         return -1;
68                 }
69                 else return -1;
70             }
71         });
72 
73         for (int i = 0; i < list.size(); i++)
74             System.out.println(list.get(i).name + " " + list.get(i).sumCost);
75     }
76 
77 }
A

B.Collecting Beepers回到顶部

题意

10个点，给个起点，问经过每个点再回到起点的最小距离

题解

爆搜，最后加上到起点的距离，复杂度O(2^10)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         Solution solver = new Solution();
 9         int t = sc.nextInt();
10         for (int ca = 1; ca <= t; ca++) {
11             solver.solve(sc);
12         }
13     }
14 
15 }
16 
17 class Solution {
18 
19     private int[] x;
20     private int[] y;
21     private boolean[] vis;
22     private int q;
23     private int sx, sy;
24     private int min;
25 
26     public void solve(Scanner sc) {
27         int n = sc.nextInt();
28         int m = sc.nextInt();
29         sx = sc.nextInt();
30         sy = sc.nextInt();
31         q = sc.nextInt();
32         x = new int[q];
33         y = new int[q];
34         vis = new boolean[q];
35         min = 1000000000;
36         for (int i = 0; i < q; i++) {
37             x[i] = sc.nextInt();
38             y[i] = sc.nextInt();
39         }
40         dfs(0, 0, sx, sy);
41         System.out.println("The shortest path has length " + min);
42     }
43 
44     private void dfs(int step, int cost, int ux, int uy) {
45         if (step == q) {
46             min = Math.min(min, cost + Math.abs(ux - sx) + Math.abs(uy - sy));
47             return;
48         }
49         if (cost <= min) {
50             for (int i = 0; i < q; i++) {
51                 if (!vis[i]) {
52                     vis[i] = true;
53                     dfs(step + 1, cost + Math.abs(x[i] - ux) + Math.abs(y[i] - uy), x[i], y[i]);
54                     vis[i] = false;
55                 }
56             }
57         }
58     }
59 }
B

C.Guess how much I love you?回到顶部

题意

n个串，按TOJ和JOT的个数大到小排序，若个数相同按长度大到小排序，若长度相同按字典序小到大排序，串总长<=10000

题解

处理出每个串的TOJ和JOT的个数，调用Collections.sort方法排序，匿名内部类new Comparator，然后排序需要把@Override去掉，复杂度O(10000)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         Solution solver = new Solution();
 9         int t = sc.nextInt();
10         for (int ca = 1; ca <= t; ca++) {
11             solver.solve(sc);
12         }
13     }
14 
15 }
16 
17 class Solution {
18     class Node {
19         String s;
20         int num;
21         Node() {
22             num = 0;
23         }
24     }
25     public void solve(Scanner sc) {
26         int n = sc.nextInt();
27         sc.nextLine(); // 读回车
28         List<Node> list = new ArrayList<Node>();
29         for (int i = 0; i < n; i++) {
30             Node node = new Node();
31             node.s = sc.nextLine();
32             for (int j = 2; j < node.s.length(); j++) {
33                 if ("TOJ".equals(node.s.substring(j - 2, j + 1)) || "JOT".equals(node.s.substring(j - 2, j + 1))) {
34                     node.num++;
35                 }
36             }
37             list.add(node);
38         }
39         Collections.sort(list, new Comparator<Node>() {
40             public int compare(Node o1, Node o2) {
41                 // 正数交换 其余不换
42                 if (o1.num < o2.num) {
43                     return 1;
44                 } else if (o1.num > o2.num){
45                     return -1;
46                 } else {
47                     if (o1.s.length() < o2.s.length())
48                         return 1;
49                     else if (o1.s.length() == o2.s.length())
50                         if (o1.s.compareTo(o2.s) < 0)
51                             return 1;
52                         else
53                             return -1;
54                     else {
55                         return -1;
56                     }
57                 }
58             }
59         });
60         for (int i = 0; i < list.size(); i++) {
61             System.out.println(list.get(i).s);
62         }
63     }
64 }
C

D.F**king string!回到顶部

题意

n(<=10)个串长度最大100，再给一个错误串，n个串都取前k个字符和错误串的最长公共子串>=d，求最小的k，若不存在-1

题解

易得k的范围[d,n个串+错误串的最小长度]，枚举n个串

对于一个串，存在一个k，使得满足最长公共子串>=d，那么k+1也满足（优化）

可以用dp求出最长公共子串长度即可，复杂度O(100^3)

PS：一开始以为错误串也要去前k个，幸好反应过来了

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     private Scanner sc;
 6     public static void main(String[] args) {
 7 
 8         Scanner sc = new Scanner(System.in);
 9         Solution solver = new Solution();
10         while (solver.solve(sc) != -1) {
11 
12         }
13     }
14 
15 }
16 
17 class Solution {
18 
19     String[] str;
20     public int solve(Scanner sc) {
21         int n = sc.nextInt();
22         int d = sc.nextInt();
23         if (n == 0 && d == 0) return -1;
24         str = new String[n + 5];
25         int upLength = 1000000000;
26         for (int i = 0; i < n; i++) {
27             str[i] = sc.next();
28             upLength = Math.min(upLength, str[i].length());
29         }
30         str[n] = sc.next();
31         upLength = Math.min(upLength, str[n].length());
32         boolean[] vis = new boolean[n];
33         for (int i = 0; i < n; i++) vis[i] = false;
34         int k = -1;
35         for (int len = d; len <= upLength; len++) {
36             boolean ok = true;
37             for (int i = 0; i < n; i++) {
38                 // 如果之前的len就合法，不用判断了
39                 if (vis[i]) continue;
40                 // str[n]和str[i]的[0,len)最长公共子串
41                 int common = LCS(str[n], str[i].substring(0, len));
42                 if (common < d) {
43                     ok = false;
44                     break;
45                 } else {
46                     vis[i] = true;
47                 }
48             }
49             if (ok) {
50                 k = len;
51                 break;
52             }
53         }
54         System.out.println(k);
55         return 1;
56     }
57 
58     private int LCS(String s1, String s2) {
59         int[][] dp = new int[s1.length()][s2.length()];
60         int maxLength = 0;
61         for (int i = 0; i < s1.length(); i++)
62             for (int j = 0; j < s2.length(); j++) {
63                 if (s1.charAt(i) == s2.charAt(j))
64                     if (i > 0 && j > 0) dp[i][j] = dp[i - 1][j - 1] + 1;
65                     else dp[i][j] = 1;
66                 else
67                     dp[i][j] = 0;
68                 maxLength = Math.max(maxLength, dp[i][j]);
69             }
70         return maxLength;
71     }
72 }
D

E.Distance Statistics回到顶部

题意

给一张图n，m<=10^5，求点对距离<=k的数量

题解

点分治模板题

点分治用在去掉某个点后，这个点不影响对答案的贡献

算法流程大概是，求出树的重心，求出重心到每个点的距离，双指针计算方案，容斥掉两点同向的情况，再移除重心，同理计算剩下的子树

复杂度O(nlog^2n)

PS：服务器jdk版本改成1.8，java代码已经可以过了

代码

  1 import java.util.*;
  2 
  3 public class Main {
  4 
  5     private Scanner sc;
  6 
  7     public static void main(String[] args) {
  8 
  9         Scanner sc = new Scanner(System.in);
 10         Solution solver = new Solution();
 11         solver.solve(sc);
 12     }
 13 
 14 }
 15 
 16 class Solution {
 17 
 18     private final int N = 100005;
 19 
 20     private int n, m, k;
 21     private int MIN, ans, root;
 22     private int[] mx = new int[N];
 23     private int[] sz = new int[N];
 24     private boolean[] vis = new boolean[N];
 25     private List<Integer> dis = new ArrayList<Integer>();
 26     private List< ArrayList<Node> > G = new ArrayList< ArrayList<Node> >();
 27 
 28     class Node {
 29         int v, w;
 30 
 31         Node(int v, int w) {
 32             this.v = v;
 33             this.w = w;
 34         }
 35     }
 36 
 37     private void init() {
 38         for (int i = 0; i < N; i++) {
 39             G.add(new ArrayList<Node>());
 40             vis[i] = false;
 41         }
 42     }
 43 
 44     public void solve(Scanner sc) {
 45         n = sc.nextInt();
 46         m = sc.nextInt();
 47         init();
 48         for (int i = 0; i < m; i++) {
 49             int u = sc.nextInt() - 1;
 50             int v = sc.nextInt() - 1;
 51             int w = sc.nextInt();
 52             sc.next();
 53             G.get(u).add(new Node(v, w));
 54             G.get(v).add(new Node(u, w));
 55         }
 56         k = sc.nextInt();
 57         dfs(0);
 58         System.out.println(ans);
 59     }
 60 
 61     private void dfs(int u) {
 62         MIN = n;
 63         dfsSz(u, u);
 64         dfsRoot(u, u, u);
 65         int gri = root;
 66         //System.out.println("grivate:" + gri);
 67         ans += cal(gri, 0);
 68         //System.out.println("u:" + u);
 69         //System.out.println("ans:" + ans);
 70         vis[root] = true;
 71         for (int i = 0; i < G.get(gri).size(); i++) {
 72             int v = G.get(gri).get(i).v;
 73             int w = G.get(gri).get(i).w;
 74             if (!vis[v]) {
 75                 ans -= cal(v, w);
 76                 dfs(v);
 77             }
 78         }
 79     }
 80 
 81     private void dfsSz(int u, int fa) {
 82         sz[u] = 1;
 83         mx[u] = 0;
 84         for (int i = 0; i < G.get(u).size(); i++) {
 85             int v = G.get(u).get(i).v;
 86             if (!vis[v] && v != fa) {
 87                 dfsSz(v, u);
 88                 sz[u] += sz[v];
 89                 mx[u] = Math.max(mx[u], sz[v]);
 90             }
 91         }
 92     }
 93 
 94     private void dfsRoot(int r, int u, int fa)//r为子树的根
 95     {
 96         //子树的其余节点
 97         if (sz[r] - sz[u] > mx[u])
 98             mx[u] = sz[r] - sz[u];
 99         //root为重心
100         if (mx[u] < MIN) {
101             MIN = mx[u];
102             root = u;
103         }
104         for (int i = 0; i < G.get(u).size(); i++) {
105             int v = G.get(u).get(i).v;
106             if (!vis[v] && v != fa)
107                 dfsRoot(r, v, u);
108         }
109     }
110 
111     private void dfsDis(int u, int fa, int d) {
112         //System.out.println("u:" + u +" fa:" + fa + " d:" + d);
113         dis.add(d);
114         for (int i = 0; i < G.get(u).size(); i++) {
115             int v = G.get(u).get(i).v;
116             int w = G.get(u).get(i).w;
117             //System.out.println("i=" + i + " v=" + v);
118             if (!vis[v] && v != fa)
119                 dfsDis(v, u, d + w);
120         }
121     }
122 
123     private int cal(int r, int w) {
124         int ret = 0;
125         dis.clear();
126         dfsDis(r, r, w);
127         Collections.sort(dis);
128         int L = 0, R = dis.size() - 1;
129         while (L < R) {
130             while (dis.get(L) + dis.get(R) > k && L < R) R--;
131             ret += R - L;
132             L++;
133         }
134         return ret;
135     }
136 }
E java
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=1e5+5;
 5 vector< pair<int,int> >G[N];
 6 int mx[N],sz[N],vis[N],dis[N],ans,MIN,n,k,num,root;
 7 void dfssz(int u,int fa)
 8 {
 9     sz[u]=1;
10     mx[u]=0;
11     for(int i=0;i<G[u].size();i++)
12     {
13         int v=G[u][i].first;
14         if(!vis[v]&&v!=fa)
15         {
16             dfssz(v,u);
17             sz[u]+=sz[v];
18             mx[u]=max(mx[u],sz[v]);
19         }
20     }
21 }
22 void dfsroot(int r,int u,int fa)//r为子树的根 
23 {
24     if(sz[r]-sz[u]>mx[u])//子树的其余节点 
25         mx[u]=sz[r]-sz[u];
26     if(mx[u]<MIN)//root为重心
27         MIN=mx[u],root=u;
28     for(int i=0;i<G[u].size();i++)
29     {
30         int v=G[u][i].first;
31         if(!vis[v]&&v!=fa)
32             dfsroot(r,v,u);
33     }
34 }
35 void dfsdis(int u,int fa,int d)
36 {
37     dis[num++]=d;
38     for(int i=0;i<G[u].size();i++)
39     {
40         int v=G[u][i].first;
41         int w=G[u][i].second;
42         if(!vis[v]&&v!=fa)
43             dfsdis(v,u,d+w);
44     }
45 }
46 int cal(int r,int w)
47 {
48     int ret=0;
49     num=0;
50     dfsdis(r,r,w);
51     sort(dis,dis+num);
52     int L=0,R=num-1;
53     while(L<R)
54     {
55         while(dis[L]+dis[R]>k&&L<R)R--;
56         ret+=R-L;    
57         L++;
58     }
59     return ret;
60 }
61 void dfs(int u)
62 {
63     MIN=n;
64     dfssz(u,u);
65     dfsroot(u,u,u);
66     int Grivate=root;
67     ans+=cal(Grivate,0);
68     vis[root]=1;
69     for(int i=0;i<G[Grivate].size();i++)
70     {
71         int v=G[Grivate][i].first;
72         int w=G[Grivate][i].second;
73         if(!vis[v])
74         {
75             ans-=cal(v,w);
76             dfs(v);
77         }
78     }
79 }
80 int main(){
81     int m;
82     scanf("%d%d",&n,&m);
83     for(int i=1;i<=m;i++){
84         int u,v,w;
85         scanf("%d%d%d%*s",&u,&v,&w);
86         G[u-1].push_back({v-1,w});
87         G[v-1].push_back({u-1,w});
88     }
89     scanf("%d",&k);
90     dfs(0);
91     printf("%d",ans);
92     return 0;
93 }
E C++

F.最长连续子序列回到顶部

题意

求最长连续子序列使得和是7的倍数

题解

这样想，如果[1,i-1]模7为3，如果[1,j]模7也为3，那么就说明[i,j]模7为0

dp[i]表示[1,i]的和模7的第一次出现的位置，那么答案就是后面出现的最大距离，复杂度O(n)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         int n = sc.nextInt();
 9         int[] dp = new int[8];
10         int max = 0, sum = 0;
11         for (int i = 1; i <= n; i++) {
12             int x = sc.nextInt();
13             sum = (sum + x) % 7;
14             if (dp[sum] != 0)
15                 max = Math.max(max, i - dp[sum]);
16             if (dp[sum] == 0)
17                 dp[sum] = i;
18         }
19         System.out.println(max);
20     }
21 }
F

G.Guessing Game回到顶部

题意

猜数字1-10，问出题的是否诚实

题解

根据too low和too high确定范围，根据right on判断是否在范围内，复杂度O(1)

PS：java中Scanner的getLine方法会读回车，所以得先把回车读掉

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         while (sc.hasNext()) {
 9             Boolean[] vis = new Boolean[11];
10             for (int i = 1; i <= 10; i++)
11                 vis[i] = false;
12             Boolean dishonest = true;
13             int guass;
14             while (true) {
15                 guass = sc.nextInt();
16                 if (guass == 0) break;
17                 sc.nextLine();// 读回车
18                 String s = sc.nextLine();
19                 if ("too high".equals(s)) {
20                     for (int i = guass; i <= 10; i++)
21                         vis[i] = true;
22                 } else if ("too low".equals(s)) {
23                     for (int i = 1; i <= guass; i++)
24                         vis[i] = true;
25                 } else {
26                     if (vis[guass]) dishonest = false;
27                     break;
28                 }
29             }
30             if (guass == 0) break;
31             if (!dishonest) System.out.println("Stan is dishonest");
32             else System.out.println("Stan may be honest");
33         }
34     }
35 }
G

H.学习之我要直线回到顶部

题意

给你2<=n<=10^5个点，问是否存在两条平行直线穿过所有点

题解

首先当n<=3一定满足

假设存在，那么取出三个点，点1，点2，点3，构造直线12，直线13，直线23，一定能够找到其中一条平行线

为什么？如果1、2不是，那么要么13在平行线上，要么23在平行线上

那么枚举12，13，23把直线上的点都去掉，再看身下的点是否在一条直线上并平行，复杂度O(n)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         Solution solver = new Solution();
 9         while (sc.hasNext()) {
10             solver.solve(sc);
11         }
12     }
13 
14 }
15 
16 class Solution {
17 
18     private int[] x = new int[100005];
19     private int[] y = new int[100005];
20     private boolean[] vis = new boolean[100005];
21     private int n;
22 
23     public void solve(Scanner sc) {
24         n = sc.nextInt();
25         for (int i = 0; i < n; i++) {
26             x[i] = sc.nextInt();
27             y[i] = sc.nextInt();
28         }
29         if ( n <= 3 || pd(0,1) || pd(0,2) || pd(1,2)) System.out.println("YES");
30         else System.out.println("NO");
31     }
32 
33     private boolean pd(int sPoint1, int sPoint2) {
34         for (int i = 0; i < n; i++) vis[i] = false;
35         int cnt = n;
36         // 第一条线
37         for (int i = 0; i < n; i++) if (check(sPoint1, sPoint2, i)) {
38             vis[i] = true;
39             cnt--;
40         }
41         if (cnt == 0) return true;
42         for (int i = 0; i < n; i++) {
43             if (!vis[i]) {
44                 // 第二条线
45                 vis[i] = true;
46                 cnt--;
47                 for (int j = i + 1; j < n; j++) if (!vis[j] && checkParallel(sPoint1, sPoint2, i, j)) {
48                     vis[j] = true;
49                     cnt--;
50                 }
51                 return cnt == 0;
52             }
53         }
54         return false;
55     }
56 
57     // 检查i，j，k是否三点共线
58     private boolean check(int i, int j, int k) {
59         return (long)(x[j] - x[i]) * (y[k] - y[i]) == (long)(x[k] - x[i]) * (y[j] - y[i]);
60     }
61 
62     // 检查i，j和k，l是否平行
63     private boolean checkParallel(int i, int j, int k, int l) {
64         return (long)(x[j] - x[i]) * (y[l] - y[k]) == (long)(x[l] - x[k]) * (y[j] - y[i]);
65     }
66 
67 }
H

I.查询数据回到顶部

题意

n个数，m次查询，每次查询一个数是否存在

题解

hashset，复杂度O(Σm)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         int n = sc.nextInt();
 9         int m = sc.nextInt();
10         HashSet<Integer> hashSet = new HashSet<Integer>();
11         for (int i = 0; i < n; i++) {
12             hashSet.add(sc.nextInt());
13         }
14         for (int i = 0; i < m; i++) {
15             if (hashSet.contains(sc.nextInt())) {
16                 System.out.println("Yes");
17             } else {
18                 System.out.println("No");
19             }
20         }
21     }
22 }
I

J.切蛋糕回到顶部

题意

每次竖直切一刀，求切n刀后可以把蛋糕分成几块

题解

由于大小不需要一样，那么第i+1刀肯定与前i刀都有交点，即多出i+1块，那么就变成等差数列求和，复杂度O(1)

代码

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6 
 7         Scanner sc = new Scanner(System.in);
 8         while(sc.hasNext()) {
 9             int n = sc.nextInt();
10             System.out.println(1 + (1 + n) * n / 2);
11         }
12     }
13 }
J
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/taozi1115402474/p/12679289.html