2020 年百度之星程序设计大赛初赛二部分题解

时间：2020-07-26 20:02:52 阅读：87 评论：0 收藏：0 [点我收藏+]

弱鸡只做出来五题。。

Poker

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6775

题意

小沃沃在玩一个有趣的游戏。

初始他有 $n$ 块钱，每一轮他需要投入至少 $m$ 块钱，系统会拿走其中 $p\%$ 的钱，并把剩下的钱还给他。

请问在最优情况下，小沃沃最多可以玩多少轮？

假设当前一轮小沃沃投入了 $x$ 块钱，那么他可以收回$ ?x\times (100?p)/100 ? $块钱，其中 $?a?$ 表示 $a$ 取下整。

小沃沃每一轮投入的钱不能超过他现在拥有的钱。

每一轮投入的钱必须为整数。

分析

那就是每一次就丢 $m$ 块钱进去，除了最后一次之外，每一次丢的实际钱数其实是 $m$ 减去返回的钱数。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        if(n<m){
            printf("0\n");
            continue;
        }
        int x=ceil(m*p*1.0/100);
        //返回的钱是向下取整，那丢出去的钱就是想上取整
        printf("%d\n",(n-m)/x+1);
    }
    return 0;
}

Distance

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6776

题意

给出一堆点到固定点的距离，问所有给出的点两两之间距离之和。

分析

自然是把所有点放到一条线上和最短。

但是题目数据范围是 $10^5$ 用 $O(n^2)$的方法是不行的。

我们可以用前缀和解决这个题目。把所有的距离按从小到大排好,用 $arr$ 数组存放数据，用 $sum$ 数组记录前缀和。

我们不需要重复记录两个点之间的距离，所有我们假定从最大的开始计算。

\[\sum_{i=1}^{n-1}dis[n,i]=arr[n]\times(n-1)-sum[n-1] \]

这样我们就可以用$O(n)$复杂度实现了。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;
long long arr[MAXN];
long long sum[MAXN];
int n;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",arr+i);
        sort(arr+1,arr+1+n);
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+arr[i];
        long long res=0;
        for(int i=n;i;i--)res+=(i-1)*arr[i]-sum[i-1];
        printf("%lld\n",res);
    }
    return 0;
}

Covid

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6777

题意

有 $n$ 个人，会在不同时刻出现在不同位置，其中 $1$ 号人物是感染者，在同一时间同一地点一起出现的人会被感染者感染，问最后哪些人感染了。

分析

我们可以用时间作为第一关键字，地点作为第二关键字排序，在循环一遍看看哪些人是在同一时间同一地点出现了，把这些人存放在一个$vector$ 里面，如果出现了感染者就全部感染，否则就清空。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXM=2e5+10;
const int MAXN=2e4+10;
int vis[MAXN];
struct node{
    int t,p;
    int id;
    bool operator<(const node a)const {
        return t==a.t?p<a.p:t<a.t;
        //以时间为第一关键字，地点为第二关键字排序
    }
}arr[MAXM];
int cnt;
int n;
vector<int>tem;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        cnt=1;
        scanf("%d",&n);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++){
            int m;
            scanf("%d",&m);
            while(m--){
                scanf("%d%d",&arr[cnt].t,&arr[cnt].p);
                arr[cnt].id=i;
                cnt++;
            }
        }
        arr[0].t=0,arr[0].p=0,arr[0].id=1;
        sort(arr,arr+cnt);
        tem.clear();
        int f=0;
        vis[1]=1;
        for(int i=1;i<cnt;i++){
            if(arr[i].t==arr[i-1].t&&arr[i].p==arr[i-1].p)tem.push_back(arr[i].id);
            //同一时间同一地点的人加到tem
            else {
                if(f){
                    //存在感染者则全部感染
                    for(auto x:tem)vis[x]=1;
                    f=0;
                }
                tem.clear();//清空
                tem.push_back(arr[i].id);
            }
            if(vis[arr[i].id])f=1;
        }
        if(f)for(auto x:tem)vis[x]=1;
        tem.clear();
        for(int i=1;i<=n;i++)
            if(vis[i])tem.push_back(i);
        //因为最后不能有空格，比赛的时候没咋考虑写法就写成这样了，其实就是输出
        for(int i=0;i<tem.size();i++){
            if(i==tem.size()-1)printf("%d",tem[i]);
            else printf("%d ",tem[i]);
        }
        printf("\n");
    }
    return 0;
}

Car

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6778

题意

给一堆车牌，可以对最后一位进行限制通行，每个尾号最多限制一次，问五天内哪种限制方法的单日最高可通行车辆数最少。

分析

发现尾号最多就 $0-9$ 就这么十个数字，那对于每天限制哪些我们可以通过全排列枚举。

但是另一个限制就是，怎么分配每天限制的尾号数量，毕竟不能一天把所有尾号都限行或者平均分。

每天分配的限制其实就只有7种情况。

周一	周二	周三	周四	周五
1	1	1	1	6
1	1	1	2	5
1	1	1	3	4
1	1	2	2	4
1	1	2	3	3
1	2	2	2	3
2	2	2	2	2

那么我们在全排列的时候分别求这其中情况下的最值就行了。

注意，对于周一限制尾号$1$，周二限制尾号$2$，周三限制尾号$3$，周四限制尾号$4$，周五限制尾号$5,6,7,8,9,0$，和周一限制尾号$5,6,7,8,9,0$，周二限制尾号$2$，周三限制尾号$3$，周四限制尾号$4$，周五限制尾号$1$，应当看成一种情况，所以只存在上面的7种情况。最后900ms压线过。

离谱代码

感觉里面套个循环有点不好写就直接。。。

#include <bits/stdc++.h>
using namespace std;

int arr[10]={0,1,2,3,4,5,6,7,8,9};
int sum[15];
int n;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(sum,0,sizeof sum);
        char str[10];
        for(int i=0;i<n;i++)scanf("%s",str),sum[str[4]-‘0‘]++;
        int res=1e9;
        do{
            int ans=0;
            ans=max(ans,n-sum[arr[0]]);
            ans=max(ans,n-sum[arr[1]]);
            ans=max(ans,n-sum[arr[2]]);
            ans=max(ans,n-sum[arr[3]]);
            ans=max(ans,n-sum[arr[4]]-sum[arr[5]]-sum[arr[6]]-sum[arr[7]]-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
            ans=0;
            ans=max(ans,n-sum[arr[0]]);
            ans=max(ans,n-sum[arr[1]]);
            ans=max(ans,n-sum[arr[2]]);
            ans=max(ans,n-sum[arr[3]]-sum[arr[4]]);
            ans=max(ans,n-sum[arr[5]]-sum[arr[6]]-sum[arr[7]]-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
            ans=0;
            ans=max(ans,n-sum[arr[0]]);
            ans=max(ans,n-sum[arr[1]]);
            ans=max(ans,n-sum[arr[2]]);
            ans=max(ans,n-sum[arr[3]]-sum[arr[4]]-sum[arr[5]]);
            ans=max(ans,n-sum[arr[6]]-sum[arr[7]]-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
            ans=0;
            ans=max(ans,n-sum[arr[0]]);
            ans=max(ans,n-sum[arr[1]]);
            ans=max(ans,n-sum[arr[2]]-sum[arr[3]]);
            ans=max(ans,n-sum[arr[4]]-sum[arr[5]]);
            ans=max(ans,n-sum[arr[6]]-sum[arr[7]]-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
            ans=0;
            ans=max(ans,n-sum[arr[0]]);
            ans=max(ans,n-sum[arr[1]]-sum[arr[2]]);
            ans=max(ans,n-sum[arr[3]]-sum[arr[4]]);
            ans=max(ans,n-sum[arr[5]]-sum[arr[6]]);
            ans=max(ans,n-sum[arr[7]]-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
            ans=0;
            ans=max(ans,n-sum[arr[0]]-sum[arr[1]]);
            ans=max(ans,n-sum[arr[2]]-sum[arr[3]]);
            ans=max(ans,n-sum[arr[4]]-sum[arr[5]]);
            ans=max(ans,n-sum[arr[6]]-sum[arr[7]]);
            ans=max(ans,n-sum[arr[8]]-sum[arr[9]]);
            res=min(ans,res);
        }while(next_permutation(arr,arr+10));
        printf("%d\n",res);
    }
    return 0;
}

Solo

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6781

题意

-.- 太长就不赘述了。

分析

一开始以为是贪心，能比bob快就做，不能就跳。结果连样例都过不了。。

这种题目贪心不行自然就想DP了。

定义 $DP[i][j]$ ，表示在前 $i$ 题中做出来 $j$ 题用的时间。初始化为$10^{18}$

因为bob是顺序做题的，而题目给出的条件可以保证bob每一题都做，且每一题的时间都花完，那么我们可以用 $sum[i]$ 表示bob做完前 $i$ 题用的时间。用 $arr[i]$ 表示alice单独做第 $i$ 题的时间。

那么转移方程就是

\[if(i>j)dp[i][j]=min(dp[i][j],dp[i-1][j]);\\if(arr[i]+dp[i-1][j-1]<=sum[i])dp[i][j]=min(dp[i][j],arr[i]+dp[i-1][j-1]); \]

如果尝试的题目大于做出来的题目时，我们可以从前一题同样做出来 $j$ 题的情况转移过来。

如果当前题目能做出来，则判断做这道题能否更快。

最后看在尝试 $n$ 题的情况下，$dp[n][i]!=10^{18}$ 当做 $i$ 的最大值就是答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e3+10;
long long arr[MAXN],brr[MAXN],sum[MAXN];
long long dp[MAXN][MAXN];
const long long INF=1e18;
int n;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",arr+i);
        for(int i=1;i<=n;i++)scanf("%lld",brr+i),sum[i]=sum[i-1]+brr[i];
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)dp[i][j]=INF;
        for(int i=0;i<=n;i++)dp[i][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(i>j)dp[i][j]=min(dp[i][j],dp[i-1][j]);
                if(arr[i]+dp[i-1][j-1]<=sum[i])dp[i][j]=min(dp[i][j],arr[i]+dp[i-1][j-1]);
            }
        }
        for(int i=n;i>=0;i--){
            if(dp[n][i]!=INF){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

2020 年百度之星程序设计大赛初赛二部分题解

原文：https://www.cnblogs.com/jianjinxiani/p/13380855.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)