算法提高班（2）期中

· · 个人记录

数字游戏v4

题意

就是选择k个数字，让(c+r_i)/2连续除法尽可能的大，我们考虑贪心，因为先这个数字会不停的除，那么加进去的数字的数字里面最小的开始加

思路

sort+循环即可

代码

    sort(a+1,a+1+n);
    for(int i=n-k+1;i<=n;i++) c=(c+a[i])/2.0;
    printf( "%.6lf",c);

平均的爱

题意

就是每个人都有不同的权值，我们考虑用dfs枚举所有的可能性，然后找出最小的权值！

思路

dfs+minn查找

注意数据范围，因为数据超过longlong的所以我们可以直接

#define int long long

代码

int n,a[100],b[100],minn=1e14+10,sa[100],sb[100];
void dfs(int s1,int s2,int step) {
    if(step==n+1){
        minn=min(minn,abs(s2-s1));
        return;
    }
    dfs(s1+a[step],s2,step+1);
    dfs(s1,s2+b[step],step+1);
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();b[i]=read();
        sa[i]=sa[i-1]+a[i];
        sb[i]=sb[i-1]+b[i];
    }
    dfs(0,0,1);
    printf("%lld",minn);
    return 0;
}

小明的手表

题意

就是想要按出1,2,3\dots n-1最多的那个需要多少次。 这里明显需要用到最短路，我们用bfs来解决

思路

bfs记录最短次数，这里面我们可以用dis数组取代vis数组的作用，然后进行bfs遍历即可，这里面我们还得注意取mod。

代码

inline void bfs()
{
    queue<int> q[2];
    q[0].push(0),q[1].push(0);
    while(!q[0].empty())
    {
        int x=q[0].front(),s=q[1].front();
        q[0].pop(),q[1].pop();
        if(dis[x]) continue;
        dis[x]=s;
        q[0].push((x+1)%n),q[1].push(s+1);
        q[0].push((x+k)%n),q[1].push(s+1);
    }
}

社交网络服务

题意

本题其实就是看同一个团体下面还有多少边未连接，那么我们可以考虑用并查集进行统计，然后用完全图的边数-目前并查集的边数即可！

思路

并查集+完全图边数量计算+边数统计

代码

void mergE(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu!=fv){
        fa[fu]=fv;
        sz[fv]+=sz[fu];
        cnt[fv]+=cnt[fu]+1;
    }else{
        cnt[fu]++;
    }
}
//合并的时候，顺便用cnt记录边的数量，用sz记录当前并查集的大小
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        mergE(a,b);
    }
    for(int i=1;i<=n;i++){
        if(find(i)==i){
            ans+=((sz[i]-1)*(sz[i])/2-cnt[i]);
        }
    }

数学趣题v5

题意

考虑到每个数字都只能选一次，而且最终构成的也是数字本身，我们可以把数字看作是容量c和价值v。

这时候我们再看题目就是一个01背包了！

思路

01背包+初始化。

我们考虑将dp数组初始化成0，如果有该数据我们就打上标签1

我们考虑开始dp，直接把n个数字看作n个物品，然后用

f[j]=f[j-a[i]]||f[j]

进行转移，相当于f数组就是一个标记数组，看看他能不能用之前生成的f[j]转移过来。

代码

    f[0]=true;
    for(int i=1; i<=n; i++)
        for(int j=sum; j>=a[i]; j--)
            f[j]=f[j]||f[j-a[i]];//具体转移方程
    for(int i=m; i<=sum; i++)
        if(dp[i])//如果和大于等于m且最小
        {
            cout<<i<<endl;
            return 0;
        }

粉刷匠

题意

自由选择刷的颜色前提下，能取到的最小值

思路

类似于美元兑换那个题目，我们考虑设计一个线性的状态DP，我们定义f[i][0/1/2]来表示刷到了第i堵墙，然后选择成一种颜色的代价。

由于相邻颜色必须不同，所以dp转移的时候，就可以直接转向另外两种即可。

换言之，就是刷成f[i][1]必须由f[i][0]或者f[i][2]转移过来。

代码

    f[1][1]=a[1];
    f[1][2]=b[1];
    f[1][3]=c[1];
    for(int i=2;i<=n;i++){
        f[i][1]=min(f[i-1][2],f[i-1][3])+a[i];
        f[i][2]=min(f[i-1][1],f[i-1][3])+b[i];
        f[i][3]=min(f[i-1][2],f[i-1][1])+c[i];
    }
    cout<<min(f[n][1],min(f[n][2],f[n][3]));