6.19noip模拟赛总结
2018-06-21 06:51:15来源:未知 阅读 ()
昨天进行了noip的模拟赛,我这个蒟蒻又是垫底....
T1
第一感觉就是贪心,从高到低排序,然后每次都将恰好满足当前条件的人数分成一组,然后移动到下一个未分组的单位上,贴代码
#include<bits/stdc++.h> using namespace std; const int N=1110000; int d[N],ans; bool cmp(int a,int b) { return a>b; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]); sort(d+1,d+1+n,cmp); int pos=1; while(pos!=n+1) { ans++; pos+=d[pos]; } printf("%d\n",ans); }
只能拿80分,存在反例 4 4 4 4 3 1 1 1 ,贪心的话得到3,最优解是4,所以这样贪心是有问题的,老师说贪心可以过,但我不会写....
正解是dp,从小到大排序,对于每个i,都可以与包括他的前面的d[i]个人分为一组,所以定义dp[i]为满足前i个人条件所能构成队伍数量的最大值,得到转移式:dp[i]=max{dp[j],0<j<=i-d[i]}+1
但这样的话有两层循环,时间复杂度是n的平方,而数据范围为10^6,会超时,所以要优化一下,大概就是保证dp[i] 为dp[1]到dp[i] 的最大值,然后就可以省去枚举j,贴代码
#include<bits/stdc++.h> using namespace std; const int N=1110000; int d[N],dp[N]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]); sort(d+1,d+1+n); for(int i=1;i<=n;i++) { if(i>=d[i]) dp[i]=dp[i-d[i]]+1; dp[i]=max(dp[i],dp[i-1]); } printf("%d\n",dp[n]); return 0; }
T2
我写的dfs...然后莫名RE...
有同学写的bfs,也非常易懂,不会出现爆栈的危险,但最后几个点超时
#include <bits/stdc++.h> using namespace std; int n; struct node{ int l,r,t; }; queue <node>q; int main(){ scanf("%d",&n); node temp,x1,x2; temp.l=1;temp.r=1;temp.t=0; q.push(temp); while(!q.empty()){ temp=q.front(); q.pop(); if((temp.l+temp.r)==n) { printf("%d",temp.t+1); return 0; } if((temp.l+temp.r)<n){ x1.l=temp.l+temp.r;x1.r=temp.r;x1.t=temp.t+1; q.push(x1); x2.l=temp.l;x2.r=temp.l+temp.r;x2.t=temp.t+1; q.push(x2); } } return 0; }
可以发现,对于一个数对(a,b),当a>b时,可由(a-b,b)得到;当a<b时,可由(a,b-a)得到;当a=b时,不可能由(1,1)变换得到;
所以我们可以倒着推,设T(a,b)为从(1,1)变换成(a,b)所需要的次数,在a/b时,有T(a,b)=T(b,a%b)+a/b,所以可以剪枝
答案为min{T(n,i),0<i<=n}
代码
#include<bits/stdc++.h> using namespace std; int check(int a,int b) { if(b==1)return a-1; if(!b) return 1e8; return a/b+check(b,a%b); } int main() { int n,ans=1e8; scanf("%d",&n); for(int i=1;i<=n;i++) ans=min(check(n,i),ans); printf("%d\n",ans); return 0; }
T3
待编辑
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 非常详细的 Linux C/C++ 学习路线总结!已拿腾讯offer 2020-03-29
- 生产者消费者算法模拟 c++ 2020-03-29
- [C++]HelloWorld背后的故事!总结一下在我们运行exe可执行文 2020-03-27
- 线段树学习资料 2020-03-19
- C语言指针学习总结 2020-02-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash