Java题解，代码已去除冗余~~~
略，时间复杂度O(1)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
System.out.println(Math.min(sc.nextInt()*sc.nextInt(),sc.nextInt()));
}
}
首先跟9个9不互质的数字不能小于n的三分之一，其次只需要把这样的数字贪心地各两个位置放置即可，时间复杂度O(nlogC),C==1e9
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),ans[]=new int[n];
Set<Integer> set=new HashSet<>();
Queue<Integer> q=new LinkedList<>();
for(int i=1;i<=n;i++){
if(gcd(999999999,i)!=1){
q.add(i);
set.add(i);
}
}
if(set.size()*3<n){
System.out.println("Baka!");
}
else{
for(int i=1;i<=n;i++){
if(set.add(i)){
q.add(i);
}
}
for(int i=1;i<n;i+=3){
ans[i]=q.poll();
}
for(int i=n-1;i>=0;i--){
System.out.println((ans[i]==0?q.poll():ans[i])+" ");
}
}
}
static int gcd(int a,int b){
return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
}
}
记录每个字符后边最近的非本身字符的是什么，如果比自己大，则优先复制一次，否则不复制，时间复杂度O(nC),C==26
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n],last[]=new int[30],next[]=new int[n+5];
//last表示的是每一种字母最近出现的位置，next表示的的最近的不同字母在哪个位置
long m=sc.nextLong();
String s=sc.next();
Arrays.fill(last,n+5);
Arrays.fill(next,n+5);
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
for(int i=n-1;i>=0;i--){
int b=s.charAt(i)-'a';
for(int j=0;j<26;j++){
if(j!=b){
next[i]=Math.min(next[i],last[j]);
}
}
last[b]=i;
}
StringBuilder ans=new StringBuilder();
for(int i=0;i<n;i++){
ans.append(s.charAt(i));
if(m>=a[i]&&next[i]<n&&s.charAt(next[i])>s.charAt(i)){
ans.append(s.charAt(i));
m-=a[i];
}
}
System.out.println(ans);
}
}
如果数组本身之和不小于y，很明显答案为0，否则钦定x的最高置位，选择所有这一位为0的数字选择，再谈心地往低位尝试填充，最后再次贪心从高到低尝试撤销置位，时间复杂度O(TnC^2),C==60
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int n=sc.nextInt(),a[]=new int[n];
long y=sc.nextLong(),arrSum=0;
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
arrSum+=a[j];
}
if(arrSum>=y){
System.out.println(0);
}
else{
for(int j=0;j<=60;j++){
//钦定j为最高位，先验证是否有必要
long sum=0,ans=1L<<j,num=0,count[]=new long[j+5];
for(long b:a){
if((b>>j&1)==0){
//此时一定要选b，因为选择了会使得答案对出1<<j，比低置为的数加起来要大
num++;
//此时sum“临时”增加的值应为b的j位之前数位，以及j位
sum+=(b>>j<<j)+(1L<<j);
for(int k=0;k<j;k++){
count[k]+=b>>k&1;
}
}
else{
sum+=b;
}
}
//当这一位取1的时候贡献大于0（也就是0的置位大于一半数量）的时候，取1
for(int k=j-1;k>=0;k--){
if(count[k]*2<num){
ans|=1L<<k;
sum+=(num-count[k])*(1L<<k);
}
else{
sum+=count[k]*(1L<<k);
}
}
if(sum>=y){
for(int k=j-1;k>=0;k--){
if((ans>>k&1)==1){
if(sum+(1L<<k)*(count[k]*2-num)>=y){
sum+=(1L<<k)*(count[k]*2-num);
ans^=1L<<k;
}
}
}
System.out.println(ans);
break;
}
}
}
}
}
}
答案即为数组差分中的正数之和，每次操作即为对区间内数字加1或者减1，采用分块儿算法，记录每个块儿内可能对答案造成影响的0和1的数目，由于map全纪录会造成常数较大因此此处采用偏离量和数组记录部分数量，阈值采用50，时间复杂度O(能过)
import java.util.*;
public class Main{
static int threshold=50;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),q=sc.nextInt(),size=(int)Math.sqrt(n),inc[]=new int[n/size+5],pos[]=new int[n/size+5],nonNeg[]=new int[n/size+5];
//inc表示的块儿内的数字偏移量，count表示的是块可能给答案造成贡献的数字的计数
long a[]=new long[n],ans=0,count[][]=new long[n/size+5][threshold*2+5];
for(int i=0;i<n;i++){
a[i]=sc.nextLong();
}
for(int i=n-1;i>=0;i--){
a[i]-=i==0?0:a[i-1];
if(Math.abs(a[i])<=threshold){
count[i/size][(int)a[i]+threshold]++;
}
if(a[i]>0){
pos[i/size]++;
ans+=a[i];
}
if(a[i]>=0){
nonNeg[i/size]++;
}
}
System.out.println(ans);
for(int i=0;i<q;i++){
int x=sc.nextInt(),p=sc.nextInt()-1;
ans+=incOp(a,size,inc,pos,nonNeg,count,p+1,Math.min(p+x,n-1))-decOp(a,size,inc,pos,nonNeg,count,p-x+1,p);
System.out.println(ans);
}
}
static int incOp(long a[],int size,int inc[],int pos[],int nonNeg[],long count[][],int l,int r){
if(l>r){
return 0;
}
//区间+1操作
//list1代表的是不完整的区间下标，list2代表完整区间
List<Integer> list1=new ArrayList<>(),list2=new ArrayList<>();
if(l/size==r/size){
list1.add(l/size);
}
else{
list1.add(l/size);
list1.add(r/size);
for(int i=l/size+1;i<r/size;i++){
list2.add(i);
}
}
int ans=0;
//完整的块儿要直接处理，超过范围的数字要重新加入list1
for(int b:list2){
inc[b]++;
if(inc[b]>threshold){
inc[b]--;
list1.add(b);
}
else{
pos[b]+=count[b][threshold+1-inc[b]];
ans+=pos[b];
nonNeg[b]+=count[b][threshold-inc[b]];
}
}
//不完整的块儿要重新洗牌
for(int b:list1){
Arrays.fill(count[b],0);
nonNeg[b]=pos[b]=0;
for(int i=size*b;i<size*(b+1)&&i<a.length;i++){
a[i]+=inc[b]+(i>=l&&i<=r?1:0);
if(Math.abs(a[i])<=threshold){
count[b][(int)a[i]+threshold]++;
}
if(a[i]>0){
pos[b]++;
//加1后为正数，说明对答案有贡献
if(i>=l&&i<=r){
ans++;
}
}
if(a[i]>=0){
nonNeg[b]++;
}
}
inc[b]=0;
}
return ans;
}
static int decOp(long a[],int size,int inc[],int pos[],int nonNeg[],long count[][],int l,int r){
if(l>r){
return 0;
}
//区间-1操作
//list1代表的是不完整的区间下标，list2代表完整区间
List<Integer> list1=new ArrayList<>(),list2=new ArrayList<>();
if(l/size==r/size){
list1.add(l/size);
}
else{
list1.add(l/size);
list1.add(r/size);
for(int i=l/size+1;i<r/size;i++){
list2.add(i);
}
}
int ans=0;
//完整的块儿要直接处理，超过范围的数字要重新加入list1
for(int b:list2){
inc[b]--;
if(inc[b]<-threshold){
inc[b]++;
list1.add(b);
}
else{
pos[b]-=count[b][threshold-inc[b]];
nonNeg[b]-=count[b][threshold-1-inc[b]];
ans+=nonNeg[b];
}
}
//不完整的块儿要重新洗牌
for(int b:list1){
//map[b].clear();
Arrays.fill(count[b],0);
nonNeg[b]=pos[b]=0;
for(int i=size*b;i<size*(b+1)&&i<a.length;i++){
a[i]+=inc[b]-(i>=l&&i<=r?1:0);//此处应为减
if(Math.abs(a[i])<=threshold){
count[b][threshold+(int)a[i]]++;
}
if(a[i]>=0){
nonNeg[b]++;
//减1后为非负数，说明对答案有贡献
if(i>=l&&i<=r){
ans++;
}
}
if(a[i]>0){
pos[b]++;
}
}
inc[b]=0;
}
return ans;
}
}
这里给出应map计数的超时代码：TLE
博弈，待完善，时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int n=sc.nextInt();
boolean hasOne=false;
for(int j=0;j<n;j++){
hasOne|=sc.nextInt()==1;
}
System.out.println(n==1||!hasOne?"Remilia":"Flandre");
}
}
}
京公网安备 11010502036488号