题解 | 牛客小白月赛104 CDEF Java题解
小红购买装备
https://ac.nowcoder.com/acm/contest/94879/A
C~F Java题解，代码已去除冗余
假设a次可以打完，那么多打一次更可以打完，因此答案满足二段性，二分即可。。在check的时候，可以假设最初全部进行了全打击，先保证不浪费的情况下进行相邻打击，在用单点打击处理残局，最后在进行一波相邻打击首尾，check返回真的条件为全体不大于0，时间复杂度O(nlogC)，其中C==1e9
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long a[]=new long[n+5];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
int l=0,r=(int)1e9;
while(l<r){
int mid=(l+r)>>1;
if(check(a.clone(),mid)){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(check(a.clone(),l)){
r=l;
}
break;
}
}
System.out.println(r);
}
static boolean check(long a[],int max){
for(int i=0;i<a.length;i++){
a[i]-=max;
}
long p1=max,p2=max;
for(int i=0;i<a.length-1;i++){
if(Math.min(a[i],a[i+1])>0){
long p=Math.min(p1,Math.min(a[i],a[i+1]));
p1-=p;
a[i]-=p;
a[i+1]-=p;
}
}
for(int i=0;i<a.length;i++){
if(a[i]>0){
long p=Math.min(p2,a[i]);
p2-=p;
a[i]-=p;
}
}
for(int i=0;i<a.length-1;i++){
if(a[i]>0){
long p=Math.min(p1,a[i]);
p1-=p;
a[i]-=p;
a[i+1]-=p;
}
}
for(long b:a){
if(b>0){
return false;
}
}
return true;
}
}
分层进行模拟即可，指针最大运行两倍圈的长度，时间复杂度O(n^2)
import java.util.*;
public class Main{
static int move[][]={{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),count[]=new int[4],ans=(int)1e9;
String s[]=new String[n*2];
for(int i=0;i<n*2;i++){
s[i]=sc.next();
}
for(int i=0;i<n;i++){
int dx=i,dy=i,idx=0,pos[][]={{i,n-1},{n-1,n*2-1-i},{n*2-1-i,n},{n,i}};
while(true){
char c=s[dx].charAt(dy);
while(true){
int x=dx+move[idx][0],y=dy+move[idx][1];
if(Math.min(Math.min(x,n*2-1-x),Math.min(y,n*2-1-y))!=i){
idx=(idx+1)%4;
}
else{
dx=x;
dy=y;
break;
}
}
if(c=='X'&&s[dx].charAt(dy)=='O'){
dx-=move[idx][0];
dy-=move[idx][1];
break;
}
}
for(int found=0,steps=0;found<4;steps++){
for(int j=0;j<4;j++){
if(dx==pos[j][0]&&dy==pos[j][1]){
found++;
count[j]+=steps;
break;
}
}
while(true){
int x=dx+move[idx][0],y=dy+move[idx][1];
if(Math.min(Math.min(x,n*2-1-x),Math.min(y,n*2-1-y))!=i){
idx=(idx+1)%4;
}
else{
dx=x;
dy=y;
break;
}
}
}
}
for(int a:count){
ans=Math.min(ans,a);
}
System.out.println(ans);
}
}
方法一：二分图最大匹配为题，敲击次序和敲击对象可构成二分图，按照匈牙利算法进行，时间复杂度O(n^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()),idx[]=new int[n+5],ans[]=new int[n+5];
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
String arr[]=bf.readLine().split(" ");
for(int j=Integer.parseInt(arr[0]);j>0;j--){
path[i].add(Integer.parseInt(arr[j]));
}
}
for(int i=1;i<=n;i++){
if(!find(path,idx,new HashSet<>(),i)){
bw.write("kou is angry");
bw.flush();
return;
}
}
for(int i=1;i<=n;i++){
ans[idx[i]]=i;
}
for(int i=1;i<=n;i++){
bw.write(ans[i]+" ");
}
bw.flush();
}
static boolean find(List<Integer> path[],int idx[],Set<Integer> set,int k){
for(int a:path[k]){
if(!set.contains(a)){
set.add(a);
if(idx[a]==0||find(path,idx,set,idx[a])){
idx[a]=k;
return true;
}
}
}
return false;
}
}
方法二：搜索（待写）
分别计算用了传送和不用的最大遍历点数，取最大值，其中在计算后者的时候，需要避免同组先点的重复计算，时间复杂度O(nlogC),其中C==19
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]),x=Integer.parseInt(arr[1]),a[]=new int[n+5],ans=Math.min(n,(x+2)/3),level[]=new int[n+5],p[][]=new int[n+5][19];
List<Integer> path[]=new List[n+5];
arr=bf.readLine().split(" ");
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(arr[i-1]);
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
arr=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
path[u].add(v);
path[v].add(u);
}
Queue<Integer> q=new LinkedList<>();
q.add(1);
level[1]=1;
while(!q.isEmpty()){
int b=q.poll();
for(int c:path[b]){
if(level[c]==0){
p[c][0]=b;
level[c]=1+level[b];
q.add(c);
}
}
}
for(int i=1;i<19;i++){
for(int j=1;j<=n;j++){
p[j][i]=p[p[j][i-1]][i-1];
}
}
for(int i=1;i<=n;i++){
int lca=find(i,a[i],p,level),num=level[i]+level[a[i]]-level[lca],cost=num+level[i]+level[a[i]]-1;
//经过点数：num=level[i]+level[a[i]]-level[lca]
//花费的时间num+1+来去的距离;
if(cost<=x){
ans=Math.max(ans,num+Math.min((x-cost)/3,n-num));
}
}
bw.write(ans+"\n");
bw.flush();
}
static int find(int a,int b,int p[][],int level[]){
if(level[a]<level[b]){
return find(b,a,p,level);
}
for(int i=18;i>=0;i--){
if(level[a]-level[b]>=1<<i){
a=p[a][i];
}
}
for(int i=18;i>=0;i--){
if(p[a][i]!=p[b][i]){
a=p[a][i];
b=p[b][i];
}
}
return a==b?a:p[a][0];
}
}
我心想怎么北大佬也焦虑上了
