Codeforces Round #437 Div. 1

时间：2022-04-08 17:08:41

　　A：显然构造一组只包含1和2面值的数据即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	int n=read();

	cout<<n*2-1<<' '<<2<<endl;

	cout<<1<<' '<<2;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：显然两种pizza的分配应尽可能贴近第二种更优和第一种更优的人数关系。于是在这个边界附近±1暴力枚举一下，然后贪心非常显然。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m;

ll t=0,ans=0;

struct data

{

	int x,y,z;

	bool operator <(const data&a) const

	{

		return y-x>a.y-a.x;

	}

}a[N];

bool cmp(const data&x,const data&y)

{

	return abs(x.y-x.x)>abs(y.y-y.x);

}

void check(ll k)

{

	if (k<0||k>t) return;

	ll x=1ll*k*m,y=(t-k)*m,s=0;

	for (int i=1;i<=n;i++)

	if (a[i].y>a[i].x)

	{

		if (a[i].z<=x) s+=1ll*a[i].y*a[i].z,x-=a[i].z;

		else if (x) s+=1ll*a[i].y*x,s+=1ll*a[i].x*(a[i].z-x),y-=a[i].z-x,x=0;

		else s+=1ll*a[i].x*a[i].z,y-=a[i].z;

	}

	else

	{

		if (a[i].z<=y) s+=1ll*a[i].x*a[i].z,y-=a[i].z;

		else if (y) s+=1ll*a[i].x*y,s+=1ll*a[i].y*(a[i].z-y),x-=a[i].z-y,y=0;

		else s+=1ll*a[i].y*a[i].z,x-=a[i].z;

	}

	ans=max(ans,s);

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++) t+=a[i].z=read(),a[i].x=read(),a[i].y=read();

	sort(a+1,a+n+1);

	t=(t-1)/m+1;

	ll x=0;for (int i=1;i<=n;i++) if (a[i].y>a[i].x) x+=a[i].z;else break;

	sort(a+1,a+n+1,cmp);

	for (ll i=x/m-2;i<=x/m+2;i++) check(i);

	sort(a+1,a+n+1);

	x=0;for (int i=1;i<=n;i++) if (a[i].y>=a[i].x) x+=a[i].z;else break;

	sort(a+1,a+n+1,cmp);

	for (ll i=x/m-2;i<=x/m+2;i++) check(i);

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：注意到在某一天卖出再买进对答案是没有影响的。于是维护一个小根堆，每次取出堆顶与当前天价格比较，若能赚钱则计入答案并将堆顶弹出，相当于在堆顶那天买进然后在当前天卖出，然后将当前天价格入堆。我们还需要支持一个反悔操作，即更换买进天的匹配对象，容易发现把当前天价格再入一次堆就可以了。大约是在模拟费用流。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

#define ll long long

#define N 300010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[N];

ll ans=0;

priority_queue<int,vector<int>,greater<int> > q;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("d.in","r",stdin);

	freopen("d.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=n;i++)

	{

		if (!q.empty()&&q.top()<a[i])

		{

			ans+=a[i]-q.top();

			int x=q.top();q.pop();

			q.push(a[i]);

		}

		q.push(a[i]);

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：期望考虑倒推，但难以计算重置带来的影响。于是考虑先固定住重置的作用，即二分答案，这样重置之后就相当于可以用等于答案的时间直接通关。然后就可以dp了，即设f[i][j]为i~n关要用至多j时间通关的话最少要花多久。最后得到f[1][m]，判断其和二分出的答案的大小，若比其大说明一开始就得重置，这显然说明二分出来的答案小了；反之亦然。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 110

#define inf ((double)100000000000)

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],b[N],p[N];

double f[N][N*N];

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),p[i]=read();

	double l=0,r=inf,ans;

	for (int _=1;_<=100;_++)

	{

		double mid=(l+r)/2;

		for (int i=n;i>=1;i--)

			for (int j=0;j<=m;j++)

			{

				f[i][j]=0.01*((a[i]+(j>=a[i]?f[i+1][j-a[i]]:mid))*p[i]+(b[i]+(j>=b[i]?f[i+1][j-b[i]]:mid))*(100-p[i]));

				if (i>1) f[i][j]=min(f[i][j],mid);

			}

		if (f[1][m]>mid) ans=mid,l=mid;else r=mid;

	}

	printf("%.11f",ans);

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

相关文章