题解 | 牛客小白月赛102 Java题解
序列中的排列
https://ac.nowcoder.com/acm/contest/91355/A
本题解中，代码已去除冗余，并保留简要注释
只需判断序列中是否包含全部1-k的数字即可，时间复杂度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=sc.nextInt();
Set<Integer> set=new HashSet<>();
for(int j=0;j<n;j++){
int a=sc.nextInt();
if(a<=k){
set.add(a);
}
}
System.out.println(set.size()==k?"YES":"NO");
}
}
}
化简可得，本题中未知数符合x=a+1/x的方程，且答案大于0，二次方程求解即可，时间复杂度O(T)（为保证运行效率，Java需要快读或者手动处理字符串为浮点数，本代码只手动处理）
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++){
double a=Double.parseDouble(sc.next());
System.out.println((a+Math.sqrt(a*a+4))/2);
}
}
}
根据实际总和与sum的大小关系，大于则需要从最大数开始最大幅度减少，否则从最小数开始最大幅度增加，时间复杂度O(Tnlogn)
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(),sum=sc.nextInt(),a[]=new int[n],ans=0;
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
sum-=a[j];
}
Arrays.sort(a);
if(sum>0){
for(int j=0;;j++){
int d=10000-a[j];
ans++;
if(d>=sum){
break;
}
sum-=d;
}
}
else if(sum<0){
sum=-sum;
for(int j=n-1;;j--){
ans++;
int d=a[j]+10000;
if(d>=sum){
break;
}
sum-=d;
}
}
System.out.println(ans);
}
}
}
分层最短路，更新数据时需要保证连续不休息次数不大于k，同时需要注意k==0的特殊情况（退化为带边权的简单最短路），时间复杂度O(T(k+1)(m+n)log((k+1)*mn))
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(),m=sc.nextInt(),k=sc.nextInt(),a[]=new int[n+5];
List<Integer> path[]=new List[n+5];
for(int j=1;j<=n;j++){
path[j]=new ArrayList<>();
a[j]=sc.nextInt();
}
for(int j=0;j<m;j++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
}
long dis[][]=new long[n+5][k+5],ans=(long)1e18;
for(int j=1;j<=n;j++){
Arrays.fill(dis[j],(long)1e18);
}
Queue<long[]> q=new PriorityQueue<>((x,y)->Long.compare(x[2],y[2]));
dis[1][0]=a[1];
q.add(new long[]{1,0,a[1]});
if(k!=0){
dis[1][1]=1;
q.add(new long[]{1,1,1});
}
while(!q.isEmpty()){
long b[]=q.poll();
if(dis[(int)b[0]][(int)b[1]]<b[2]){
continue;
}
for(int c:path[(int)b[0]]){
long d=b[2]+a[c];
if(dis[c][0]>d){
dis[c][0]=d;
q.add(new long[]{c,0,d});
}
if(b[1]<k){
d=b[2]+1;
if(dis[c][(int)b[1]+1]>d){
dis[c][(int)b[1]+1]=d;
q.add(new long[]{c,b[1]+1,d});
}
}
}
}
for(long b:dis[n]){
ans=Math.min(ans,b);
}
System.out.println(ans);
}
}
}
至少经过一个k类型的点，那么就固定某个k类型点，计算经过的所经的路线最大值去更新k的答案即可，次数可利用树上递归求得，时间复杂度O(Tn)
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 t=Integer.parseInt(bf.readLine());
for(int i=0;i<t;i++){
int n=Integer.parseInt(bf.readLine()),c[]=new int[n+5],w[]=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<>();
c[j]=Integer.parseInt(arr[j-1]);
}
arr=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
w[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],ans[]=new long[n+5];
Arrays.fill(ans,-(long)1e18);
find(1,path,w,max,new boolean[n+5]);
find(1,path,w,c,0,max,ans,new boolean[n+5]);
for(int j=1;j<=n;j++){
bw.write(ans[j]==-1e18?"-1 ":ans[j]+" ");
}
bw.write("\n");
}
bw.flush();
}
static void find(int k,List<Integer> path[],int w[],long max[],boolean has[]){
has[k]=true;
for(int a:path[k]){
if(!has[a]){
find(a,path,w,max,has);
max[k]=Math.max(max[k],max[a]);
}
}
max[k]+=w[k];
}
static void find(int k,List<Integer> path[],int w[],int c[],long pre,long max[],long ans[],boolean has[]){
has[k]=true;
pre=Math.max(pre,0);
long max1=-(long)1e18,max2=-(long)1e18;
for(int a:path[k]){
if(!has[a]){
if(max[a]>max1){
max2=max1;
max1=max[a];
}
else if(max[a]>max2){
max2=max[a];
}
}
}
for(int a:path[k]){
if(!has[a]){
find(a,path,w,c,Math.max(pre,max1==max[a]?max2:max1)+w[k],max,ans,has);
}
}
long cur[]=new long[]{pre,max1,max2};
Arrays.sort(cur);
ans[c[k]]=Math.max(ans[c[k]],w[k]+Math.max(0,cur[1])+Math.max(0,cur[2]));
}
}
本题需要将所有的点的可能得类型值先利用随机映射为较大的数，若一个路线的哈希值之和与某排列的哈希值之和相同，基本可以判断路径成立，对于每个类型的节点，可用哈希表记录其在某个哈希和之下的最大值，便于同类型之间互相查找。。由于遍历树的顺序与答案的更新无影响，本题采用的广搜，且鉴于复杂收据结构难以通过本题，需要优化建图方式和队列的实现，本题皆采用传统的数组模拟，时间复杂度O(Tn+le6)
import java.util.*;
import java.io.*;
public class Main{
static int head=0,tail=0;
static long pre[]=new long[(int)1e6+10],q[][]=new long[(int)1e6][];
static{
for(int i=1;i<=1e6;i++){
pre[i]=pre[i-1]+(long)(Math.random()*1e12);
}
}
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++){
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),x=Integer.parseInt(arr[1]),c[]=new int[n+5],w[]=new int[n+5],start[]=new int[n+5],next[]=new int[n*2+5],cur=1,edge[]=new int[n*2+5];
Map<Long,Long> map[]=new Map[n+5];
arr=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
c[j]=Integer.parseInt(arr[j-1]);
map[j]=new HashMap<>();
}
arr=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
w[j]=Integer.parseInt(arr[j-1]);
}
Arrays.fill(next,-1);
for(int j=0;j<n-1;j++){
arr=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
next[cur]=start[u];
start[u]=cur;
edge[cur++]=v;
next[cur]=start[v];
start[v]=cur;
edge[cur++]=u;
}
long ans[]=new long[n+5];
Arrays.fill(ans,-(long)1e18);
boolean has[]=new boolean[n+5];
has[x]=true;
add(new long[]{x,0,0});
while(head!=tail){
long a[]=poll(),target=pre[c[(int)a[0]]-1]+(pre[c[x]]-pre[c[x]-1])-a[1];
ans[c[(int)a[0]]-1]=Math.max(ans[c[(int)a[0]]-1],map[c[(int)a[0]]].getOrDefault(target,-(long)1e18)+a[2]+w[(int)a[0]]-w[x]);
map[c[(int)a[0]]].put(a[1],Math.max(map[c[(int)a[0]]].getOrDefault(a[1],-(long)1e18),a[2]+w[(int)a[0]]));
for(int j=start[(int)a[0]];j!=0;j=next[j]){
if(!has[edge[j]]){
has[edge[j]]=true;
add(new long[]{edge[j],a[1]+pre[c[(int)a[0]]]-pre[c[(int)a[0]]-1],a[2]+w[(int)a[0]]});
}
}
}
for(int j=0;j<n;j++){
bw.write(ans[j]<-(long)1e17?"-1 ":ans[j]+" ");
}
bw.write("\n");
}
bw.flush();
}
static void add(long a[]){
q[tail++]=a;
}
static long[] poll(){
return q[head++];
}
}
本题的思路跟F类似，只是需要不断缩小树的范围求解，具体需要在当前连通子树中找到重心，以此为根沿用F的做法，这样可以保证最大搜索量仅为log级别，时间复杂度O(Tnlogn+1e6)
import java.util.*;
import java.io.*;
public class Main{
static int head=0,tail=0,c[],w[],start[],next[],edge[],cur,centerIdx,minSize,count[],curNum;
static long pre[]=new long[(int)1e6+10],q[][]=new long[(int)1e6][],ans[];
static boolean forbid[];
static Map<Long,Long> map[];
static{
for(int i=1;i<=1e6;i++){
pre[i]=pre[i-1]+(long)(Math.random()*1e12);
}
}
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());
c=new int[n+5];
w=new int[n+5];
start=new int[n+5];
next=new int[n*2+5];
cur=1;
edge=new int[n*2+5];
map=new Map[n+5];
count=new int[n+5];//临时存储子树大小
String[] arr=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
c[j]=Integer.parseInt(arr[j-1]);
}
arr=bf.readLine().split(" ");
for(int j=1;j<=n;j++){
w[j]=Integer.parseInt(arr[j-1]);
}
Arrays.fill(next,-1);
for(int j=0;j<n-1;j++){
arr=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
next[cur]=start[u];
start[u]=cur;
edge[cur++]=v;
next[cur]=start[v];
start[v]=cur;
edge[cur++]=u;
}
ans=new long[n+5];
Arrays.fill(ans,-(long)1e18);
forbid=new boolean[n+5];
find(-1,1);
for(int j=0;j<n;j++){
bw.write(ans[j]<-(long)1e17?"-1 ":ans[j]+" ");
}
bw.write("\n");
}
bw.flush();
}
static void findAns(){
head=tail=0;
add(new long[]{centerIdx,0,0,-1});
while(head!=tail){
long a[]=poll(),target=pre[c[(int)a[0]]-1]+(pre[c[centerIdx]]-pre[c[centerIdx]-1])-a[1];
ans[c[(int)a[0]]-1]=Math.max(ans[c[(int)a[0]]-1],map[c[(int)a[0]]].getOrDefault(target,-(long)1e18)+a[2]+w[(int)a[0]]-w[centerIdx]);
map[c[(int)a[0]]].put(a[1],Math.max(map[c[(int)a[0]]].getOrDefault(a[1],-(long)1e18),a[2]+w[(int)a[0]]));
for(int j=start[(int)a[0]];j!=0;j=next[j]){
if(edge[j]!=a[3]&&!forbid[edge[j]]){
add(new long[]{edge[j],a[1]+pre[c[(int)a[0]]]-pre[c[(int)a[0]]-1],a[2]+w[(int)a[0]],a[0]});
}
}
}
}
static void find(int last,int k){
//存储本轮遍历过的点，并初始化相应的map，count
curNum=0;
minSize=(int)1e9;
centerIdx=-1;
findAll(last,k);
findCenter(-1,k);
findAns();
forbid[centerIdx]=true;
for(int j=start[centerIdx];j!=0;j=next[j]){
if(!forbid[edge[j]]){
find(centerIdx,edge[j]);
}
}
}
static void findAll(int last,int k){
//搜索子树中的所有点
curNum++;
map[c[k]]=new HashMap<>();
count[k]=1;
for(int j=start[k];j!=0;j=next[j]){
if(!forbid[edge[j]]&&last!=edge[j]){
findAll(k,edge[j]);
count[k]+=count[edge[j]];
}
}
}
static void findCenter(int last,int k){
//寻找当前子树的重心
int max=0,total=0;
for(int j=start[k];j!=0;j=next[j]){
if(!forbid[edge[j]]&&edge[j]!=last){
findCenter(k,edge[j]);
total+=count[edge[j]];
max=Math.max(max,count[edge[j]]);
}
}
max=Math.max(max,curNum-1-total);
if(max<minSize){
minSize=max;
centerIdx=k;
}
}
static void add(long a[]){
q[tail++]=a;
}
static long[] poll(){
return q[head++];
}
}
