题解 | 牛客小白月赛99 BCDEFG Java题解
材料打印
https://ac.nowcoder.com/acm/contest/88455/A
B~G Java题解，代码中已去掉冗余
目标是尽量把n保持在最大的可能得值，才能保持次数最多，那么最大的除数肯定是大于n的一半的，时间复杂度O(Tlogn)
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++){
long n=sc.nextLong();
int ans=0;
while(n!=0){
n=n/2-1+n%2;
ans++;
}
System.out.println(ans);
}
}
}
利用并查集，先合并连通块，假如起终点是联通的，就代表无需激光，，否则遍历格子，每个格子是否存在邻居是跟终点相连的，并标记这一行以及这一列，，再遍历第二次，遇到跟起点联通并且行或者列跟终点连通的各自直接返回YES，，时间复杂度O(nm)
import java.util.*;
public class Main{
static int move[][]={{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),group[]=new int[n*m],start=-1,end=-1;
char c[][]=new char[n][];
for(int i=0;i<n;i++){
c[i]=sc.next().toCharArray();
for(int j=0;j<m;j++){
group[i*m+j]=i*m+j;
if(c[i][j]=='S'){
start=i*m+j;
}
else if(c[i][j]=='E'){
end=i*m+j;
}
}
}
//寻找连通块：
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(c[i][j]!='#'){
for(int mo[]:move){
int x=i+mo[0],y=j+mo[1];
if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]!='#'){
union(i*m+j,x*m+y,group);
}
}
}
}
}
if(find(start,group)==find(end,group)){
//不需要用激光
System.out.println("YES");
}
else{
boolean row[]=new boolean[n],col[]=new boolean[m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int mo[]:move){
int x=i+mo[0],y=j+mo[1];
if(x>=0&&x<n&&y>=0&&y<m&&find(x*m+y,group)==find(end,group)){
row[i]=col[j]=true;
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(find(i*m+j,group)==find(start,group)&&(row[i]||col[j])){
System.out.println("YES");
return;
}
}
}
System.out.println("NO");
}
}
static void union(int a,int b,int group[]){
group[find(b,group)]=find(a,group);
}
static int find(int a,int group[]){
if(a!=group[a]){
group[a]=find(group[a],group);
}
return group[a];
}
}
若存在任何人的时间间隔都除不尽的最小数，一定是质数，质数不可能大于第n+1个，因此筛出前2e5个质数，再进行判断，找出每组中最小不存在的质数，时间复杂度O(ClogC+Tn)，其中C==3e6
import java.util.*;
public class Main{
public static void main(String args[]){
boolean notPrime[]=new boolean[(int)3e6];
List<Integer> prime=new ArrayList<>();
for(int i=2;i<3e6;i++){
if(!notPrime[i]){
prime.add(i);
for(int j=i*2;j<3e6;j+=i){
notPrime[j]=true;
}
}
}
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt();
Set<Integer> set=new HashSet<>();
for(int j=0;j<n;j++){
set.add(sc.nextInt());
}
for(int a:prime){
if(!set.contains(a)){
System.out.println(a);
break;
}
}
}
}
}
有些骨牌可以导致连锁反应，因此可以区间合并，只推起头的那个，时间复杂度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(),m=sc.nextInt(),h[]=new int[n],x[]=new int[n],ans=0;
Integer idx[]=new Integer[n];
for(int j=0;j<n;j++){
h[j]=sc.nextInt();
idx[j]=j;
}
for(int j=0;j<n;j++){
x[j]=sc.nextInt();
}
Arrays.sort(idx,(a,b)->Integer.compare(x[a],x[b]));
Queue<Integer> q=new PriorityQueue<>((a,b)->Integer.compare(b,a));
for(int j=0,k=1;j<n;){
int max=x[idx[j]]+h[idx[j]];
while(k<n&&max>=x[idx[k]]){
max=Math.max(max,x[idx[k]]+h[idx[k]]);
k++;
}
q.add(k-j);
j=k;
}
for(int j=0;j<m&&!q.isEmpty();j++){
ans+=q.poll();
}
System.out.println(ans);
}
}
}
总的可能得距离等于最短距离加上在某两堵墙之间来回的距离，那么可以等同于在相邻的墙之间来回，这样的距离种数最多有sqrt(n)种，因此采用背包来计算，时间复杂度O(Ttsqrt(n))
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(),t=sc.nextInt(),x[]=new int[m];
for(int j=0;j<m;j++){
x[j]=sc.nextInt();
}
if(n>t){
System.out.println("0");
}
else{
Arrays.sort(x);
boolean has[]=new boolean[n*2+5],dis[]=new boolean[t-n+1];
dis[0]=true;
for(int j=1;j<m;j++){
has[(x[j]-x[j-1])*2]=true;
}
for(int j=0;j<=n*2;j+=2){
if(has[j]){
for(int k=j;k<=t-n;k++){
dis[k]|=dis[k-j];
}
}
}
for(int j=t-n;;j--){
if(dis[j]){
System.out.println(j+n);
break;
}
}
}
}
}
}
优先队列维护此时的鱼，离散化并用树状数组记录每一段的总重量，二分找到每一次吃的最大值，O(能过)
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(),x=sc.nextInt(),weight[]=new int[n+5],p=1;
TreeSet<Integer> set1=new TreeSet<>(),set2=new TreeSet<>();
Queue<int[]> q1=new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0])),q2=new PriorityQueue<>((a,b)->Integer.compare(a[1],b[1]));
for(int j=0;j<n;j++){
int l=sc.nextInt(),r=sc.nextInt(),y=sc.nextInt();
q1.add(new int[]{l,r,y});
set1.add(y);
set2.add(l);
set2.add(r);
}
Map<Integer,Integer> map=new HashMap<>();
for(int a:set1){
weight[p]=a;
map.put(a,p);
p++;
}
long count[]=new long[n+5],ans=x;
for(int a:set2){
while(!q2.isEmpty()&&q2.peek()[1]<=a){
int b[]=q2.poll();
update(count,map.get(b[2]),-b[2]);
}
while(!q1.isEmpty()&&q1.peek()[0]<=a){
int b[]=q1.poll();
update(count,map.get(b[2]),b[2]);
q2.add(b);
}
int maxIdx=0;
long cur=x;
while(maxIdx<p-1){
int l=maxIdx+1,r=p-1;
if(weight[l]>cur){
break;
}
while(l<r){
int mid=(l+r)>>1;
if(weight[mid]<=cur){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(weight[r]<=cur){
l=r;
}
break;
}
}
cur=x+get(count,l);
maxIdx=l;
}
ans=Math.max(ans,cur);
}
System.out.println(ans);
}
}
static long get(long count[],int idx){
long ans=0;
for(int i=idx;i!=0;i&=i-1){
ans+=count[i];
}
return ans;
}
static void update(long count[],int idx,int inc){
for(int i=idx;i<count.length;i+=i&-i){
count[i]+=inc;
}
}
}
