A:
图片说明
思路:ans=自己能够挨的🔪数/一只怪物能挨的🔪数

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int main(){

    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int h, a, H, A;
        cin>>h>>a>>H>>A;
        int x=H/a+(H%a?1:0);
        int y=x-1;//自己能够挨的🔪数
        int s2=(h-1)/A;//一只怪物能够挨的🔪数
        if(a>=H){
            cout<<-1<<endl;
        }
        else
        cout<<s2/y<<endl;
    }

    return 0;
}

B:
图片说明
思路:如果开始n>m2或者m>n2就一直翻倍。后面就一直吃。一直到一个是另外一个的2倍。再翻倍。就n=m

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int main(){

    int t; scanf("%d", &t);
    for(int i=1; i<=t; i++){
        int n, m; scanf("%d%d", &n, &m);

        int ans=0;
        while(n>m*2){
            m*=2;
            ans++;
        }
        while(m>2*n){
            n*=2;
            ans++;
        }
        while(n!=m){
            if(n==2*m||m==2*n){
                n=max(n, m);
                ans++;
                break;
            }
            n--; m--;
            ans++;
        }
        ans+=n;
        cout<<ans<<endl;
    }

    return 0;
}

C:
图片说明
思路:用并查集处理一下必须染相同颜色的块。然后2^n。或者DP就可以了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int f[20]={0};
int fd(int x){
    if(f[x]==0) return x;
    else return fd(f[x]);
}
int siz[20]={0}, tot=0, s[20]={0};
int v[20]={0};
LL F[20][20][20][20][20]={0};
int main(){

    for(int i=1; i<=4; i++){
        scanf("%d", &s[i]);
    }
    int m; scanf("%d", &m);
    for(int i=1; i<=m; i++){
        int x, y; scanf("%d%d", &x, &y);
        x=fd(x); y=fd(y); if(x!=y) f[x]=y;
    }
    for(int i=1; i<=12; i++){
        siz[fd(i)]++;
    }
    for(int i=1; i<=12; i++){
        if(siz[i]){
            v[++tot]=siz[i];
        }
    }
    F[0][0][0][0][0]=1;
    for(int i=1; i<=tot; i++){
        for(int k1=0; k1<=s[1]; k1++){
            for(int k2=0; k2<=s[2]; k2++){
                for(int k3=0; k3<=s[3]; k3++){
                    for(int k4=0; k4<=s[4]; k4++){
                        if(F[i-1][k1][k2][k3][k4]){
                            F[i][k1+v[i]][k2][k3][k4]+=F[i-1][k1][k2][k3][k4];
                            F[i][k1][k2+v[i]][k3][k4]+=F[i-1][k1][k2][k3][k4];
                            F[i][k1][k2][k3+v[i]][k4]+=F[i-1][k1][k2][k3][k4];
                            F[i][k1][k2][k3][k4+v[i]]+=F[i-1][k1][k2][k3][k4];
                        }
                    }
                }
            }
        }
    }
    printf("%lld\n", F[tot][s[1]][s[2]][s[3]][s[4]]);

    return 0;
}

D:
图片说明
图片说明

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100005;

vector< pair<LL ,LL > > e[maxn], e2[maxn];
LL n, m;
LL dis[maxn], DIS[maxn], vis[maxn];

priority_queue<pair<LL, LL> > q;
void dijkstra(LL s, LL dis[]){

    memset(vis, 0, sizeof(vis));
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty())  {
        int now=q.top().second;
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        int len=e[now].size();

        for(int i=0;i<len;i++){
            LL v=e[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e[now][i].second){
                dis[v]=dis[now]+e[now][i].second;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

void dijkstra2(LL s, LL dis[]){

    memset(vis, 0, sizeof(vis));
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty())  {
        int now=q.top().second;
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        int len=e2[now].size();
        for(int i=0;i<len;i++){
            LL v=e2[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e2[now][i].second){
                dis[v]=dis[now]+e2[now][i].second;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

struct node{
    LL x, y, z;
    node(LL x1, LL y1, LL z1){
        x=x1, y=y1, z=z1;
    }
    node(){

    }

}E[200005];

int main(){

    LL n, m; scanf("%lld%lld", &n, &m);
    for(LL i=0;i<maxn;i++){
        dis[i]=1ll<<60;DIS[i]=1ll<<60;
    }

    for(LL i=1;i<=m;i++){
        LL x, y, z;
        scanf("%lld%lld%lld",&x,&y,&z);
        e[x].push_back(make_pair(y ,z));
        e2[y].push_back(make_pair(x ,z));
        E[i]=node{x, y, z};
    }
    dijkstra(1, dis);
    dijkstra2(n, DIS);

    int q; scanf("%d", &q);
    while(q--){
        int k; scanf("%d", &k);
        if(dis[E[k].y]+DIS[E[k].x]+E[k].z<dis[n]){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }

    return 0;
}

图片说明
思路一:字符串哈希。二分x用哈希在找是否存在k个没有重叠的长度为x的字符串。
对于同一个字符的若干位置[l, r]我们按r排序贪心就可以了。但是我们不知道这个子串具体是哪段。我们用map保存所有的子串的r位置和可以选取的个数就可以了。
思路二:后缀数组得到height[i]>=mid的一个区间。对区间的SA位置进行排序贪心就可以。得到最多的选取的个数就可以了。
复杂度都是O(n * logn * logn)

思路一:
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e6+10;

LL mod[2]= {1610612741, 998244353};
LL base[2] ={131, 233};
LL p[2][maxn];
LL g[2][maxn];
char s[200005];

void getp(){
    p[0][0]=p[1][0]=1;
    for(int i=1; i<maxn; i++){
        p[0][i]=p[0][i-1]*base[0]%mod[0];
        p[1][i]=p[1][i-1]*base[1]%mod[1];
    }
}

pair<LL, LL> Hash(char s[]){
    int len=strlen(s+1);
    g[0][0]=0, g[0][1]=s[1];
    g[1][0]=0, g[1][1]=s[1];
    for(int i=2; i<=len; i++){
        g[0][i]=(g[0][i-1]*base[0]+s[i])%mod[0];
        g[1][i]=(g[1][i-1]*base[1]+s[i])%mod[1];
    }
    return {g[0][len], g[1][len]};
}

pair<LL, LL> getLR(int l, int r){
    LL ans1=((g[0][r]-g[0][l-1]*p[0][r-l+1])%mod[0]+mod[0])%mod[0];
    LL ans2=((g[1][r]-g[1][l-1]*p[1][r-l+1])%mod[1]+mod[1])%mod[1];
    return {ans1, ans2};
}

map<pair<LL, LL>, pair<int,int> > mp;
int slove(int mid, int n, int k){

    int res=0;
    for(int i=mid; i<=n; i++){
        pair<LL, LL> now=getLR(i-mid+1, i);
        if(mp.count(now)){
            if(i>=mp[now].first+mid){
                mp[now]=make_pair(i, mp[now].second+1);
                res=max(res, mp[now].second);
            }
        }
        else{
            mp[now]=make_pair(i, 1);
            res=max(res, 1);
        }
    }
    mp.clear();
    return res>=k;
}

int main(){

    getp();
    int n, k; scanf("%d%d", &n, &k);
    scanf("%s", s+1);
    Hash(s);
    int len=strlen(s+1);
    int l=0, r=len/k, x=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(slove(mid, len, k)){
            l=mid+1; x=mid;
        }
        else{
            r=mid-1;
        }
    }
    cout<<x<<endl;

    return 0;
}
思路二:
//#pragma GCC optimize(3,"Ofast","inline")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

#define Mid ((l+r)/2)
#define pb push_back
#define mp make_pair
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)
#define sq(u) ((u)*(u))
#define Abs(u) ((u)>0?(u):-(u))
#define ze(u) (Abs(u)<eps)
#define eq(u, v) (ze((u)-(v)))
#define Sgn(u) ((u)>eps?1:((u)<-eps?-1:0))
typedef long long LL;
typedef unsigned long long UL;
typedef double DB;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const DB eps = 1e-8;
const DB pi = acos(-1.0);

const int N = (int)2e5;
const int M = (int)12;
const int mxn = N + 5;
const int mxm = M + 5;

//以下为倍增算法求后缀数组
int wa[mxn], wb[mxn], wv[mxn], Ws[mxn];
int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}

/**< 传入参数:str,sa,len+1,ASCII_MAX+1 */
void da(const char r[], int sa[], int n, int m)
{
    int i, j, p, * x = wa, * y = wb, * t;
    for (i = 0; i < m; i++) Ws[i] = 0;
    for (i = 0; i < n; i++) Ws[x[i] = r[i]]++;//以字符的ascii码为下标
    for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--Ws[x[i]]] = i;
    /*cout<<"SA"<<endl;;
    for(int i=0;i<n+1;i++)cout<<sa[i]<<' ';*/
    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
        for (i = 0; i < n; i++) wv[i] = x[y[i]];
        for (i = 0; i < m; i++) Ws[i] = 0;
        for (i = 0; i < n; i++) Ws[wv[i]]++;
        for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = y[i];
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
    return;
}

int sa[mxn], Rank[mxn], height[mxn];
//求height数组
/**< str,sa,len */

void calheight(const char* r, int* sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; i++) Rank[sa[i]] = i;
    for (i = 0; i < n; height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++);
    for (int i = n; i >= 1; --i) ++sa[i], Rank[i] = Rank[i - 1];
}

char str[mxn];
int f[mxn];
vector<int> v;
int slove(int mid, int n, int kk){

    int l=0, r=0, res=0;
    for(int i=1; i<=n; ){
        if(height[i]>=mid){
            l=r=i;
            while(r<=n&&height[r]>=mid){
                r++;
            }
            r--; l--;
            for(int i=l; i<=r; i++){
                v.push_back(sa[i]);
            }
            sort(v.begin(), v.end());
            int now=-1<<30, ans=0;
            for(auto x: v){
                if(x>=now+mid){
                    ans++;
                    now=x;
                }
            }
            res=max(res, ans);
            i=r+1;
            v.clear();
        }
        else{
            i++;
        }
    }
    if(res>=kk){
        return 1;
    }
    else{
        return 0;
    }
}

int main()
{
    //int T; scanf("%d", &T);
    //int n; scanf("%d", &n);

    int n, k;
    scanf("%d %d", &n, &k);
    scanf("%s", str);
    int len = n;
    da(str, sa, len + 1, 130);
    calheight(str, sa, len);

    int l=1, r=(len/k), ans=0;
    while(l<=r){
        int mid=(l+r)/2;

        if(slove(mid, len, k)){
            l=mid+1;
            ans=mid;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans<<endl;


    return 0;
}

/*
7 4
abbabab
*/