D~F Java题解，代码已去除冗余，并保留简要的注释
由题可知，最后至多保留两颗珠子，因此需要特判n<=2的情况（也就是不用任何操作直接保留）；；而由于最多进行k次移除，那么靠后边的幸存的珠子不会早于倒数第k+1颗，而前边幸存的珠子跟后边幸存的珠子距离不会小于n-k，利用前缀和思想计算前缀最大值，再遍历后k+1颗珠子即可，时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),k=Math.min(sc.nextInt(),Math.max(0,n-2)),a[]=new int[n];
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
}
if(n==1){
System.out.println(a[0]);
}
else{
long ans=-1;
for(int j=0;j<n;j++){
if(j-(n-k)+1>0){
a[j-(n-k)+1]=Math.max(a[j-(n-k)+1],a[j-(n-k)]);
}
if(j>0&&n-j<=k+1){
ans=Math.max(ans,a[j]+a[Math.max(0,j-(n-k)+1)]);
}
}
System.out.println(ans);
}
}
}
}
由题意可知，1到点p的距离其实就是1 xor p，本质上是计算1到n的异或值，因此暴力求得每一个二进制位在范围内的bit数量的奇偶性即可，时间复杂度O(TlogC)，其中C==1e9，需要注意的是本题实际测试数据有大于1e9的值，因此在实际代码的中间计算中使用了long
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),ans=n>>1&1;
for(int j=30;j>0;j--){
if((n+1)%(1L<<(j+1))>1L<<j){
ans|=(((n+1)%(1L<<(j+1))^(1L<<j))&1)<<j;
}
}
System.out.println(ans);
}
}
}
本题还可以打表找规律，代码实现时间复杂度O(T)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt();
System.out.println(n%4==1?0:n%4==2?n+1:n%4==3?1:n);
}
}
}
本题的题意即为，使得相邻项的数字大的要是小的的倍数，首先特判数组全部相同的，此时x可以取得任意值；；否则，相邻的数的较小值必须是差值的某个约数，找到这样一个差值，枚举约数依次验证即可，时间复杂度O(T(C+Pn))，其中C==1e9，max(P)约为1400，代表的是范围内数字约数最多个数
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),k=sc.nextInt(),a[]=new int[n],max=-1,min=(int)2e9;
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
max=Math.max(max,a[j]);
min=Math.min(min,a[j]);
}
if(max==min){
System.out.println(k+" "+(long)k*(k+1)/2);
}
else{
int count=0,d=0,pre=-1;
for(int j=1;j<n;j++){
if(a[j]!=a[j-1]){
d=Math.abs(a[j]-a[j-1]);
pre=Math.min(a[j],a[j-1]);
break;
}
}
long sum=0;
for(int j=1;j*j<=d;j++){
if(d%j==0){
if(check(k,a,j-pre)){
count++;
sum+=j-pre;
}
if(j*j<d&&check(k,a,d/j-pre)){
count++;
sum+=d/j-pre;
}
}
}
System.out.println(count+" "+sum);
}
}
}
static boolean check(int k,int arr[],int val){
if(val<1||val>k){
return false;
}
for(int i=1;i<arr.length;i++){
int min=Math.min(arr[i],arr[i-1]),max=arr[i]+arr[i-1]-min;
if((max+val)%(min+val)!=0){
return false;
}
}
return true;
}
}
对于一个非根节点，要么保留节点并保留子树中的权值正数的子树，要么删除节点且只保留最多一个正数子树，因此在前期搜索中需要对每个节点确定两个值：正数的子树之和以及子树最大值；在第二次搜索的时候，要假设每个节点为根的情况，同时依次计算其在删除节点和最多保留两个“子树”的最大值，时间复杂度O(Tn)
import java.util.*;
import java.io.*;
public class Main{
static long ans;
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 t=Integer.parseInt(bf.readLine());
for(int i=0;i<t;i++){
int n=Integer.parseInt(bf.readLine()),a[]=new int[n+5];
List<Integer> path[]=new List[n+5];
String arr[]=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
path[j]=new ArrayList<>();
a[j]=Integer.parseInt(arr[j-1]);
}
for(int j=0;j<n-1;j++){
arr=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);;
path[u].add(v);
path[v].add(u);
}
long max[][]=new long[n+5][],sum[]=new long[n+5];
ans=0;
find(1,path,max,sum,a);
find(1,path,0,max,sum,a,new boolean[n+5]);
bw.write(ans+"\n");
}
bw.flush();
}
static void find(int k,List<Integer> path[],long pre,long max[][],long sum[],int a[],boolean has[]){
//pre表示的是从k的父节点传来的最大的值
has[k]=true;
//不删k:
ans=Math.max(ans,a[k]+sum[k]+pre);
//删除k的时候需要取pre和max的最大值
long arr[]=new long[]{max[k][0],max[k][1],pre};
Arrays.sort(arr);
ans=Math.max(ans,arr[1]+arr[2]);
for(int b:path[k]){
if(!has[b]){
//对于传下去的新pre，要么保留k，加上”子树“之和，要么去掉b并加上”非b子树“和pre的max
long newPre=Math.max(pre+sum[k]-Math.max(0,Math.max(a[b]+sum[b],max[b][0]))+a[k],Math.max(pre,max[k][0]==Math.max(a[b]+sum[b],max[b][0])?max[k][1]:max[k][0]));
find(b,path,newPre,max,sum,a,has);
}
}
}
static void find(int k,List<Integer> path[],long max[][],long sum[],int a[]){
//此方法更新的是k（不含）子树所有的子树的[sum,max]
max[k]=new long[2];
for(int b:path[k]){
if(max[b]==null){
find(b,path,max,sum,a);
//对于b，要么保留b，可以保留尽可能多的子树，或者删除b，并保留最多一个子树
sum[k]+=Math.max(0,Math.max(a[b]+sum[b],max[b][0]));
modify(max[k],Math.max(a[b]+sum[b],max[b][0]));
}
}
}
static void modify(long max[],long p){
if(p>max[0]){
max[1]=max[0];
max[0]=p;
}
else if(p>max[1]){
max[1]=p;
}
}
}
京公网安备 11010502036488号