2020牛客暑期多校训练营（第四场）

wenzhuan

发布于 2022-08-15 12:25:28

2970

发布于 2022-08-15 12:25:28

文章被收录于专栏：你会烧尽还是结冰

7.20 节目效果拉满的牛客4

B-Basic Gcd Problem

题意

定义函数 f 在 x>1f_c(x)=\max_{i=1…x-1}c*f_c(gcd(i,x))，在 x=1 时 f_c(x)=1，给定 c 和 x，求 f

思路

即求 c 的 x 因子个数次方

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int p[maxn],vis[maxn],pn;
void init(){
    rep(i,2,maxn){
        if(!vis[i]) p[pn++]=i;
        for(int j=0;j<pn&&i*p[j]<maxn;j++) vis[i*p[j]]=1;
    } mst(vis,0);
}
ll qpow(ll a,ll b){
    ll ans=1; while(b>0){
        if(b&1) ans=ans*a%mod;
        b>>=1; a=a*a%mod;
    } return ans;
}
ll cnt[maxn];
void dfs(int x){
    if(x==1){ cnt[x]=0,vis[x]=1; return;}
    rep(i,0,pn){
        if(p[i]*p[i]>x) break;
        if(x%p[i]==0){
            if(!vis[x/p[i]]) dfs(x/p[i]);
            cnt[x]=cnt[x/p[i]]+1,vis[x]=1;
            return;
        }
    } cnt[x]=1,vis[x]=1;
}
int solve(){
    int n,c; sc(n); sc(c);
    if(n==1) return pf("1\n");
    return pf("%lld\n",qpow(c,cnt[n]));
}
int main(){
    init(); dep(i,1e6,1) if(!vis[i]) dfs(i);
    int _; sc(_); while(_--) solve();
}

C-Count New String

题意

给定一个字符串，求此字符串的前缀最大值的前缀最大值的本质不同子串个数。

思路

参考 出来看神仙.jpg 代码。太牛了！！！永远滴神！！！

《叛逆小转偏偏要乱搞过板子题》

倒着处理。每次和后一位对比，如果比后一位小或者和后一位一样，那后面已经不会有变化了，所以只用加上包含当前位的所有方案数；如果比后一位大，那就需要更新，更新到和此位一样或者更大的位置。t 记录的是这个位数差。每次更新答案就是 1+d 到 t+d 的等差为 1 的数列求和，其中 d=len-i-t+1。

同时每次记录当前状态。其实和 sa 的最后相邻 lcp 去重一个道理。

代码

#include<bits/stdc++.h>
#define pf printf
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
char s[maxn];
vector<vector<int>>vv;
int solve(){
    scs(s+1); int len=strlen(s+1);
    vector<int>tmp(10); s[len+1]='z'+1;
    ll ans(0); dep(i,len,1){
        int val=s[i]-'a',t(0);
        rep(j,0,val) t+=tmp[j]; t++;
        if(s[i]<=s[i+1]){
            ans+=len-i+1;
            tmp[val]++;
            vv.push_back(tmp);
        }
        else if(s[i]>s[i+1]){
            rep(j,0,val) tmp[j]=0;
            rep(j,0,t){
                tmp[val]++;
                vv.push_back(tmp);
            } ans+=1ll*t*(t+(len-i-t+1)*2+1)/2;
        }
        // 如果前一位是大的 说明后面要更新
        // 更新到不用更新的地方的串数量
        // 如果是小的 只用加上包含此位的所有串数量
    } // 去重 相邻的lcp
    sort(vv.begin(),vv.end());
    rep(i,1,vv.size()) rep(j,0,10){
        ans-=min(vv[i-1][j],vv[i][j]);
        if(vv[i-1][j]!=vv[i][j]) break;
    } return pf("%lld\n",ans);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

D-Dividing Strings

题意

给定一个数字串，问怎么划分能使划分中的数字最大最小差值最小。划分的串不能包含前导零。

思路

模拟。每个串先拆为等长的数字串，枚举因数取 min 。再考虑进位情况：如果进位是三位即以上，找 10 开头的子串，到结尾/下一个 9 /下一个 10 为止，取为一个单位长度。如果进位是两位，一个 1 后面跟上一个数，剩下的全取个位数。注意当 1 为末尾的时候要判掉。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
const int maxn = 1e5 + 5;
int n; char s[maxn];
int qaq(){
    int len(0); rep(i,1,n-1) if(s[i]=='1'&&s[i+1]=='0'){
        rep(j,i+2,n+2) if(j==n+1||s[j]=='9'||(s[j]=='1'&&s[j+1]=='0')){
            len=j-i; break;
        } break;
    } if(len<=2||len==n) return 9;
    int mn(0),mx(0),t(0),ff(0);
    rep(i,1,n+1) if(ff){
        if(ff>0) t=t*10+s[i]-'0',ff++;
        else t=t*10-s[i]+'0',ff--;
        if(t>=9) return 9;
        if(abs(ff)==len){
            if(ff<0) mn=max(mn,t);
            else mx=max(mx,t);
            t=0; ff=0;
        }
    } else{
        if(s[i]=='1') ff=1,t=0;
        else if(s[i]=='9') ff=-2,t=1;
        else return 9;
    } if(ff) return 9;
    return mn+mx;
}
int qwq(){
    int mn=1e9,mx(0),t(0);
    rep(i,1,n+1){
        if(t) mx=max(mx,t*10+s[i]-'0'),t=0; 
        else if(s[i]=='1'&&i!=n) t=1;
        else mn=min(mn,(int)s[i]-'0');
    } if(mn==1e9||!mx) return 9;
    return mx-mn;
}
int slove(int x){
    int mn(0),mx(0),t(0),c=1;
    rep(i,x+1,n+1){
        if(i%x==1&&s[i]=='0') return 9;
        t=t*10+s[i]-s[i-c*x];
        if(abs(t)>=9) return 9;
        if(i%x==0){
            if(t<0) mn=max(mn,-t);
            else mx=max(mx,t);
            c++; t=0;
        }
    } return mn+mx;
}
int solve(){
    sc(n); scs(s+1);
    char a='9'+1,b='0'-1;
    rep(i,1,n+1) a=min(a,s[i]),b=max(b,s[i]);
    int mn=b-a; if(s[1]=='0') return pf("%d\n",mn);
    for(int i=2;i*i<=n;++i) if(n%i==0){
        mn=min(mn,slove(i));
        if(i*i!=n) mn=min(mn,slove(n/i));
    } mn=min(mn,qaq()); mn=min(mn,qwq());
    return pf("%d\n",mn);
}
int main(){
    int _; sc(_); while(_--) solve();
}

H-Harder Gcd Problem

题意

将 1-n 不重复地放入两个无交集的集合 A 、B且满足所有 gcd(A[i],B[i])>1

思路

1 到 n 分解质因数。将所有有同一个质因数的放进同一个 vector ，倒着两两匹配。使用过的数打上标记，没使用过的数存进临时使用的 vector 。如果有奇数个，考虑剩一个偶数出来。因为 2 是最小的质数，2 的倍数个数是最多的。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
vector<int>vv[maxn];
void init(int x){
    int x1=x;
    vv[x].push_back(x);
    rep(i,2,x+1){
        if(i*i>x) break;
        if(x%i==0){
            vv[i].push_back(x1);
            while(x%i==0) x/=i;
        }
    } if(x>1&&x!=x1) vv[x].push_back(x1);
}
int vis[maxn];
vector<pii>ans;
void solve(){
    int n; sc(n); rep(i,1,n+1) init(i);
    ans.clear(); dep(i,n,2){
        if(vv[i].size()<=1) continue;
        int cnt(0),tt(0); vector<int>tmp;
        rep(j,0,vv[i].size()){
            int x=vv[i][j];
            if(!vis[x]){
                tmp.push_back(x);
                if(x%2==0) tt=x;
            }
        } int sz=tmp.size();
        if(sz%2&&tt){
            vector<int>::iterator it;
            for(it=tmp.begin();it!=tmp.end();++it){
                if(*it==tt) tmp.erase(it),--it;
            } sz--;
        } if(sz<=1) continue;
        rep(j,0,sz){
            int x=tmp[j],y=tmp[j+1];
            vis[x]=vis[y]=1,j++;
            ans.push_back(pii(x,y));
        }
    } pf("%d\n",ans.size());
    for(pii x:ans) pf("%d %d\n",x.first,x.second);
    rep(i,1,n+1) vis[i]=0,vv[i].clear();
}
int main(){
    int _; sc(_); while(_--) solve();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

海外加速