这次的题目都不算很水,还是比较有价值的一套题来纪念一下
USACO18OPEN 主题模拟赛
T1: Out of Sorts
题意简述
sorted = false
while (not sorted):
sorted = true
moo++
for i = 0 to N-2:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = N-2 downto 0:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = 0 to N-2:
if A[i+1] < A[i]:
sorted = false
给一段伪代码,求出最后答案的moo值是多少,(这段代码是根据冒泡排序改的)
题解
事实上交以上伪代码的c++版本可获得40分的好成绩,稍加一些优化有50分。
然而正解其实很玄学。
这个moo的值实际上就是离散化之后的序列中,前$i$个数中大于$i$的数的最大值。
对于一个(伪)冒泡排序的过程,以一个$i$为界限,
- 向后扫会保证把前 𝑖 个位置上一个值$> 𝑖$ 的数扔到后边去
- 向前扫会保证被换到前𝑖 个位置上的新数的值是$≤ 𝑖 $的
于是前$i$个中大于$i$的数就是需要交换的次数,扫一遍求最大值就行。
至于求法,可以模拟,也可以树状数组,我就只打了模拟。。
代码
模拟代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+110;
int n,m,ans,Case,tree[N],pos[N];
bool flag,vis[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void add(int x,int k)
{
for(int i=x;i<=n;i+=i&(-i))
tree[i]+=k;
}
int query(int x)
{
int sum=0;
for(int i=x;i>=0;i-=i&(-i))
sum+=tree[i];
return sum;
}
struct node
{
int val,num;
bool operator < (const node &v)const
{
return val<v.val||val==v.val&&num<v.num;
}
}a[N];
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i].val=read(),a[i].num=i;
sort(a+1,a+1+n);
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i].num>i)sum++;
if(vis[i])sum--;
vis[a[i].num]=1;
ans=max(ans,sum);
}
printf("%d",max(1,ans));//注意有可能是0
return 0;
}
树状数组
#include<bits/stdc++.h>
#define MAXN 100005
#define LL long long
#define INF 2147483640
#define MOD 100000007
#define lowbit(x) ((x&(-x)))
using namespace std;
const int L=1e5+5;
struct node
{
int x,num;
};
bool cmp(const node &a,const node &b)
{
return a.x<b.x||(a.x==b.x&&a.num<b.num);
}
int n,ans,sum[L];
node a[L];
void ins(int x)
{
for(int i=x;i<=L;i+=lowbit(i))
sum[i]++;
}
int ask(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=sum[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
ins(a[i].num);
ans=max(ans,i-ask(i));
}
printf("%d",max(ans,1));
return 0;
}
T2: Milking Order
题意简述
共有$n$头牛,给定$m$个排列顺序(可以只有部分牛),求在满足最大的x的情况下,找到最终的一个排列顺序,满足前x个给出的排列顺序,且放在前面的牛尽量小。。题意很长我尽力了。
题解
是一个裸的拓扑。。。
二分一个最大的x,每一次可以拓扑或tarjan判环,最后用小根堆拓扑排序一下就行。
关于每次check,可以选择每一次摧毁之前所有的边,重新建边。
也可以定一个time,一次行先建完所有的边,最后只查time<=当前x的边就行,跑的很快
代码
#include <bits/stdc++.h>
using namespace std;
const int M=5e5+110;
const int N=1e5+110;
int n,m,in[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int head[N],cnt;
struct node
{
int nt,to;
};
node edge[M];
void add(int x,int y)
{
edge[++cnt]=(node){head[x],y};
head[x]=cnt;
}
vector<int>ve[M];
void build(int x)
{
memset(head,0,sizeof(head));
memset(in,0,sizeof(in));
cnt=0;
for(int i=1;i<=x;i++)
{
for(int j=0;j<ve[i].size()-1;j++)
{
add(ve[i][j],ve[i][j+1]);
in[ve[i][j+1]]++;
}
}
}
bool check(int x)
{
build(x);
queue<int>q;
for(int i=1;i<=n;i++)
if(!in[i])q.push(i);
int ans=0;
while(!q.empty())
{
int u=q.front();
q.pop();
ans++;
for(int i=head[u];i;i=edge[i].nt)
{
int v=edge[i].to;
in[v]--;
if(!in[v])q.push(v);
}
}
if(ans<n)return 0;
else return 1;
}
void print(int x)
{
build(x);
priority_queue<int, vector<int>, greater <int > >q;
for(int i=1;i<=n;i++)
if(!in[i])q.push(i);
while(!q.empty())
{
int u=q.top();
q.pop();
printf("%d ",u);
for(int i=head[u];i;i=edge[i].nt)
{
int v=edge[i].to;
in[v]--;
if(!in[v])q.push(v);
}
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x=read();
for(int j=1;j<=x;j++)
{
int y=read();
ve[i].push_back(y);
}
}
int l=1,r=m;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid-1;
}
print((l+r)/2);
return 0;
}
T3: Talent Show
题意简述
每个物品有一个$w_i,t_i$,求当总的w大于等于一个给定值$W$使$\sum_{t_i}/\sum_{w_i}$的最大值
题解
裸的01分数规划背包dp,可惜我不会,因为数据水就混到了90分。。。。
考虑$ans=\sum_{t_i}/\sum_{w_i}$ 是最优的解,Z是当前不那么优秀的解
则有$\sum_{t_i}/\sum_{w_i}>=Z$
移项得$\sum_{t_i}-\sum_{w_i} \times Z>=0$
此时一个i的贡献值就只和i有关了!!
于是可以考虑二分答案,在check的时候做一个01背包dp
设$dp[i]$表示当容量与i的时候$t[i]-w[i] \times Z$的最大值,当$dp[W]$ 为非负值时,说明此时的答案时成立的
代码
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
const int N = 260;
const int M = 1e3+10;
const int INF=(1<<30);
int w[N],t[N],n,m,W,sum;
double dp[M],a[M];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool check(double ans)
{
memset(dp,-0x3f,sizeof(dp));
for(int i=1;i<=n;i++)a[i]=t[i]-w[i]*ans;
dp[0]=0.0;
for(int i=1;i<=n;i++)
for(int j=W;~j;j--)
{
int p=min(W,j+w[i]);
dp[p]=max(dp[p],dp[j]+a[i]);
}
return dp[W]>=0;
}
int main()
{
n=read();W=read();
for(int i=1;i<=n;i++)w[i]=read(),t[i]=read(),sum+=t[i];
double l=0,r=sum*1.0;
while(r-l>=eps)
{
double mid=(l+r)/2;
if(check(mid))l=mid+eps;
else r=mid-eps;
}
cout<<(int)((l+r)/2*1000);
return 0;
}