牛客算法周周练7 部分题解

还是来写点有意思的题目的题解吧/x

C.Rabbit的工作(1)

这题很明显是个dp题，因为n很小，我们直接乱搞就行了，不用考虑优化什么的。。。

我们设dp[i][j]表示前i天，我们一共工作了j天所耗费的最小疲惫度

那么对于第i天来说，我们有如下情况：

如果第i天为0，直接从i-1那里将值继承过来就行了，即dp[i][j]=dp[i-1][j]

如果第i天为1，那么就有两个情况：

1.第i天不上课，那么和上面的一样，dp[i][j]=dp[i-1][j]

2.第i天上课，但是，我们无法保证连续性啊，难道我们还要多加一维0/1表示第i是否上课吗？

不用，我们直接乱搞,我们直接枚举我们从哪天开始到第i天连续工作就行了，我们设我们枚举的从第k天到第i天连续工作，那么，我们要从k-2开始更新，为啥？因为如果我们从第k-1天更新的话，就会使得如果我们第k-1天工作的话，就和现在的k到i天工作连续起来了，但是我们转移的时候，算贡献却只算了k-j+1天连续工作的贡献，就会使得答案偏小。

也即是,dp[i][j]=min(dp[i][j],dp[k-2][j-(i-k+1)]+sum(i-k+1))(其中，i-k都是1且k>=2,sum(x)表示1+2+...+x的值)

如果k=1的话，直接特判就好了,即dp[i][i]=min(dp[i][i],sum(i))

然后，这题就解完了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=401;
int dp[N][N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    string x;
    cin>>x;
    memset(dp,0x3f3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            dp[i][j]=dp[i-1][j];
        }
        if(x[i-1]=='1'){
            for(int j=i;j;--j){//枚举第j->i天工作
                if(x[j-1]=='0')break;
                int t=i-j+1,sum=(1+t)*t/2;
                if(j==1){
                    dp[i][t]=min(dp[i][t],sum);
                }else{
                    for(int k=t;k<=i;++k){
                        dp[i][k]=min(dp[i][k],dp[j-2][k-t]+sum);
                    }
                }
            }
        }
    }
    for(int i=n;~i;--i){
        if(dp[n][i]<=k){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}

Update:

看了@ 神崎兰子大佬的做法后恍然大悟，于是优化到了（大雾）

因为上限在排序，带个log，但是值都很小，于是直接上桶排！（若差值较大，请使用松式基排）

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=401,M=256,mod=255;
int d[4][N],f[N];
int a[N],e,b[N*101],c[N];
inline int calc(int x,int y){//计算连续x个可工作日中工作y天的最小疲惫度
    if(x<y)return 2e9;
    int A=x-y+1;//A段
    if(A>=y)return y;
    int B=y/A,C=y%A;
    int res=A*(1+B)*B/2+C*(B+1);
    return res;
}
inline void bad_sort(int l,int r){//直接上暴力桶排,如果差距过大，直接使用基数排序即可
    int maxe=0;
    for(int i=l;i<=r;++i){
        ++b[c[i]];maxe=max(maxe,c[i]);
    }
    int tot=l-1;
    for(int i=1;i<=maxe;++i){
        while(b[i]){
            c[++tot]=i;--b[i];
        }
    }
}
inline void base_sort(int n){
    for(int i=1;i<=n;++i){
        ++d[0][c[i]&mod];++d[1][(c[i]>>8)&mod];
        ++d[2][(c[i]>>16)&mod];++d[3][(c[i]>>24)&mod];
    }
    for(int i=1;i<M;++i){
        d[0][i]+=d[0][i-1];d[1][i]+=d[1][i-1];
        d[2][i]+=d[2][i-1];d[3][i]+=d[3][i-1];
    }
    for(int i=n;i;--i){
        f[d[0][c[i]&mod]--]=c[i];
    }
    for(int i=n;i;--i){
        c[d[1][(c[i]>>8)&mod]--]=f[i];
    }
    for(int i=n;i;--i){
        f[d[2][(c[i]>>16)&mod]--]=c[i];
    }
    for(int i=n;i;--i){
        c[d[3][(c[i]>>24)&mod]--]=f[i];
    }
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    string x;
    cin>>x;
    for(int i=1;i<=n;++i){
        if(x[i-1]=='1'){
            int res=0;
            for(int j=i;j<=n;++j){
                if(x[j-1]=='0')break;
                ++res;
            }
            a[++e]=res;i+=(res-1);
        }
    }
    int tot=0;
    for(int i=1;i<=e;++i){//运行次数=1的个数<=n
        int pas=0;
        for(int j=1;j<=a[i];++j){
            int now=calc(a[i],j);
            c[++tot]=now-pas;pas=now;
        }
    }
    bad_sort(1,tot);
    //base_sort(tot);
    int ans=0;
    for(int i=1;i<=tot;++i){
        if(k<c[i])break;++ans;k-=c[i];
    }
    printf("%d",ans);
    return 0;
}

一个猜想（下午来试着证明下）

设一共有x天可以连续加班，我们一共加班y天的最小代价为calc(x,y)

那么有，其中1<y<x

证明：

如果，

明显成立。(左边=1，右边也一定大于等于1)

考虑其它可能性

我们设每段连续工作的天数分别为(工作y-1天):

那么，一定有

那么总代价就是

若我们工作y天，那么，现在我们就发现我们需要将k段变成k-1段，并将和变为y

那么在使用最小代价的策略下，不难发现，我们必然是将平均分配给剩余的几个数（优先分配给前面的），也就是说，现在的工作段数变为了：

那么，计算下变化代价就是：

同理，我们计算出y->y+1的变化代价：

（为了方便计算，这里直接使用放缩，也即是，按道理，本来中已经有多个数字变大了，但这里我们先默认不变）

下减上，我们把中间的一大堆先照抄（看起来太麻烦了qwq），把(b_2+1)和后面的求和合并下就有：

注意到，由于，所以，除了最右边那个-1以外的那堆东西，它们的"加的项数">="减的项数"，而且，因为加的项数是每k-2个就翻一翻（也即是增长的要快些），所以，加的和>=减的和

也即是，说，该式的值应该。

但是-1明显不是我们所想要的，但是，注意到，我们之前使用了“放缩法”，也即是说，实际上，我们y->y+1变化的值是大于目前的值的，又由于变化值肯定是个整数，所以，就有：

y->y+1变化值-y->y-1变化值>-1 &&y->y+1变化值和y->y-1变化值都是整数

那么，就不难有:

y->y+1变化值-y->y-1变化值>=0成立了

用calc表达就是我们需要证明的东西了！

证毕后的我：

证明了这个结论后有啥用呢？

我的算法是：我们如果将所有阶段的变化值按小到大排序的话，那么，我们依次将变化值加入，直到加入后会大于k为止，那么，加入的变化值的个数就是答案数

如果证明了这个的话，那么，我们就可以知道，我们一定是会先加入y-1->y后才会加入y->y+1，而不会没加入y-1->y就加入y->y+1而使得答案出错

D.华华和月月逛公园

其实就是求，有多少条边满足删除后剩下的图不连通。

其实就是个简单的tarjan缩环问题，但是，我们的是无向图啊，该怎么办呢？

Ps:如果是单向边的话，其实就是等价求，有多少条边参与构成了任意一个环（yy就行辣）

无向图缩环了解一下。(我大号终于又暴露了，2333)

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
struct node{
    int v,nex;
}t[N<<1];
int len,las[N];
bool vis[N];int dfn[N],low[N],sta[N],top,cnt;
int fa[N];int U[N],V[N];
bool kil[N];
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
inline void tarjan(int x){
    dfn[x]=low[x]=++cnt;sta[++top]=x,vis[x]=1;
    for(int i=las[x];i;i=t[i].nex){
        if(kil[i])continue;kil[i^1]=1;
        int v=t[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(vis[v]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(dfn[x]==low[x]){
        while(true){
            int v=sta[top--];vis[v]=0;fa[v]=x;
            if(v==x)break;
        }
    }
}
int main(){
    int n,m;len=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        U[i]=u,V[i]=v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    int res=0;
    for(int i=1;i<=m;++i){
        res+=(fa[U[i]]==fa[V[i]]);
    }
    printf("%d",res);
    return 0;
}