第六届 传智杯初赛B组

---

🥰 Tips：AI可以把代码从 java 转成其他语言的版本，思路比语言更重要。

A. 字符串拼接

👨‍🏫 题目地址

🍻 AC code

#include <iostream>
using namespace std;int main() {string a, b;getline(cin,a);getline(cin,b);cout << a + b << endl;return 0;
}

B. 最小差值

👨‍🏫 参考地址

🍻 AC code

import java.util.*;
import java.io.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws NumberFormatException, IOException {int n = Integer.parseInt(in.readLine());int[] a = new int[n];String[] ss = in.readLine().split(" ");for(int i =0; i < n; i++)a[i] = Integer.parseInt(ss[i]);Arrays.sort(a);//排序int min = Integer.MAX_VALUE;for(int i =1; i < n; i++)min = Math.min(min, a[i]-a[i-1]);//算差值out.write(min + "");out.flush();}
}

C. 红色和紫色

👨‍🏫 题目地址

🍻 AC code

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();long ans = (long)n*m;if(ans % 2 == 0)System.out.println("yukari");else {System.out.println("akai");}}
}

D. abb

👨‍🏫 题目地址

🐷 思路：统计字符串中 a~z 每个字符出现的次数存在 cnt 数组中，根据题意，从前往后枚举 abb中的 a,没枚举一位就减去当前位上的字符数量，这样 cnt[ ] 的字符数量就是当前位往后的字符出现次数了，根据 cnt[ ] 来计算 abb中的bb的情况，使用组合数公式即可
$$C_n^m=\frac{n!}{(n-m)!\times m!}$$

🍻 AC code

import java.util.*;
import java.io.*;public class Main {static long mod = (int)1e9+7;static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));static int N = (int)1e5+10;static int[] cnt = new int[256];//统计字母出现次数//	C(x,2) = x! / 2! (引以为戒)
//	C(x,2) = x! / (2! * (x-2)!) = x * x -1 / 2private static long cal(int x) {long ans = x*(x-1)/2;return ans;}public static void main(String[] args) throws IOException {int n = Integer.parseInt(in.readLine());String s = in.readLine();char[] a = s.toCharArray();n = a.length;long ans = 0;for(int i = 0; i < n; i++)cnt[a[i]]++;for(int i = 0; i < n-1; i++){char c = a[i];cnt[c]--;for(int j = 'a'; j <= 'z'; j++){if(j == c)continue;if(cnt[j] >= 2) {{long t = cal(cnt[j]) % mod;ans += t;}}}}out.write(ans+"\n");out.flush();}
}

E. kotori和素因子

👨‍🏫 题目地址

🐷 思路：先预处理出 0 到 1000 的所有质数，接着找到每个整数的所有质数因子存在因子数组中。根据题意，每个整数需要选出独一无二质因子，由于数据范围比较小 $1\le n\le 10$,所以可以直接 dfs 枚举每个整数选取哪个质因子。

🍻 AC code

import java.util.*;public class Main {static int N = 15,n,INF = 0x3f3f3f3f;static int[] a = new int[N];//整数数组static int[] p = new int[300];//存2~1000的质数static int cnt = 0;//2~1000的质数个数static ArrayList[] factors = new ArrayList[N];//存每个整数的质因数
//	static boolean[] st = new boolean[N];static HashSet<Integer> st = new HashSet<>();//记录已经使用过的质数（st：state 状态）static int ans = INF;//答案public static void main(String[] args) {getPrimes();Scanner sc = new Scanner(System.in);n = sc.nextInt();for(int i =0; i < n; i++){factors[i] = new ArrayList<Integer>();a[i] = sc.nextInt();ArrayList<Integer> t = cal(a[i]);factors[i] = t;}dfs(0,0);if(ans != INF)System.out.println(ans);else {System.out.println(-1);}}//	x 表示当前搜索到的第几个整数private static void dfs(int x,int sum) {if(x == n){ans = Math.min(sum, ans);return;}ArrayList<Integer> ls = factors[x];boolean flag = false;for(Integer xx : ls){if(st.contains(xx))continue;flag = true;st.add(xx);dfs(x+1, sum + xx);st.remove(xx);}if(!flag)return;}//	返回 x 的所有质因数private static ArrayList<Integer> cal(int x) {ArrayList<Integer> ans = new ArrayList<Integer>();for(int i = 0; i < cnt; i++)if(x % p[i] == 0)ans.add(p[i]);return ans;	}//	预处理质数数组private static void getPrimes() {p[cnt++] = 2;for (int i = 3; i <= 1000; i++)if (isP(i))p[cnt++] = i;}//	判断x是否为质数private static boolean isP(int x) {for(int i = 2; i*i <= x; i++)if(x % i == 0)return false;return true;}
}

F. 红和蓝

👨‍🏫 题目地址
🐷 思路：如果叶子结点为一种颜色时，它的周围只有其父亲结点，所以父亲结点必须和它同色

🍻 AC code

import java.util.*;
import java.io.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));static int N = 200010,n,idx;
//	以无向图的邻接表形式存树static int[] h = new int[N];static int[] e = new int[N];static int[] ne = new int[N];static int[] cnt = new int[N];//存储每个节点包含多少个叶子节点(要求当前节点同色的节点)static int[] sz = new int[N];//存储每个节点所包含的子树的节点数量//	加边函数static void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;}//	u表示当前节点，p表示父结点static boolean dfs(int u,int p){sz[u] = 1;//初始化为1，表示当前节点自身for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == p)continue;//存的是无向边,特判 父 --> 子 --> 父 的情况if(!dfs(j, u))return false;sz[u] += sz[j];//子树节点数量累加到当前节点的sz值上if((sz[j] & 1 )== 1)//当子树j的结点数为奇数时,当前节点u必须与节点j同色cnt[u]++;}if(cnt[u] > 1 )//两个叶子节点要求同色,无解return false;return true;}static int[] ans = new int[N];//答案数组
//	再跑一次搜索染色,0表示红色R,1表示蓝色B
//	u表示当前节点，p表示父结点, c表示颜色static void dfs2(int u,int p,int c){ans[u] = c;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == p)continue;if((sz[j] & 1) == 1)dfs2(j, u, c);else {dfs2(j, u, 1-c);}}}public static void main(String[] args) throws Exception {Arrays.fill(h, -1);n = Integer.parseInt(in.readLine());for(int i = 1; i < n; i++){String[] ss = in.readLine().split(" ");int a = Integer.parseInt(ss[0]);int b = Integer.parseInt(ss[1]);add(a, b);add(b, a);}if(n % 2 == 1){System.out.println(-1);System.exit(0);}if(!dfs(1, -1)){System.out.println(-1);return;}dfs2(1, -1, 0);for(int i = 1; i <= n; i++)System.out.print(ans[i] == 0 ? "R" : "B");
//			if(ans[i] != 0)
//				System.out.print("B");
//			else {
//				System.out.print("R");
//			}}
}