11.7usaco模拟赛题解



夏9赛高!

P4375 USACO18OPEN Out of Sorts G

题意

给你一组数,问你用双向冒泡排序要几次才能使序列有序

思路

对普通的冒泡,他的遍数是max{1,每个数前面有几个比它大的}
同理我们可以推得,对双冒泡排序,他的遍数是max{1,前i个位置上>i的数有多少个}
对于每个i
1.向后扫会把前i个位置上的一个>i的数扔到后面去
2.向前扫会保证新换到前i个数里面的新数的值一定是<=i的
(说法转自luogu第一篇题解)
这样可以o(n)的模拟了,当然,看过一些题解用的是树状数组,当然也行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define N 100000+100
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int val,id;
bool operator < (const node &b)const
{
return val<b.val||val==b.val&&id<b.id;
}
}a[N];
int n,cnt=0,ans=1;
bool vis[N];
main()
{
//freopen("sort.in","r",stdin);
//freopen("sort.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)a[i].val=read(),a[i].id=i;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(i<a[i].id)cnt++;
if(vis[i])cnt--;
vis[a[i].id]=1;
ans=max(ans,cnt);
}
printf("%lld",ans);
return 0;
}

P4376 USACO18OPEN Milking Order

考试的时候听到旁边的巨神说拓扑排序,然后回忆了一下拓扑排序,大概是将入度为1的点丢到队列里面去,每次将所连的边的另一边入度–,每次将队头输出大概吧

题意

给出一些代表奶牛挤奶的先后顺序的序列,序列中每一项的奶牛都必须在后一项之前挤奶,当多种顺序满足前x个序列的要求时,编号小的奶牛先挤奶,求能满足前面连续几个序列要求并且每个奶牛的挤奶顺序都能确定的挤奶顺序

思路

将“每一项在后一项之前”理解为i向i+1建边,这个题就变为了拓扑排序的题目,当然,要满足前面连续的x个序列顺序都能成立,所形成的图肯定是不能有环的,这个放到拓扑中判断就是最后排序完之后入度为1的点的个数与n相等
第一个问题就这样解决了,第二个问题就是怎么得到x,如果从1~n枚举,到一个i的时候会产生环,那么i-1就是所求的最大的x,然而这样复杂度太大了
不妨二分x不看题解我也不知道

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define N 100000+10
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int x;
node(int b):x(b){}
bool operator < (const node &y)const
{
return y.x<x;
}
};
priority_queue <node> p;
vector <int> f[50005],point[N];
int n,m,in[N],pos,cnt,l,r;
bool suc=false;
void putin()
{
for(int i=1;i<=m;i++)
{
int mi=read();
for(int j=1;j<=mi;j++)
{
int x=read();
f[i].push_back(x);
}
}
}
void build(int x)
{
memset(in,0,sizeof(in));
memset(point,0,sizeof(point));
for(int i=1;i<=x;i++)
{
for(int j=0;j<f[i].size()-1;j++)
{
point[f[i][j]].push_back(f[i][j+1]);
in[f[i][j+1]]++;
}
}
}
void topo()
{
for(int i=1;i<=n;i++)
if(!in[i])
p.push(i);
while(!p.empty())
{
int u=p.top().x;
printf("%d ",u);
p.pop();
for(int i=0;i<point[u].size();i++)
{
int v=point[u][i];
in[v]--;
if(!in[v])
p.push(v);
}
}
}

queue<int> q;
inline bool Topo_Sort()
{
for(int i=1;i<=n;i++)
{
if(!in[i])q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<point[u].size();i++)
{
int v=point[u][i];
in[v]--;
if(!in[v])
{
q.push(v);
}
}
}
for(int i=1;i<=n;i++)
{
if(in[i])return 0;
}
return 1;
}
bool check(int x)
{
build(x);
return Topo_Sort();
}
main()
{
n=read(),m=read();
putin();
l=0,r=m+1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
pos=mid;
}
else r=mid-1;
}
suc=true;
build(pos);
topo();
return 0;
}

P4337 USACO18OPEN Talent Show

题意

n头奶牛,每一头牛重量为wi,才艺水平为ti,要选出若干只总重量至少为W的奶牛,并且使得才艺值与总重量的比值最大

思路

以下大部分转自题解
这道题所需要的知识点是:01分数规划 背包dp
01分数规划就是将这样的式子中有‘/’的数据处理需求“可贪心化”
定义一个数组x,x[i]表示的是拿不拿这头牛,如果拿为1,不拿为0
则有答案R=sigma(t[i]x[i])/sigma(w[i]x[i])
假设有一个没那么优的答案Z满足Z<=R,那么就会有如下的式子sigma(t[i]x[i])>=sigma(w[i]x[i])Z
可以发现每头牛的贡献变为了(t[i]-w[i])
x[i]*Z
只要在最优选取的状态下可以使总和非负,就说明这个Z是可行的
所以,与二分配合,进行01分数规划就是这题的第一步
第二步,这里要求总质量不小于W,那么就用背包吧,大于W的也存在f[W]中就行了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define N 100000+10
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,w,cost[N],val[N],dp[N];
bool check(int z)
{
memset(dp,128,sizeof(dp));
dp[0]=0;
int cnt=dp[w];
for(int i=1;i<=n;i++)
{
for(int j=w;j>=0;j--)
{
if(dp[j]!=cnt)
{
int tj=j+cost[i];
tj=min(tj,w);
dp[tj]=max(dp[tj],dp[j]+val[i]-(long long)cost[i]*z);
}
}
}
return dp[w]>=0;
}
int twodivide()
{
int l=0,r=1000000;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
return l-1;
}
main()
{
n=read(),w=read();
for(int i=1;i<=n;i++)
{
cost[i]=read(),val[i]=read();
val[i]*=1000;
}
printf("%lld",twodivide());
return 0;
}