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 }
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 }
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 }
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 }
E.Distance Statistics回到顶部
题意
给一张图n，m<=10^5，求点对距离<=k的数量
题解
点分治模板题
点分治用在去掉某个点后，这个点不影响对答案的贡献
算法流程大概是，求出树的重心，求出重心到每个点的距离，双指针计算方案，容斥掉两点同向的情况，再移除重心，同理计算剩下的子树
复杂度O(nlog^2n)
PS：JAVA代码在OJ爆栈了，本地的话手动JVM调优，-Xss32m，提交的话目前还不行
代码
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 }
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 }
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 }
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 }
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 }
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 }
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 }
原文：https://www.cnblogs.com/taozi1115402474/p/12679289.html
