《安徽省年度“达内杯”程序设计大赛解题报告(doc 19页)》由会员分享，可在线阅读，更多相关《安徽省年度“达内杯”程序设计大赛解题报告(doc 19页)（18页珍藏版）》请在金锄头文库上搜索。
1、n更多企业学院： 中小企业管理全能版183套讲座+89700份资料总经理、高层管理49套讲座+16388份资料中层管理学院46套讲座+6020份资料国学智慧、易经46套讲座人力资源学院56套讲座+27123份资料各阶段员工培训学院77套讲座+ 324份资料员工管理企业学院67套讲座+ 8720份资料工厂生产管理学院52套讲座+ 13920份资料财务管理学院53套讲座+ 17945份资料销售经理学院56套讲座+ 14350份资料销售人员培训学院72套讲座+ 4879份资料安徽省2011“达内杯”程序设计大赛解题报告A-幸运数字此题只需题目描述解即可，没有任何算法和trick.#include u
2、sing 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(yesn); else printf(non); return 0;B-转换二叉树首先根据先序序列和中序序列建立二叉树，然后按要求先序遍历一遍二叉树即可。当然，由于建树过程实际也是在先序遍历二叉树，所以可以不用实际建树，只是模拟那个过程，然后再过程中输出即可。建树过程简单的说就是以先序序列定根节点，以中序序列和和根节点定左
3、右子树。#include #include using namespace std;const int maxn = 27;int N;char PreOrdermaxn, InOrdermaxn;void DFS(int PreStart, int PreEnd, int InStart, int InEnd) int pos; for (pos = InStart; PreOrderPreStart != InOrderpos; pos+) if (pos != InStart) printf(); DFS(PreStart + 1, PreStart + pos - InStart, I
4、nStart, pos - 1); printf(); printf(%c, PreOrderPreStart); 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,
5、 len - 1); printf(n); return 0;C-取石子首先给出必胜结论，只要n != 2x，则先手必胜。证明：假设n = 12，将它转换为二进制则为1100。先手第一次取只需把二进制中从低位数起第一个1取走即可。在这个例子中，先手留给后手石子数的二进制为1000。这样后手能取的石子数的二进制范围为0001-0100，无论后手怎么取，它都不可能把所有数字都取完，而且取了之后剩下的石子数的二进制后3位肯定有一个1。先手只需再次将从低位数起的第一个1取走即可重复上述过程直至游戏结束。而如果先手第一次面对的石子数是2x个，由于他第一次不能把石子都取完，所以他无论如何取都会把上述必胜状
6、态留给对手。同样根据上述证明方法可以证明如果先手必胜，那么他第一次取的最少石子数就是石子数的二进制中，从低位数起的第一个1。#include 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(losen); else printf(win %dn, t); return 0;D-关键词统计这题最佳解法是先建立单词的字典树，然后再把文章中的单词一个一个抠出来进行匹配，时间复杂度是O(m+n)。m是文
7、章长度，n是单词总长度。但是省赛时我们数据放得比较松，只要是把单词一个一个抠出来比较的都能过。#include using namespace std;const int maxn = 10162;const int maxm = 200005;struct Node int next26; int index; void init() memset(next, -1, sizeof(next); index = -1; tiremaxn*5;char strmaxm, word50;int cuntmaxn, nxtmaxn, sz, idx;void insert(char *s) int
8、 p = 0; while (*s) int v = *s - a; if (tirep.nextv = -1) tirep.nextv = +sz; tiresz.init(); p = tirep.nextv; s+; nxtidx = tirep.index; tirep.index = idx+;void find(char *s) int p = 0; while (*s) int v = *s - a; if (tirep.nextv = -1) return; p = tirep.nextv; s+; for (p = tirep.index; p != -1; p = nxtp
9、) cuntp+;bool lowercase(const char &c) return a = c & c = z;bool uppercase(const char &c) return A = c & c = Z;int main() int n, i, t; gets(str); scanf(%d%*c, &n); memset(cunt, 0, 4 * n); tire0.init(); for (i = 0; i n; i+) scanf(%s, word); insert(word); for (i = t = 0; ; i+) if (lowercase(stri) word
10、t+ = stri; else if (uppercase(stri) wordt+ = stri + 32; else if (t) wordt = 0; find(word); t = 0; if (!stri) break; for (i = 0; i n; i+) printf(%dn, cunti); return 0;E-搬书这题很多人可能想复杂了，比赛中有的队是用DP过的。但其实只要对体积进行二分，然后暴力法测试即可。二分体积时间复杂度O(logd)，测试时间复杂度O(n+m)。所以总的时间复杂度是O(n+m)logd)，其中d是箱子体积最大可能值和最小可能值之差，n是书的数量，m是箱子的数量。#include using namespace std;const int maxn = 1000;int vmaxn;int main() int n, m; int maxv, minv; int left, right, mid, cunt, ptr, leave; while (scanf(%d %d, &n, &m) != EOF) maxv = minv = 0; for (int i = 0; i minv) minv = vi; left = minv, right = maxv; while (left right)
