首页 > 代码库 > 周一训练赛题解
周一训练赛题解
这次完全是水题大集合啊,希望大家A的开心;
前两个题是我找的,后两个是陶叔找的,另外因为我的偷懒,下面所有的代码都是陶叔亲自写的,十分感谢陶叔;
陶叔暑假为了大家的集训,牺牲了很多自己宝贵的时间,大家接下来要好好训练啊!!!!
废话少说,进入正题:
Problem A SPOJ QUEST5
签到题:
将所有的边按照右端点排个序,然后每次选择没有钉住的点,然后把这之后的所有与它相交的边全去掉;
代码:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 10100;struct Table{ int l,r; bool operator < (const Table &rhs) const{ return r < rhs.r; }}table[maxn];int main(){ int kase,n; scanf("%d",&kase); while(kase--){ scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%d%d",&table[i].l,&table[i].r); } sort(table,table+n); int ans = 0,r = -1; for(int i = 0;i < n;i++){ if(r < table[i].l){ ans++; r = table[i].r; } } printf("%d\n",ans); } return 0;}
Problem B SPOJ FAVDICE
数学题,也是给大家YY的题,不会只能怪高中老师了~~~
从已经出现i面变成已经出现i+1面的期望投掷次数是N/(N-i)。
代码:
#include <cstdio>int main(){ int kase,n; scanf("%d",&kase); while(kase--){ scanf("%d",&n); double ans = 0; for(int i = 1;i <= n;i++) ans += (n+0.0)/(i+0.0); printf("%.2f\n",ans); } return 0;}
Problem C SPOJ GNYR09F
dp题,dp可能刚刚开始对大家来说比较难,但是静下心来分析还是比较简单的;
dp(i ,j ,k)表示前i个数中,当前累积和为j,末尾数字为k的方案数。
考虑第i个位置的2种情况:
1.放0:dp(i,j,0) = dp(i-1,j,0) + dp(i-1,j,1)
2.放1:dp(i,j,1) = dp(i-1,j,0)
如果还有j>=1,dp(i,j,1) += dp(i-1,j-1,1)
#include <cstdio>#include <cstring>int dp[101][101][2];int main(){ int kase,hehe,n,k; scanf("%d",&kase); while(kase--){ scanf("%d%d%d",&hehe,&n,&k); for(int i = 0;i <= k;i++) dp[1][i][0] = dp[1][i][1] = 0; dp[1][0][0] = dp[1][0][1] = 1; for(int i = 2;i <= n;i++){ for(int j = 0;j <= k;j++){ dp[i][j][0] = dp[i-1][j][0]+dp[i-1][j][1]; dp[i][j][1] = dp[i-1][j][0]; if(k >= 1) dp[i][j][1] += dp[i-1][j-1][1]; } } printf("%d %d\n",hehe,dp[n][k][0]+dp[n][k][1]); } return 0;}
Problem D SPOJ VENOM
二分题,如果有人把它当做暴力题来做,而且执迷不悟,那么欢迎前来和聪哥组队去跑马拉松了~~~
直接二分英雄死亡的时间,然后计算判断即可~~~
代码:
#include <cstdio>typedef long long LL;int H,P,A;bool judge(int n){ LL ans = (LL)(n+1)*n/2*P-(LL)(n-1)*A-H; if(ans >= 0) return 1; return 0;}int main(){ int kase; scanf("%d",&kase); while(kase--){ scanf("%d%d%d",&H,&P,&A); int l = 1,r = 1000000,ans = l; while(l <= r){ int mid = (l+r)>>1; if(judge(mid)) r = mid-1,ans = mid; else l = mid+1; } printf("%d\n",ans*2-1); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。