牛客练习赛61 ABCDE 二分+后缀数组SA

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)

牛客练习赛61 ABCDE 二分+后缀数组SA

全站热榜

创作者周榜