太久没打比赛，手感极差，而且题意问题导致我T3 WA了 。

比赛链接

1.树木规划

二分+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.正三角形拼接

显然答案最多只有 $2$ ，所以只要讨论 $0,1,2$ 三种情况就行了。

• 答案为 $0$ ：同种长度棍子有三根

• 答案为 $1$ ：

  1. 同种长度棍子有两根，并且有比这种长的棍子
  2. 存在 $x,2x$ 两种长度的棍子
• 答案为 $2$ ：其他情况答案都是 $2$

#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;
    }
};

3.大楼间穿梭

题面有问题，不是“第一栋比当前位置高的大楼”，而是不低于。

对于每个位置，二分+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];
    }
};

4.对称前后缀

爆枚子串，每个子串二分+哈希求答案。

#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;
    }
};