题解 | 牛客周赛 Round 38 CDEFG
小红的正整数自增
https://ac.nowcoder.com/acm/contest/78292/A
思路：尽量用尽可能长的相同的字母连续段构造重复回文，剩下的空间用a-z循环填充
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt();
for(int i=0,count=0,p=0;i<n;i++){
if(k>0){
if(k>=count){
System.out.print((char)(p+'a'));
k-=count;
count++;
}
else{
p=(p+1)%26;
System.out.print((char)(p+'a'));
count=1;
}
}
else{
p=(p+1)%26;
System.out.print((char)(p+'a'));
}
}
}
}
思路：假如相邻的之差最大值小于k，那么只需要在某一个空隙中加一个比较小的数字大k的数字，答案是1次；；否则在每个相邻差大于等于k的空隙尝试添加k间隔的数字，从而把最大差控制在k
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt(),a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
long ans=0;
boolean maxOverK=false;
for(int i=1;i<n;i++){
int d=Math.abs(a[i]-a[i-1]);
if(d>=k){
maxOverK=true;
ans+=(d-1)/k;
}
}
System.out.println(maxOverK?ans:ans+1);
}
}
思路：首先特判公差为1，也就是相同数字的最大数量；再考虑公差大于1的情况，此时序列中的数字只需判断有或者无，因为每个数字都不一样，配合剪枝：当max/a对公比q取对数的值小于当前答案时即可截断
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),count[]=new int[200005],ans=0;
for(int i=0;i<n;i++){
int a=sc.nextInt();
count[a]++;
ans=Math.max(ans,count[a]);
}
Set<Long> set=new HashSet<>();
for(int i=1;i<=200000;i++){
if(count[i]>0){
for(int j=2;j*i<=200000;j++){
if(ans>Math.log(400000.0/i)/Math.log(j)){
break;
}
int len=1;
long cur=j*i;
while(cur<=200000){
long p=op(cur,j);
if(!set.add(p)){
break;
}
len=count[(int)cur]>0?len+1:0;
ans=Math.max(ans,len);
cur*=j;
}
}
}
}
System.out.println(ans);
}
static long op(long a,long b){
//映射以a为结尾，公比为b的等比数列的长度
return a*(long)1e9+b;
}
}
思路：预处理对确定的左端点，寻找存在回文的最早右端点，有回文就表示，存在某种字符，在该区间内首次出现和末次出现的位置相差大于1，，用TreeSet有序维护，以上过程用双指针维护，之后只需离线查询
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
Map<Integer,TreeSet<Integer>> map=new HashMap<>();
int n=sc.nextInt(),q=sc.nextInt(),a[]=new int[n+5],ans[]=new int[n+5];
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
}
for(int i=1,j=1,count=0;i<=n;i++){
while(j<=n&&count==0){
map.putIfAbsent(a[j],new TreeSet<>());
TreeSet<Integer> set=map.get(a[j]);
boolean b=check(set);
set.add(j);
if(!b&&check(set)){
count++;
}
j++;
}
ans[i]=count>0?j-1:j;
TreeSet<Integer> set=map.get(a[i]);
boolean b=check(set);
set.remove(i);
if(b&&!check(set)){
count--;
}
}
for(int i=0;i<q;i++){
int l=sc.nextInt(),r=sc.nextInt();
System.out.println(r>=ans[l]?"YES":"NO");
}
}
static boolean check(TreeSet<Integer> set){
return !set.isEmpty()&&set.last()-set.first()>1;
}
}
思路：构造前缀和和后缀的树状数组，双指针删除或者添加数字，找到对于每一个后缀的起点，满足删除的最大区间
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],pre[]=new int[1000005],suf[]=new int[1000005];
long k=sc.nextLong(),ans=1,count=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
count+=i-get(suf,a[i]);
update(suf,a[i],1);
}
if(count<k){
System.out.println("0");
return;
}
for(int i=0,j=0;i<n;i++){
update(suf,a[i],-1);
count-=get(suf,a[i]-1)+j-get(pre,a[i]);
while(count<k){
update(pre,a[j],1);
count+=j+1-get(pre,a[j])+get(suf,a[j]-1);
j++;
}
ans+=i-j+1;
}
System.out.println(ans);
}
static void update(int arr[],int idx,int inc){
for(int i=idx;i<=1000000;i+=i&-i){
arr[i]+=inc;
}
}
static int get(int arr[],int idx){
int ans=0;
for(int i=idx;i!=0;i-=i&-i){
ans+=arr[i];
}
return ans;
}
}
美团公司氛围 1827人发布