Stilwell's Blog

有T恤的CF，不过对我来说T恤也就只是个幻像罢了

只做了ABC，值得庆幸的是没掉分，还涨了一点点

A  Feed with Candy

有两种共n个糖果，给个糖果有一个高度属性，需要一定的弹跳力才能够到，吃一个糖果会增加一定的弹跳力，两种糖果要交替吃，求最多能吃到的糖果数

Solution：贪心，每次吃能够到的能增加最多弹跳力的糖果

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int n,m,x,a,b,i,j,k,lim,ans1,ans2,Max;

struct node
{
	int t,h,x;
}t[2005];
inline bool cmp(const node &a,const node &b){return a.h<b.h;}

bool use[2005];

int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)scanf("%d%d%d",&t[i].t,&t[i].h,&t[i].x);
	sort(t+1,t+n+1,cmp);
	x=m;lim=0;t[0].x=-1;
	for(i=1;i<=n;++i)
	{
		while(lim<n&&t[lim+1].h<=x)++lim;
		Max=0;
		for(j=1;j<=lim;++j)if(t[j].t==i%2&&!use[j]&&t[j].x>t[Max].x)Max=j;
		if(!Max)break;
		x+=t[Max].x;use[Max]=true;
	}
	ans1=i-1;
	for(i=1;i<=n;++i)use[i]=false;
	x=m;lim=0;t[0].x=-1;
	for(i=1;i<=n;++i)
	{
		while(lim<n&&t[lim+1].h<=x)++lim;
		Max=0;
		for(j=1;j<=lim;++j)if(t[j].t!=i%2&&!use[j]&&t[j].x>t[Max].x)Max=j;
		if(!Max)break;
		x+=t[Max].x;use[Max]=true;
	}
	ans2=i-1;
	printf("%d\n",max(ans1,ans2));
}

B  Om Nom and Spiders

一张方格图上有一些蜘蛛，每个蜘蛛有一个移动方向，求从(1,x)开始往下走能遇到的蜘蛛数

Solution：每个蜘蛛只会对一个答案有贡献，直接算出

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int n,m,K,i,j,k;
int ans[2005];
char s[2005][2005];

int main()
{
	scanf("%d%d%d",&n,&m,&K);
	for(i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(i=1;i<=n;++i)
	for(j=1;j<=m;++j)
	{
		if(s[i][j]=='R'&&i+j-1<=m)++ans[i+j-1];
		if(s[i][j]=='L'&&j-i+1<=m)++ans[j-i+1];
		if(s[i][j]=='U'&&i%2==1)++ans[j];
	}
	printf("%d",ans[1]);
	for(i=2;i<=m;++i)printf(" %d",ans[i]);
	printf("\n");
}

C  Dungeons and Candies

需要传输一些文件，有两种传输方式：直接传输和在前面的基础上传输。求最小费用

Solution：Prim最小生成树

#include <stdio.h>
#include <stdlib.h>
using namespace std;

int n,m,K,w,i,j,k,a,b,tmp,aim;
char s[1005][15][15];
int cost[1005][1005];
int q[1005],fa[1005],Min[1005],from[1005],ans;
bool use[1005];

int main()
{
	scanf("%d%d%d%d",&n,&m,&K,&w);
	for(i=1;i<=K;++i)
	for(j=1;j<=n;++j)
	scanf("%s",s[i][j]+1);
	for(i=1;i<=K;++i)
	for(j=i+1;j<=K;++j)
	{
		tmp=0;
		for(a=1;a<=n;++a)
		for(b=1;b<=m;++b)
		if(s[i][a][b]!=s[j][a][b])
		++tmp;
		cost[i][j]=cost[j][i]=tmp*w;
	}
	for(i=1;i<=K;++i)cost[0][i]=cost[i][0]=n*m;
	for(i=1;i<=K;++i)Min[i]=n*m;
	for(i=1;i<=K;++i)
	{
		aim=0;
		for(j=1;j<=K;++j)
		if(!use[j])
		{
			if((!aim)||(Min[j]<Min[aim]))
			aim=j;
		}
		q[i]=aim;
		fa[aim]=from[aim];
		use[aim]=true;
		ans+=Min[aim];
		for(j=1;j<=K;++j)if(cost[aim][j]<Min[j])Min[j]=cost[aim][j],from[j]=aim;
	}
	printf("%d\n",ans);
	for(i=1;i<=K;++i)printf("%d %d\n",q[i],fa[q[i]]);
}

D  Pudding Monsters

一条带子上有一些特殊格子和一些monster，每次可以把一个monster向左或向右扔到第一个挡住的地方，相邻的monster会连在一起，问最多能覆盖多少特殊格子

Solution：DP，f[i]表示用前i个monster最多能覆盖的特殊格子数，以某个monster不动，枚举左右转移

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int n,m,i,j,k,Max,lim;
int a[100005],b[100005],l[100005],r[100005];
int f[100005];

int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=1;i<=m;++i)scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	a[0]=a[1]-1000;a[n+1]=a[n]+1000;
	for(i=1;i<=n;++i)if(a[i]==a[i-1]+1)l[i]=l[i-1];else l[i]=i;
	for(i=n;i>=1;--i)if(a[i]==a[i+1]-1)r[i]=r[i+1];else r[i]=i;
	lim=0;
	for(i=1;i<=n;++i)
	{
		while(lim<m&&b[lim+1]<=a[i])++lim;
		if(l[i]==i)Max=f[i-1]+(a[i]==b[lim]);
		else Max=-10000000;
		if(Max>f[i])f[i]=Max;
		for(j=lim;j>=1;--j)
		{
			k=i-(a[i]-b[j]);
			if(k<=0)break;
			k=l[k];
			if(f[k-1]+lim-j+1>f[i])f[i]=f[k-1]+lim-j+1;
			if(f[k-1]+lim-j+1>Max)Max=f[k-1]+lim-j+1;
		}
		for(j=lim+(b[lim]<a[i]);j<=m;++j)
		{
			k=i+(b[j]-a[i]);
			if(k>n)break;
			k=r[k];
			if(Max+j-lim>f[k])f[k]=Max+j-lim;
		}
		if(f[i]>f[i+1])f[i+1]=f[i];
	}
	printf("%d\n",f[n]);
}

E  Cardboard Box

有n个箱子，每个箱子可以选择0/1/2星，1/2星有耗时分别为a/b，求得到w个星的最小耗时

Solution：问题可以转化为使ans/w最小，那么把箱子拆点1星/2星，并分两类，一类为b-a≤a，那么权值设为b*0.5/b*0.5，否则权值设为a/b-a，按这个权值排序，最多有一个b*0.5/b*0.5的箱子只取了一半，即不合法情况，对这种情况微调下就行了

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int n,m,i,j,k;
int a[300005],b[300005],use[300005],cnt[600005];
int Inc,inc[300005],inc_val[300005];
long long ans,tmp;

struct node
{
	int x,id,id2;
}t[600005];
inline bool cmp(const node &a,const node &b)
{
	if(a.x!=b.x)return a.x<b.x;
	if(a.id2!=b.id2)return a.id2<b.id2;
	return a.id<b.id;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%d%d",&a[i],&b[i]);
		a[i]<<=1;b[i]<<=1;
		if(b[i]-a[i]<a[i])t[i].x=t[i+n].x=b[i]>>1,t[i].id2=i*2,t[i+n].id2=i*2+1;
		else t[i].x=a[i],t[i+n].x=b[i]-a[i];
		t[i].id=i;t[i+n].id=i+n;
	}
	sort(t+1,t+n+n+1,cmp);
	for(i=1;i<=m;++i)ans+=t[i].x,++cnt[t[i].id];
	if(t[m].id<=n&&!cnt[t[m].id+n]&&t[m].x!=a[t[m].id])
	{
		tmp=ans-t[m].x;
		ans=ans-t[m].x+a[t[m].id];
		--cnt[t[m].id];
		Inc=1;inc[Inc]=t[m].id;inc_val[Inc]=1;
		for(i=1;i<=n;++i)
		if(i!=t[m].id)
		{
			if(!cnt[i])
			{
				if(a[i]+tmp<ans)
				{
					Inc=0;
					inc[++Inc]=i;inc_val[Inc]=1;
					ans=a[i]+tmp;
				}
			}
			if(cnt[i]&&!cnt[i+n])
			{
				if(tmp+b[i]-a[i]<ans)
				{
					Inc=0;
					inc[++Inc]=i+n;inc_val[Inc]=1;
					ans=tmp+b[i]-a[i];
				}
				if(tmp-a[i]+b[t[m].id]<ans)
				{
					Inc=0;
					inc[++Inc]=i;inc_val[Inc]=-1;
					inc[++Inc]=t[m].id;inc_val[Inc]=1;
					inc[++Inc]=t[m].id+n;inc_val[Inc]=1;
					ans=tmp-a[i]+b[t[m].id];
				}
			}
			if(cnt[i]&&cnt[i+n])
			{
				if(tmp-b[i]+a[i]+b[t[m].id]<ans)
				{
					Inc=0;
					inc[++Inc]=i+n;inc_val[Inc]=-1;
					inc[++Inc]=t[m].id;inc_val[Inc]=1;
					inc[++Inc]=t[m].id+n;inc_val[Inc]=1;
					ans=tmp-b[i]+a[i]+b[t[m].id];
				}
			}
		}
		for(;Inc;--Inc)cnt[inc[Inc]]+=inc_val[Inc];
	}
	printf("%I64d\n",ans>>1);
	for(i=1;i<=n;++i)printf("%d",cnt[i]+cnt[i+n]);
	printf("\n");
}

F  Banners