ACM暑期集训Day2题解

ACM暑期集训Day2题解

地址

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

A 最少拦截系统

#1 思路

本题求的是所需的拦截系统数量,由题意得后面火箭的高度不能超过前面火箭的高度,由Dilworth定理可得最长上升(高度)子序列的长度即是我们所需要的拦截系统数量。求最长上升子序列的长度的方法挺多,我用的是树状数组,比较快。写的时候不仅发现自己原来写的模板错了,还忘记是多组数据🙃。

  • Dilworth定理:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。对偶形式也成立。

当然也有人用贪心写这道题。再吐槽下:这道题连个数据范围都没有❌。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
 
int a[100005],bit[100005],r[100005];
int ans;
 
bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}
 
int lowbit(int x)
{
    //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
    return x&-x;
}
void change_point(int u,int d,int j)    //单点修改
{
    while (u<=j)    //不能越界
    {
        bit[u]=max(bit[u],d);
        u+=lowbit(u);
    }
}
int ask_max(int u)    //区间查询
{
    int ans=0;
    while (u>=1)
    {
        ans=max(ans,bit[u]);
        u-=lowbit(u);
    }
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    
    while (cin>>n)
    {
        ans=0;
        memset(a,0,sizeof(a));
        memset(bit,0,sizeof(bit));
 
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int m=unique(a+1,a+n+1)-a-1;

        for (int i=1;i<=m;i++)
            r[i]=i;
        sort(r+1,r+m+1,cmp);
 
        for(int i=1;i<=m;i++)
        {
            change_point(r[i],ask_max(r[i])+1,m);
            ans=max(ans,bit[r[i]]);
        }
 
        cout<<ans<<'\n';
    }
    return 0;
}

B Learning Languages(补)

#1 思路

这是一道并查集的题目。具体做法是将每个语言、每个人都看作一个节点,一个人掌握一门语言就可以表示为将这个人代表的节点与这门语言代表的节点连一条边,只需将所有人都联通即可。

可以用并查集来模拟建边,将并查集分为两部分1-n记录人,n+1-n+m记录语言,将人与对应的语言并入同一个集合中,最后统计集合个数,只有语言就不用统计了。但是题目给我们一个信息:有可能没有人会语言,所以需要进行特判。

#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 n,m;
    cin>>n>>m;

    int pd=1;
    for (int i=1;i<=n;i++)
    {
        int k;
        cin>>k;

        if (k) pd=0;

        for (int j=1;j<=k;j++)
        {
            int ki;
            cin>>ki;
            union_anc(ki+n,i);
        }
    }
    
    int ans=0;
    for (int i=1;i<=n;i++) 
        if (check_anc(i)==i) ans++;
    
    if (pd) cout<<n<<'\n';
    else cout<<ans-1<<'\n';
    return 0;
}

C A hard puzzle

#1 思路

常规的快速幂题,需要取模。

#2 程序1(C++)

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

long long fast_power(int a,int b,int mod)
{
    long long ans=1,base=a;
    while(b)
    {
        if(b&1)
            ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans%mod;    //非多余步,如果没有b=0这种数据可以去掉取余
}

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

    while (cin>>a>>b)
    {
        cout<<fast_power(a,b,10)<<'\n';
    }
    return 0;
}

D Repeating Cipher

#1 思路

题目给的都是保证合法的数据,所以说直接遍历取字母就可以了。

#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);
    string s;
    int n;
    cin>>n>>s;

    for (int i=0,j=0;i<n;i+=j)
    {
        cout<<s[i];
        j++;
    }
    return 0;
}

E Array Stabilization

#1 思路

将输入进来的数组进行排序,因为是必须要删除一个数字,所以在排序后我们将a[n-1]-a[1]与a[n]-a[2]作比较(删除的一定是最大值或最小值),将比较小的值输出。

#2 程序1(C++)

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

int a[100005];

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

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

    cout<<min(a[n-1]-a[1],a[n]-a[2])<<'\n';
    return 0;
}

F Nightmare(补)

G Adjacent Replacements

#1 思路

题面真他🐎的长。

题目中的玄学算法从1(奇数)开始,我们把奇数设为2k-1,偶数设为2k。那么奇数会经历两个步骤:2k-1➡2k➡2k-1,偶数会经历一个步骤:2k➡2k-1。那么此题的算法就很明显了,奇数直接输出,偶数-1再输出。

#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 n;
    cin>>n;

    for (int i=1;i<=n;i++)
    {
        int ai;
        cin>>ai;
        if (ai%2) cout<<ai<<' ';
        else cout<<ai-1<<' ';
    }
    return 0;
}

H Polycarp's Practice

#1 思路

本题的意思就是要你求出分成的k个区间的最大值之和的最大值与这些区间的长度。既然要让最大值之和最大,那么即考虑贪心求数组的前k大的数的和。之后我们只需要去标记这前k大的数的位置,进行分段输出长度即可。我采用的分段方法是留最后一段,前几段从首位置开始累加长度,遇到标记的位置就输出长度并且置为0,最后的一段把剩下的长度全部选取。

#2 程序1(C++)

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

int a[2005],r[2005],pd[2005];

bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}

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];
        r[i]=i;
    }
    sort(r+1,r+n+1,cmp);

    int maxn=0;
    for (int i=n;i>n-k;i--)
    {
        maxn+=a[r[i]];
        pd[r[i]]=1;
    }

    cout<<maxn<<'\n';
    
    int res=0;
    for (int i=1;i<=n+1;i++)
    {
        if (k<=1) {res=n+1-i; break;}
        if (pd[i])
        {
            cout<<++res<<' ';
            k--;
            res=0;
        }
        else res++;
    }
    
    cout<<res<<'\n';
    return 0;
}

I 饭卡

#1 思路

某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额...

不能再明显了凹,就是01背包的变种。很容易想到如何使得剩下的余额最少(可以看成是拿的价值最大),那就是在最后去选取价值最大的物品,因为只要大于等于5元就可以刷任意价值的物品,相当于可以把这5元当成万能消费券。其他的部分就是由01背包来处理了,但注意01背包的过程中不能选取价值最大的那个物品。

#2 程序1(C++)

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

int v[1005],dp[1005];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    
    while (cin>>n&&n)
    {
        memset(dp,0,sizeof(dp));

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

        sort(v+1,v+n+1);

        int m;
        cin>>m;

        if (m<5)
        {
            cout<<m<<'\n'; continue;
        }
        else m-=5;

        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]]+v[i]);
        
        cout<<m+5-(dp[m]+v[n])<<'\n';
    }
    
    return 0;
}

总结

简单题部分觉得是比Day1还要简单些,中等题明显加强。还是得好好补题。


感谢浏览😝!

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

h