USACO 2017 February Contest,Gold

Posted by

Problem 1.Why Did the Cow Cross the Road I G

题目链接:https://www.luogu.org/problemnew/show/P3659 思路:考虑把二维坐标转换为点来操作,枚举曼哈顿距离小于3的点,与他们连边,跑一遍最短路。然后考虑终点的问题。枚举能够到终点的点的最小代价,统计即可。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
static const int dirx[]={-1,-2,-3,-1,-2,0,1,2,1,2,3,0,0,1,0,-1};
static const int diry[]={-2,-1,0,2,1,-3,-2,-1,2,1,0,3,1,0,-1,0};
static const int MAXN=100050;
static const int INF=1<<30;
using namespace std;
int n,t,ans=INF,num,a[150][150],head[MAXN],dis[MAXN];
bool vis[MAXN];
struct Edge{
    int to,val,nextt;
}edge[MAXN<<1];
struct node{
    int pos,dis;
    bool operator < (const node &a)const {
        return dis>a.dis;
    }
};
priority_queue<node> q;
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 void addedge(int u,int v,int w){
    edge[++num].to=v;
    edge[num].val=w;
    edge[num].nextt=head[u];
    head[u]=num;
}
inline int change(int x,int y){
    return (x-1)*n+y;
}
inline bool check(int x,int y){
    return (x<1||y<1||x>n||y>n)?true:false;
}
inline void work(int x,int y){
    int u=change(x,y);
    for(int i=0;i<16;i++){
        int dx=x+dirx[i],dy=y+diry[i];
        if(!check(dx,dy)) addedge(u,change(dx,dy),t*3+a[dx][dy]);
    }
}
inline void Dijkstra(){
    for(int i=1;i<=n*n;i++) dis[i]=INF;
    dis[1]=0;
    q.push((node){1,0});
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int x=now.pos;
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=head[x];i;i=edge[i].nextt){
            int to=edge[i].to,val=edge[i].val;
            if(dis[to]>dis[x]+val){
                dis[to]=dis[x]+val;
                if(!vis[to]) q.push((node){to,dis[to]});
            }
        }
    }
}
int main(){
    n=read();t=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=read();
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            work(i,j);
        }
    }
    Dijkstra();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((n<<1)-i-j<3) ans=min(ans,dis[change(i,j)]+((n<<1)-i-j)*t);
        }
    }
    printf("%d\n",ans);
    return 0;
}

Problem 2.Why Did the Cow Cross the Road II G

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4993 思路:使用dp求解。 设f[i][j]表示序列Ai位与序列Bj位的最大匹配。 则:

    \[ f[i][j]=max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+(int)((abs(a[i]-b[j])<=4)))) \]

代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
static const int MAXN=1050;
using namespace std;
int n,a[MAXN],b[MAXN],f[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;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    f[1][1]=(abs(a[1]-b[1])<=4);
    for(int i=2;i<=n;i++){
        f[i][1]=max(f[i-1][1],(int)(abs(a[i]-b[1])<=4));
        f[1][i]=max(f[1][i-1],(int)(abs(a[1]-b[i])<=4));
    }
    for(int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            f[i][j]=max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+(int)(abs(a[i]-b[j])<=4));
        }
    }
    printf("%d\n",f[n][n]);
    return 0;
}

Problem 3.Why Did the Cow Cross the Road III G

题目链接:https://www.luogu.org/problemnew/show/P3660 思路: 考虑使用树状数组来维护。对于所有的数,以左端点排序。这样就保证了a[i]<a[j]。然后累加查询区间和,把右端点放进数组中更新(+1)即可。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=50050;
using namespace std;
struct node{
    int l,r;
}a[MAXN];
int n,x,ans,c[MAXN<<1];
bool vis[MAXN<<1];
inline bool cmp(node a,node b){
    return a.l<b.l;
}
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 lowbit(int x){
    return x&(-x);
}
inline void add(int x,int y){
    for(int i=x;i<=(n<<1);i+=lowbit(i)) c[i]+=y;
}
inline int query(int x){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i)) sum+=c[i];
    return sum;
}
int main(){
    n=read();
    for(int i=1;i<=(n<<1);i++){
        x=read();
        if(!vis[x]) vis[x]=1,a[x].l=i;
        else a[x].r=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        ans+=query(a[i].r)-query(a[i].l-1);
        add(a[i].r,1);
    }
    printf("%d\n",ans);
    return 0;
}
    ]]>

Leave a Reply

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