首页 > 代码库 > Topcoder SRM 147

Topcoder SRM 147

Div2 600 PeopleCircle

题意:略

题解:暴力模拟

#line 2 "PeopleCircle.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;int dp[60];int n;char ans[60];inline void inc(int& pos){    pos=(pos+1)%n;}class PeopleCircle{    public:    string order(int numMales, int numFemales, int K)    {        n=numMales+numFemales;        int cur=-1;        memset(dp,0,sizeof(dp));        for (int i=1;i<=numFemales;++i)        {            for (int j=1;j<=K;++j)            {                inc(cur);                while (dp[cur]) inc(cur);            }            dp[cur]=1;            printf("%d\n",cur);        }        for (int i=0;i<=n-1;++i)        {            if (dp[i]) ans[i]=F;            else ans[i]=M;        }        return ans;    }};#ifdef exint main(){    #ifdef ex1    freopen ("in.txt","r",stdin);    #endif}#endif

 

Div2 950 GoldenChain

题意:略

题解:二分答案再判断,判断时选择贪心地剪长度短的sections。

#line 2 "GoldenChain.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;LL sum[60];int n;bool check(int num){    int p=upper_bound(sum+1,sum+1+n,num)-sum-1;    if (n-p<=num) return true;    else return false;}class GoldenChain{    public:    int minCuts(vector <int> sections)    {        n=sections.size();        sort(sections.begin(),sections.end());        sum[0]=0;        for (int i=1;i<=n;++i)        {            sum[i]=sum[i-1]+sections[i-1];        }        LL lb=0;        LL ub=INT_MAX;        while (ub-lb>1)        {            int mid=(lb+ub)>>1;            if (check(mid)) ub=mid;            else lb=mid;        }        return ub;    }};#ifdef exint main(){    #ifdef ex1    freopen ("in.txt","r",stdin);    #endif}#endif

 

Topcoder SRM 147