USACO 2017 January Contest,Silver

Posted by

Problem 1.Cow Dance Show

题目链接:https://www.luogu.org/problemnew/show/P3611 思路: 由题,k越大,则T越小,显然满足单调性。 考虑使用二分,二分k的取值,如果满足二分条件则试图减小范围,反之亦然。 对于二分条件,则为当前时间的最优值是否小于规定时间最大值。 对于计算当前时间的最优值,考虑使用优先队列来维护,利用小根堆的性质,每次取出最小的,累加答案。 对于已经跳完舞的牛,如果考虑出队再入队新的牛,时间可能承受不起,故直接入队当前结果+即将上台的牛要跳的时间,维护总值。然后统计答案即可。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <queue>
static const int MAXN=10050;
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,mid,ans,tmax,l,r,a[MAXN];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline bool check(int x){
    int ans=0;
    for(int i=1;i<=x;i++) q.push(a[i]);
    for(int i=x+1;i<=n;i++){
        int now=q.top();q.pop();
        if(now+a[i]>tmax) return false;
        q.push(now+a[i]);
    }
    while(!q.empty()){
        int now=q.top();q.pop();
        ans=max(ans,now);
    }
    return ans<=tmax;
}
int main(){
    n=read();tmax=read();
    for(int i=1;i<=n;i++) a[i]=read();
    l=1,r=n,ans=n;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

Problem 2.Hoof, Paper, Scissor

题目链接:https://www.luogu.org/problemnew/show/P3609 思路: 经典的dp题。 设f[i][j][k]表示第i轮,第 j种手势,用了k次转换时的最优解。 首先预处理res数组,为每种手势时的得分情况。输入时处理每种手势对应的数字。 具体细节代码见:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int res[3][3]={{0,1,0},{0,0,1},{1,0,0}};
static const int MAXN=100050;
static const int MAXK=25;
using namespace std;
int n,K,ans,ins[MAXN],f[MAXN][4][MAXK];
char opt[2];
int main(){
    scanf("%d %d",&n,&K);
    for(int i=1;i<=n;i++){
        scanf("%s",opt);
        if(opt[0]=='H') ins[i]=0;
        else if(opt[0]=='P') ins[i]=2;
        else ins[i]=1;
    }
    for(int i=0;i<3;i++) f[1][i][0]=res[i][ins[1]];
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<=K;k++){
                f[i][j][k]=f[i-1][j][k];
                if(k){
                    for(int l=0;l<3;l++) f[i][j][k]=max(f[i][j][k],f[i-1][l][k-1]);
                }
                f[i][j][k]+=res[j][ins[i]];
            }
        }
    }
    for(int j=0;j<3;j++){
        for(int k=0;k<=K;k++)
          ans=max(ans,f[n][j][k]);
    }
    printf("%d\n",ans);
    return 0;
}

Problem 3.Secret Cow Code

题目链接:https://www.luogu.org/problemnew/show/P3612 思路: 不难发现,每次要添加的字符串的第一个字符为原字符串的最后一个字符,每次构建出来的新的字符串的长度为原字符串两倍。这里的“原”指的是相对含义。 因此我们可以使用倒推的方法,每次把n减去小于n的最大长度,循环维护这个最大长度,如果n0,则让n等于现在字符串的长度,直到n<len(s)s为题目中给出的最初的字符串,输出s[n-1]即可。 代码:
#include <cstdio>
#include <cctype>
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
string s;
int len;
ll n,l;
int main(){
    ios::sync_with_stdio(false);
    cin>>s>>n;
    len=s.length();
    while(n>len){
        l=len;
        while(n>(l<<1)) l<<=1;
        n-=(l+1);
        if(n==0) n=l;
    }
    printf("%c",s[n-1]);
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注