小美的字符串匹配度
我的代码（16/20）
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n=in.nextInt();
in.nextLine();
String s = in.nextLine();
String t = in.nextLine();
int res=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==t.charAt(i)){
res++;
}
}
if(res==s.length()){
System.out.println(res);
continue;
}
int max=0;
boolean flag=true;
for(int j=0;j<s.length();j++){
if(!flag){
break;
}
if(s.charAt(j)!=t.charAt(j)){
for(int k=0;k<t.length();k++){
if(t.charAt(k)==s.charAt(k)){
max=0;
}else{
if(t.charAt(k)==s.charAt(j)){
if(t.charAt(j)==s.charAt(k)){
max=2;
}else{
max=1;
}
}
}
if(max==2){
System.out.println(res+max);
flag=false;
break;
}
}
}
}
if(!flag){
continue;
}
System.out.println(res+max);
}
}
}
树形dp题
import java.util.Scanner;
import java.util.*;
class Solution{
public void getAns(int i,int[][] dp,long[] valArray,ArrayList<ArrayList<Integer>> sonNode){
if(i<0){
return;
}
//不染当前结点
for(int j=0;j<sonNode.get(i).size();j++){
dp[i][0]+=Math.max(dp[sonNode.get(i).get(j)][0],dp[sonNode.get(i).get(j)][1]);
}
//染当前结点
for(int j=0;j<sonNode.get(i).size();j++){
//和子节点权值可以开方才能染
int numj=sonNode.get(i).get(j);
if(Math.sqrt(valArray[i]*valArray[numj])%1==0){
//其它儿子依旧是和不染时情况一样 只有一个儿子选择不染+2
dp[i][1]=Math.max(dp[i][1],dp[i][0]-Math.max(dp[sonNode.get(i).get(j)][0],dp[sonNode.get(i).get(j)][1])+dp[sonNode.get(i).get(j)][0]+2);
}
}
//i-1为上层或邻居结点
getAns(i-1,dp,valArray,sonNode);
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
long[] valArray=new long[n+1];
for(int i=1;i<=n;i++){
long val=in.nextLong();
valArray[i]=val;
}
ArrayList<ArrayList<Integer>> sonNode=new ArrayList<>();
for(int i=0;i<=n;i++){
sonNode.add(new ArrayList<Integer>());
}
// int[] sonNum=new int[n+1];
for(int i=0;i<n-1;i++){
int father = in.nextInt();
int son=in.nextInt();
sonNode.get(father).add(son);
}
//树形dp
//dp[i][0]为当前结点i为根结点不染i的最大染色数
//dp[i][1]为当前结点i为根节点染i的最大染色数
int[][] dp=new int[n+1][2];
Solution solution=new Solution();
solution.getAns(n,dp,valArray,sonNode);
System.out.println(Math.max(dp[1][0],dp[1][1]));
}
}
}
可分为染当前结点和不染当前结点进行dp
7.小美的好矩阵
暴力
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int m = in.nextInt();
if(n<3||m<3){
System.out.println(0);
continue;
}
in.nextLine();
char[][] matix=new char[n][m];
for(int i=0;i<n;i++){
String s=in.nextLine();
for(int j=0;j<m;j++){
matix[i][j]=s.charAt(j);
}
}
long res=0;
for(int i=2;i<n;i++){
for(int j=2;j<m;j++){
int numA=0;
int numB=0;
int numC=0;
boolean falg=true;
outerLoop:
for(int p=i-2;p<=i;p++){
for(int q=j-2;q<=j;q++){
if(p>i-2){
if(matix[p][q]==matix[p-1][q]){
falg=false;
break outerLoop;
}
}
if(q>j-2){
if(matix[p][q]==matix[p][q-1]){
falg=false;
break outerLoop;
}
}
if(matix[p][q]!='A'&&matix[p][q]!='B'&&matix[p][q]!='C'){
falg=false;
break outerLoop;
}
if(matix[p][q]=='A'){
numA++;
}
if(matix[p][q]=='B'){
numB++;
}
if(matix[p][q]=='C'){
numC++;
}
}
}
// System.out.println(numA);
// System.out.println(numB);
// System.out.println(numC);
if(numA>0&&numB>0&&numC>0&&falg){
res++;
}
}
}
System.out.println(res);
}
}
}
