C~F Java题解
容易发现，只要数组排序后符合要求就一定有一种方案，否则没有，时间复杂度O(nlogn)
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()),a[]=new int[n];
String arr[]=bf.readLine().split(" ");
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(arr[i]);
}
Arrays.sort(a);
for(int i=1;i<n-1;i++){
if((long)a[i-1]*a[i]>=(long)a[i]*a[i+1]){
bw.write("NO\n");
bw.flush();
return;
}
}
bw.write("YES\n");
for(int b:a){
bw.write(b+" ");
}
bw.flush();
}
}
除了四种移动方向建图之外，还有“虫洞”，事实上，虫洞就是横向或者纵向的最大连续0的两端位置互相连接的，因此双指针寻找即可，由于边权为1，因此每个格子最多遍历1次，时间复杂度O(n^2)
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(),a[][]=new int[n][n],dis[][]=new int[n][n];
List<int[]> path[][]=new List[n][n];
for(int i=0;i<n;i++){
Arrays.fill(dis[i],-1);
for(int j=0;j<n;j++){
path[i][j]=new ArrayList<>();
a[i][j]=sc.nextInt();
}
}
//处理虫洞：
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]==0){
int k=j;
while(k<n&&a[i][k]==0){
k++;
}
path[i][j].add(new int[]{i,k-1});
path[i][k-1].add(new int[]{i,j});
j=k;
}
}
for(int j=0;j<n;j++){
if(a[j][i]==0){
int k=j;
while(k<n&&a[k][i]==0){
k++;
}
path[j][i].add(new int[]{k-1,i});
path[k-1][i].add(new int[]{j,i});
j=k;
}
}
}
//最短路：
Queue<int[]> q=new LinkedList<>();
dis[0][0]=0;
q.add(new int[]{0,0});
while(!q.isEmpty()){
int b[]=q.poll();
for(int mo[]:move){
int x=b[0]+mo[0],y=b[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<n&&a[x][y]==0&&dis[x][y]==-1){
dis[x][y]=1+dis[b[0]][b[1]];
q.add(new int[]{x,y});
}
}
for(int c[]:path[b[0]][b[1]]){
if(dis[c[0]][c[1]]==-1){
dis[c[0]][c[1]]=1+dis[b[0]][b[1]];
q.add(c);
}
}
}
System.out.println(dis[n-1][n-1]);
}
}
按照序列最后一个数字数组中的那一个进行动态规划，并且需要分别记录每种末尾个位数数的序列数量，以及每种末尾个位数的序列种总共的“6”的数量，时间复杂度O(nC)，其中n==10
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(),count1[]=new int[10],count2[]=new int[10],ans=0;
count2[1]=1;
//c1表示的是所有目前所有末尾的序列中6的总数，c2表示的是当前各种末尾序列的数量
for(int i=0;i<n;i++){
int a=sc.nextInt()%10,count3[]=new int[10],count4[]=new int[10];
for(int j=0;j<10;j++){
int r=a*j%10;
count3[r]=(count3[r]+count1[j])%mod;
if(r==6){
count3[6]=(count3[6]+count2[j])%mod;
}
count4[r]=(count4[r]+count2[j])%mod;
}
for(int j=0;j<10;j++){
count1[j]=(count1[j]+count3[j])%mod;
count2[j]=(count2[j]+count4[j])%mod;
}
}
for(int i=0;i<10;i++){
ans=(ans+count1[i])%mod;
}
System.out.println(ans);
}
}
根据向量求进入和出来的时间，需要舍弃无法进入的，以及进入时间是负数的那些人，排序后区间合并即可，时间复杂度O(nlogn)（此处假定数学函数的时间复杂度都是O(1)，但实际上一定不是，从运行时间来看，常数很大）
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int x0=sc.nextInt(),y0=sc.nextInt(),r=sc.nextInt(),n=sc.nextInt(),x=sc.nextInt();
double pre=0,ans=0;
List<double[]> list=new ArrayList<>();
for(int i=0;i<n;i++){
double us=sc.nextDouble(),vs=sc.nextDouble(),ue=sc.nextDouble(),ve=sc.nextDouble(),s=sc.nextDouble(),arr[]=find(us,vs,ue,ve,s,x0,y0,r);
if(arr!=null&&arr[0]>0){
arr[1]+=x;
list.add(arr);
}
}
Collections.sort(list,(a,b)->Double.compare(a[0],b[0]));
for(double a[]:list){
if(a[1]<=pre){
continue;
}
if(a[0]>=pre){
pre=a[1];
ans+=a[1]-a[0];
}
else{
ans+=a[1]-pre;
pre=a[1];
}
}
System.out.println(ans);
}
static double[] find(double us,double vs,double ue,double ve,double s,double x0,double y0,double r){
double t=Math.sqrt(Math.pow(us-ue,2)+Math.pow(ve-vs,2))/s,v1=(ue-us)/t,v2=(ve-vs)/t;
return solEquation(Math.pow(v1,2)+Math.pow(v2,2),(v1*(us-x0)+v2*(vs-y0))*2,Math.pow(us-x0,2)+Math.pow(vs-y0,2)-Math.pow(r,2));
}
static double[] solEquation(double a,double b,double c){
double delta=b*b-a*c*4;
return delta<0?null:new double[]{(-b-Math.sqrt(delta))/2/a,(-b+Math.sqrt(delta))/2/a};
}
}
京公网安备 11010502036488号