题解 | 牛客周赛 Round 39 BCDEFG
小红不想做炸鸡块粉丝粉丝题
https://ac.nowcoder.com/acm/contest/78904/A
思路：最后剩下的小球个数一定是sum%k个，那么只需从最多的小球开始取，直到取够这么多为止，时间复杂度O(nlogn)
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(),sum=0,a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
sum=(sum+a[i])%k;
}
if(sum==0){
System.out.println("0");
return;
}
//取完最后一次，剩下sum个
Arrays.sort(a);
for(int i=n-1;i>=0;i--){
if(sum-a[i]<=0){
System.out.println(n-i);
return;
}
sum-=a[i];
}
}
}
C小红不想做完全背包（easy） and D小红不想做完全背包 （hard）
题目要求最少取一个球，取得的球只跟其价值mod p有关，首先特判球中有p倍数的，直接返回1；；其次把取得每种余数的球看做一个状态，每个球可以在两种状态之间连边，之后跑一遍最短路，完全图遍历的时间复杂度最大为O(p^2)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),p=sc.nextInt();
Set<Integer> path[]=new Set[p];
for(int i=0;i<p;i++){
path[i]=new HashSet<>();
}
for(int i=0;i<n;i++){
int a=sc.nextInt()%p;
if(a==0){
System.out.println("1");
return;
}
for(int j=0;j<p;j++){
path[j].add((j+a)%p);
}
}
int dis[]=new int[p],ans=p+5;
Arrays.fill(dis,p+5);
dis[0]=0;
Queue<Integer> q=new PriorityQueue<>();
q.add(0);
while(!q.isEmpty()){
int a=q.poll();
for(int b:path[a]){
if(dis[b]>dis[a]+1){
q.add(b);
dis[b]=dis[a]+1;
}
}
}
for(int i=1;i<p;i++){
ans=Math.min(ans,dis[i]+dis[p-i]);
}
System.out.println(ans);
}
}
思路：枚举长宽即可，可推出高是否存在以及数据范围是否合格，时间复杂度O(mn)
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(),p=sc.nextInt(),x=sc.nextInt(),ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int d=x-i*j;
if(d>0&&d%((i+j)*2)==0&&d/(i+j)/2<=p){
ans++;
}
}
}
System.out.println(ans);
}
}
线段树，节点内分别懒标记对应字符串时时的1的个数，以及两者都为1的个数，修改操作可以看做把一个串的1的个数改为区间长度，共同个数改为另一个串的1的个数，时间复杂度O(n+qlogn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
char a[]=sc.next().toCharArray(),b[]=sc.next().toCharArray();
SegTree st=new SegTree(0,n-1);
build(st,a,b);
int q=sc.nextInt();
for(int i=0;i<q;i++){
String op=sc.next();
int l=sc.nextInt()-1,r=sc.nextInt()-1;
modify(st,l,r,op);
System.out.println(st.count);
}
}
static void clear(SegTree st){
int l=st.l,r=st.r;
if(l<r){
int mid=(l+r)>>1;
if(st.changed1){
st.changed1=false;
st.left.num1=mid-l+1;
st.right.num1=r-mid;
st.left.count=st.left.num2;
st.right.count=st.right.num2;
st.left.changed1=st.right.changed1=true;
}
if(st.changed2){
st.changed2=false;
st.left.num2=mid-l+1;
st.right.num2=r-mid;
st.left.count=st.left.num1;
st.right.count=st.right.num1;
st.left.changed2=st.right.changed2=true;
}
st.count=st.left.count+st.right.count;
st.num1=st.left.num1+st.right.num1;
st.num2=st.left.num2+st.right.num2;
}
}
static void modify(SegTree st,int a,int b,String op){
int l=st.l,r=st.r;
clear(st);
if(l==a&&r==b){
if(op.equals("A")){
st.num1=r-l+1;
st.count=st.num2;
st.changed1=true;
}
else{
st.num2=r-l+1;
st.count=st.num1;
st.changed2=true;
}
}
else{
int mid=(l+r)>>1;
if(b<=mid){
modify(st.left,a,b,op);
}
else if(a>mid){
modify(st.right,a,b,op);
}
else{
modify(st.left,a,mid,op);
modify(st.right,mid+1,b,op);
}
st.count=st.left.count+st.right.count;
st.num1=st.left.num1+st.right.num1;
st.num2=st.left.num2+st.right.num2;
}
}
static void build(SegTree st,char c1[],char c2[]){
int l=st.l,r=st.r;
if(l==r){
st.count=c1[l]==c2[l]&&c1[l]=='1'?1:0;
st.num1=c1[l]-'0';
st.num2=c2[l]-'0';
}
else{
int mid=(l+r)>>1;
st.left=new SegTree(l,mid);
st.right=new SegTree(mid+1,r);
build(st.left,c1,c2);
build(st.right,c1,c2);
st.count=st.left.count+st.right.count;
st.num1=st.left.num1+st.right.num1;
st.num2=st.left.num2+st.right.num2;
}
}
}
class SegTree{
SegTree left,right;
int l,r,count,num1,num2;
//count为同时为1的个数，num12为ab中1的个数
boolean changed1=false,changed2=false;
public SegTree(int l,int r){
this.l=l;
this.r=r;
}
}
用有序集合分别存储下波峰和波谷的坐标。，，好子区间的一定要么是单增，单减、增减、减增、增减增这五种，根据起始坐标在（增区间或者是减区间）的位置分类计数即可，时间复杂度O(nlogn)
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];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
TreeSet<Integer> peak=new TreeSet<>(),val=new TreeSet<>();
for(int i=0;i<n;i++){
if((i==0||a[i]>a[i-1])&&(i==n-1||a[i]>a[i+1])){
peak.add(i);
}
if((i==0||a[i]<a[i-1])&&(i==n-1||a[i]<a[i+1])){
val.add(i);
}
}
long ans=1;
for(int i=0;i<n-1;i++){
if(atDec(i,peak,val)){
//可以是先下降，这一段都是好区间
//后边转折的第一个数字，值要比i处的大才有必要继续找下去
Integer nextVal=val.ceiling(i);
ans+=nextVal-i+1;
if(nextVal<n-1&&a[nextVal+1]>a[i]){
Integer nextPeak=peak.ceiling(nextVal);
ans+=nextPeak-nextVal;
}
}
else{
//先找到第一个peak
Integer nextPeak=peak.ceiling(i);
ans+=nextPeak-i+1;
if(nextPeak<n-1){
//此时下一个山峰并不是最后一个，那么需要找到下一个山谷
Integer nextVal=val.ceiling(nextPeak);
if(a[nextVal]<a[nextPeak-1]){
int l=nextPeak,r=nextVal;
while(l<r){
int mid=(l+r)>>1;
if(a[mid]>a[nextPeak-1]){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(a[r]>a[nextPeak-1]){
l=r;
}
break;
}
}
ans+=l-nextPeak;
}
else{
ans+=nextVal-nextPeak;
if(nextVal<n-1&&a[nextVal+1]>a[nextPeak]){
nextPeak=peak.ceiling(nextVal);
ans+=nextPeak-nextVal;
}
}
}
}
}
System.out.println(ans);
}
static boolean atDec(int idx,TreeSet<Integer> peak,TreeSet<Integer> val){
//判断idx是是否在下降区间
if(peak.contains(idx)){
return true;
}
if(val.contains(idx)){
return false;
}
Integer nextVal=val.ceiling(idx),nextPeak=peak.ceiling(idx);
return nextVal!=null&&(nextPeak==null||nextPeak>nextVal);
}
}
