第一题 [USACO3.4] 美国血统 American Heritage
题目描述
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 26 个的顶点。 这是在样例输入和 样例输出中的树的图形表达方式：
C / \ / \ B G / \ / A D H / \ E F
树的中序遍历是按照左子树，根，右子树的顺序访问节点。
树的前序遍历是按照根，左子树，右子树的顺序访问节点。
树的后序遍历是按照左子树，右子树，根的顺序访问节点。
输入格式
第一行： 树的中序遍历
第二行： 同样的树的前序遍历
输出格式
单独的一行表示该树的后序遍历。
样例 #1
样例输入 #1
ABEDFCHG CBADEFGH
样例输出 #1
AEFDBHGC
提示
题目翻译来自NOCOW。
USACO Training Section 3.4
解题思路
1）找到根结点。
2）递归左子树。
2）递归右子树。
参考代码
#include <bits/stdc++.h> using namespace std; string s1,s2; void houxu(int l1,int r1,int l2,int r2) { int m=s2.find(s1[l1]); if(m>l2) houxu(l1+1,l1+m-l2,l2,m-1); if(m<r2) houxu(l1+m-l2+1,r1,m+1,r2); cout<<s1[l1]; } int main() { cin>>s2>>s1; houxu(0,s1.size()-1,0,s2.size()-1); return 0; }
第二题 生日
题目描述
cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。
输入格式
输入共有 2 行，
第 1 行为 OI 组总人数 n；
第 2 行至第 n + 1 行分别是每人的姓名 s、出生年 y 、月 m 、日 d 。
输出格式
输出共有 n 行，
即 n 个生日从大到小同学的姓名。（如果有两个同学生日相同，输入靠后的同学先输出）
样例 #1
样例输入 #1
3 Yangchu 1992 4 23 Qiujingya 1993 10 13 Luowen 1991 8 1
样例输出 #1
Luowen Yangchu Qiujingya
提示
数据保证，1 < n < 100 ，1 ≤ ∣ s ∣ < 20。保证年月日实际存在，且年份 ∈ [ 1960 , 2020 ] 。
解题思路
1）结构体的比较排序。
参考代码
#include<bits/stdc++.h> using namespace std; int i,j,k,n,m; struct student{ string name; int year,mon,day,level; }a[1001]; int cmp(student a,student b) { if(a.year != b.year) return a.year < b.year; else { if(a.mon != b.mon) return a.mon < b.mon; else if(a.day == b.day && a.mon == b.mon) return a.level > b.level; else if(a.day != b.day && a.mon == b.mon) return a.day < b.day; } } int main() { cin>>n; for(i=1;i<=n;i++) { cin>>a[i].name>>a[i].year>>a[i].mon>>a[i].day; a[i].level=i; } sort(a+1,a+1+n,cmp); for(i=1;i<=n;i++) cout<<a[i].name<<endl; return 0; }
第三题 [NOIP2001 提高组] 数的划分
题目描述
将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：n = 7 ，k = 3 ，下面三种分法被认为是相同的。
1 , 1 , 5 ;
1 , 5 , 1 ;
5 , 1 , 1.
问有多少种不同的分法。
输入格式
n , k（6 < n ≤ 200 ，2 ≤ k ≤ 6 ）
输出格式
1 个整数，即不同的分法。
样例 #1
样例输入 #1
7 3
样例输出 #1
4
提示
四种分法为：
1 , 1 , 5 ;
1 , 2 , 4 ;
1 , 3 , 3 ;
2 , 2 , 3 .
解题思路
1）深度优先搜索。
参考代码
#include<bits/stdc++.h> using namespace std; int ans; void dfs(int x,int n,int k) { if(n==1) { ans++; return; } for(int i=x;i<=k/n;i++) dfs(i,n-1,k-i); } int main() { int n,k; cin>>n>>k; dfs(1,k,n); cout<<ans; return 0; }
第四题 [BOI2009]Radio Transmission 无线传输
题目描述
给你一个字符串 s 1 ，它是由某个字符串 s 2 不断自我连接形成的。但是字符串 s 2 是不确定的，现在只想知道它的最短长度是多少。
输入格式
第一行一个整数 L，表示给出字符串的长度。
第二行给出字符串 s 1的一个子串，全由小写字母组成。
输出格式
仅一行，表示 s 2 的最短长度。
样例 #1
样例输入 #1
8 cabcabca
样例输出 #1
3
提示
样例输入输出 1 解释
对于样例，我们可以利用 abc 不断自我连接得到 abcabcabc ，读入的 cabcabca ，是它的子串。
规模与约定
对于全部的测试点，保证 1 < L ≤
。
解题思路
1）kmp算法。
参考代码
#include<cstdio> using namespace std; int n,next[1000050]; char ss[1000050]; int main() { scanf("%d%s",&n,ss+1); int j=0; for(int i=2;i<=n;++i) { while(j&&ss[i]!=ss[j+1]) j=next[j]; if(ss[i]==ss[j+1]) ++j; next[i]=j; } printf("%d",n-kmp[n]); return 0; }
