周一训练赛题解

这次完全是水题大集合啊，希望大家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
",ans);
    }
    return 0;
}

View Code

#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 ",ans); } return 0; }

#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 ",hehe,dp[n][k][0]+dp[n][k][1]); } return 0; }

#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 ",ans*2-1); } return 0; }

相关推荐