GDUT 寒假排位赛一_dfs简单签到题c++-程序员宅基地

技术标签: GDUT集训  

感想:过个年10多天没刷题,一开始连签到题都不是很顺利,而且一开始作死开了D题,结果全场有D,F两道题没人过,结果排在了3题尾,哭死。但这不是理由,最重要的原因是自己菜,而且寒假第一阶段所学的知识点还不会运用,因为寒假第一阶段是专题训练,每道题都有说考察什么知识点,而且这次排位赛E题考二分,我却想不到二分做,I题考优先队列,我却一直卡在那里,一直想模拟过程,B题考DP,我却一直想贪心,根本没有想到状态转移,C题却嫌麻烦,不想模拟,所以放弃。最终只做完三道签到题,被rank1差点7题的lyr大佬无情的锤爆
总而言之,题还是刷的比较少,不懂得系统的总结加以应用,好多只知道知识点,却不会应用到题目中去
题目链接】:http://codeforces.com/group/NVaJtLaLjS/contest/238166

A.The Bucket List(签到题)
题意:给定N只奶牛,每只奶牛开始挤奶时间以及结束时间分别为s与t,以及每只奶牛在挤奶时间需要b只桶,问最多需要多少只桶?
思路:(由于题目数据1<= s,t <=1000,且保证在某个时刻只有一只奶牛开始挤奶或者结束挤奶,所以直接暴力就行)
复杂度O(1000)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1005],b[1005];
int main()
{
   
    
    int n,s,e,c;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
   
    
        cin>>s>>e>>c;
        a[s]=b[e]=c;
    }
    int cnt=0,tmp=0,i;
    for(i=1;i<=1000;i++)
    {
   
    
        if(a[i]){
   
    
            if(a[i]<=tmp)
            tmp-=a[i];
            else{
   
    
            cnt+=(a[i]-tmp);
            tmp=0;
            }
        }
        if(b[i])
        {
   
    
            tmp+=b[i];
        }
    }
    cout<<cnt<<endl;
    return 0;
}

B. Teamwork(dp)
题意: 给定n只奶牛,每只奶牛有一个技能点,把1-n只奶牛连续分成多组,每组奶牛不超过k只,每只奶牛只能存在一组,且该组的奶牛技能点都会升高到与组里某只奶牛最高技能点一样,如何分配,求得n只奶牛总的技能点最大
思路: dp,dp[i]表示前i只奶牛总的最大技能点,而且第i只奶牛会会受到前面k只奶牛影响,复杂度O(n*k)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10005],dp[10005];
int main()
{
   
    
    int n,k;
    ll sum=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
   
    
        int maxx=-1;
        for(int j=1;j<=min(i,k);j++)
        {
   
    
            maxx=max(maxx,a[i-j+1]);
            dp[i]=max(dp[i],dp[i-j]+maxx*j);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

C. Mooyo Mooyo(联通块dfs+简单模拟)
题意: 有点类似于消消乐,如果相邻同颜色的超过k块,就消去,消完后,若底下为空,由于重力会掉下去,问最后无法可消去后的方阵
思路: 先dfs一次求得各自相邻同颜色的方块数,若是满足>=k,则再dfs一次消去,接着模拟掉落过程,记住在地图mp[ ][ ]最底层为第n行,而不是第0行,模拟时不要写错,重复以上操作,直到符合条件结束循环

#include<bits/stdc++.h>
using namespace std;
char mp[105][15],vis[105][15];
int n,k,cnt;
int dis[4][2]=
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42819598/article/details/87517461

智能推荐

SQL创建默认值语句(CREATE DEFAULT)-程序员宅基地

文章浏览阅读5.8k次。微软的解释:创建称为默认值的对象。当绑定到列或别名数据类型时,如果插入时没有显式提供值,则默认值将指定一个值,以便将其插入该对象所绑定的列中(或者,如果是别名数据类型,则插入所有列中)。后续版本的 Microsoft SQL Server 将删除该功能。请避免在新的开发工作中使用该功能,并着手修改当前还在使用该功能的应用程序。语法 ..._sql declare default

Linux分区格式化实训操作说明_sdb7这个分区的具体含义-程序员宅基地

文章浏览阅读2.2k次。首先介绍一下背景知识:Linux主分区,扩展分区,逻辑分区的联系和区别Linux硬盘分区有三种,主磁盘分区、扩展磁盘分区、逻辑分区。一个硬盘主分区至少有1个,最多4个,扩展分区可以没有,最多1个。且主分区+扩展分区总共不能超过4个。逻辑分区可以有若干个。在linux下主分区和逻辑分区都可以用来放系统,引导os开机。分出主分区后,其余的部分可以分成扩展分区,一般情况是剩余磁盘空间全部配成扩展分区,..._sdb7这个分区的具体含义

[转载]答《漫话ID》中的疑问:UniqueID和ClientID的来源-程序员宅基地

文章浏览阅读47次。在《漫话ID》一文中,作者提出了一个问题:为什么在ItemCreated事件中访问ClientID会导致MyButton无法响应事件,事实上 MyButton无法响应事件是因为他在客户端的ID被改变了,而此文从UniqueID和ClientID入手,进行较为深入的探讨,展示 UniqueID和ClientID是如何生成的,在何时生成,并同时解答《漫话ID》一文中作者的疑问。为什么有U..._clientld在c语言中是什么意思

python编程:从入门到实践习题第六章6-1~6-11*_人:在为完成练习6-1-程序员宅基地

文章浏览阅读3.3k次。6-1 人:使用一个字典来存储一个熟人的信息,包括名、姓、年龄和居住的城市。 该字典应包含键 first_name、last_name、age 和 city。将存储在该字典中的每项信息都 打印出来。 people={'first_name':'Alan','last_name':'Walker','age':28,'city':'Daqing'} print(people)6-2..._人:在为完成练习6-1

Lombok 妙用之 @RequiredArgsConstructor 注解_@requiredargsconstructor(onconstructor = @__(@reso-程序员宅基地

文章浏览阅读4.6k次,点赞3次,收藏14次。Lombok 妙用之 @RequiredArgsConstructor 注解,丢掉 @Autowired,@Resource 让代码更简洁。_@requiredargsconstructor(onconstructor = @__(@resource))

Diff/Patch 工具的使用 分类: 嵌入式开发学习 ...-程序员宅基地

文章浏览阅读95次。补丁Patch是天才程序员、Perl的发明者LarryWall发明的,它应高效地交流程序源代码之需求而生,随着以Linux为代表的开发源代码运行的蓬勃发展,patch这个概念已经成为开放源代码发起者、贡献者和参与者的集体无意识的一部分。patch只包含了对源代码修改的部分,这对于开放源代码社区的协同开发模式具有重要意义,意味的软件新版本的发布和对软件的缺陷或改进可以以更小的文件发布,可以..._patch 嵌入式

随便推点

java ocr技术--tesseract-ocr:使用jTessBoxEditor制作训练库_jtessboxeditor训练英文和数字结合的图片-程序员宅基地

文章浏览阅读1.8k次,点赞4次,收藏18次。几个常见的问题:问题一:相关的几个软件下载地址Tesseract:Index of /tesseractjTessBoxEditor: VietOCR - Browse /jTessBoxEditor at SourceForge.net问题二:jTessBoxEditor下载是注意一下,中文的话要下载jTessBoxEditorFX问题三:mftraining执行时提示停止工作,一般是Tesseract版本的问题,可以选择Tesseract3验证过是好的,Tesser._jtessboxeditor训练英文和数字结合的图片

天平称重,进制转换解法_天平称重(进制解法) python-程序员宅基地

文章浏览阅读302次。题目:用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有5个砝码,重量分别是1,3,9,27,81则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。本题目要求编程实现:对用户给定的重量,给出砝码组合方案。例如:用户输入:5程序输出:9-3-1用户输入:19程序输出:27-9+1要求程序输出的组合总是大数在前小数在后。可以假设用户的输入的数字符合范围1~121。思路:观察输出,都是3的多少次方,所以我们可以把输入的值,转换成3进制的_天平称重(进制解法) python

druid-1.1.21.jar-程序员宅基地

文章浏览阅读954次。链接:https://pan.baidu.com/s/1w5_GTiWuAR_X2t8J7JIP4Q提取码:a0u1_druid-1.1.21.jar

pthread_spinlock_t与pthread_mutex_t性能对比_pthread 性能 效率-程序员宅基地

文章浏览阅读8k次。看到一篇pthread_spinlock_t与pthread_mutex_t性能对比做的非常细致的博客,记录下来原文在此:http://www.cnblogs.com/diyunpeng/archive/2011/06/07/2074059.html_pthread 性能 效率

mysql innodb与myisam存储文件的区别-程序员宅基地

文章浏览阅读1.1k次。myisam:.frm: 存储表定义.myd(MYData):存储数据.MYI(MYindex):存储引擎innodb:.frm:存储表定义.idb:存储数据和索引,在同一个文件中_innodb和mylsam生成文件的区别

poj2773 —— 二分 + 容斥原理 + 唯一分解定理-程序员宅基地

文章浏览阅读868次。题目链接:http://poj.org/problem?id=2773Happy 2006Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 12023 Accepted: 4256DescriptionTwo positive int_poj2773