太久没打比赛,手感极差,而且题意问题导致我T3 WA了 。
二分+DP。
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100000;
int f[maxn+5];
class Solution {
public:
int Find(vector<int> &a,int L,int R,int x){
for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
a[mid]<=x?L=mid+1:R=mid-1;
return R;
}
int treePlanning(vector<int> &a, int d) {
int n=a.size();f[0]=1;
for (int i=1;i<n;i++){
int j=Find(a,0,i-1,a[i]-d);
if (j>=0) f[i]=f[j]+1; else f[i]=1;
f[i]=max(f[i],f[i-1]);
}
return n-f[n-1];
}
};
显然答案最多只有 $2$ ,所以只要讨论 $0,1,2$ 三种情况就行了。
答案为 $1$ :
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
class Solution {
public:
int makeEquilateralTriangle(vector<int> &a) {
int n=a.size();sort(a.begin(),a.end());
for (int i=1;i<n-1;i++) if (a[i-1]==a[i] && a[i]==a[i+1]) return 0;
for (int i=1;i<n-1;i++) if (a[i-1]==a[i]) return 1;
for (int i=0;i<n-1;i++)
for (int j=i+1;j<n;j++)
if (a[j]==(a[i]<<1)) return 1;
return 2;
}
};
题面有问题,不是“第一栋比当前位置高的大楼”,而是不低于。
对于每个位置,二分+RMQ找到右边 $k$ 个中第一个不低于当前的大楼,然后DP。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,LOG=17;
int n,RMQ[maxn+5][LOG+1],lg[maxn+5];
LL f[maxn+5];
class Solution {
public:
int Max(int L,int R) {int k=lg[R-L+1];return max(RMQ[L][k],RMQ[R-(1<<k)+1][k]);}
int Find(int l,int r,int x){
int L=1,R=r-l+1;
for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
Max(l,l+mid-1)>=x?R=mid-1:L=mid+1; //改成 >x 就过不了
return l+L-1;
}
long long shuttleInBuildings(vector<int> &a, int k, int x, int y) {
n=a.size();for (int i=1;i<=n;i++) RMQ[i][0]=a[i-1];
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
RMQ[i][j]=max(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
f[1]=0;for (int i=2;i<=n;i++) f[i]=1e18;
for (int i=1;i<n;i++){
f[i+1]=min(f[i+1],f[i]+y);f[i+2]=min(f[i+2],f[i]+y);
int j=Find(i+1,min(i+k,n),a[i-1]);
if (j<=min(i+k,n)) f[j]=min(f[j],f[i]+x);
}
return f[n];
}
};
爆枚子串,每个子串二分+哈希求答案。
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int p[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103};
const int maxn=3000,BA=23333;
ULL pre[maxn+5],suf[maxn+5],pw[maxn+5];
class Solution {
public:
#define PRE(L,R) (pre[R]-pre[(L)-1]*pw[(R)-(L)+1])
#define SUF(L,R) (suf[L]-suf[(R)+1]*pw[(R)-(L)+1])
int Count(int l,int r){
int L=1,R=r-l+1;
for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
PRE(l,l+mid-1)==SUF(r-mid+1,r)?L=mid+1:R=mid-1;
return R;
}
long long suffixQuery(string &s) {
int n=s.length();ULL ans=n;
pw[0]=1;for (int i=1;i<=n;i++) pw[i]=pw[i-1]*BA;
for (int i=1;i<=n;i++) pre[i]=pre[i-1]*BA+p[s[i-1]-'a'];
for (int i=n;i>=1;i--) suf[i]=suf[i+1]*BA+p[s[i-1]-'a'];
for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) ans+=Count(i,j);
return ans;
}
};