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

链接

题目大意：构造一个 1∼N 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，会发现所有重量比价值大于我们二分的值的，都是“对于当前二分值”有用的，故我们贪心选掉，然后问题又回到了背包。
又发现了一个性质：因为剩下的可以说都是“累赘”，所以肯定是选的越少越好，故所有大于”距离下限剩余重量“的物品，肯定只会选一个，然后我们枚举选择哪个，看看是否合法。
然后我们就把所有物品一步步缩减，缩减成了一些 1∼W 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。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
十五.各设计模式总结与对比

十五.各设计模式总结与对比

1.各设计模式总结与对比 1.1.课程目标 1、 简要分析GoF 23种设计模式和设计原则,做整体认知。 2、 剖析Spirng的编程思想，启发思维,为之后深入学习Spring做铺垫。 3、 了解各设计模式之间的关联，解决设计模式混淆的问题。 1.2.内容定位 1、 掌握设计模式的"道" ，而不只是"术" 2、 道可道非常道，滴水石穿非一日之功，做好长期修炼的准备。 3、 不要为了
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
Java注解详细总结

Java注解详细总结

什么是注解？         Java注解是代码中的特殊标记，比如@Override、@Test等，作用是：让其他程序根据注解信息决定怎么执行该程序。         注解不光可以用在方法上，还可以用在类上、变量上、构造器上等位置。 自定义注解  现在我们自定义一个MyTest注解 public @interface MyTest{String aaa();boolean bbb()
阅读更多...
tensorboard-----summary用法总结

tensorboard-----summary用法总结

Tensorflow学习笔记——Summary用法         最近在研究tensorflow自带的例程speech_command,顺便学习tensorflow的一些基本用法。 其中tensorboard 作为一款可视化神器，可以说是学习tensorflow时模型训练以及参数可视化的法宝。 而在训练过程中，主要用到了tf.summary()的各类方法，能够保存训练过程以及参数分布图并在
阅读更多...
七种排序方式总结

七种排序方式总结

/*2018.01.23*A:YUAN*T:其中排序算法：冒泡排序，简单排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序*/#include <stdio.h>#include <math.h>#include <malloc.h>#define MAXSIZE 10000#define FALSE 0#define TRUE 1typedef struct {i
阅读更多...
Java实现MD5加密总结

Java实现MD5加密总结

Java实现MD5加密总结 大家好，我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编，也是冬天不穿秋裤，天冷也要风度的程序猿！ 1. 什么是MD5加密 MD5是一种常用的哈希算法，用于将任意长度的数据通过哈希运算转换为固定长度的数据串，通常为128位的二进制串，常用于对密码等敏感信息进行加密存储或传输。 2. Java实现MD5加密的方法 2.1 使用java.sec
阅读更多...
Linux通配符总结

Linux通配符总结

Linux通配符总结 大家好，我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编，也是冬天不穿秋裤，天冷也要风度的程序猿！ 在Linux系统中，通配符是一种用于匹配文件名或路径名的特殊字符。通过使用通配符，可以方便地匹配多个文件或目录，从而进行文件操作或查找。 2. 常用的通配符 在Linux系统中，常用的通配符包括以下几种： *：匹配任意长度的任意字符。?：匹配任意单个字符
阅读更多...
【Linux文件系统】被打开的文件与文件系统的文件之间的关联刨析总结

【Linux文件系统】被打开的文件与文件系统的文件之间的关联刨析总结

操作系统管理物理内存以及与外设磁盘硬件进行数据的交换 操作系统如何管理物理内存呢？ 其实操作系统内核先对内存先描述再组织的！操作系统管理内存的基本单位是4KB，操作系统会为每一个4KB大小的物理内存块创建一个描述该4KB内存块的struct page结构体，该结构体存储着这4KB内存块的属性信息，通过管理struct page来对内存进行管理，page结构体的大小比较小，OS通常将它们组成一个
阅读更多...
Java反射详细总结

Java反射详细总结

什么是反射？         反射，指的是加载类的字节码到内存，并以编程的方法解刨出类中的各个成分（成员变量、方法、构造器等）。         反射获取的是类的信息，那么反射的第一步首先获取到类才行。由于Java的设计原则是万物皆对象，获取到的类其实也是以对象的形式体现的，叫字节码对象，用Class类来表示。获取到字节码对象之后，再通过字节码对象就可以获取到类的组成成分了，这些组成成分其实也
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2