USACO 2017 February Contest总结

本文主要是介绍USACO 2017 February Contest总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接

T1 Why Did the Cow Cross the Road

题目链接

题目大意：给定一个 $N\times N$ 的网格。穿过两个格子的交界处需要有一个花费，每走三个格子也会有一个花费，问从左上角走到右下角的最小花费。

思路：一眼看上去每三个格有一个花费，看上去不是很好处理，仔细一想。
想
想。
发现我们可以将每三步化成一步，看一个点走三步可以到哪，就连边，边权为三次穿越边界的权值+这个点的权值。

WA了N次。。。原因：反向边和正向边。。。边权不相等。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
#include<cctype>
#include<set>
#define mp make_pair
#define pa pair<long long,long long>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long longusing namespace std;inline ll read()
{long long f=1,sum=0;char c=getchar();while (!isdigit(c)){if (c=='-') f=-1;c=getchar();}while (isdigit(c)){sum=sum*10+c-'0';c=getchar();}return sum*f;
}
const int MAXN=10010;
struct edge
{int next,to;ll val;
};
edge e[MAXN*40];
int head[MAXN],cnt;
void addedge(int u,int v,ll w)
{e[++cnt].next=head[u];e[cnt].to=v;e[cnt].val=w;head[u]=cnt;
}
priority_queue <pa,vector<pa>,greater<pa> > q;
ll dis[MAXN],n;
bool visit[MAXN];
#define id(x,y) (x-1)*n+y
void Dijkstra()
{for (int i=1;i<=n*n;i++)dis[i]=1e15;dis[1]=0;q.push(make_pair(0,1));while (!q.empty()){int x=q.top().se;q.pop();if (visit[x]) continue;visit[x]=1;for (int i=head[x];i;i=e[i].next){int v=e[i].to;if (dis[x]+e[i].val<dis[v])dis[v]=dis[x]+e[i].val,q.push(make_pair(dis[v],v));}}   
} 
int a[110][110];
const int dx[16]={3,0,0,-3,1,2,-1,-2,2,-1,-2,1,0,1,0,-1};
const int dy[16]={0,3,-3,0,2,1,-2,-1,-1,2,1,-2,1,0,-1,0};
int main()
{int cost;scanf("%d%d",&n,&cost);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%d",&a[i][j]);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){for (int k=0;k<16;k++){int nx=i+dx[k],ny=j+dy[k];if (nx<=0 || ny<=0 || nx>n || ny>n) continue;addedge(id(i,j),id(nx,ny),cost*3+a[nx][ny]);}}Dijkstra();ll ans=INF;for (int i=n-2;i<=n;i++)for (int j=n-2;j<=n;j++){int dist=(n-i)+(n-j);if (dist>=3) continue;ll now=dist*cost+dis[id(i,j)];ans=min(ans,now);}cout<<ans;return 0;   
}

T2 Why Did the Cow Cross the Road II

题目链接

题目大意：左边一个 $1\sim N$ 的排列，右边一个 $1\sim N$ 的排列，现在可以让一个点向另一侧权值和他相差不超过4的点连边。问在边不交叉的情况下最多连几条边。

思路： $N\le 1000$ ，感觉不是DP就是网络流，先想了想网络流，感觉无法建模，然后考虑DP。
- $f[i][j]$ 表示左边前 $i$ 个点，右边前 $j$ 个点匹配不交叉的最大匹配数。
- 转移：向前转移（i向i+1转移）。考虑 $i+1$ 的匹配，应该找到 $j+1\sim N$ 所有与它权值不超过4的点。预处理位置即可。
- 复杂度 $O(n^2)$ ，转移常数 9 <script type="math/tex" id="MathJax-Element-38">9</script>。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
#include<cctype>
#include<set>
#define mp make_pair
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long longusing namespace std;inline ll read()
{long long f=1,sum=0;char c=getchar();while (!isdigit(c)){if (c=='-') f=-1;c=getchar();}while (isdigit(c)){sum=sum*10+c-'0';c=getchar();}return sum*f;
}
const int MAXN=1010;
int a[MAXN],b[MAXN],vis1[MAXN],vis2[MAXN];
int f[MAXN][MAXN];
int main()
{freopen("nocross.in","r",stdin);freopen("nocross.out","w",stdout); int n;scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]),vis1[a[i]]=i;for (int i=1;i<=n;i++)scanf("%d",&b[i]),vis2[b[i]]=i;int ans=0;for (int i=1;i<=n;i++)f[1][i]=(abs(a[1]-b[i])<=4);for (int i=1;i<=n;i++){for (int j=0;j<=n;j++){f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1==0?j:j-1]));ans=max(ans,f[i][j]);for (int k=-4;k<=4;k++){int val=a[i+1]+k;if (val<=0 || val>n || vis2[val]<=j) continue;f[i+1][vis2[val]]=max(f[i+1][vis2[val]],f[i][j]+1); }}}cout<<ans;return 0;
}

T3 Why Did the Cow Cross the Road III

题目链接

题目大意：给定一些线段的左端点和右端点，求相交的线段条数。

思路：树状数组。
将所有线段按照左端点排序，每次查询线段区间内有几个右端点即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
#include<cctype>
#include<set>
#define mp make_pair
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long longusing namespace std;inline ll read()
{long long f=1,sum=0;char c=getchar();while (!isdigit(c)){if (c=='-') f=-1;c=getchar();}while (isdigit(c)){sum=sum*10+c-'0';c=getchar();}return sum*f;
}
const int MAXN=50010;
struct node
{int l,r;
}a[MAXN];
int lowbit(int x){return x&(-x);}
int f[2*MAXN],n;
void update(int x)
{for (int i=x;i<=2*n;i+=lowbit(i))f[i]++;
}
int query(int x)
{int ans=0;for (int i=x;i;i-=lowbit(i))ans+=f[i];return ans;
}
bool visit[MAXN];
int main()
{scanf("%d",&n);for (int i=1;i<=2*n;i++){int x;scanf("%d",&x);if (visit[x])a[x].r=i;elsea[x].l=i,visit[x]=1;}sort(a+1,a+1+n,[](node i,node j){return i.l<j.l;});int ans=0;for (int i=1;i<=n;i++){ans+=query(a[i].r)-query(a[i].l-1);update(a[i].r);}cout<<ans;return 0;
}