Q: 把字符串s統一成小寫字母形態

題型：簽到

知識點: 考察字符串的API題

c++可以借助transform函數，進行轉化

#include <bits/stdc++.h>using namespace std;int main() {string s;cin >> s;// 把自己轉化為小寫/大寫態// tolower/touppertransform(s.begin(), s.end(), s.begin(), ::tolower);cout << s << endl;return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {AReader sc = new AReader();String s = sc.next();System.out.println(s.toLowerCase());}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }// 若需要nextDouble等方法，請自行調用Double.parseDouble包裝}}

Q: 不能被 [2, a]范圍內的數整除的數，被稱為不合群數， 求[2, b]內最大的不合群數

思路: 枚舉

核心就是，一個前置的知識點:

$$10億內的最大質數是999999937，且相鄰質數之間的差值均不超過300$$

因為大于a的質數，一定是不合群數，而每300數，必然有一個質數存在。因此找到這個質數即可。

從b開始，從大到小進行枚舉，判定即可。

當然不見得質數才滿足需求

比如

input
5 50output
49
# 因為49=7*7， 其不被[2, 5]區間的數整除

但是質數，給了枚舉范圍的上限值，所以這是一道很有趣的題。

#include <bits/stdc++.h>using namespace std;using int64 = int64_t;// 判定質數, O(sqrt(n))
bool judge(int64 v, int64 a) {if (v <= a) return false;for (int64 i = 2; i <= v / i && i <= a; i++) {if (v % i == 0) {return false;}}return true;
}int main() {int64 a, b;cin >> a >> b;int64 res = -1;for (int64 i = b; i >= max(b - 300, a + 1); i--) {if (judge(i, a)) {res = i;break;}}cout << res << endl;return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {static boolean isPrime(long v) {if (v <= 1) return false;for (int i = 2; i <= v / i; i++) {if (v % i == 0) return false;}return true;}public static void main(String[] args) {AReader sc = new AReader();long a = sc.nextLong(), b = sc.nextLong();long res = -1;for (long i = b; i > a && i >= b - 300; i--) {// a^2if (isPrime(i)) {res = i;break;}if (i >= a * a) {boolean ok = true;for (int j = 2; j <= a; j++) {if (i % j == 0) {ok = false;}}if (ok) {res = i;break;}}}System.out.println(res);}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }// 若需要nextDouble等方法，請自行調用Double.parseDouble包裝}}

Q: 在一個無向圖中，同類點需保證任意兩點間最短距離為0，然后求非同類點的距離矩陣

思路: 圖論+縮點思路

這邊不是tanjar求縮點，

$$借助并查集來合并$$

把邊長為0的兩點進行合并，這樣就能快速判定是否滿足第一個條件(注意借橋搭路)

然后根據縮點后，進行路徑的壓縮k*k

跑一遍floyd就可以出來了

#include <bits/stdc++.h>using namespace std;class Dsu {
public:Dsu(int n) : n(n), arr(n + 1) {}int find(int u) {if (arr[u] == 0) return u;return arr[u] = find(arr[u]);}void merge(int u, int v) {int ai = find(u), bi = find(v);if (ai != bi) {arr[ai] = bi;}}bool isSame(int u, int v) {return find(u) == find(v);}private:int n;vector<int> arr;
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, k;cin >> n >> m >> k;vector<int> cats(k);for (int i = 0; i < k; i++) {cin >> cats[i];}Dsu dsu(n);vector<array<int, 3>> edges;for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;edges.push_back({u, v, w});if (w == 0) {dsu.merge(u, v);}}bool ok = true;int start = 1;vector<int> mp(n + 1);for (int i = 0; i < cats.size(); i++) {for (int j = start + 1; j < start + cats[i]; j++) {if (!dsu.isSame(start, j)) {ok = false;break;}}for (int j = start; j < start + cats[i]; j++) mp[j] = i;start = start + cats[i];}if (!ok) {cout << "No" << endl;} else {cout << "Yes" << endl;int inf = -1;vector<vector<int>> path(k, vector<int>(k, -1));for (int i = 0; i < k; i++) path[i][i] = 0;for (auto e: edges) {int u = mp[e[0]],  v = mp[e[1]];if (path[u][v] == -1 || path[u][v] > e[2]) {path[u][v] = path[v][u] = e[2];}}for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++) {if (path[j][i] == -1) continue;for (int t = 0; t < k; t++) {if (path[i][t] == -1) continue;if (path[j][t] == -1 || path[j][t] > path[j][i] + path[i][t]) {path[j][t] = path[j][i] + path[i][t];}}}}for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++) {cout << path[i][j] << " \n"[j == k - 1];}}}return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;public class Main {static class Dsu {int n;int[] arr;int[] gz;public Dsu(int n) {this.n = n;this.arr = new int[n + 1];this.gz = new int[n + 1];Arrays.fill(gz, 1);}int find(int u) {if (arr[u] == 0) return u;return arr[u] = find(arr[u]);}void union(int u,int v) {int ai = find(u), bi = find(v);if (ai != bi) {arr[ai] = bi;gz[bi] += gz[ai];}}int gSize(int u) {return gz[find(u)];}}public static void main(String[] args) {AReader sc = new AReader();int n = sc.nextInt(), m = sc.nextInt();int k = sc.nextInt();int[] arr = new int[k];int acc = 1;TreeMap<Integer, Integer> hash = new TreeMap<>();for (int i = 0; i < k; i++) {arr[i] = sc.nextInt();hash.put(acc, i);acc += arr[i];}long inf = Long.MAX_VALUE / 10;long[][] dp = new long[k][k];for (int i = 0; i < k; i++) {Arrays.fill(dp[i], inf);dp[i][i] = 0;}Dsu dsu = new Dsu(n);for (int i = 0; i < m; i++) {int u = sc.nextInt(), v = sc.nextInt();int x = sc.nextInt();Map.Entry<Integer, Integer> e1 = hash.floorEntry(u);Map.Entry<Integer, Integer> e2 = hash.floorEntry(v);int p1 = e1.getValue(), p2 = e2.getValue();if (p1 == p2) {} else {dp[p1][p2] = Math.min(dp[p1][p2], x);dp[p2][p1] = Math.min(dp[p2][p1], x);}if (x == 0) {dsu.union(u, v);}}boolean check = true;acc = 1;for (int i = 0; i < k; i++) {for (int j = acc; j < acc + arr[i]; j++) {if (dsu.find(acc) != dsu.find(j)) check = false;}acc += arr[i];}if (!check) {System.out.println("No");} else {System.out.println("Yes");for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++) {for (int t = 0; t < k; t++) {if (dp[j][t] > dp[j][i] + dp[i][t]) {dp[j][t] = dp[j][i] + dp[i][t];}}}}for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++) {if (dp[i][j] == inf) dp[i][j] = -1;}System.out.println(Arrays.stream(dp[i]).mapToObj(String::valueOf).collect(Collectors.joining(" ")));}}}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }// 若需要nextDouble等方法，請自行調用Double.parseDouble包裝}}