牛客小白月赛23

牛客小白月赛23

A.膜法记录

二进制枚举行的状态，可以只枚举二进制1个数为a的状态。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        int n,m,a,b;
        scanf("%d%d%d%d",&n,&m,&a,&b);
        string s[n];
        for(int i=0;i<n;i++)cin>>s[i];
        vector<int>v;
        for(int i=0;i<1<<n;i++){
            int x=__builtin_popcount(i);
            if(x==a)v.push_back(i);
        }
        function<bool(int x)>fun=[&](int x){
            vector<string>p;
            for(int i=0;i<n;i++){
                if(!(x>>i&1))p.push_back(s[i]);
            }
            int sz=p.size();
            int ans=0;
            for(int j=0;j<m;j++){
                bool l=0;
                for(int i=0;i<sz&&!l;i++){
                    l|=p[i][j]=='*';
                }
                ans+=l;
            }
            return ans<=b;
        };
        bool f=0;
        for(int &x:v){
            if(fun(x)){
                f=1;
                puts("yes");break;
            }
        }
        if(!f)puts("no");
    }
}

B.阶乘

二分判断。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        int p;scanf("%d",&p);
        if(p==1)
        {
            puts("1");continue;
        }
        vector<pair<int,int> >v;
        for(int i=2;i*i<=p;i++){
            if(p%i==0){
                int cnt=0;
                while(p%i==0)p/=i,cnt++;
                v.push_back({i,cnt});
            }
        }
        if(p>1)v.push_back({p,1});
        if(v.size()==1&&v[0].second==1){
            printf("%d\n",p);continue;
        }
        int sz=v.size();
        function<bool(int mid)>ck=[&](int mid){
           for(int i=0;i<sz;i++){
               int ans=mid,cnt=0;
               int x=v[i].first;
               while(ans)cnt+=ans/=x;
               if(cnt>=v[i].second)continue;
               return 0;
           }
            return 1;
        };
        int l=v[sz-1].first,r=1e9+7;
        int ans=l;
        while(l<=r){
            int mid=l+r>>1;
            if(ck(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
}

C.完全图

二分长度即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;cin>>t;
    while(t--){
        ll x,y;scanf("%lld%lld",&x,&y);
        __int128 n=x,m=y;
        if((m>=n*(n-1)/2)){
            printf("%lld\n",x);
            continue;
        }
        __int128 l=1,k=1,r=n;
        while(r>=l){
            __int128 mid=l+r>>1;
            __int128 x=mid*(mid+1)/2;
            if(n*mid-x<=m)k=mid,l=mid+1;
            else r=mid-1;
        }
        while(n*k-k*(k+1)/2<=m)k++;
        if(n*k-k*(k+1)/2>m)k--;
        printf("%lld\n",(ll)k+1);
    }
}

E.A+B问题

puts("4294967296");

G.树上求和

一棵树上经过一条边的路径数等于两端点节点数之积。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
vector<int>g[N];
vector<long long >v;
int dp[N];
void dfs(int u,int fa){
    dp[u]=1;
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];
    }
}
void Dfs(int u,int fa){
    if(fa){
        v.push_back(1LL*dp[u]*(dp[fa]-dp[u]));
        dp[u]=dp[fa];
    }
    for(int v:g[u]){
        if(v==fa)continue;
        Dfs(v,u);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);Dfs(1,0);
    sort(v.begin(),v.end());
    long long ans=0;
    for(int i=0,k=n-1;i<n-1;i++,k--){
        ans+=v[i]*k;
    }
    printf("%lld\n",ans);
}

H.奇怪的背包问题增加了

从大到小合并，可以利用栈来实现。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int k[N],a[N],s[N],tp=0;
int f[32];
int main(){
    int t;cin>>t;
    while(t--){
        scanf("%d",&n);
        memset(f,0,sizeof f);tp=0;
        for(int i=0;i++<n;scanf("%d",&k[i]),a[i]=k[i]);
        sort(a+1,a+1+n,greater<int>());
        for(int i=1;i<=n;i++){
            int v=a[i];
            while(tp&&s[tp]==v)v++,tp--;
            s[++tp]=v;f[a[i]]++;
            if(s[1]==30)break;
        }
        if(s[1]!=30)printf("impossible\n");
        else{
            for(int i=1;i<=n;i++){
                if(f[k[i]])f[k[i]]--,putchar('1');
                else putchar('0');
            }
            putchar(10);
        }
    }
}

I.寻找子串

尺取。

#include<bits/stdc++.h>
using namespace std;
string KP(string s) {
        int st = 0;
        int len = s.size();
        for(int i = 1; i < len; i++) {
            int sz = 0;
            while(i+sz < len && s[st + sz] == s[i + sz]) {
                sz++;
            }
            if(s[i + sz] > s[st + sz]) st = i;
            if(i+sz == len) break;
        }
    return s.substr(st);
}
int main(){
    string a;
    cin>>a;
    cout<<KP(a)<<endl;
}

J.最大的差

MAX-MIN