A~F Java题解，代码已去除冗余~~~
根据梯形面积计算公式，可知排在中间的木棍会加两次，边缘的加一次，只需要让最短的两个在边缘即可，但是需要特判n为1的情况，时间复杂度O(nlogn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
double sum=0;
int n=sc.nextInt(),a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
sum+=a[i]*2;
}
Arrays.sort(a);
System.out.println(String.format("%.2f",n==1?0:(sum-a[0]-a[1])/2));
}
}
牌是否参与顺子，只跟存在与否有关，因此可对已存在的牌面去重并排序。有贪心可知，要想存在的牌尽可能多的参与到组成顺子，最优的一定是以某个存在的牌为最小值，其中空白用鬼牌填充，因此对每个可能的起始牌二分查找最大的末端，可用双指针，时间复杂度O(nlogn)
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(),a[]=new int[n],idx=0,ans=0;
TreeSet<Integer> set=new TreeSet<>();
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
set.add(a[i]);
}
for(int b:set){
a[idx++]=b;
}
for(int i=0,j=0;i<idx;i++){
while(j<idx&&k>=(a[j]-a[i])-(j-i)){
j++;
}
//j-1是最后一个符合的下标
ans=Math.max(ans,k+j-i);
}
System.out.println(Math.min(ans,m));
}
}
首先n为奇数的时候一定无法平分，偶数的时候，点可分为n/2对儿，每一对儿最多一个点选中，利用组合数以及2的幂次数即可完成计算，为降低复杂度，需要预处理阶乘以及阶乘的逆元，时间复杂度O(1e7+Tlogk)
import java.io.*;
public class Main{
static int mod=(int)1e9+7;
static long fac[]=new long[(int)1e7+10],inv[]=new long[(int)1e7+10];
static{
fac[0]=1;
for(int i=1;i<=1e7;i++){
fac[i]=fac[i-1]*i%mod;
}
inv[(int)1e7]=pow(fac[(int)1e7],mod-2);
for(int i=(int)1e7-1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
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 t=Integer.parseInt(bf.readLine());
for(int i=0;i<t;i++){
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),k=Integer.parseInt(arr[1]);
bw.write(n%2==1?"0\n":(comb(n,k)+mod-comb(n/2,k)*pow(2,k)%mod)%mod+"\n");
}
bw.flush();
}
static long comb(int a,int b){
return a<b?0:fac[a]*inv[b]%mod*inv[a-b]%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;
}
}
本题即为求至少包含平方数的区间个数（的二倍），全部区间数减去不含的区间数即可，那么对于(p^2,(p+1)^2)这个区间内的数字，不含的区间数可以表示为p(2p+1)=2p^2+p，利用自然数的平方前缀和以及自然数前缀和两部分即可计算，，而由于精度问题，开方需要用二分来计算，时间复杂度O(TlogC)，其中C==1e9
import java.io.*;
public class Main{
static int mod=(int)1e9+7;
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 t=Integer.parseInt(bf.readLine());
for(int i=0;i<t;i++){
String arr[]=bf.readLine().split(" ");
bw.write(find(Long.parseLong(arr[0]),Long.parseLong(arr[1]))+"\n");
}
bw.flush();
}
static long find(long a,long b){
long l=sqrt(a-1)+1,r=sqrt(b);
return r>=l?((sum(b-a+1)-(squareSum(r-1)-squareSum(l-1))*2-(sum(r-1)-sum(l-1))-sum(l*l-a)-sum(b-r*r))%mod+mod)*2%mod:0;
}
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;
}
static long sum(long a){
a%=mod;
return a*(a+1)%mod*pow(2,mod-2)%mod;
}
static long squareSum(long a){
//n*(n+1)*(2n+1)/6
return a*(a+1)%mod*(a*2+1)%mod*pow(6,mod-2)%mod;
}
static long sqrt(long a){
long l=0,r=(long)1e9;
while(l<r){
long mid=(l+r)>>1;
if(mid*mid<=a){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(r*r<=a){
l=r;
}
break;
}
}
return l;
}
}
部分思路参考，对于每一个元素，他是否可以被更新，取决于它附近的元素是否可以全部可以被更新（也就是有无可能变得不小于它），因此一旦某个元确定不会再次改变，那么其周围的所有元素也就确定不会再次改变，那么在初始时吗，外圈元素已经无法改变，何不从内到外类似BFS式的更新为该位置最终值？而小的元素周围的更容易优先确定，因此可用优先队列进行优化，时间复杂度O(nmlog(nm))
import java.util.*;
public class Main{
static int move[][]={{0,1},{1,0},{-1,0},{0,-1}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),a[][]=new int[n][m];
Queue<int[]> q=new PriorityQueue<>((p1,p2)->Integer.compare(p1[2],p2[2]));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=sc.nextInt();
}
}
boolean has[][]=new boolean[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(Math.min(Math.min(i,n-1-i),Math.min(j,m-j-1))==0){
q.add(new int[]{i,j,a[i][j]});
has[i][j]=true;
}
}
}
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-1&&y>0&&y<m-1&&!has[x][y]){
a[x][y]=Math.max(a[x][y],b[2]+1);
q.add(new int[]{x,y,a[x][y]});
has[x][y]=true;
}
}
}
long ans1=0,ans2=0;
for(int b[]:a){
for(int c:b){
ans1+=c;
ans2^=c;
}
}
System.out.println(ans1+" "+ans2);
}
}
预处理出最小值直角边不大于2e5，且斜边不大于3e5的所有勾股数，依次比对，，而关键在于用于预处理的过程，考虑平方差公式拼凑出另外两数，暴力枚举每一个i^2的约数不可取，因为复杂度会高达4e10，但是这样的数字的约数的个数却是很小，因此可以预先保存2e5内每个数字的质因数，再DFS暴力组合为i^2的约数，预处理的复杂度为O(C(p+logC))，其中C==2e5为枚举上限，而P为i^2的约数的个数，在所给范围内的max(P)不会超过3^7<2200，（参考2x3x5x7x11x13x17==485100），，上述预处理再Java1.8下需要BFS完成，DFS会TLE，，预处理后的勾股对儿数量为535509
import java.util.*;
public class Main{
static List<long[]> list=new ArrayList<>();
static List<Integer> div[]=new List[(int)2e5+10];
static{
for(int i=1;i<=2e5;i++){
div[i]=new ArrayList<>();
}
for(int i=2;i<=2e5;i++){
if(div[i].size()==0){
for(int j=i;j<=2e5;j+=i){
div[j].add(i);
}
}
}
//枚举一条直角边不大于2e5的全部勾股数
for(int i=1;i<=2e5;i++){
Queue<long[]> q=new LinkedList<>();
q.add(new long[]{1,0});
while(!q.isEmpty()){
long a[]=q.poll();
if((long)i*i%a[0]!=0){
continue;
}
if(a[1]==div[i].size()){
if(a[0]%2==(long)i*i/a[0]%2&&((long)i*i/a[0]-a[0])/2>=i&&((long)i*i/a[0]+a[0])/2<=3e5){
list.add(new long[]{i,((long)i*i/a[0]-a[0])/2,((long)i*i/a[0]+a[0])/2});
}
}
else{
q.add(new long[]{a[0],a[1]+1});
q.add(new long[]{a[0]*div[i].get((int)a[1]),a[1]});
}
}
}
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int a[]=new int[3];
long ans=(int)1e9;
for(int j=0;j<3;j++){
a[j]=sc.nextInt();
}
Arrays.sort(a);
for(long b[]:list){
long sum=0;
for(int j=0;j<3;j++){
sum+=Math.abs(b[j]-a[j]);
}
ans=Math.min(ans,sum);
}
System.out.println(ans);
}
}
}
京公网安备 11010502036488号