1.
题目内容
小红拿到了一个字符串，她想知道这个字符串能否通过重新排列组成 Baidu 字符串？注：必须大小写完全相同。 共有 t 组询问。
输入描述
第一行输入一个正整数 t ，代表询问次数。
接下来的 t 行，每行输入一个仅包含英文字母的字符串。
所有字符串的长度之和保证不超过 200000
输出描述
对于每次询问，输出一行答案。如果可以通过重新排列组成 Baidu，则输出 Yes ，否则输出 No 。
思路
字符串长度必须为5，且必须包含Baidu5个char。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); char[] chars = "Baidu".toCharArray(); for (int i = 0; i < n; i++) { String s = in.next(); if(s.length()!=5||!s.contains("B")||!s.contains("a")||!s.contains("i")||!s.contains("d")||!s.contains("u")) System.out.println("No"); else System.out.println("Yes"); } }}2.
题目内容：
给定一个整数x，请你构造一个仅由’r’,‘e’,'d’三种字符组成的字符串，其中回文子串的数量恰好为x
输入描述
一个正整数x. 1≤x≤10^9
输出描述
回文子串的数量恰好为x的字符串
思路
d包含1个回文子串，dd包含3个回文子串，ddd包含6个，dddd包含10个，依次累加求。
比如x=14，那么14-10-3-1=0；依次构建10个r，3个e，1个d。
因为10>3>1，所以不会有其他多余的回文子串。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x = in.nextInt(); int temp=0,index=0,c=1; StringBuilder builder = new StringBuilder(""); while(x>0){ temp=0; for (int i = 1; i < 1000000; i++) { temp+=i; if(temp>x){ temp-=i; index=i-1; break; } }// 这段可以用（n+1）*n/2替换 if(c==1){ for (int i = 0; i < index; i++) { builder.append("r"); } c++; }else if(c==2){ for (int i = 0; i < index; i++) { builder.append("e"); } c++; }else { for (int i = 0; i < index; i++) { builder.append("d"); } c=1; } x=x-temp; } System.out.println(builder.toString()); }}3.
题目内容
小红拿到了一棵树，每个节点被染成了红色或者蓝色。
小红定义每条边的权值为：删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。
小红想知道，所有边的权值之和是多少？
输入描述
第一行输入一个正整数 n ,代表节点的数量。
第二行输入一个长度为 n 且仅由 R 和 B 两种字符组成的字符串。
第 i 个字符为 R 代表 i 号节点被染成红色，为 B 则被染成蓝色。
接下来的 n−1 行，每行输入两个正整数 u 和 v ，代表节点 u 和节点 v 有一条边相连。
输出描述
一个正整数，代表所有节点的权值之和。
思路
关键在于构建无向图，取每个节点，记录其父节点的位置，之后从当前节点往下dfs，
sum=1+Σ儿子节点的同色联通块数量
同时需要考虑父子之间的数量
如果子节点的颜色和当前节点的颜色是否相同，子节点所在子树的数量需要-1，
比如R-R，右边R的同色连通块数量为1，但因为父子相同色，就是1+（1-0）
如果不同，儿子节点的同色联通块数量不需要-1。
比如B-R，右边R的同色连通块数量为1，但因为父子不同色，就是1+（1）
最后对所有边遍历一遍即可。
import java.util.ArrayList;import java.util.List;import java.util.Scanner;//4//BBRR//1 2//3 2//4 1//答案为2// 7// RRBRRRB// 1 2// 1 3// 1 4// 3 5// 3 6// 4 7// 答案为16public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x = in.nextInt(); TreeNode[] treeNodes = new TreeNode[x]; char[] colors = in.next().toCharArray(); for (int i = 0; i < x; i++) { treeNodes[i] = new TreeNode(colors[i]); } int[][] ints = new int[x - 1][2]; for (int i = 1; i < x; i++) { int a = in.nextInt() - 1; int b = in.nextInt() - 1; ints[i - 1] = new int[]{a, b}; // 构建无向图，选取每个节点dfs treeNodes[a].setFriend(treeNodes[b]); treeNodes[b].setFriend(treeNodes[a]); } int sum = 0; for (int i = 0; i < ints.length; i++) { int num1 = dfs(treeNodes[ints[i][0]], treeNodes[ints[i][1]]); int num2 = dfs(treeNodes[ints[i][1]], treeNodes[ints[i][0]]); sum += num1 > num2 ? num1 - num2 : num2 - num1; } System.out.println(sum); } static int dfs(TreeNode node, TreeNode pre) { int sum = 1; for (TreeNode friend : node.friends) { if (friend != pre) { int dfs = dfs(friend, node); if (friend.color != node.color) sum += dfs; else sum += dfs - 1; } } return sum; } static class TreeNode { char color; List<TreeNode> friends; public TreeNode(char color) { this.color = color; friends = new ArrayList<>(); } void setFriend(TreeNode node) { friends.add(node); } }}