USACO 2015 December Contest,Gold

Posted by

Problem 1.High Card Low Card G

题目链接:https://www.luogu.org/problemnew/show/P4816 使用田忌赛马的思路。由于前(n>>1)轮是比大的,那我们在处理本方卡片时选择倒序存储,才能保证最优。然后将对方前(n>>1)张按倒序排序。若本方最大值大于对方的最大值,则双方抵消,否则牺牲最小的一张。后半部分思路相同,在此不再赘述。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=50050;
using namespace std;
int n,ans,num,a[MAXN<<1],b[MAXN<<1];
bool vis[MAXN<<1];
inline bool cmp(int a,int b){
    return a>b;
}
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 int solve(int l1,int r1,int l2,int r2,int kind){
    int ans=0;
    while(l1<=r1&&l2<=r2){
        if(kind==1){
            if(a[l1]<b[l2]) l1++,l2++,ans++;
            else l1++,r2--;
        }
        else{
            if(a[l1]>b[l2]) l1++,l2++,ans++;
            else l1++,r2--;
        }
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),vis[a[i]]=1;
    for(int i=(n<<1);i>=1;i--){
        if(!vis[i]) b[++num]=i;
    }
    sort(a+1,a+(n>>1)+1,cmp);
    sort(a+(n>>1)+1,a+n+1);
    sort(b+(n>>1)+1,b+n+1);
    printf("%d\n",solve(1,(n>>1),1,(n>>1),1)+solve((n>>1)+1,n,(n>>1)+1,n,2));
    return 0;
}

Problem 2.Fruit Feast

题目链接:https://www.luogu.org/problemnew/show/P4817 思路:爆搜即可。加个记忆化才能保证不超时。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int t,a,b,ans;
bool vis[5000005];
void dfs(int now,bool used){
    if(now>t) return ;
    if(vis[now]) return ;
    vis[now]=1;
    ans=max(ans,now);
    dfs(now+a,used);
    if(!used) dfs(now>>1,1);
    dfs(now+b,used);
    ans=max(ans,now);
}
int main(){
    scanf("%d %d %d",&t,&a,&b);
    dfs(0,0);
    printf("%d\n",ans);
    return 0;
}

Problem 3.Bessie’s Dream

题目链接:https://www.luogu.org/problemnew/show/P4818 思路:坑了我许久。 大搜索。因为允许多次在可行的情况下走过一个点,所以在这里我们记录状态,若当前状态未出现过则继续搜索。 本题使用STL queue,因为枚举次数不宜确定,手写导致我wa了许多次。队列结构体维护坐标,方向,橙子味,距离。当a[x][y]==4时,不同的方向会造成不同的结果,所以要记录方向。剩下就不再赘述了。 搜索过程中不用使用判重数组的原因是边界外的点的值是0,与红色格子的值相同。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <queue>
static const int MAXN=1050;
static const int dirx[]={1,-1,0,0};
static const int diry[]={0,0,1,-1};
using namespace std;
struct node{
    int x,y,d,ora,dis;
};
queue<node> q;
int n,m,head,tail,a[MAXN][MAXN];
bool vis[MAXN][MAXN][2][5];
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 y){
    return (x<1||y<1||x>n||y>m)?true:false;
}
inline int bfs(){
    q.push((node){1,1,0,0,0});
    while(!q.empty()){
        node now=q.front();q.pop();
        int x=now.x,y=now.y,d=now.d,ora=now.ora,dis=now.dis;
        bool flag=0;
        if(vis[x][y][ora][d]) continue;
        vis[x][y][ora][d]=1;
        if(x==n&&y==m) return dis;
        if(a[x][y]==4){
            int dx=x+dirx[d],dy=y+diry[d];
            if(!a[dx][dy]||a[dx][dy]==3);
            else if(a[dx][dy]==1||a[dx][dy]==4) q.push((node){dx,dy,d,0,dis+1}),flag=1;
            else q.push((node){dx,dy,d,1,dis+1}),flag=1;
        }
        if(a[x][y]==4&&flag) continue;
        for(int i=0;i<4;i++){
            int dx=x+dirx[i],dy=y+diry[i];
            if(!a[dx][dy]||(a[dx][dy]==3&&!ora)) continue;
            else if((a[dx][dy]==3&&ora)||a[dx][dy]==1||a[dx][dy]==4) q.push((node){dx,dy,i,ora,dis+1});
            else if(a[dx][dy]==2) q.push((node){dx,dy,i,1,dis+1});
        }
    }
    return -1;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
        }
    }
    printf("%d\n",bfs());
    return 0;
}
  ]]>

Leave a Reply

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