USACO 2018 US Open Contest总结

2024-03-07 12:18
文章标签 总结 open 2018 contest us usaco

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

比赛链接

T1 Out of Sorts

题目链接

题目大意:给定一个类似于冒泡排序的程序,问能while循环多少次。
思路:观察给定程序,实际上是从左向右将每个数移到它左边第一个比它大的数左边,然后从右向左将每个数移到它右边第一个比他小的数右边。
所以问题就转化成了一个数左边多少个数比他大。
树状数组即可。
1A。
Code:

#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=100010;
struct node
{int x,id;bool operator <(node b){return x==b.x?id<b.id:x<b.x;}
}a[MAXN];
int lowbit(int x){return x&(-x);}
int f[MAXN],n;
void update(int x)
{for (int i=x;i<=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;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i].x);a[i].id=i;}sort(a+1,a+1+n);int ans=0;for (int i=1;i<=n;i++){update(a[i].id);ans=max(ans,i-query(i));}printf("%d",max(ans,1));return 0;
}

T2 Milking Order

链接

题目大意:构造一个 1N 1 ∼ N 的排列,使得按照先后顺序最大化满组给定的M个要求,要求是给定一个序列,序列前面的数必须出现在序列后面的数前面。若有多个答案同时满足”最大化要求“,则输出字典序最小的一个。

思路:最大化满足要求的个数,易想到二分。
二分能满足多少要求。建图跑拓扑排序,若有环即说明不行。
求出满足了多少要求,如何求字典序最小的答案呢。
把普通队列改成优先队列即可,再跑一次。
也是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=100010;
struct edge
{int next,to;
};
edge e[MAXN*10];
int head[MAXN],cnt,in[MAXN];
void addedge(int u,int v)
{e[++cnt].next=head[u];e[cnt].to=v;in[v]++;head[u]=cnt;
}
vector <vector<int> > v;
int n;
queue <int> q;
bool check(int mid)
{memset(head,0,sizeof(head));cnt=0;for (int i=1;i<=n;i++) in[i]=0;for (int i=1;i<=mid;i++)for (int j=0;j<(int)v[i].size()-1;j++)addedge(v[i][j],v[i][j+1]); for (int i=1;i<=n;i++)if (!in[i])q.push(i);while (!q.empty()){int x=q.front();q.pop();for (int i=head[x];i;i=e[i].next){int v=e[i].to;if (!in[v]) continue;in[v]--;if (!in[v])q.push(v);}}for (int i=1;i<=n;i++)if (in[i])return 0;return 1;
}
vector <int> anss;
priority_queue <int,vector<int>,greater<int> > fq;
int main()
{freopen("milkorder.in","r",stdin);freopen("milkorder.out","w",stdout);int m;scanf("%d%d",&n,&m);v.resize(m+1);for (int i=1;i<=m;i++){int num;scanf("%d",&num);v[i].resize(num);for (int j=0;j<num;j++)scanf("%d",&v[i][j]);}int l=0,r=m,mid,ans;while (l<=r){mid=(l+r)>>1;if (check(mid))ans=mid,l=mid+1;elser=mid-1;}memset(head,0,sizeof(head));cnt=0;for (int i=1;i<=n;i++) in[i]=0;for (int i=1;i<=ans;i++)for (int j=0;j<(int)v[i].size()-1;j++)addedge(v[i][j],v[i][j+1]); for (int i=1;i<=n;i++)if (!in[i])fq.push(i);while (!fq.empty()){int x=fq.top();anss.push_back(x);fq.pop();for (int i=head[x];i;i=e[i].next){int v=e[i].to;if (!in[v]) continue;in[v]--;if (!in[v]) fq.push(v);}}for (int i=0;i<n-1;i++)printf("%d ",anss[i]);printf("%d",anss[n-1]);return 0;
}

T3 Talent Show

链接

题目大意:有一些物品,有重量和价值,要求选择至少为W的重量,使价值和重量的比值最大。

思路:此题做的颇为艰难,WA了一次。。。
“价值和重量的比值最大”让人很容易想起了分数规划。
那么有下限该怎么做呢。。。
临时YY了一个做法。我们二分这个比值,然后将重量乘以这个比值,于是就成了一个背包。
但是会发现一个问题,原题的重量太大,背包会爆炸。然后继续YY,会发现所有重量比价值大于我们二分的值的,都是“对于当前二分值”有用的,故我们贪心选掉,然后问题又回到了背包。
又发现了一个性质:因为剩下的可以说都是“累赘”,所以肯定是选的越少越好,故所有大于”距离下限剩余重量“的物品,肯定只会选一个,然后我们枚举选择哪个,看看是否合法。
然后我们就把所有物品一步步缩减,缩减成了一些 1W 1 ∼ W 的物品,就可以做背包了。

赛后发现其实根本没有这么麻烦,只需要把所有超过W的物品的质量全部变成W即可。。。

Code:

#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=255;
const int MAXM=1010;
int n,W;
struct node{ll w,t;
}a[MAXN];
vector <int> tmpw,tmpt;
ll f[2*MAXM];
bool check(int mid)
{ll tot=0,tot1=0;for (int i=1;i<=n;i++)if (a[i].w*mid<=a[i].t*1000)tot+=a[i].w,tot1+=a[i].t;
//  cout<<tot<<' '<<tot1<<endl;if (tot>=W) return 1;ll nw=W-tot;for (int i=1;i<=n;i++)if (a[i].w*mid>a[i].t*1000 && a[i].w>=nw)if ((tot1+a[i].t)*1000>=mid*(tot+a[i].w))return 1;for (int i=1;i<=2*nw+10;i++)f[i]=-1e10;f[0]=0;for (int i=1;i<=n;i++){if (a[i].w*mid<=a[i].t*1000 || a[i].w>=nw) continue;for (int j=2*nw;j>=a[i].w;j--)f[j]=max(f[j],f[j-a[i].w]+a[i].t);}for (int i=nw;i<=2*nw;i++)if ((tot1+f[i])*1000>=(tot+i)*mid)return 1;return 0;
}
int main()
{freopen("talent.in","r",stdin);freopen("talent.out","w",stdout);scanf("%d%d",&n,&W);for (int i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].t);int l=1,r=1e9,mid,ans;while (l<=r){mid=(l+r)>>1;
//      cout<<l<<' '<<r<<' '<<mid<<endl;if (check(mid))ans=mid,l=mid+1;elser=mid-1;}cout<<ans;return 0;
}

这篇关于USACO 2018 US Open Contest总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/783480

相关文章

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

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

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

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

usaco 1.3 Calf Flac(暴搜)

思路是暴搜。 需要注意的地方是输入的方法,以及输出时的换行。 代码: /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<