目录

牛客.mari和shiny

牛客.对称之美

牛客.最小公倍数

牛客.非对称之美

牛客.mari和shiny

1.状态转移方程

s[i]:表示字符串str中[0,i]区间内，有多少个s。

h[i]:字符串str中[0,i]区间内，有多少个sh。

y[i]:字符串str[0,i]区间内，有多少个shy。

2.状态转移方程

(0-i-1)区间

s[i]

h[i]

y[i]

import java.util.*; public class Main{     //多状态dp       public static void main(String[] args)  {       Scanner in=new Scanner(System.in);             int n=in.nextInt();             in.nextLine();             String a=in.nextLine();             char[]str=a.toCharArray();            long[]s=new long[n+1];             long[]h=new long[n+1];             long[]y=new long[n+1];             //初始化，看他是s,就初始化为1             for(int i=1;i<=str.length;i++){                 if(str[i-1]=='s'){                     s[i]=s[i-1]+1;                     h[i]=h[i-1];                     y[i]=y[i-1];                 }else if(str[i-1]=='h'){                     s[i]=s[i-1]; //假如第一个是h,但是前面没有s,所以h还是为0                     h[i]=s[i-1]+h[i-1];                     y[i]=y[i-1];                 }else if(str[i-1]=='y'){                     s[i]=s[i-1];                     h[i]=h[i-1];                     y[i]=h[i-1]+y[i-1];                 }else{                     s[i]=s[i-1];                     h[i]=h[i-1];                     y[i]=y[i-1];                 }             }             System.out.print(y[n]);     } }

牛客.对称之美

import java.util.*; public class Main{     public static boolean check(boolean[][]hash,int left,int right){         for(int i=0;i<26;i++){             if(hash[left][i]&&hash[right][i]){                 return true;             }         }             return false;               } public static void main(String[] args) {        Scanner in=new Scanner(System.in);         int t = in.nextInt();         for(int i=0;i

 public static int gcd(int a,int b){         if(b==0)return a;         return gcd(b,a%b);     }