题解 | 牛客小白月赛92 BCDEFG
获得木头
https://ac.nowcoder.com/acm/contest/81126/A
思路：第二四排的宝石需要1个体力来得到，而第一五排的宝石需要多少体力得到，取决于它靠近矿道的那一个位置是否有宝石，贪心地先取得所有1体力的宝石，再去取2体力的，事时间复杂度O(n+h)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),h=sc.nextInt(),ans=0,count[]=new int[3];
String s[]=new String[5];
for(int i=0;i<5;i++){
s[i]=sc.next();
}
for(int i=0;i<n;i++){
if(s[1].charAt(i)=='*'){
count[1]++;
if(s[0].charAt(i)=='*'){
count[1]++;
}
}
else if(s[0].charAt(i)=='*'){
count[2]++;
}
if(s[3].charAt(i)=='*'){
count[1]++;
if(s[4].charAt(i)=='*'){
count[1]++;
}
}
else if(s[4].charAt(i)=='*'){
count[2]++;
}
}
for(int i=1;i<=2;i++){
if(h>=count[i]*i){
ans+=count[i];
h-=count[i]*i;
}
else{
ans+=h/i;
break;
}
}
System.out.println(ans);
}
}
经过估计，每个种子最多可以播种20轮，因此，循环到不能播种（或者说直到等级小于等于x）为止，记录每一轮播种得到的x等级种子数量的总和，时间复杂度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(),a[]=new int[n];
long count[]=new long[55],ans=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
int x=sc.nextInt();
for(int b:a){
find(b,x,count);
}
for(long b:count){
ans=Math.max(ans,b);
}
System.out.println(ans);
}
static void find(int a,int x,long count[]){
long num=1;
for(int i=1;;i++,num<<=1,a=(a+2)/3){
if(a==x){
count[i]+=num;
break;
}
if(a<x){
break;
}
}
}
}
整理成一个关于位置x的一元二次函数，计算系数后，从0到n-1逐一尝试，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
//f(x)=a*x^2+b*x+c
long a=0,b=0,c=0,ans=(long)9e18;
int n=sc.nextInt();
for(int i=0;i<n;i++){
int ai=sc.nextInt();
a+=ai;
b-=ai*2*i;
c+=(long)ai*i*i;
}
for(int i=0;i<n;i++){
ans=Math.min(ans,a*i*i+b*i+c);
}
System.out.println(ans);
}
}
分组背包问题，难点在于只能用一次魔法，因此分别记录使用了魔法的最短时间以及未使用魔法的最短时间，注意更新顺序，时间复杂度O(nm)
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();
long count0[]=new long[m+1],count1[]=new long[m+1];
Arrays.fill(count0,(long)1e18);
Arrays.fill(count1,(long)1e18);
count0[0]=0;
for(int i=0;i<n;i++){
int x=sc.nextInt(),y=sc.nextInt();
for(int j=m;j>=0;j--){
//使用了魔法：
count1[j]=Math.min(count1[j],count1[Math.max(0,j-x)]+y);
count1[j]=Math.min(count1[j],count0[Math.max(0,j-x*2)]+y/2);
//没使用魔法：
count0[j]=Math.min(count0[j],count0[Math.max(0,j-x)]+y);
}
}
System.out.println(Math.min(count0[m],count1[m]));
}
}
对于每只羊，其贡献发生变化只有可能在边界上的时候，因此利用差分思想记录每个边界的增量即可得到总的贡献之和，时间复杂度O(mnlog(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(),v[]=new int[n];
long w[]=new long[n+1],pre=0;
for(int i=1;i<=n;i++){
w[i]=w[i-1]+sc.nextInt();
}
for(int i=0;i<n;i++){
v[i]=sc.nextInt();
}
TreeMap<Long,Long> map=new TreeMap<>();
for(int i=0;i<m;i++){
int x=sc.nextInt();
for(int j=1;j<=n;j++){
modify(map,w[j-1]-x,v[j-1]);
modify(map,w[j]-x,-v[j-1]);
}
}
Set<Long> set=new HashSet<>();
set.add(0L);
for(long a:map.values()){
pre+=a;
set.add(pre);
}
System.out.println(set.size());
}
static void modify(TreeMap<Long,Long> map,long a,long b){
map.put(a,map.getOrDefault(a,0L)+b);
}
}
方法一：折半预处理，固定时间复杂度为O(sqrt(C)*(logC)^2)，其中C==1e10
import java.util.*;
public class Main{
static int mod=998244353;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
long n=sc.nextLong(),k=sc.nextLong(),ans=0;
List<Long> list[]=new List[12];
for(int i=0;i<12;i++){
//m==i的时候，最大的后缀位数可以是i/2
list[i]=new ArrayList<>();
for(int j=(int)Math.pow(10,i>>1)-1;j>=0;j--){
list[i].add(cal(j,i,j));
}
Collections.sort(list[i]);
}
int digitCount=findNumDigits(n);
//先处理位数小于这个数的数字
for(int i=1;i<digitCount;i++){
int num2=i/2,num1=i-i/2;//前后半部分的位数
int low=(int)Math.pow(10,num1-1),high=low*10;
for(int j=low;j<high;j++){
long cur=cal(j,i,j*(long)Math.pow(10,num2));
ans+=find(list[i],k-cur)-find(list[i],-k-1-cur);
}
}
//处理位数相同，且前缀小于的数字
int num2=digitCount/2,num1=digitCount-digitCount/2;//前后半部分的位数
int low=(int)Math.pow(10,num1-1),high=(int)(n/(int)Math.pow(10,num2));
for(int i=high-1;i>=low;i--){
long cur=cal(i,digitCount,i*(long)Math.pow(10,num2));
ans+=find(list[digitCount],k-cur)-find(list[digitCount],-k-1-cur);
}
//处理位数相同，且前缀相同的数字，一个个尝试
long cur=cal(high,digitCount,high*(long)Math.pow(10,num2)),suf=n%(int)Math.pow(10,num2);
for(int i=0;i<=suf;i++){
if(Math.abs(cur+cal(i,digitCount,i))<=k){
ans++;
}
}
System.out.println(ans%mod*pow(n%mod,mod-2)%mod);
}
static int find(List<Long> list,long max){
if(list.get(0)>max){
return 0;
}
int l=0,r=list.size()-1;
while(l<r){
int mid=(l+r)>>1;
if(list.get(mid)<=max){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(list.get(r)<=max){
l=r;
}
break;
}
}
return l+1;
}
static int findNumDigits(long a){
//计算一个数在10进制下的位数
int ans=0;
while(a!=0){
ans++;
a/=10;
}
return ans;
}
static long cal(long a,int b,long c){
//计算数字a在m==b的时候的f(a)
long ans=-c;
for(;a!=0;a/=10){
ans+=(long)Math.pow(a%10,b);
}
return ans;
}
static long pow(long a,int b){
//快速幂
long ans=1;
for(;b!=0;b>>=1,a=a*a%mod){
if(b%2==1){
ans=ans*a%mod;
}
}
return ans;
}
}
方法二：听说还有其他奇怪的算法，挖个坑吧先。。。。
查看3道真题和解析
