ACM暑期集训Day1题解

ACM暑期集训Day1题解

地址

集训赛地址:https://vjudge.net/contest/384255

A Polycarp's Pockets

#1 思路

题面很清楚了,核心就是一个口袋里不能放同种(数字相同的)硬币,所以所需要的最小口袋数就是重复最多次的数字的重复次数,那么我们用一个计数(计排)或者是映射(map)来记录每个出现的数字的重复次数,最后遍历求其中最大值即可。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int t[105];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    for (int i=1;i<=n;i++)
    {
        int z;
        cin>>z;
        t[z]++;    //计数
    }

    int maxn=0;
    for (int i=1;i<=105;i++)
        maxn=max(maxn,t[i]);

    cout<<maxn<<'\n';
    
    return 0;
}

B Binary String Constructing

#1 思路

看起来挺简单,但是写起来很麻烦的一道题。本题求的是满足一定交替次数的01序列。题目给出了0,1的个数和交替次数。我们先考虑把交替次数做完:

  • 样例:[2 2 1]
  • 先用完交替次数:01
  • 发现不行

这样显然行不通,因为后面还剩0,1,必定是要多出一个交替次数。那我们可以退一步考虑,选择留一个交替次数,把其他的交替次数先用完,最后剩下的一个交替次数,把剩下的0,1数字收集起来一起输出。这样一来0,1数字和交替次数都用完了。

但是还需要考虑一个问题:最后剩下的0,1只剩下其中一个怎么办?这很好办,只需要把数量多的数字(0或者1)留最后面输出就可以了,并且保证其他的交替次数做完后序列尾位的数字为(1或者0)。这道题需要分类讨论。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a,b,x;
    cin>>a>>b>>x;

    int ch;
    if (a>b)
    {
        if (x%2)
            ch=1;
        else ch=0;

        for (int i=1;i<=x;i++)
        {
            cout<<ch;
            if (ch) b--;
            else a--;
            ch=!ch;
        }

        for (int i=1;i<=b;i++)
            cout<<1;
        for (int i=1;i<=a;i++)
            cout<<0;
    }
    else
    {
        if (x%2)
            ch=0;
        else ch=1;

        for (int i=1;i<=x;i++)
        {
            cout<<ch;
            if (ch) b--;
            else a--;
            ch=!ch;
        }

        for (int i=1;i<=a;i++)
            cout<<0;
        for (int i=1;i<=b;i++)
            cout<<1;
    }

    cout<<'\n';
    return 0;
}

C Intense Heat

#1 思路

这道题求得是长度大于等于k的子段的平均值的最大值。首先要注意是子段而不是子序列,这是不同的概念。既然是子段,那么就非常简单了,数据范围也不大,前缀和直接伺候上!然后再来个暴力求平均值就可以了,时间复杂度$O(n^2)$,非常常规。

  • 前缀和:构造一个序列s满足$s_0=0$,$s_i=s_{i−1}+a_i$,则我们要求的答案为$s_r−s_{l−1}$。序列s称为序列a的前缀和

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int a[5005];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,k;
    cin>>n>>k;
	
    for(int i=1;i<=n;i++)
    { 
        cin>>a[i];
        a[i]+=a[i-1];
    }

    double maxn=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+k-1;j<=n;j++) 
            maxn=max(maxn,((double)(a[j]-a[i-1])/(j-i+1)));
    }

    cout<<setiosflags(ios::fixed)<<setprecision(15)<<maxn<<endl;
    return 0;
}

D Coins and Queries

#1 思路

这是一道贪心题。做法就是,从大到小循环硬币面值,每次尽可能的去取可以取的当前的硬币面值。如果能凑成,则输出取的数的数目,不能则输出-1。为什么这个方法是正确的呢,来证明一下:

  • 正确性:因为每个硬币面值都是2的次幂,所以从大到小去取,不会使得本来可以凑成的数值凑不成(想一想啦)。
  • 最优性:因为是从大到小循环取面值,所以一定能保证数量最优。

当然本题还需要一点处理的技巧。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

map<int,int> b;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,q;
    cin>>n>>q;

    for (int i=1;i<=n;i++)
    {
        int bi;
        cin>>bi;
        b[bi]++;
    }
    
    while (q--)
    {
        int d;
        cin>>d;

        int cnt=0;
        for (int i=31;~i;i--)
        {
            if ((1<<i)>d) continue;
            cnt+=min(d/(1<<i),b[1<<i]);
            d-=min(d/(1<<i),b[1<<i])*(1<<i);
            if (d==0) break;
        }
        if (!d)
            cout<<cnt<<'\n';
        else cout<<"-1\n";
    }

    return 0;
}

E How Many Tables

#1 思路

常规的并查集算法。如何计算分组的数量?在经过处理之后,在同一组的人都有相同的"祖先",所以只需要计所有人的"祖先"的种数就可以了,这里推荐用set,方便的不得了啊。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int fa[100005];

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return fa[x]=check_anc(fa[x]);    //路径压缩
    return x;
}
void union_anc(int x,int y)    //合并
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    fa[x]=y;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;

    while (t--)
    {
        memset(fa,0,sizeof(fa));

        set<int> num;
        int n,m;
        cin>>n>>m;

        for (int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;

            union_anc(u,v);
        }

        for (int i=1;i<=n;i++)
            num.insert(check_anc(i));

        cout<<num.size()<<'\n';

        num.clear();
    }
    
    return 0;
}

G Bone Collector

#1 思路

01背包原型题,空间优化注意循环顺序,不讲了。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int w[3505],v[3505];
int dp[20005];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;

    while (t--)
    {
        memset(dp,0,sizeof(dp));

        int n,m;    //n为物品数量,m为容量
        cin>>n>>m;
 
        for (int i=1;i<=n;i++)
            cin>>w[i];    //输入物品的价值和体积
        
        for (int i=1;i<=n;i++)
            cin>>v[i];    //输入物品的价值和体积
 
        for (int i=1;i<=n;i++)
            for (int j=m;j>=0;j--)
                if (j-v[i]>=0)
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

       cout<<dp[m]<<'\n';
    }
    return 0;
}

H Max Sum

#1 思路

啊,本来是一道普普通通的DP题,可是加了求首尾的要求后就变的稍微难一些了,需要回忆一下这道题DP的本质。

  • 设数组为a,求解数组为f
  • 状态:以当前下标为结尾的子段和最大有多大
  • 转移方程:f[i]=max{a[i],f[i-1]+a[i]}

尾边界可以很容易得出:找到满足f[i]最大的那个下标。首边界怎么求呢,观察转移方程,当f[i]+a[i]>=a[i],即f[i]>=0时,就会刷新首边界,所以我们从尾边界开始往前遍历,直到不满足这个条件,那么此时的位置就是首边界的前一个位置。

大坑:最后一个测试数据的末尾不要用两个换行。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) x.begin(),x.end()
    
int a[200005],f[200005];
    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;


    for (int j=1;j<=t;j++)
    {
        int n;
        cin>>n;

        for (int i=1;i<=n;i++)
            cin>>a[i];

        for (int i=1;i<=n;i++)
            f[i]=max(a[i],f[i-1]+a[i]);

        int maxn=INT_MIN,s,e;
        for(int i=1;i<=n;i++)
        {
            if (maxn<f[i])
            {
                maxn=f[i];
                e=i;
            }
        }
        s=e;
        for(int i=s-1;i;i--)
        {
            if (f[i]>=0) s=i;
            else break;
        }
        cout<<"Case "<<j<<":\n"<<maxn<<' '<<s
            <<' '<<e<<"\n";

        if (j!=t)
            cout<<"\n";
    }
    return 0;
}

总结

题目还是比较好写的,有些题目还是有点意思的凹😎。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。