2011年安徽省第二届“达内杯”程序设计比赛试题答案.docVIP

安徽省2011“达内杯”程序设计大赛解题报告 A-幸运数字 此题只需题目描述解即可，没有任何算法和trick... #include iostream using namespace std; int main() { int n; while (scanf(%d, n) != EOF) { int t = n, s = 0; while (t) { s += t % 10; t /= 10; } if (n % s == 0) printf(yes\n); else printf(no\n); } return 0; } B-转换二叉树 首先根据先序序列和中序序列建立二叉树，然后按要求先序遍历一遍二叉树即可。当然，由于建树过程实际也是在先序遍历二叉树，所以可以不用实际建树，只是模拟那个过程，然后再过程中输出即可。建树过程简单的说就是以先序序列定根节点，以中序序列和和根节点定左右子树。 #include iostream #include string.h using namespace std; const int maxn = 27; int N; char PreOrder[maxn], InOrder[maxn]; void DFS(int PreStart, int PreEnd, int InStart, int InEnd) { int pos; for (pos = InStart; PreOrder[PreStart] != InOrder[pos]; pos++) {} if (pos != InStart) { printf((); DFS(PreStart + 1, PreStart + pos - InStart, InStart, pos - 1); printf()); } printf(%c, PreOrder[PreStart]); if (pos != InEnd) { printf((); DFS(PreStart + pos - InStart + 1, PreEnd, pos + 1, InEnd); printf()); } } int main() { int i, len; scanf(%d, N); getchar(); for (i = 0; i N; i++) { scanf(%s %s, PreOrder, InOrder); len = strlen(PreOrder); DFS(0, len - 1, 0, len - 1); printf(\n); } return 0; } C-取石子 首先给出必胜结论，只要n != 2^x，则先手必胜。证明：假设n = 12，将它转换为二进制则为1100。先手第一次取只需把二进制中从低位数起第一个1取走即可。#include iostream using namespace std; int main() { int n, t; while (scanf(%d, n) != EOF) { t = 1; while (!(n 1)) { n = 1; t = 1; } if (n == 1) printf(lose\n); else printf(win %d\n, t); } return 0; } D-关键词统计 这题最佳解法是先建立单词的字典树，然后再把文章中的单词一个一个抠出来进行匹配，时间复杂度是O(m+n)。m是文章长度，n是单词总长度。但是省赛时我们数据放得比较松，只要是把单词一个一个抠出来比较的都能过。 #include iostream using namespace std; const int maxn = 10162; const int maxm = 200005; struct Node { int next[26]; int index; void init() { memset(next,