阅读量:0
目录
牛客.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<t;i++){ int n=in.nextInt(); //表示第n组使用hash标记26 boolean[][]hash=new boolean[n][26]; for(int j=0;j<n;j++){ String a=in.next(); char[]m=a.toCharArray(); for(int k=0;k<m.length;k++) //使用hash存储，然后设置为boolean即可 hash[j][m[k]-'a']=true; } int right=n-1; int left=0; while(left<right){ //检查是否有重复的字符 if(!check(hash,left,right))break; left++; right--; } if(left<right){ System.out.println("No"); }else{ System.out.println("Yes"); } } } }牛客.最小公倍数
public static int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); }牛客.非对称之美
回文串(一般解法，中心扩展算法，dp,动态窗口等等)
找规律，贪心
如果本身就不是回文串，那么直接返回全部
假如本身是一个字符串,他其实是关于中心对称的，那么只要为对左边或者右边对应的删除一个，就是非回文，
换句话说，我们只需要看一个字符串是不是回文，
除非你是aaaaaa这种，所有这种字符串都相同的时候，这种没有非回文串，只需要返回0。
import java.util.*; public class Main{ public static void main(String[]args){ Scanner in=new Scanner(System.in); String aa=in.nextLine(); char[]a=aa.toCharArray(); //首先先检查他是不是回文串 int left=0; int right=a.length-1; while(left<right&&a[left]==a[right]){ left++; right--; } int ret=0; for(int i=1;i<a.length;i++){ if(a[i]!=a[i-1]){ ret=1; } } if(ret==0){ System.out.print(0); } else if(left>=right) { System.out.print(a.length-1); }else{ System.out.print(a.length); } } }
