[十一集训] Day1 (2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018))

A Altruistic Amphibians

原题

题目大意：

n只青蛙在高度为d的井中，每只有跳跃距离、重量和高度，每只青蛙可以借助跳到别的青蛙的背上而跳出井，每只青蛙能承受的最大重量是自身重量，求最多能出去多少青蛙。

题解：

因为青蛙能承受的重量小于等于自身重量，所以重的青蛙无法依靠轻的青蛙出井。因此，将青蛙按照重量降序排序，每个青蛙只能依靠排名在前的青蛙，问题便转化为01背包。dp[i][j]表示到第i个青蛙重量为j到达的最大高度，转移方程即为dp[i][j]=max(dp[i-1][j],dp[i-1][min(j+a[i].w,1e8)]).

代码：

#include<cstdio>

#include<algorithm>

#define N 100010

#define M 100000010

using namespace std;

int n,d,ans,dp[M];

struct hhh

{

	int l,w,h;

	bool operator < (const hhh &b) const

	{

		return w>b.w;

	}

}a[N];

int read()

{

	int ans=0,op=1;

	char c=getchar();

	for (;(c<'0' || c>'9') && c!='-';c=getchar()) ;

	if (c=='-') c=getchar(),op=-1;

	for (;c>='0' && c<='9';c=getchar()) ans*=10,ans+=c^48;

	return ans*op;

}

int main()

{

	n=read();d=read();

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

	{

		a[i].l=read();

		a[i].w=read();

		a[i].h=read();

	}

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

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

	{

		if (dp[a[i].w]+a[i].l>d) ans++;

		for (int j=1;j<a[i].w;j++)

			dp[j]=max(dp[j],dp[min(j+a[i].w,M-1)]+a[i].h);

	}

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

	return 0;

}

B Baby Bites

原题

签到题

#include<cstdio>

#include<cstring>

using namespace std;

int n,ANS=1,t;

char s[10];

int read()

{

	int ans=0,op=1;

	char c=getchar();

	for (;(c<'0' || c>'9') && c!='-';c=getchar()) ;

	if (c=='-') op=-1,c=getchar();

	for (;c>='0' && c<='9';c=getchar()) ans*=10,ans+=c^48;

	return ans*op;

}

bool isnumber()

{

	if (s[1]>='0' && s[1]<='9') return 1;

	return 0;

}

int change()

{

	int ans=0,l;

	l=strlen(s+1);

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

		ans*=10,ans+=s[i]^48;

	return ans;

}

int main()

{

	n=read();

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

	{

		++t;

		scanf("%s",s+1);

		if (isnumber())

		{

			j=change();

			ANS&=(j==t);

		}

	}

	if (ANS) printf("makes sense");

	else printf("something is fishy");

	return 0;

}

C Code Cleanups

原题

题目大意：

给出一年内的n个日期，在每个日期会投放一个垃圾，垃圾拥有一个肮脏值，其每天增加一，需要在总肮脏值小于等于20时进行清理（清理时只清理之前的，不清理当天的）。且在最后一天结束时必须为干净的。问最少清理几次。

题解：

暴力枚举

#include<cstdio>

#define N 400

using namespace std;

int n,d,a[N],l=1,r=1,now,ans;

//[l,r)

int read()

{

	int ans=0,op=1;

	char c=getchar();

	for (;(c<'0' || c>'9') && c!='-';c=getchar()) ;

	if (c=='-') op=-1,c=getchar();

	for (;c>='0' && c<='9';c=getchar()) ans*=10,ans+=c^48;

	return ans*op;

}

int main()

{

	n=read();

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

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

	{

		if (a[r]==i) r++;

		if (now+r-l>=20) ans++,now=0,l=r;

		else now+=r-l;

	}

	if (now) ans++;

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

	return 0;

}

巴特西

[十一集训] Day1 (2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018))

A Altruistic Amphibians

原题

B Baby Bites

原题

C Code Cleanups

原题

最新文章

热门文章