2021牛客寒假算法基础集训营4（A B D E F G H J）

比赛链接：这里

OP

个人能力有限，有的题目实在知识点欠缺太多，这里是大佬的题解

A 九峰与签到题

签到题

思路

持续模拟打标记即可，注意题目描述：他认为任意时间内通过率大于等于50%的题为签到题

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int m,n,i,j;
    int ac[25]={0},sb[25]={0};
    bool pro[25];
    char g[10];
    int gq;
    cin>>m>>n;
    for(i=1;i<=n;i++)pro[i]=1;
    while(m--)
    {
        scanf("%d",&gq);
        sb[gq]++;
        cin>>g;
        if(!strcmp(g,"AC"))ac[gq]++;
        if(ac[gq]*1.0/sb[gq]<0.5)pro[gq]=0;
    }
    int f=0;
    for(i=1;i<=n;i++)
    {
        if(pro[i]&&sb[i])
        {
            if(f)printf(" ");
            printf("%d",i),f=1;
        }
    }
    if(!f)printf("-1");
    return 0;
}

B 武辰延的字符串

哈希字符串、二段性二分

思路

这道题首先想到的就是 O(n²) 的二分，显然是要爆的，但是 s_j 是有二段性的，即如果 s_ja 满足条件且 s_j(a+1) 不满足，则所有的 s_jp( p<=a ) 均满足，所有的 s_jq( q>a ) 均不满足。

有了二段性，我们便可以进行二分。

对于二分的 check 过程，我们可以用哈希字符串在 O(1) 的时间复杂度内完成判断，关于哈希字符串，可以参照这里。

代码的细节还蛮多需要注意的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,t;
const int N=1e5+5,P=131;
const ll M=1e9+7;
ll a[N],b[N];
ll qm(ll a,ll b)//快速幂
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans;
}
void makehash(string& str,ll aim[])//构建哈希字符串
{
    int i;
    aim[0]=str[0]-'a';
    //printf("%d ",aim[0]);
    for(i=1;str[i];i++)
    {
        aim[i]=aim[i-1]*P%M+str[i]-'a';
        aim[i]%=M;
    }
}
ll gethash(ll aim[],int l,int r)//摘取子串的哈希字符串
{
    return (aim[r]+M-aim[l-1]*qm(P,r-l+1)%M)%M;
}
int main()
{
    cin>>s;
    cin>>t;
    makehash(s,a);
    makehash(t,b);
    int i,j;
    ll ans=0;
    for(i=0;s[i]==t[i]&&s[i]&&t[i];i++)
    {
        int l=0,r=min(s.length(),t.length()-1-i),mid;
        while(l<r)
        {
            mid=l+r+1>>1;
            if(a[mid-1]==gethash(b,i+1,i+mid))l=mid;
            else r=mid-1;
        }
        ans+=l;
    }
    cout<<ans;
	return 0;
}

D 温澈滢的狗狗

容斥，二分

思路

亲密值是狗狗编号差值，而不是颜色编号差值，在这里耽误了自己不少时间。

首先对于1e10的数据量，模拟是会爆的，而且选择的亲密值上界越高，狗狗对数就越多，存在单调性，所以选择二分进行计数；

我们需要通过二分找出一个最大的亲密值上界 $l$，使得满足亲密值小于等于此值的狗狗对数严格小于 k ，再对亲密值为 $l+1$ 的狗狗对进行模拟；

如何计算亲密值小于等于 mid 的狗狗对数：

我们可以使用容斥思想，对数=编号差值小于等于mid的所有狗狗对数-编号差值小于等于mid的同色狗狗对数；

差值为1的狗狗有 n-1 对，差值为2有 n-2 对，…
依据等差数列求和公式，所有狗狗对数即为 $\frac{(n-1+n-x)*x}2$；

对于同色狗狗，我们可以在每个颜色的狗狗集合内使用滑窗思想，计算以集合内每只狗狗为最小值时，有多少差值小于等于mid的狗狗对，具体可以见注释。

至于非法输入判定：

如果$cnt(mid)<=k$，mid 值会持续右移，如果输入数据非法，mid 会持续右移至 r 的初始值，我只需要将 r 的初始值设为一个不合法的值，即可区分非法输入。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,k;
int col[100005];//存第 i 只狗狗颜色
vector<int> num[100005];//存颜色编号为 i 的狗狗集合

ll cnt(int x)
{
    ll sum=(2*n-1-x)*x/2;//所有狗狗对数
    for(int i=1;i<=n;i++)
    {
        int r=0;//滑窗右界
        for(int l=0;l<num[i].size();l++)//遍历滑窗左界
        {
            while(r<num[i].size()&&num[i][r]-num[i][l]<=x)r++;//右滑至右界非法
            sum-=(r-l-1);//区间长即为在颜色i中，以l为小号的非法狗狗对数
        }
    }
    return sum;
}

int main()
{
    cin>>n>>k;
    int i,g;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&col[i]);
        num[col[i]].push_back(i);
    }
    int l=0,r=n+1,mid;
    while(l<r)
    {
        mid=l+r+1 >>1;
        if(cnt(mid)<k)l=mid;
        else r=mid-1;
    }
    if(l==n+1)printf("-1");//亲密值在合法情况下不可能为 n+1
    else
    {
        k-=cnt(l);
        //printf("*%d %lld\n",l,k);
        for(i=1;i+1+l<=n;i++)//在亲密值为 l+1 中模拟
        {
            if(col[i]!=col[i+1+l])k--;
            if(k==0)
            {
                printf("%d %d",i,i+1+l);
                break;
            }
        }
    }
    return 0;
}

E 九峰与子序列

哈希字符串，dp

思路

B题思路中有关于哈希字符串的简介链接。

本题类似于01背包问题，即对每个字符串有选与不选两种情况，n个字符串共同组成长度为$|k|$的串；

如果此字符串与目标字符串的对应段匹配，即选，否则即不选；

构建dp数组$dp[i][j]$即为使用前 i 个字串，能组成至目标串第 j 位的方法数；

$dp[i][j]=dp[i-1][j]+dp[i-1][j-|a[i]|]*(a[i]==k[j-|a[i]|+1,j])$

判断字符串相等时用哈希字符串可以将时间复杂度降为 O(1)；

遍历长度$|k|$时，需要从后向前，避免同一个字符串被使用多次；

时间复杂度为O(n|k|)，卡的比较紧。

注意：函数外定义数组时不能直接初始化（p[5000006]={1}）
有的编译环境也可以

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll M=1e9+7,P=131,N=5000006;
ll p[5000006];//存P的幂次，用快速幂会超时

ll gethash(ll aim[],ll l,ll r)//摘取子串的哈希字符串
{
    if(l==0)return aim[r];
    return (aim[r]+M-aim[l-1]*p[r-l+1]%M)%M;
}

int main()
{
    char k[N],a[N];//k是目标字符串，a是目前字符串
    ll z[N],ha;//z是目标字符串的哈希值数组，ha是目前字符串的哈希值
    int n,i,j;
    cin>>n;
    scanf("%s",k);
    p[0]=1;
    z[0]=k[0]-'a';
    for(i=1;i<strlen(k);i++)//计算p的幂次及哈希化目标字符串
    {
        p[i]=p[i-1]*P%M;
        z[i]=(z[i-1]*P+k[i]-'a')%M;
    }
    int dp[N]={1};//dp数组
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a);
        ha=0;
        for(j=0;j<strlen(a);j++)//计算目前字符串的哈希值
        {
            ha=(ha*P+a[j]-'a')%M;
        }
        for(j=strlen(k);j>=strlen(a);j--)
        {
            if(dp[j-strlen(a)]>0)//如果此位 之前的字符串已达
            {
                if(gethash(z,j-strlen(a)+1-1,j-1)==ha)dp[j]+=dp[j-strlen(a)];
            }
        }
    }
    printf("%lld",dp[strlen(k)]);
    return 0;
}

F 魏迟燕的自走棋

贪心，并查集

思路

这道题的一个关键就是$k_i\in\{1,2\}$。

首先易得，优先配发增益更大的武器能使总增益值更大；

在具体分配时：

举例来说：
如果有一个武器可以分配给1，2，我们便可以认为此武器可以被使用，且可以在1，2之间随意调换，且空位为1；
若又有一武器可以分配给2，3，我们便可以认为此武器可以被使用，且这两个武器可以通过在1，2，3间调换使任一玩家无武器，空位为1；
若再有一武器可以分配给1，3，我们便可以认为此武器可以被使用，且使1，2，3均有武器，空位为0；

所以，一个武器可以串起总空位大于0的两个不同集合，且新集合空位数为旧集合空位和-1；
若一个武器可用范围是在同一集合的两个元素，如果该集合有空位，则此武器可用，空位-1；
对于可用人数为1的武器，我们可以认为可用元素是两个相同元素，便可以归类为上面的情况。

这个过程可以通过并查集实现。

初始化时，我们使得fa[i]=i的同时，也要初始化lef[i]=1。

我们可以发现，任何时候，任一集合空位数只能为0或1；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e9+7;
int fa[N],lef[N];
struct node{
    int a,b,w;
}e[N];
bool cmp(node a,node b){
     return a.w>b.w;
}
int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    int i,n,m,k;
    ll ans=0;
    cin>>n>>m;
    for(i=1;i<=n;i++)fa[i]=i,lef[i]=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d",&k);
        if(k==1)scanf("%d",&e[i].a),e[i].b=e[i].a;
        else scanf("%d%d",&e[i].a,&e[i].b);
        scanf("%d",&e[i].w);
    }
    sort(e+1,e+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        int af=find(e[i].a),bf=find(e[i].b);
        if(lef[af]||lef[bf])//判断是否可用
        {
            ans+=e[i].w;
            if(af==bf)lef[af]=0;//判断两集合关系
            else fa[bf]=af,lef[af]+=lef[bf]-1;
        }
    }
    cout<<ans;
    return 0;
}

G 九峰与蛇形填数

模拟

思路

这道题卡得比较狠：对m个矩阵依次填会爆，对每一个位置判断在哪一个小矩阵里再填还会爆。

所以我们要先找到能包含所有有值的位置的最小矩形，在此矩形中遍历每一个位置，判断在哪一个矩阵里再填数。

还有另一种方法，翻别人代码时发现的，就是反向枚举m个子矩阵，在对空格填数时，在该格打上一个”路标“，指示此矩阵在该行的最后一个数的位置，在再次扫过此格时可以直接跳到该位置，时间复杂度比上面的还小一些。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2003,M=3003;
int main()
{
    static int n,m,a[N][N]= {0},bi[M],bj[M],k[M];
    int i,j,p,q,pmi,pmx,qmi,qmx;
    cin>>n>>m;
    pmi=qmi=n;
    pmx=qmx=1;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&bi[i],&bj[i],&k[i]);
        pmi=min(pmi,bi[i]),qmi=min(qmi,bj[i]);//更新有值的边界
        pmx=max(pmx,bi[i]+k[i]-1),qmx=max(qmx,bj[i]+k[i]+1);
    }
    for(p=pmi; p<=pmx; p++)
        for(q=qmi; q<=qmx; q++)
            for(i=m; i>=1; i--)//遍历矩阵
                if(p>=bi[i]&&p<=bi[i]+k[i]-1&&q>=bj[i]&&q<=bj[i]+k[i]-1)
                {
                    if(p-bi[i]&1)a[p][q]=(p-bi[i]+1)*k[i]-(q-bj[i]);
                    else a[p][q]=(p-bi[i])*k[i]+(q-bj[i]+1);
                    break;
            	}
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

注：这道题题干中x是行数，y是列数。

H 吴楚月的表达式

DFS

思路

此题中任一表达式均可用 a + b 表示：
如果运算为$+n$，则 $a=a^\prime+b^\prime,b=n$;
如果运算为$-n$，则 $a=a^\prime+b^\prime,b=M-n$（负数取模会出问题）;
如果运算为$*n$，则 $a=a^\prime,b=b^\prime*n$;
如果运算为$/n$，则 $a=a^\prime,b=b^\prime*n^{M-2}\%M$（除法取模会出问题，所以用逆元处理）.

接下来从根部向下DFS即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e9+7;
vector<ll>son[N];
ll num[N],ans[N],n;
char o[N];
ll qm(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
    }
    return ans;
}
void dfs(ll a,ll b,int no)
{
    int i;
    if(o[no-2]=='*')
    {
        b=b*num[no]%M;
    }
    else if(o[no-2]=='/')
    {
        b=b*qm(num[no],M-2)%M;//逆元
    }
    else if(o[no-2]=='+')
    {
        a=(a+b)%M;
        b=num[no]%M;
    }
    else if(o[no-2]=='-')
    {
        a=(a+b)%M;
        b=-num[no]+M;//负数求余会出现问题
    }
    ans[no]=(a+b)%M;
    for(i=0;i<son[no].size();i++)dfs(a,b,son[no][i]);
}
int main()
{
    ll i,j,g;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)scanf("%lld",&num[i]);
    for(i=2;i<=n;i++){scanf("%lld",&g);son[g].push_back(i);}
    scanf("%s",o);
    ans[1]=num[1];
    for(i=0;i<son[1].size();i++)dfs(0,num[1],son[1][i]);
    for(i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}

J 邬澄瑶的公约数

思路

用 p_i 表示第 i 个质数，则任意整数均可表示为 $a=\prod p_{i}^{k_i}$；
则$gcd(a_1^{t_1},a_2^{t_2},...)=\prod p_{i}^{min(k_{a_1}*t_1,k_{a_2}*t_2,...)}$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000;
const ll M=1000000007;
ll qm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans%M;
}
int main()
{
    int ny[N],zy[N],i,j;
    for(i=1;i<N;i++)zy[i]=1000000;//这个足够大数一定要够大
    int n,gx[N+1],gp[N+1];
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&gx[i]);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&gp[i]);
    }
    for(i=1;i<=n;i++)
    {
        memset(ny,0,sizeof ny);
        for(j=2;j<=gx[i];j++)
        {
            while(gx[i]%j==0)
            {
                ny[j]++;
                gx[i]/=j;
            }
        }
        for(j=2;j<N;j++)
        {
            zy[j]=min(zy[j],ny[j]*gp[i]);
        }
    }
    ll ans=1;
    for(j=2;j<N;j++)
    {
        ans*=qm(j,zy[j]);
        ans%=M;
    }
    cout<<ans;
    return 0;
}

ED

\