本文主要是介绍USACO 2017 February Contest总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
比赛链接
T1 Why Did the Cow Cross the Road
题目链接
题目大意:给定一个 N×N N × 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∼N 1 ∼ N 的排列,右边一个 1∼N 1 ∼ N 的排列,现在可以让一个点向另一侧权值和他相差不超过4的点连边。问在边不交叉的情况下最多连几条边。
思路: N≤1000 N ≤ 1000 ,感觉不是DP就是网络流,先想了想网络流,感觉无法建模,然后考虑DP。
- f[i][j] f [ i ] [ j ] 表示左边前 i i 个点,右边前个点匹配不交叉的最大匹配数。
- 转移:向前转移(i向i+1转移)。考虑 i+1 i + 1 的匹配,应该找到 j+1∼N j + 1 ∼ N 所有与它权值不超过4的点。预处理位置即可。
- 复杂度 O(n2) O ( n 2 ) ,转移常数 9 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
题目链接
题目大意:给定一些线段的左端点和右端点,求相交的线段条数。
思路:树状数组。
将所有线段按照左端点排序,每次查询线段区间内有几个右端点即可。
1A
#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;
}
这篇关于USACO 2017 February Contest总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!