Pizza

Pizza

关注
发信
关注(28)粉丝(399)

【AtCoder】 ARC 096

link

C-Half and Half

题意：三种pizza，可以花\(A\)价钱买一个A-pizza，花\(B\)价钱买一个B-pizza，花\(C*2\)价钱买A-pizza和B-pizza各一个，需要\(x\)个A-pizza和\(y\)个B-pizza，最小化代价

枚举买多少个AB-pizza即可

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline int read()

{

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

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

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

ll ans,A,B,C,X,Y;

ll val(ll i){return i*2ll*C+max(X-i,0ll)*A+max(Y-i,0ll)*B;}

int main()

{

	A=read(),B=read(),C=read(),

	X=read(),Y=read();

	reg int i;

	ans=val(0);

	for(i=1;i<=X||i<=Y;++i)

		ans=min(ans,val(i));

	return 0*printf("%lld\n",ans);

}

D-Static Sushi

题意：环形吧台，从指定点开始，移动需要耗体力，吃寿司可涨体力，求最大收益

分别枚举顺时针走，逆时针走，先顺后逆，先逆后顺

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

const int MN=1e5+5;

ll N,C,X[MN],W[MN];

ll p1,p2,s1,s2,p1m[MN],p2m[MN],s1m[MN],s2m[MN];

int main()

{

	N=read(),C=read();

	reg int i;

	for(i=1;i<=N;++i) X[i]=read(),W[i]=read();

	X[N+1]=C;

	for(i=1;i<=N;++i)

	{

		p1+=W[i]+X[i-1]-X[i];

		p2=p1-X[i];

		p1m[i]=max(p1m[i-1],p1);

		p2m[i]=max(p2m[i-1],p2);

	}

	for(i=N;i;--i)

	{

		s1+=W[i]-X[i+1]+X[i];

		s2=s1-C+X[i];

		s1m[i]=max(s1,s1m[i+1]);

		s2m[i]=max(s2,s2m[i+1]);

	}

	ll ans=0;

	for(i=1;i<=N;++i)

		ans=max(p2m[i]+s1m[i+1],ans),

		ans=max(p1m[i],ans);

	for(i=1;i<=N;++i)

 		ans=max(s2m[i]+p1m[i-1],ans),

 		ans=max(s1m[i],ans);

 	return 0*printf("%lld\n",ans);

}

E-Everything on it

题意：有\(n\)个元素，一种合法的方案为任意多个集合，每个集合互不相同，\(n\)个元素的出现次数不少于\(2\)次，求方案数，对\(M\)（是质数）取模，\(n\le 3000\)

容斥。

\[ans=\sum_{i=0}^n(-1)^i\binom{n}{i}W(i)
\]

\(W(i)\)表示表示至少有\(i\)个元素出现小于\(2\)次的方案数

\[W(i)=\sum_{j=0}^if(i,j)2^{(N-i)j}2^{2^{N-i}}
\]

\(f(i,j)\)表示球标号，盒子不标号，球可以不放，盒子非空的方案数，递推可得

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline int read()

{

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

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

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

int N,M;

const int MN=3005;

int fac[MN],inv[MN],pw[9000005];

int Mul(int x,int y){return (1ll*x*y)%M;}

int Add(int x,int y){return (x+y)%M;}

int C(int x,int y){return Mul(fac[x],Mul(inv[y],inv[x-y]));}

int f[MN][MN],g[MN],ans;

int main()

{

	N=read();M=read();

	reg int i,j;

	for(pw[0]=i=1;i<=N*N;++i) pw[i]=Mul(2,pw[i-1]);

	for(fac[0]=i=1;i<=N;++i)fac[i]=Mul(fac[i-1],i);

	for(inv[0]=inv[1]=1,i=2;i<=N;++i)inv[i]=Mul(inv[M%i],(M-M/i));

	for(i=2;i<=N;++i)inv[i]=Mul(inv[i-1],inv[i]);

	f[0][0]=1;

	for(i=1;i<=N;++i)for(f[i][0]=1,j=1;j<=i;++j)

		f[i][j]=Add(f[i-1][j],Add(f[i-1][j-1],Mul(f[i-1][j],j)));

	reg int tmp=2;

	for(i=N;~i;--i,tmp=Mul(tmp,tmp))for(j=0;j<=i;++j)

		g[i]=Add(g[i],Mul(f[i][j],Mul(tmp,pw[(N-i)*j])));

	for(i=0;i<=N;++i)

		ans=Add(ans,Mul((i&1?M-1:1),Mul(C(N,i),g[i])));

	return 0*printf("%d\n",ans);

}

F-Sweet Alchemy

题意：有棵树，每个点都有代价，要求从上面取点，单个点可取多次，孩子取的次数大于等于父亲的次数且小于等于父亲次数\(+D\)，代价和不超过\(X\)，求最多取多少次。

很容易转化题面为：

每个点的代价为子树代价和，价值为子树大小，除\(1\)点可取inf次外，其它都只能选最多\(D\)个

除了\(n\)，以及价值很小（\(\le 50\)），其它都很大

考虑贪心做法：每次取性价比高的，取到不能取为止

但是这么做是有问题的

假设有一种做法，性价比高的还剩下50个，而性价比低已经选了50个，那么可以将他们互换，数量为对方的价值大小，这样贡献不变，体积减小

因为如果性价比高的数有\(>50\)个没选，那么性价比低的数选的数量一定\(<50\)，所以将物品分为两个部分，第一个部分每个物品为50个（或者少于50个），\(f[i],i\le N^3\)，表示达到这样价值需要的最少体积，第二个部分为剩下部分，贪心选择性价比高的就可以了

最后枚举第一个部分贡献的价值，求第二个部分的最大价值即可

发现答案一定再枚举的方案中

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

const int MN=51;

ll N,X,D,v[MN],p[MN],z[MN],id[MN],nm[MN];

vector<int>s[MN];

void dfs(int x)

{

	reg int i;p[x]=1;

	for(i=s[x].size()-1;~i;--i)

		dfs(s[x][i]),v[x]+=v[s[x][i]],p[x]+=p[s[x][i]];

}

ll f[MN*MN*MN];

bool cmp(const int&x,const int&y){return p[x]*v[y]>p[y]*v[x];}

signed main()

{

	N=read(),X=read(),D=read();

	reg ll i,j,k;ll lim=0;

	for(v[1]=read(),i=2;i<=N;++i)

		v[i]=read(),s[read()].push_back(i),z[i]=min(D,N);

	dfs(1);z[1]=N;

	for(i=1;i<=N;++i)lim+=z[i]*p[i];

	for(i=1;i<=lim+1;++i)f[i]=1e18;

	for(i=1;i<=N;++i)for(j=lim;j;--j)

	{

		ll r=min(z[i],j/p[i]);

		for(k=1;k<=r;++k)f[j]=min(f[j],f[j-p[i]*k]+v[i]*k);

		f[j]=min(f[j],f[j+1]);

	}

	for(z[1]=1e18,i=2;i<=N;++i)z[i]=D-z[i];

	for(i=1;i<=N;++i)id[i]=i;

	std::sort(id+1,id+N+1,cmp);

	ll ans=0;

	for(j=X,i=1;i<=N;++i)

	{

		nm[i]=min(z[id[i]],j/v[id[i]]);

		ans+=p[id[i]]*nm[i];

		j-=v[id[i]]*nm[i];

	}

	ll tmp=ans;

	for(j=X-j,k=i,i=1;i<=lim;++i)

	{

		if(f[i]>X)break;

		ll most=X-f[i];

		while(j>most)

		{

			while(!nm[k])--k;

			ll n=(j-most+v[id[k]]-1)/v[id[k]];

			n=min((ll)n,nm[k]);nm[k]-=n;

			j-=v[id[k]]*n;tmp-=p[id[k]]*n;

		}

		ans=max(ans,tmp+i);

	}

	printf("%lld\n",ans);

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

05-11 22:09
Powered by LMLPHP ©2024 Pizza 0.059618