【c++百日刷题计划】 ———— DAY20，刷题百天，养成刷题好习惯

第一题 找啊找啊找GF

题目背景

“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”

“诶，别再见啊…”

七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。

但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

题目描述

sqybi 现在看中了 $n$ 个 MM，我们不妨把她们编号 $1$ 到 $n$。请 MM 吃饭是要花钱的，我们假设请 $i$ 号 MM 吃饭要花 $rmb[i]$ 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 $i$ 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 $rp[i]$ 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 $i$ 个 MM 来说叫做 $time[i]$。sqybi 保证自己有足够的魅力用 $time[i]$ 的时间搞定第 $i$ 个 MM ^_。

sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有 $m$ 块大洋,他也通过一段时间的努力攒到了 $r$ 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…

输入格式

输入的第一行是 $n$，表示 sqybi 看中的 MM 数量。

接下来有 $n$ 行，依次表示编号为 $1,2,3,\dots ,n$ 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：$rmb$，$rp$ 和 $time$。

最后一行有两个整数，分别为 $m$ 和 $r$。

输出格式

你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。

样例 #1

样例输入 #1

4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
1
2
3
4
5
6

样例输出 #1

13
1

提示

sqybi 说：如果题目里说的都是真的就好了…

sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 $0$），他要用这些时间出七夕比赛的题来攒 rp…

【数据规模】

对于 $20\%$ 的数据，$1\le n\le 10$；
对于 $100\%$ 的数据，$1\le rmb\le 100$，$1\le rp\le 100$，$1\le time\le 1000$。
对于 $100\%$ 的数据，$1\le m,r,n\le 100$。

解题思路

• 1）二维01背包.
• 2）注意人数的重要性大于时间。

参考代码

#include
using namespace std;
int dp[105][105],times[105][105];
int main()
{
	int n,m,r;
	int rmb[105],rp[105],time[105];
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>rmb[i]>>rp[i]>>time[i];
	cin>>m>>r;
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=rmb[i];j--)
		{
			for(int k=r;k>=rp[i];k--)
			{
				if(dp[j][k]<dp[j-rmb[i]][k-rp[i]]+1)
				{
					dp[j][k]=dp[j-rmb[i]][k-rp[i]]+1;
					times[j][k]=times[j-rmb[i]][k-rp[i]]+time[i];
				}
				if(dp[j][k]==dp[j-rmb[i]][k-rp[i]]+1&&times[j][k]>times[j-rmb[i]][k-rp[i]]+time[i])
				{
					times[j][k]=times[j-rmb[i]][k-rp[i]]+time[i];
				}
			
			}
		}
	}
	cout<<times[m][r];
	return 0;
}
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

第二题 [NOIP2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

样例 #1

样例输入 #1

BADC
BDCA
1
2

样例输出 #1

ABCD
1

解题思路

• 1）后序遍历中，最后一个节点一定是根节点。
• 2）递归将一棵树分成两颗子树，找到他们的父节点，不断递归输出。

参考代码

#include 
using namespace std;
string mid, aft;
void dfs(int ml, int mr, int al, int ar) 
{
    if (ml > mr || al > ar) 
        return;
        printf("%c", aft[ar]);
    for (int k = ml; k <= mr; k++) 
	{
        if (mid[k] == aft[ar]) 
		{
            dfs(ml, k-1, al, al+k-ml-1);
            dfs(k+1, mr, al+k-ml, ar-1);
            break; 
        }
    }
}
int main(void)
 {
    cin>>mid>>aft;
    int len = mid.size()-1;
    dfs(0, len, 0, len);
    return 0;    
}
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

第三题 取数游戏

题目描述

一个$N\times M$的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻$8$个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式

第1行有一个正整数$T$，表示了有$T$组数据。

对于每一组数据，第一行有两个正整数$N$和$M$，表示了数字矩阵为$N$行$M$列。

接下来$N$行，每行$M$个非负整数，描述了这个数字矩阵。

输出格式

$T$行，每行一个非负整数，输出所求得的答案。

样例 #1

样例输入 #1

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1
1
2
3
4
5
6
7
8
9
10
11
12
13

样例输出 #1

271
172
99
1
2
3

提示

对于第1组数据，取数方式如下：

[67] 75 63 10

29 29 [92] 14

[21] 68 71 56

8 67 [91] 25

对于$20\%$的数据，$N,M\le 3$；

对于$40\%$的数据，$N,M\le 4$；

对于$60\%$的数据，$N,M\le 5$；

对于$100\%$的数据，$N,M\le 6,T\le 20$。

解题思路

• 1）深度优先搜索。
• 2）遍历时若取该数字，标记周围一圈的数字。
• 3）进行回溯后，查找下一个。

参考代码

#include
using namespace std;
const int d[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int t,n,m,s[8][8],mark[8][8],ans,mx;
void dfs(int x,int y)
{
	if(y==m+1)
	{ 
		dfs(x+1,1);
		return;
	}
	if(x==n+1)
	{
		mx=max(ans,mx);
		return;
	}
	
	dfs(x,y+1);
	
	if(mark[x][y]==0)
	{ 
		ans+=s[x][y];
		for(int fx=0;fx<8;++fx)
		{ 
			mark[x+d[fx][0]][y+d[fx][1]]++;
		}
		dfs(x,y+1);
		for(int fx=0;fx<8;++fx)
		{ 
			mark[x+d[fx][0]][y+d[fx][1]]--;
		}
		ans-=s[x][y];
	}
	
}
int main()
{
	cin>>t; 
	while(t--)
	{
		memset(s,0,sizeof(s));
		memset(mark,0,sizeof(mark)); 
		cin>>n>>m;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
			{
				cin>>s[i][j];
			}
		}
		mx=0;
		dfs(1,1); 
		cout<<mx<<endl;
	}
	return 0;
}
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

统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 $n\times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 $n,m$（$n\le 5000,m\le 5000$）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

2 3
1

样例输出 #1

8 10
1

解题思路

• 1）正方形的右下角为(i,j)时，正方形的个数为Min(i,j)。
• 2）长方形的右下角为(i,j)时，长方形的个数为i*j。

参考代码

#include
using namespace std;
int main()
{
	long long n,m,i,j,sum=0,sum1=0;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
	  for(j=1;j<=m;j++)
	  {
	    sum+=min(i,j);
	    sum1+=i*j;
	  }
	}
	
	cout<<sum<<" "<<sum1-sum<<endl;
	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19