第一题 找啊找啊找GF
题目背景
“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”
“诶，别再见啊…”
七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。
但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。
题目描述
sqybi 现在看中了 n个 MM，我们不妨把她们编号 1到 n。请 MM 吃饭是要花钱的，我们假设请 i号 MM 吃饭要花 r m b [ i ] 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 i号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 r p [ i ]的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 i 个 MM 来说叫做 t i m e [ i ] 。sqybi 保证自己有足够的魅力用 t i m e [ i ] 的时间搞定第 i个 MM _。
sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。
sqybi 现在有 m块大洋,他也通过一段时间的努力攒到了 r 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。
注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…
输入格式
输入的第一行是 n ，表示 sqybi 看中的 MM 数量。
接下来有 n 行，依次表示编号为 1 , 2 , 3 , … , n 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：r m b，r p 和 t i m e。
最后一行有两个整数，分别为 m 和 r 。
输出格式
你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。
样例 #1
样例输入 #1
4 1 2 5 2 1 6 2 2 2 2 2 3 5 5
样例输出 #1
13
提示
sqybi 说：如果题目里说的都是真的就好了…
sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 0），他要用这些时间出七夕比赛的题来攒 rp…
【数据规模】
对于 20 %的数据，1 ≤ n ≤ 10 ；
对于 100 % 的数据，1 ≤ r m b ≤ 100 ，1 ≤ r p ≤ 100，1 ≤ t i m e ≤ 1000 。
对于 100 % 的数据，1 ≤ m , r , n ≤ 100 。
解题思路
1）二维01背包.
2）注意人数的重要性大于时间。
参考代码
#include<bits/stdc++.h> 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&×[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; }
第二题 [NOIP2001 普及组] 求先序排列
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。
输入格式
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串，表示一棵二叉树的先序。
样例 #1
样例输入 #1
BADC BDCA
样例输出 #1
ABCD
解题思路
1）后序遍历中，最后一个节点一定是根节点。
2）递归将一棵树分成两颗子树，找到他们的父节点，不断递归输出。
参考代码
#include<bits/stdc++.h> 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; }
第三题 取数游戏
题目描述
一个N × M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
输入格式
第1行有一个正整数T，表示了有T TT组数据。
对于每一组数据，第一行有两个正整数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
271 172 99
提示
对于第1组数据，取数方式如下：
[67] 75 63 10
29 29 [92] 14
[21] 68 71 56
8 67 [91] 25
对于20 % 的数据，N , M ≤ 3 ；
对于40 % 的数据，N , M ≤ 4 ；
对于60 %的数据，N , M ≤ 5 ；
对于100 % 的数据，N , M ≤ 6 , T ≤ 20。
解题思路
1）深度优先搜索。
2）遍历时若取该数字，标记周围一圈的数字。
3）进行回溯后，查找下一个。
参考代码
#include<bits/stdc++.h> 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; }
统计方形（数据加强版）
题目背景
1997年普及组第一题
题目描述
有一个 n × m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。
输入格式
一行，两个正整数 n , m （n ≤ 5000 , m ≤ 5000 ）。
输出格式
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。
样例 #1
样例输入 #1
2 3
样例输出 #1
8 10
解题思路
1）正方形的右下角为(i,j)时，正方形的个数为Min(i,j)。
2）长方形的右下角为(i,j)时，长方形的个数为i*j。
参考代码
#include<iostream> 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; }
