USACO 2015 December Contest,Silver

Posted by

Problem 1.Switching on the Lights

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4395 思路: 对于储存暴力选用二维vector+pair。 考虑使用广搜。对于队列中的点,如果周围存在已经被点亮但还未入过队,则将其入队。然后再尝试扩充这个点,如果能将其他灯点亮,统计答案;然后再判断这个新被点亮的灯周围如果有被点亮的灯,则代表可以通过其他周围的灯到达这里,则入队。 之前WA了好几次的原因就是没考虑到最后一种情况。尝试修复bug但似乎写法不太优秀。 代码:
#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
static const int MAXN=150;
static const int dirx[10]={0,1,0,-1};
static const int diry[10]={1,0,-1,0};
using namespace std;
vector<pair<int,int> > vec[MAXN][MAXN];
struct node{
    int x,y;
}q[100050];
int head,tail,ans,n,m,x1,y1,x2,y2;
bool vis[MAXN][MAXN],in[MAXN][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 y){return (x<1||x>n||y<1||y>n)?true:false;}
inline bool check1(int x,int y){
    for(int i=0;i<4;i++) if(in[x+dirx[i]][y+diry[i]]) return true;
    return false;
}
inline void bfs(){
    q[head]=(node){1,1};
    in[1][1]=1;vis[1][1]=1;
    ans=1;
    while(head<=tail){
        node now=q[head];head++;
        for(int i=0;i<4;i++){
            int dx=now.x+dirx[i],dy=now.y+diry[i];
            if(check(dx,dy)||in[dx][dy]) continue;
            if(vis[dx][dy]) in[dx][dy]=1,q[++tail]=(node){dx,dy};
        }
        for(vector<pair<int,int> >::iterator it=vec[now.x][now.y].begin();it!=vec[now.x][now.y].end();it++){
            int nx=(*it).first,ny=(*it).second;
            if(in[nx][ny]||vis[nx][ny]) continue;
            vis[nx][ny]=1;ans++;
            if(check1(nx,ny)) in[nx][ny]=1,q[++tail]=(node){nx,ny};
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        x1=read();y1=read();x2=read();y2=read();
        vec[x1][y1].push_back(make_pair(x2,y2));
    }
    bfs();
    printf("%d\n",ans);
    return 0;
}

Problem 2.High Card Wins

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4396 思路:贪心。每次使用比对手牌大且最小的牌。于是在O(2n)的循环中判断如果此时还有牌直接统计答案即可。(因为循环是从大到小的)。 此题似乎可以使用并查集解决,或者田忌赛马的思路也可以? 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=100050;
using namespace std;
int n,num,ans,b[MAXN];
bool vis[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;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) b[i]=read(),vis[b[i]]=1;
    for(int i=1;i<=(n<<1);i++){
        if(vis[i]) num++;
        else{
            if(num) ans++,num--;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Problem 3.Breed Counting

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4397 思路:区间问题,线段树维护即可。 考虑更优秀的写法,前缀和。每次直接查询更快。 在此两种写法都会呈现: 代码1:线段树
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#define ls p<<1
#define rs p<<1|1
static const int MAXN=100050;
using namespace std;
int n,q,x,ql,qr,ans1,ans2,ans3;
struct node{
    int c1,c2,c3;
}a[MAXN<<2];//此题中开2倍空间会RE,所以开大点
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;
}
struct Segment_Tree{
    inline void push_up(int p){
        a[p].c1=a[ls].c1+a[rs].c1;
        a[p].c2=a[ls].c2+a[rs].c2;
        a[p].c3=a[ls].c3+a[rs].c3;
    }
    void build(int p,int l,int r){
        if(l==r){
            x=read();
            if(x==1) a[p].c1=1;
            else if(x==2) a[p].c2=1;
            else a[p].c3=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(p);
    }
    void query(int p,int l,int r){
        if(ql<=l&&qr>=r){
            ans1+=a[p].c1;
            ans2+=a[p].c2;
            ans3+=a[p].c3;
            return ;
        }
        int mid=(l+r)>>1;
        if(ql<=mid) query(ls,l,mid);
        if(qr>mid) query(rs,mid+1,r);
    }
}Tree;
int main(){
    n=read();q=read();
    Tree.build(1,1,n);
    for(int i=1;i<=q;i++){
        ql=read();qr=read();
        Tree.query(1,1,n);
        printf("%d %d %d\n",ans1,ans2,ans3);
        ans1=ans2=ans3=0;
    }
    return 0;
}
代码2:前缀和
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
static const int MAXN=100050;
using namespace std;
int n,q,x,l,r,f[5][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;
}
int main(){
    n=read();q=read();
    for(int i=1;i<=n;i++){
        x=read();
        f[1][i]=f[1][i-1];
        f[2][i]=f[2][i-1];
        f[3][i]=f[3][i-1];
        f[x][i]++;
    }
    for(int i=1;i<=q;i++){
        l=read();r=read();
        printf("%d %d %d\n",f[1][r]-f[1][l-1],f[2][r]-f[2][l-1],f[3][r]-f[3][l-1]);
    }
    return 0;
}
]]>

Leave a Reply

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