牛客练习赛60

A.大吉大利

考虑每一位对答案的贡献。

如果两个数的第 $i$ 位都是 $1$ ，那么就会对答案产生 $2^i$ 的贡献。

所以答案就是 $\sum_{i=0}^{30}2^i \times gs[i]^2$ 。 $gs[i]$ 就是第 $i$ 位是 $1$ 的个数。

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,k,ans,a[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        for(int j=0;j<=30;j++)
            if(x&(1<<j))a[j]++;
    }
    for(int i=0;i<=30;i++)ans+=a[i]*a[i]*(1<<i);
    cout<<ans;
    return 0;
}

B.三角形周长和

考虑每条边的贡献。由于每个点两两间都有边，所以对于一条边，它会在 $n-2$ 个三角形中出现。

答案就是 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} ( \left| x[i]-x[j] \right|+\left| y[i]-y[j] \right| ) \times (n-2)$

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=998244353;
const int N=1e6+5;
int n,m,k,ans,a[N],b[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read(),b[i]=read();
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ans=(ans+(abs(a[i]-a[j])+abs(b[i]-b[j]))%mod*(n-2)%mod)%mod;
    cout<<ans;
    return 0;
}

C.操作集锦

提供一个 $O(nm)$ 的做法。

考虑 $DP$ ，设 $f[i][j]$ 表示前 $i$ 个数，选了 $j$ 的方案数。

如果不考虑有重复的情况，那么 $f[i][j]=f[i-1][j]+f[i-1][j-1]$

但是有重复的情况，怎么办？那就把重复的减去就好了。

重复了那些呢，记 $last$ 为：第 $i$ 个字符上一次出现的地方。

那么重复的就是 $f[last-1][j-1]$ 。相当于 $f[last-1][j-1]$ 多的方案就是加了个第 $i$ 个字符，但在 $last$ 的时候这个答案就已经算过了。

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=1e9+7;
const int N=1005;
int n,m,k,ans,f[N][N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();m=read();
    scanf("%s",s+1);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=1;f[i][i]=1;
        int lst=0;
        for(int j=i-1;j;j--)
            if(s[j]==s[i])
            {
                lst=j;
                break;
            }
        for(int j=1;j<i;j++)
        {
            f[i][j]=f[i-1][j];
            if(lst)
            {
                f[i][j]+=f[i-1][j-1]-f[lst-1][j-1];
            }
            else f[i][j]+=f[i-1][j-1];
            f[i][j]=(f[i][j]%mod+mod)%mod;
        }
    }
    cout<<f[n][m];
    return 0;
}

D.斩杀线计算大师

好像不少都是用 $exgcd$ 过的，这里介绍一种新的做法——同余最短路

同余最短路是什么？

就是每个点 $i$ 的意义是在模 $mn$ 的意义下能被构造出来的最小值

这有什么用呢？

这可以用最短路的方法求的余数是 $0-(mn-1)$ 的最小能构造出来的数

这就可一求 $1-k$ 中有多少数能被 $Σa_i*x_i$ 构造出来，即若干个 $a1$ 到 $an$ 的和

$dis[(u+a[i])\%mn]=min(dis[(u+a[i])\%mn],dis[u]+a[i])$

还不会的可以详见我的博客（内有例题和题解）https://blog.nowcoder.net/n/05b3573da70d414693afd7ec2b3fc5ce

这题和跳楼机几乎一样，有兴趣的可以先做那题。

这题就是在同余最短路的基础上记录一下上一个选的是啥，然后就能统计出每个数使用的次数了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int h,a,b,c,mi,dis[N],vis[N],gs[N];
struct node{
    int id,val;
}nxt[N];
bool operator < (node a,node b)
{
    return a.val>b.val;
}
priority_queue<node>q;
void dj()
{
    for(int i=0;i<N;i++)dis[i]=1e18;
    dis[0]=0;
    q.push((node){0,0});
    while(!q.empty())
    {
        int u=q.top().id;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        if(dis[(u+a)%mi]>dis[u]+a)
        {
            dis[(u+a)%mi]=dis[u]+a;
            nxt[(u+a)%mi]=(node){u,1};
            q.push((node){(u+a)%mi,dis[(u+a)%mi]});
        }
        if(dis[(u+b)%mi]>dis[u]+b)
        {
            dis[(u+b)%mi]=dis[u]+b;
            nxt[(u+b)%mi]=(node){u,2};
            q.push((node){(u+b)%mi,dis[(u+b)%mi]});
        }
        if(dis[(u+c)%mi]>dis[u]+c)
        {
            dis[(u+c)%mi]=dis[u]+c;
            nxt[(u+c)%mi]=(node){u,3};
            q.push((node){(u+c)%mi,dis[(u+c)%mi]});
        }
    }
}
void work(int h)
{
    if(h==0)return;
    gs[nxt[h].val]++;
    h=nxt[h].id;
    work(h);
}
signed main()
{
    scanf("%lld%lld%lld",&a,&b,&c);
    scanf("%lld",&h);
    mi=max(a,max(b,c));
    dj();
    work(h%mi);
    int x=a*gs[1]+b*gs[2]+c*gs[3];
    x=h-x;
    if(mi==a)gs[1]+=x/a;
    else if(mi==b)gs[2]+=x/b;
    else if(mi==c)gs[3]+=x/c;
    cout<<gs[1]<<" "<<gs[2]<<" "<<gs[3];
    return 0;
}

E.旗鼓相当的对手

这题题意有点不清，有歧义，导致我wa了4发。

应该可以换根DP，我用的是长链剖分，这真是模板题啊。

维护 $f[i][j]$ 表示从点 $i$ 出发向下的长度为 $j$ 的端点权值和。 $g[i][j]$ 表示从点 $i$ 出发向下的长度为 $j$ 的端点个数。

然后就可以用这两个数组来求答案了。

$ans[u]+=f[u][m-j-1]*g[v][j];$
$ans[u]+=g[u][m-j-1]*f[v][j];$

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=1e6+5;
struct node{
    int too,next;
}edge[N*2];
int n,top,m,ans[N],a[N],head[N],len[N],son[N],tmp[N],*f[N],*g[N],*id=tmp;
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fa)continue;
        dfs(v,u);
        if(len[v]>len[son[u]])son[u]=v;
    }
    len[u]=len[son[u]]+1;
}
void dp(int u,int fa)
{
    if(son[u])
    {
        f[son[u]]=f[u]+1;
        g[son[u]]=g[u]+1;
        dp(son[u],u);
//      ans[u]+=ans[son[u]];
    }
    f[u][0]=a[u];
    g[u][0]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fa||v==son[u])continue;
        f[v]=id;
        id+=len[v]*2;
        g[v]=id;
        id+=len[v]*2;
        dp(v,u);
//      ans[u]+=ans[v];
        for(int j=0;j<len[v];j++)
            if(m-j-1>0&&m-j-1<len[u])
            {
                ans[u]+=f[u][m-j-1]*g[v][j];
                ans[u]+=g[u][m-j-1]*f[v][j];
//              if(u!=1)continue;
//              cout<<j<<" "<<ans[u]<<" "<<f[u][j+1]<<" "<<f[v][m-j-2]<<endl;
            }
        for(int j=0;j<len[v];j++)
        {
            f[u][j+1]+=f[v][j];
            g[u][j+1]+=g[v][j];
        }
    }
}
signed main()
{
    int x,y;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    f[1]=id;
    id+=len[1]*2;
    g[1]=id;
    id+=len[1]*2;
    dp(1,0);
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}
/*
7 2
1 2 3 4 5 6 7
1 2
2 3
2 4
1 5
5 6
5 7
*/