题解 | 牛客周赛 Round 62 DEFG Java题解
小红的字符移动
https://ac.nowcoder.com/acm/contest/91177/A
D~G Java题解，代码已去除冗余
不妨把树看做是以1为根的，可知，在停下来之前，移动方向是远离根节点的，因此只需要统计通往叶节点的概率即可，时间复杂度O(nlog(mod))
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
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,1,path,new boolean[n+5]));
}
static long find(int k,int level,long p,List<Integer> path[],boolean has[]){
has[k]=true;
List<Integer> list=new ArrayList<>();
for(int a:path[k]){
if(!has[a]){
list.add(a);
}
}
if(list.size()==0){
return level*pow(p,mod-2)%mod;
}
long ans=0;
for(int a:list){
ans+=find(a,level+1,p*list.size()%mod,path,has);
}
return ans%mod;
}
static long pow(long a,long b){
long ans=1;
for(;b!=0;b>>=1,a=a*a%mod){
if(b%2==1){
ans=ans*a%mod;
}
}
return ans;
}
}
E 小红的中位数查询（easy） && F 小红的中位数查询（hard）
可离散值域后，主席树上二分，时间复杂度O(nlogn+q(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));
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]),a[]=new int[n+5],p=0,map2[]=new int[n];
TreeSet<Integer> set=new TreeSet<>();
arr=bf.readLine().split(" ");
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(arr[i-1]);
set.add(a[i]);
}
Map<Integer,Integer> map1=new HashMap<>();
for(int b:set){
map1.put(b,p);
map2[p]=b;
p++;
}
SegTree st[]=new SegTree[n+1];
st[0]=new SegTree(0,p-1);
build(st[0]);
for(int i=1;i<=n;i++){
st[i]=new SegTree(0,p-1);
insert(st[i-1],st[i],map1.get(a[i]));
}
for(int i=0;i<q;i++){
arr=bf.readLine().split(" ");
int l=Integer.parseInt(arr[0]),r=Integer.parseInt(arr[1]),low=0,high=p-1;
while(low<high){
int mid=(low+high)>>1;
if((find(st[r],0,mid)-find(st[l-1],0,mid))*2>=r-l+1){
high=mid;
}
else{
low=mid+1;
}
if(low==high-1){
if((find(st[r],0,low)-find(st[l-1],0,low))*2>=r-l+1){
high=low;
}
break;
}
}
bw.write(map2[high]+"\n");
}
bw.flush();
}
static int find(SegTree st,int a,int b){
int l=st.l,r=st.r;
if(l==a&&r==b){
return st.count;
}
int mid=(l+r)>>1;
return b<=mid?find(st.left,a,b):a>mid?find(st.right,a,b):find(st.left,a,mid)+find(st.right,mid+1,b);
}
static void insert(SegTree st1,SegTree st2,int a){
st2.count=st1.count+1;
int l=st1.l,r=st1.r;
if(l<r){
int mid=(l+r)>>1;
if(a<=mid){
st2.left=new SegTree(l,mid);
st2.right=st1.right;
insert(st1.left,st2.left,a);
}
else{
st2.right=new SegTree(mid+1,r);
st2.left=st1.left;
insert(st1.right,st2.right,a);
}
}
}
static void build(SegTree st){
int l=st.l,r=st.r;
st.count=0;
if(l<r){
int mid=(l+r)>>1;
st.left=new SegTree(l,mid);
st.right=new SegTree(mid+1,r);
build(st.left);
build(st.right);
}
}
}
class SegTree{
int l,r,count;
SegTree left,right;
public SegTree(int l,int r){
this.l=l;
this.r=r;
}
}
最小距离保证的是中间不会提前到0，事假复杂度O(nC),其中C==1e4
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),x=sc.nextInt(),a[]=new int[n+1],sum=0,dis[][]=new int[n+1][20005],last[][][]=new int[n+1][20005][3];
Arrays.fill(dis[0],(int)1e9);
dis[0][10000+x]=0;
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
sum+=a[i];
dis[i]=dis[i-1].clone();
for(int j=0;j<=20000;j++){
last[i][j]=last[i-1][j].clone();
}
//先考虑加的
for(int p=a[i];p<=20000;p++){
int d=dis[i-1][p-a[i]]+a[i];
if(d<dis[i][p]){
dis[i][p]=d;
last[i][p]=new int[]{i-1,p-a[i],i};
}
}
//再考虑减的：
for(int p=0;p<=20000-a[i];p++){
int d=dis[i-1][p+a[i]]+a[i];
if(d<dis[i][p]){
dis[i][p]=d;
last[i][p]=new int[]{i-1,p+a[i],-i};
}
}
}
if(dis[n][10000]>1e6){
System.out.println(sum);
for(int i=1;i<=n;i++){
System.out.print(i+" ");
}
}
else{
boolean has[]=new boolean[n+1];
System.out.println(dis[n][10000]);
Queue<Integer> q1=new PriorityQueue<>((u,v)->a[v]-a[u]),q2=new PriorityQueue<>((u,v)->a[v]-a[u]);
int p1=n,p2=10000;
while(p1>0){
int b[]=last[p1][p2];
if(b[2]<0){
q2.add(-b[2]);
}
else{
q1.add(b[2]);
}
has[Math.abs(b[2])]=true;
p1=b[0];
p2=b[1];
}
while(x!=0){
if(x<0){
System.out.print(q1.peek()+" ");
x+=a[q1.poll()];
}
else{
System.out.print(q2.peek()+" ");
x-=a[q2.poll()];
}
}
for(int i=1;i<=n;i++){
if(!has[i]){
System.out.print(i+" ");
}
}
}
}
}
