首页 > 代码库 > 周一训练赛题解

周一训练赛题解

这次完全是水题大集合啊,希望大家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;}
View Code

 

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;}
View Code

 

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;}
View Code

 

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;}
View Code