C~F Java题解，代码已去除冗余~~~
最终状态只能是全0，因此相邻格子在正负性上如果相同，必然会无法继续接近0而导致失败，挨个验证即可，时间复杂度O(n^2)
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+2][n+2];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=sc.nextInt();
if((long)a[i][j]*a[i-1][j]>0||(long)a[i][j]*a[i][j-1]>0){
System.out.println("NO");
return;
}
}
}
System.out.println("YES");
}
}
不管是顺时针走x还是逆时针走y，其最大周期长度必定是n，因此预处理出走各种次数的y后的位置，再枚举走各种次数的x，即可得到最小次数，，另外k不为0的时候需要再次验证走半圈的情况，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt(),ans=n*2+10,r[]=new int[n];
Arrays.fill(r,n*10);
for(int i=0;i<n;i++){
int d=(int)((long)i*y%n);
r[d]=Math.min(r[d],i);
}
for(int i=0;i<n;i++){
ans=Math.min(ans,i+r[(int)(((long)i*x-b+a+n)%n)]);
if(k!=0){
ans=Math.min(ans,1+i+r[(int)(((long)i*x-b+a+n*3/2)%n)]);
}
}
System.out.println(ans>n*2?-1:ans);
}
}
要想最大深度最大，且操作次数为1，那么操作一定发生在某个节点的二两长的子树时间，一个子树打断后接在另一个子树末端的父节点上，那么直接深搜即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
}
System.out.println(find(1,1,path,new boolean[n+5])[0]);
}
static int[] find(int k,int pre,List<Integer> path[],boolean has[]){
int ans[]=new int[]{pre,pre},max1=0,max2=0;
has[k]=true;
for(int a:path[k]){
if(!has[a]){
int d[]=find(a,pre+1,path,has);
ans[0]=Math.max(ans[0],d[0]);
ans[1]=Math.max(ans[1],d[1]);
if(d[1]>max1){
max2=max1;
max1=d[1];
}
else if(d[1]>max2){
max2=d[1];
}
}
}
ans[0]=Math.max(ans[0],max1+max2-1-pre);
return ans;
}
}
答案符合二段性，也就是假如某个最大深度的可以达到，那么更长的深度也能达到，因此给定最大深度，枚举到所有深度超标的点，求得它们的父节点的最近公共祖先lca，那么要想在一次操作就减小道规定深度以内，需要再次枚举跟lca非祖孙关系的节点，尝试操作后判断，时间复杂度O(n(logn)^2)
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
int n=Integer.parseInt(bf.readLine()),level[]=new int[n+5],m=(int)(Math.log(n)/Math.log(2))+1,p[][]=new int[m][n+5],dep[]=new int[n+5],l=1,r=n;
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
String arr[]=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
path[u].add(v);
path[v].add(u);
}
level[1]=1;
find(1,path,level,p,dep);
for(int i=1;i<m;i++){
for(int j=1;j<=n;j++){
p[i][j]=p[i-1][p[i-1][j]];
}
}
while(l<r){
int mid=(l+r)>>1;
if(check(n,mid,level,p,dep)){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(check(n,l,level,p,dep)){
r=l;
}
break;
}
}
bw.write(r+"\n");
bw.flush();
}
static void find(int k,List<Integer> path[],int level[],int p[][],int dep[]){
dep[k]=level[k];
for(int a:path[k]){
if(level[a]==0){
level[a]=1+level[k];
p[0][a]=k;
find(a,path,level,p,dep);
dep[k]=Math.max(dep[k],dep[a]);
}
}
}
static int lca(int a,int b,int level[],int p[][]){
if(level[a]<level[b]){
return lca(b,a,level,p);
}
for(int i=p.length-1;i>=0;i--){
if(level[a]-level[b]>=(1<<i)){
a=p[i][a];
}
}
for(int i=p.length-1;i>=0;i--){
if(p[i][a]!=p[i][b]){
a=p[i][a];
b=p[i][b];
}
}
return a==b?a:p[0][a];
}
static boolean check(int n,int max,int level[],int p[][],int dep[]){
int anc=-1;
boolean has[]=new boolean[n+5];
for(int i=1;i<=n;i++){
if(level[i]>max){
has[i]=has[p[0][i]]=true;
anc=anc==-1?p[0][i]:lca(anc,p[0][i],level,p);
}
}
if(anc==-1){
return true;
}
for(int i=1;i<=n;i++){
if(!has[i]){
int lca=lca(anc,i,level,p);
if(lca!=i&&anc!=lca&&level[p[0][i]]+1+dep[anc]-level[anc]<=max&&level[p[0][anc]]+1+dep[i]-level[i]<=max){
return true;
}
}
}
return false;
}
}
京公网安备 11010502036488号