哈哈哈封面图是题目描述里面的。本场比赛是HDU女生专场的clone。

A

HDU - 5702

题目大意

一次ACM中打气球的志愿者们比较蠢，某一道题提前打好的气球越多，意味着题目越水。
现在给出每道题打好的气球数，问你按照什么顺序做题，能够得以从易到难的顺序解决所有问题。

思路

直接开个结构体排序就好了。结果我一直PE，因为题目中说了不能有多余的空格，但是删掉所有多余的空格了还是不行，到最后都没有过。最后发现，必须要有多余的空行（什么鬼破题）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
struct node
{
	char str[15];
	int x;
} a[maxn];
int T,n;
bool cmp(node a,node b) {return a.x>b.x;}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%s%d",a[i].str,&a[i].x);
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++)
		{
			if(i==n) printf("%s",a[i].str);
			else printf("%s ",a[i].str);
		}
		printf("\n");
	}
	return 0;
}

B

HDU - 5704

题目大意

n（2~100）个人参加一个游戏，
每个人选择1~100范围的数。
然后得到所有数的平均数，再*=2/3，设得到的数为m。
如果一个人选的数，比m小，且相距m最为接近，那么其便在所有选数相同的人中等概率中奖。

现在，我们也参加比赛，其他n-1个人所选择的数也已经确定了，并且我们知道。
问你，选什么数拥有最高中奖率，并输出。

思路

直接枚举每一种情况，取最大值就好。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=200005;
int T,n,a[maxn],cnt[maxn];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(cnt,0,sizeof(cnt));
		int sum=0,maxx=0;
		scanf("%d",&n);
		for(int i=1;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			cnt[a[i]]++;
		}
		for(int i=0;i<=100;i++)
		{
			double k=(double)sum+(double)i;
			k/=(double)n;
			double m=k*2.0/3.0;
			if(i<=floor(m)) maxx=floor(m);
		}
		printf("%d %.2lf\n",maxx,1.0/(cnt[maxx]+1.0));
	}
	return 0;
}

C

HDU - 5706

题目大意

给一个n*m的由小写字母组成的字符地图，从某个点开始，每次沿着相邻的点走，如果从起点开始计数，连着走4步并且构成“girl”，那么girl数++；如果连着走3步并且构成“cat”，那么cat数++。请问图上有多少个girl和多少只cat。

思路

把每一个点作为起点开始搜索，直接dfs或bfs即可。这道题又吃了看错题意的亏……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=2005;
char str[maxn][maxn];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,m,T;
long long cat,girl;
void dfs1(int x,int y,int cnt)
{
	if(cnt==4)
	{
		girl++;
		return;
	}
	for(int i=1;i<=4;i++)
	{
		int ddx=dx[i]+x,ddy=dy[i]+y;
		if(cnt==1&&str[ddx][ddy]=='i') dfs1(ddx,ddy,cnt+1);
		if(cnt==2&&str[ddx][ddy]=='r') dfs1(ddx,ddy,cnt+1);
		if(cnt==3&&str[ddx][ddy]=='l') dfs1(ddx,ddy,cnt+1);
	}
}
void dfs2(int x,int y,int cnt)
{
	if(cnt==3)
	{
		cat++;
		return;
	}
	for(int i=1;i<=4;i++)
	{
		int ddx=dx[i]+x,ddy=dy[i]+y;
		if(cnt==1&&str[ddx][ddy]=='a') dfs2(ddx,ddy,cnt+1);
		if(cnt==2&&str[ddx][ddy]=='t') dfs2(ddx,ddy,cnt+1);
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);cat=girl=0;
		memset(str,0,sizeof(str));
		for(int i=1;i<=n;i++) scanf("%s",str[i]+1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				if(str[i][j]=='g') dfs1(i,j,1);
				if(str[i][j]=='c') dfs2(i,j,1);
			}
		printf("%lld %lld\n",girl,cat);
	}
	return 0;
}

D

HDU - 5710

题目大意

令s(n)为n的各位数之和，如n=12345时，s(n)=1+2+3+4+5=15。现在给定a，b，求找出最小的正整数n满足

a×s(n)==b×s(2⋅n)  (1≤a,b≤100)a\times s(n)==b\times s(2\cdot n)\;(1\leq a,b\leq100)

思路

转自：qq_40875849

HDU5710

E

HDU - 2670

题目大意

有n个男生追一个女生，每个男生有一个相应的爱慕值Vx(i)，给定一个天数m，每天这个女生只能找一个女生，并且得到这个男生的爱慕值。每过一天，每个男生的爱慕值就会减少相应的 Vy(i)；问女生如何选择，m天之后，才能得到最大的爱慕值。

思路

好像是经典的背包问题，感觉很早很早之前做过。
一个男生要么选要么不选，可以看作只有0和1两种情况，所以直接做01背包即可。
但我们先按下降速度从大到小排序，因为如果这样的话保证了先选一定比后选优，也就是说如果之前都没选，那么后面也不可能选，保证了dp的无后效性原则。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=2005;
int f[maxn],n,k;
struct node {int love,cost;} stu[maxn];
bool cmp(node a,node b) {return a.cost>b.cost;}
int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		for(int i=1;i<=n;i++) scanf("%d",&stu[i].love);
		for(int i=1;i<=n;i++) scanf("%d",&stu[i].cost);
		sort(stu+1,stu+n+1,cmp);
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
			for(int j=k;j;j--)
				f[j]=max(f[j],f[j-1]+stu[i].love-stu[i].cost*(j-1));
		printf("%d\n",f[k]);
	}
	return 0;
}

F

HDU - 2674

题目大意

Calculate  N!  mod  2009  (0≤N≤109)Hint  :  0!  =  1,  N!  =  N×(N−1)!Calculate\;N!\;mod\;2009\;(0\leq N\leq10^9)\\Hint\;:\;0!\;=\;1,\;N!\;=\;N\times(N-1)!

思路

显然2009的倍数mod上2009等于0，那么当计算到2009的阶乘时，答案就已经为0了，而0乘任何数都等于0，所以当N > 2009时，直接输出0就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=200005;
unsigned long long fac[maxn];
int n;
int main()
{
	fac[0]=fac[1]=1;
	for(unsigned long long i=2;i<maxn;i++)
	{
		fac[i]=i*fac[i-1];
		fac[i]%=2009;
	}
	while(~scanf("%d",&n))
	{
		if(n>=2009) printf("0\n");
		else printf("%llu\n",fac[n]);
	}
	return 0;
}

G

HDU - 2672

题目大意

GDJIJ,EL SSJT UT YWOSQNIVZMI. -> HELLO,MY NAME IS LINDAINVERS.
CN WLP JRVMFGQ BVR,IJCFI? -> DO YOU REQUIRE AID,HUMAN?
NMAB VYNNF, FI’E VC HP IXJ ZLQZI. -> ONCE AGAIN, IT’S UP TO THE ELVES.
SGC CGGJX GC BMHVQ BGU BCIHNYNBX GNPLV! -> THE FLOWS OF MAGIC ARE WHIMSICAL TODAY!

输入一个字符串，根据以上规律解码后输出。

思路

什么条件都没给，肯定和字符串字母变换直接有关。先写了一个打表程序，看了一下解码串与原串的ascii码差，发现是斐波拉契数列。于是，直接模拟就好了，注意空格和非大写字母字符不转码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
#include&#60; string &#62;
#include&#60; iostream &#62;
using namespace std;
const int maxn=200005;
unsigned long long a[maxn];
int main()
{
	string s;
	a[1]=1;a[2]=1;
	for(int i=3;i<maxn;i++) a[i]=a[i-1]+a[i-2],a[i]%=26;
	while(getline(cin,s))
	{
		int len=s.length(),cnt=1;
		for(int i=0;i<len;i++)
		{
			if(s[i]<'A'||s[i]>'Z') cout<<s[i];
			else
			{
				s[i]='A'+(s[i]+a[cnt]-'A')%26;
				cout<<s[i];
				cnt++;
			}
		}
		cout<<endl;
		s.clear();
	}
	return 0;
}

H

HDU - 5707

题目大意

给定a，b，c三个串，问c能否按序分成a和b串，不要求连续。

思路

首先想到扫两遍，但这样会有问题，因为比如aaa，daf，adafaa，就会发现第一遍扫的时候，占用了前面的一个a，导致了第二遍匹配失败。
既然这样不行，要保证无后效性，那显然就是dp了，用f[i][j]表示a串的i个位置和b串的j个位置能否匹配到c串的i+j个位置。那么转移也就是从i-1或者j-1转移而来了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=2005;
char s1[maxn],s2[maxn],s3[maxn];
int cnt[maxn],cnt2[maxn];
bool vis[maxn],f[maxn][maxn];
int main()
{
	while(~scanf("%s%s%s",s2+1,s3+1,s1+1))
	{
		memset(cnt,0,sizeof(cnt));
		memset(cnt2,0,sizeof(cnt2));
		memset(vis,true,sizeof(vis));
		memset(f,false,sizeof(f));
		bool flag=true;
		int l1=strlen(s1+1),l2=strlen(s2+1),l3=strlen(s3+1);
		for(int i=1;i<=l1;i++) cnt[s1[i]]++;
		for(int i=1;i<=l2;i++) cnt2[s2[i]]++;
		for(int i=1;i<=l3;i++) cnt2[s3[i]]++;
		for(int i=0;i<maxn;i++)
			if(cnt[i]!=cnt2[i]) flag=false;
		f[0][0]=true;
		for(int i=0;i<=l2;i++)
		{
			for(int j=0;j<=l3;j++)
			{
				//i:l2 j:l3
				if(i&&f[i-1][j]&&s2[i]==s1[i+j]) f[i][j]=true;
				if(j&&f[i][j-1]&&s3[j]==s1[i+j]) f[i][j]=true;
			}
		}
		if(l2+l3!=l1) flag=false;
		if(!f[l2][l3]) flag=false;
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

总结

难度不大，但是那个PE真的把我坑惨了……以后要多试试，因为你根本不知道出题人想让你干什么。

rank