C~F Java题解,代码已去除冗余~~~
对于一个序列来说,如果最大值确定,那么数列越短mex就不会增大,因此只需检查长度为2的子数组即可,时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t!=0;t--){
int n=sc.nextInt(),pre=0,ans=-1;
for(int i=0;i<n;i++){
int a=sc.nextInt();
ans=Math.max(ans,find(pre,a));
pre=a;
}
System.out.println(ans);
}
}
static int find(int a,int b){
return a>b?find(b,a):a==b?(a==0?-1:a):a==0?(b==1?-1:b-1):b;
}
}
按照顺序从小到大排列并计算前缀和,枚举删除的位置分段计算即可,时间复杂度O(Tnlogn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t!=0;t--){
int n=sc.nextInt();
long a[]=new long[n+1],ans=(long)1e18;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
Arrays.sort(a);
for(int i=1;i<=n;i++){
a[i]+=a[i-1];
}
for(int i=1;i<=n;i++){
ans=Math.min(ans,i*2>=n+1?a[n]-a[i]+a[i-1]-a[n/2-1]-a[n/2]+(n/2L*2-n)*(a[n/2]-a[n/2-1]):a[n]-a[n/2-i+2]*2+a[i]-a[i-1]+((n/2L-i+2)*2-1-n)*(a[n/2-i+2]-a[n/2-i+1]));
}
System.out.println(ans);
}
}
}
其实类似于方差的计算,想要是的目标最小,只需让删除最小的或者最大的即可(不知如何证明),时间复杂度O(Tnlogn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t!=0;t--){
int n=sc.nextInt(),a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
Arrays.sort(a);
System.out.println(Math.min(find(a,0,n-2),find(a,1,n-1)));
}
}
static long find(int a[],int l,int r){
long ans=0;
for(int i=l;i<=r;i++){
ans+=Math.abs(a[i]-a[(l+r)>>1]);
}
return ans;
}
}
根据小学数学知识,一个正整数的数根就是其对9取模的值(特殊的,9的倍数的根为9),因此遍历每个字符,找到以每个字符结尾的字串的根即可,另外要减去连续0形成的额外的9,时间复杂度O(9Tsum(len(x)))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t!=0;t--){
int count[]=new int[9],num=0;
long ans=0;
for(char c:sc.next().toCharArray()){
num=c=='0'?num+1:0;
count[0]++;
int cur[]=new int[9];
for(int i=0;i<9;i++){
cur[(i+c-'0')%9]=count[i];
ans+=(long)cur[(i+c-'0')%9]*((i+c-'0')%9==0?9:(i+c-'0')%9);
}
count=cur;
ans-=num*9L;
}
System.out.println(ans);
}
}
}
重要结论:假如答案确定且数组分成若干段,其中连续的三段一定可以合并成一段,因为三段合并一定是的异或结果是答案的超集,且两段取与操作也一定是答案的超集,那么数组只需分成1或2段,时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t!=0;t--){
int n=sc.nextInt(),a[]=new int[n+1],ans=0;
for(int i=1;i<=n;i++){
a[i]=a[i-1]^sc.nextInt();
}
for(int i=0;i<n;i++){
ans=Math.max(ans,(a[n]^a[i])&a[i]);
}
System.out.println(Math.max(ans,a[n]));
}
}
}