BDEF Java
B 小红的伪回文子串（easy） && E 小红的伪回文子串（hard）
遍历每个字符，字符需要跟前边遍历过的字符的配对儿计算贡献（必须跟当前不同），贡献量要么是当前位置距离串尾的距离，要么是前边某个字符距离串首的距离，两者距离取较小值，实现的时候可以按照26个字母记录两个前缀和：一个是字母距离串首的距离之和，一个是遍历到该位置字母数量总和；贡献求得时候分成两部分求即可，时间复杂度O(nC),其中是n是字符串长度，C==26
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length(),count[][]=new int[n+1][26];
long ans=0,pre[][]=new long[n+1][26];
for(int i=1;i<n;i++){
count[i]=count[i-1].clone();
pre[i]=pre[i-1].clone();
count[i][s.charAt(i-1)-'a']++;
pre[i][s.charAt(i-1)-'a']+=i;
int idx=Math.min(n-2-i,i-1);
for(int j=0;j<26;j++){
if(j!=s.charAt(i)-'a'){
ans+=pre[idx+1][j]+(n-i)*(count[i][j]-count[idx+1][j]);
}
}
}
System.out.println(ans);
}
}
三种情况，在一个数字上操作，在相邻数字上操作，再不相邻数字上操作，计算变化值的最小值，其中第三种情况统计的时候用前后缀来降低复杂度，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n+5];
long sum=0,min=(long)1e18;
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
if(i>1){
sum+=Math.abs(a[i]-a[i-1]);
}
}
int b[]=a.clone();
//修改单个位置：
for(int i=1;i<=n;i++){
min=Math.min(min,find(n,a,b,new int[][]{{i,0},{i,1}}));
}
//修改相邻位置：
for(int i=2;i<=n;i++){
min=Math.min(min,find(n,a,b,new int[][]{{i,0},{i-1,1}}));
min=Math.min(min,find(n,a,b,new int[][]{{i-1,0},{i,1}}));
}
//修改不相邻位置：
long left1[]=new long[n+5],left2[]=new long[n+5],right1[]=new long[n+5],right2[]=new long[n+5];
left1[0]=left2[0]=right1[n+1]=right2[n+1]=(long)1e18;
for(int i=1;i<=n;i++){
left1[i]=Math.min(left1[i-1],find(n,a,b,new int[][]{{i,0}}));
left2[i]=Math.min(left2[i-1],find(n,a,b,new int[][]{{i,1}}));
}
for(int i=n;i>=1;i--){
right1[i]=Math.min(right1[i+1],find(n,a,b,new int[][]{{i,0}}));
right2[i]=Math.min(right2[i+1],find(n,a,b,new int[][]{{i,1}}));
}
for(int i=2;i<n;i++){
min=Math.min(min,left1[i-1]+right2[i+1]);
min=Math.min(min,left2[i-1]+right1[i+1]);
}
System.out.println(sum+min);
}
static long find(int n,int a[],int b[],int idx[][]){
int maxIdx=-1,minIdx=n+1;
long d1=0,d2=0;
for(int c[]:idx){
maxIdx=Math.max(maxIdx,c[0]);
minIdx=Math.min(minIdx,c[0]);
}
for(int i=minIdx;i<=maxIdx+1;i++){
if(i<=n&&i>1){
d1+=Math.abs((long)b[i]-b[i-1]);
}
}
for(int c[]:idx){
if(c[1]==0){
b[c[0]]>>=1;
}
else{
b[c[0]]<<=1;
}
}
for(int i=minIdx;i<=maxIdx+1;i++){
if(i<a.length&&i>1){
d2+=Math.abs((long)b[i]-b[i-1]);
}
}
for(int c[]:idx){
b[c[0]]=a[c[0]];
}
return d2-d1;
}
}
预处理1-1e5数字的约数，建图，把每个数字看做一个点，再把每个点跟自己的约数正反连边，跑最短路，
时间复杂度O(ClogC+能过)
import java.util.*;
public class Main{
static int move[][]={{0,1},{1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),dis[]=new int[n*m+100005];
Arrays.fill(dis,(int)1e9);
dis[0]=0;
List<int[]> path[]=new List[n*m+100005];
List<Integer> divisors[]=new List[100005];
for(int i=0;i<path.length;i++){
path[i]=new ArrayList<>();
}
for(int i=1;i<=100000;i++){
divisors[i]=new ArrayList<>();
}
for(int i=2;i<=100000;i++){
for(int j=i;j<=100000;j+=i){
divisors[j].add(i);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int a=sc.nextInt();
for(int mo[]:move){
int x=i+mo[0],y=j+mo[1];
if(x<n&&y<m){
path[i*m+j].add(new int[]{x*m+y,1});
}
}
for(int b:divisors[a]){
path[i*m+j].add(new int[]{n*m+b,1});
path[n*m+b].add(new int[]{i*m+j,0});
}
}
}
Queue<int[]> q=new PriorityQueue<>((a1,a2)->Integer.compare(a1[1],a2[1]));
q.add(new int[]{0,0});
while(!q.isEmpty()){
int a[]=q.poll();
if(dis[a[0]]<a[1]){
continue;
}
for(int b[]:path[a[0]]){
if(dis[b[0]]>a[1]+b[1]){
dis[b[0]]=a[1]+b[1];
q.add(new int[]{b[0],dis[b[0]]});
}
}
}
System.out.println(dis[n*m-1]);
}
}
京公网安备 11010502036488号