B~F Java题解，代码已去除冗余~~~
球的数量必须至少保证每行每列都有，因此需要特判站不全的情况，否则尽量在遍历行列的情况下挨个放球，时间复杂度O(nm)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
if(k<Math.max(n,m)){
System.out.println("-1");
}
else{
int ans[][]=new int[n][m];
for(int i=n-1,j=m-1;i>=0||j>=0;i--,j--,k--){
ans[Math.max(i,0)][Math.max(j,0)]++;
}
ans[0][0]+=k;
StringBuilder sb=new StringBuilder();
for(int a[]:ans){
for(int b:a){
sb.append(b+" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
}
只需要每一步过后的数字尽可能小，那么在数字小于3的时候只有减1才能最小，否则开方最小，时间复杂度O(T*min(logn,m))
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();
for(;m!=0;m--){
if(n<=2){
n-=m;
break;
}
n=(int)Math.sqrt(n-0.5)+1;
}
System.out.println(n);
}
}
}
考虑特殊情况：只有一种球时无法取胜，答案为-1；每种球只有一个的时候可以随便拿都能取胜，答案为0；次多的球有一个的时候，最坏的情况为预测了最多个球减一个，其中都是最大频率的球，这时只需要在剩下的球随便选即可，因此答案是最大频数减一；否则需要按照最坏情况，预测的球全部颜色一样，答案是最大频率，时间复杂度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(),a[]=new int[n];
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
}
Arrays.sort(a);
System.out.println(n==1?-1:a[n-2]==1?a[n-1]-1:a[n-1]);
}
}
}
首先数组内数字不吭重复，其次需要找到一个单调的区间，再去掉这个区间后的，剩下的数字的值必须全部分布在区间的两侧，正反遍历一遍即可，可用有序集合实现，时间复杂度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(),a[]=new int[n];
TreeSet<Integer> set=new TreeSet<>();
set.add(0);
set.add((int)2e9);
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
set.add(a[j]);
}
System.out.println(set.size()==n+2&&(check(a,m,0,1,set)||check(a,m,a.length-1,-1,set))?"YES":"NO");
}
}
static boolean check(int a[],int m,int start,int inc,TreeSet<Integer> set){
for(int i=start,j=start+inc;i>=0&&i<a.length;i=j,j+=inc){
while(j>=0&&j<a.length&&a[j]>a[j-inc]){
j+=inc;
}
if(Math.abs(i-j)>=m){
for(int k=i;k!=i+m*inc;k+=inc){
set.remove(a[k]);
}
if(set.lower(a[i+(m-1)*inc])<a[i]&&set.higher(a[i])>a[i+(m-1)*inc]){
return true;
}
for(int k=i+m*inc;k!=j;k+=inc){
set.remove(a[k]);
set.add(a[k-m*inc]);
if(set.lower(a[k])<a[k-(m-1)*inc]&&set.higher(a[k-(m-1)*inc])>a[k]){
return true;
}
}
for(int k=i;k!=j;k+=inc){
set.add(a[k]);
}
}
}
return false;
}
}
考虑正难则反：不好的路径是什么样的？不好的路径要么权值全部小于b，要么权值全部大于啊，要么两个都是，因此就是总路径数减去符合上边的所有路径，可深搜，依次统计以每一个节点为路径最高点的时，且节点数值在某个范围内的路径数量，时间复杂度O(n)，，，本题略微卡常，需要在时间上优化读写以防TLE，同时实现过程中减少多开数组以防MLE，另外由于统计数据过程的相似性，可整合代码，一次深搜完成
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));
StringTokenizer st=new StringTokenizer(bf.readLine());
int n=Integer.parseInt(st.nextToken()),a=Integer.parseInt(st.nextToken()),b=Integer.parseInt(st.nextToken()),w[]=new int[n+5];
List<Integer> path[]=new List[n+5];
st=new StringTokenizer(bf.readLine());
for(int i=1;i<=n;i++){
w[i]=Integer.parseInt(st.nextToken());
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
st=new StringTokenizer(bf.readLine());
int u=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken());
path[u].add(v);
path[v].add(u);
}
bw.write(((long)n*(n-1)+find(1,0,new int[][]{{0,b-1,-1},{a+1,(int)2e9,-1},{a+1,b-1,1}},w,path)[3])/2+"\n");
bw.flush();
}
static long[] find(int k,int pre,int task[][],int w[],List<Integer> path[]){
long ans[]=new long[4];
for(int a:path[k]){
if(a!=pre){
long cur[]=find(a,k,task,w,path);
ans[3]+=cur[3];
for(int i=0;i<3;i++){
if(w[k]>=task[i][0]&&w[k]<=task[i][1]){
ans[3]+=task[i][2]*(ans[i]*cur[i]*2+cur[i]*2);
ans[i]+=cur[i];
}
}
}
}
for(int i=0;i<3;i++){
if(w[k]>=task[i][0]&&w[k]<=task[i][1]){
ans[i]++;
}
else{
ans[i]=0;
}
}
return ans;
}
}
京公网安备 11010502036488号