USACO 2017 January Contest总结

2024-03-07 12:18
文章标签 总结 2017 contest usaco january

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

比赛链接

T1 Balanced Photo

题目链接

题目大意：一个人要给他的一堆牛拍照，每头牛有一个身高且身高互不相同。定义 L[i] L [ i ] 为第 i i 头牛左边比它高的牛的个数，R[i]为第 i i 头牛右边比它高的牛的个数，定义“不平衡的牛”：它的L[i],R[i]相差两倍以上，求不平衡的牛的个数。

思路：以下是刚看到题的时候的心理活动
- 大概就是查询一个数前面有几个数比他大。
- 也就是查询一个数的排名。
- 为什么不用set啊
- set查不了排名啊
- 那我就手写平衡树吧。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_backusing 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=100010;
int ch[MAXN][2],fa[MAXN],sz[MAXN],val[MAXN],root,cnt,t[MAXN];
int son(int x){return x==ch[fa[x]][1];}
int update(int x){sz[x]=sz[ch[x][1]]+sz[ch[x][0]]+t[x];}
void rotate(int x)
{int y=fa[x],z=fa[y],b=son(x),c=son(y);ch[z][c]=x,fa[x]=z;if (ch[x][!b]) fa[ch[x][!b]]=y;ch[y][b]=ch[x][!b],ch[x][!b]=y,fa[y]=x;update(y),update(x);
}
void splay(int x,int p)
{while (fa[x]!=p){int y=fa[x],z=fa[y];if (z==p) rotate(x);else{if (son(x)!=son(y))rotate(x),rotate(x);elserotate(y),rotate(x);}}if (!fa[x]) root=x;
}
int find_qq(int x)
{int now=root,ans=0;while (now){if (val[now]<x)ans=now,now=ch[now][1];elsenow=ch[now][0];}return ans;
}
int find_hj(int x)
{int now=root,ans=0;while (now){if (val[now]>x)ans=now,now=ch[now][0];elsenow=ch[now][1];}return ans;
}
void insert(int x)
{int qq=find_qq(x),hj=find_hj(x);splay(qq,0),splay(hj,qq);int y=ch[hj][0];if (y) t[y]++,update(y);else ch[hj][0]=++cnt,val[cnt]=x,sz[cnt]=1,fa[cnt]=hj,t[cnt]=1,splay(cnt,0);
}
int query_upper(int x)
{int now=root,ans=0;while (now){if (x>val[now])now=ch[now][1];else{ans+=sz[ch[now][1]];if (x==val[now]) return ans;ans+=t[now];now=ch[now][0]; }}
}
void init()
{memset(sz,0,sizeof(sz)),memset(t,0,sizeof(t));memset(ch,0,sizeof(ch)),memset(fa,0,sizeof(fa));memset(val,0,sizeof(val));val[1]=1e9,val[2]=-1e9;fa[2]=1,root=1,cnt=2,ch[1][0]=2;
}
int a[MAXN],l[MAXN],r[MAXN];
int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);init();for (int i=1;i<=n;i++){insert(a[i]);l[i]=query_upper(a[i]);}init();for (int i=n;i>=1;i--){insert(a[i]);r[i]=query_upper(a[i]);}int ans=0;for (int i=1;i<=n;i++)if (min(l[i],r[i])*2<max(l[i],r[i]))ans++;cout<<ans;return 0;
}

后来发现只需要一个求逆序对的东西，所以写了权值线段树。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_backusing 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=100010;
int f[4*MAXN];
void update(int root,int left,int right,int x)
{if (left==right){f[root]++;return ;}int mid=(left+right)>>1;if (x<=mid)update(2*root,left,mid,x);elseupdate(2*root+1,mid+1,right,x);f[root]=f[2*root]+f[2*root+1];
}
int query(int root,int left,int right,int qleft,int qright)
{if (qleft<=left && qright>=right)return f[root];int mid=(left+right)>>1;if (qright<mid)return query(2*root,left,mid,qleft,qright);else if (qleft>mid)return query(2*root+1,mid+1,right,qleft,qright);else{int ans1,ans2;ans1=query(2*root,left,mid,qleft,mid);ans2=query(2*root+1,mid+1,right,mid+1,qright);return ans1+ans2;}
}
int a[MAXN],l[MAXN],r[MAXN];
vector <int> v;
int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);sort(v.begin(),v.end());for (int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;for (int i=1;i<=n;i++){l[i]=query(1,1,n,a[i]+1,n);update(1,1,n,a[i]);}memset(f,0,sizeof(f));for (int i=n;i>=1;i--){r[i]=query(1,1,n,a[i]+1,n);update(1,1,n,a[i]);}int ans=0;for (int i=1;i<=n;i++)if (min(l[i],r[i])*2<max(l[i],r[i]))ans++;cout<<ans;return 0;
}
T2 Hoof, Paper, Scissors

题目链接

题目大意：你在玩石头剪子布，你已知你的对手的出招顺序，你一开始会出石头，然后一直保持一个手势出下去，你可以改变K次手势，问你最多赢几次。

思路：算是比较简单的DP。
f[i][j][1/2/3] f [ i ] [ j ] [ 1 / 2 / 3 ] 表示前i轮变换j次手势最多赢几次，你现在的手势是什么。预处理出一直不变能赢几次。先枚举第二维，再枚举第一维。转移即可。
因为把一个2打成了1所以WA了两发。。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_backusing 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=100010;
const int MAXK=22;
const int SET=4;
int f[MAXN][MAXK][SET];
int a[MAXN];
int win(int x,int y)
{if (x==1 && y==2) return 1;else if (x==2 && y==3) return 1;else if (x==3 && y==1) return 1;else return 0;
}
int main()
{int n,k;scanf("%d%d",&n,&k);for (int i=1;i<=n;i++){char s[10];scanf("%s",s+1);if (s[1]=='H') a[i]=1;else if (s[1]=='S') a[i]=2;else a[i]=3;}for (int i=1;i<=n;i++){f[i][0][1]=f[i-1][0][1]+win(1,a[i]);f[i][0][2]=f[i-1][0][2]+win(2,a[i]);f[i][0][3]=f[i-1][0][3]+win(3,a[i]);}for (int j=1;j<=k;j++){for (int i=1;i<=n;i++){f[i][j][1]=max(f[i-1][j][1],max(f[i-1][j-1][2],f[i-1][j-1][3]))+win(1,a[i]);f[i][j][2]=max(f[i-1][j][2],max(f[i-1][j-1][1],f[i-1][j-1][3]))+win(2,a[i]);f[i][j][3]=max(f[i-1][j][3],max(f[i-1][j-1][1],f[i-1][j-1][2]))+win(3,a[i]);}}int ans1=-1,ans2=-1,ans3=-1;for (int i=1;i<=n;i++){ans1=max(ans1,f[n][k][1]);ans2=max(ans2,f[n][k][2]);ans3=max(ans3,f[n][k][3]);}cout<<max(ans1,max(ans2,ans3));return 0;
}
T3 Cow Navigation

题目链接

题目大意：一个 n×n n × n 的网格，在 (n,1) ( n , 1 ) 有两头牛，分别面向正上方和正右方，现在你要给他们两个同时发出指令“向前走”，“右转”或“左转”，两头牛会同时遵守这个指令。
地图上有一些不能去的格子，若你的指令让牛向无法到达的格子前进，他会自动忽略。
他们俩都要去 (n,n) ( n , n ) ，若一头牛已经到达终点，他会忽略后面所有的指令，求想让两头牛都到达终点的最短指令是多段。

思路：BFS。
令 dis[x1][y1][x2][y2][d1][d2] d i s [ x 1 ] [ y 1 ] [ x 2 ] [ y 2 ] [ d 1 ] [ d 2 ] 表示两头牛分别在 (x1,y2),(x2,y2) ( x 1 , y 2 ) , ( x 2 , y 2 ) ，面向 d1,d2 d 1 , d 2 的最少指令数。暴力转移分三种情况，前进，左转，右转。

WA了一次因为没看到这句话。
若一头牛已经到达终点，他会忽略后面所有的指令

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_backusing 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=25;
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
struct node
{int x1,y1,x2,y2,d1,d2;node (int x1,int y1,int x2,int y2,int d1,int d2):x1(x1),y1(y1),x2(x2),y2(y2),d1(d1),d2(d2) {}node () {}
};
int a[MAXN][MAXN],n;
queue <node> q;
bool visit[MAXN][MAXN][MAXN][MAXN][5][5];
int dis[MAXN][MAXN][MAXN][MAXN][5][5];
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){char s[MAXN];scanf("%s",s+1);for (int j=1;j<=n;j++)a[i][j]=s[j]=='E';}memset(dis,inf,sizeof(dis));dis[n][1][n][1][1][2]=0;q.push(node(n,1,n,1,1,2));visit[n][1][n][1][1][2]=1;while (!q.empty()){node x=q.front();int dist=dis[x.x1][x.y1][x.x2][x.y2][x.d1][x.d2];
//      cout<<x.x1<<' '<<x.y1<<' '<<x.x2<<' '<<x.y2<<' '<<x.d1<<' '<<x.d2<<' '<<dist<<endl;q.pop();int nx1,ny1,nx2,ny2,nd1,nd2;nx1=x.x1+dx[x.d1],ny1=x.y1+dy[x.d1];nx2=x.x2+dx[x.d2],ny2=x.y2+dy[x.d2];if (nx1>n || ny1>n || nx1<=0 || ny1<=0 || !a[nx1][ny1] || (x.x1==1 && x.y1==n)) nx1=x.x1,ny1=x.y1;if (nx2>n || ny2>n || nx2<=0 || ny2<=0 || !a[nx2][ny2] || (x.x2==1 && x.y2==n)) nx2=x.x2,ny2=x.y2;nd1=x.d1,nd2=x.d2;int &ndis1=dis[nx1][ny1][nx2][ny2][nd1][nd2];if (ndis1>dist+1){ndis1=dist+1;if (!visit[nx1][ny1][nx2][ny2][nd1][nd2]){q.push(node(nx1,ny1,nx2,ny2,nd1,nd2));visit[nx1][ny1][nx2][ny2][nd1][nd2]=1;  }}nx1=x.x1,ny1=x.y1,nx2=x.x2,ny2=x.y2;nd1=x.d1-1,nd2=x.d2-1;if (!nd1) nd1=4;if (!nd2) nd2=4;int &ndis2=dis[nx1][ny1][nx2][ny2][nd1][nd2];if (ndis2>dist+1){ndis2=dist+1;if (!visit[nx1][ny1][nx2][ny2][nd1][nd2]){q.push(node(nx1,ny1,nx2,ny2,nd1,nd2));visit[nx1][ny1][nx2][ny2][nd1][nd2]=1;  }}nd1=x.d1+1,nd2=x.d2+1;if (nd1==5) nd1=1;if (nd2==5) nd2=1;int &ndis3=dis[nx1][ny1][nx2][ny2][nd1][nd2];if (ndis3>dist+1){ndis3=dist+1;if (!visit[nx1][ny1][nx2][ny2][nd1][nd2]){q.push(node(nx1,ny1,nx2,ny2,nd1,nd2));visit[nx1][ny1][nx2][ny2][nd1][nd2]=1;  }}
//      visit[x.x1][x.y1][x.x2][x.y2][x.d1][x.d2]=0;}int ans=INF;for (int i=1;i<=4;i++)for (int j=1;j<=4;j++)ans=min(ans,dis[1][n][1][n][i][j]);cout<<ans;return 0;
}

这篇关于USACO 2017 January Contest总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/783485。

相关文章

Python中连接不同数据库的方法总结

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo
阅读更多...
Git提交代码详细流程及问题总结

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》：本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push
阅读更多...
Kubernetes常用命令大全近期总结

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes（有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes？Kubernetes常用命令总
阅读更多...
Python中实现进度条的多种方法总结

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres
阅读更多...
Android数据库Room的实际使用过程总结

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象（DAO）和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类（Entity）3.创建数据访问对象（DAO
阅读更多...
Java向kettle8.0传递参数的方式总结

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的
阅读更多...
C# Task Cancellation使用总结

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2