安徽省年度“达内杯”程序设计大赛解题报告.doc

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 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(yesn); else printf(non); return 0;B-转换二叉树首先根据先序序列和中序序列建立二叉树，然后按要求先序遍历一遍二叉树即可。当然，由于建树过程实际也是在先序遍历二叉树，所以可以不用实际建树，只是模拟那个过程，然后再过程中输出即可。建树过程简单的说就是以先序序列定根节点，以中序序列和和根节点定左右子树。#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, InStart, 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, len - 1); printf(n); return 0;C-取石子首先给出必胜结论，只要n != 2x，则先手必胜。证明：假设n = 12，将它转换为二进制则为1100。先手第一次取只需把二进制中从低位数起第一个1取走即可。在这个例子中，先手留给后手石子数的二进制为1000。这样后手能取的石子数的二进制范围为0001-0100，无论后手怎么取，它都不可能把所有数字都取完，而且取了之后剩下的石子数的二进制后3位肯定有一个1。先手只需再次将从低位数起的第一个1取走即可重复上述过程直至游戏结束。而如果先手第一次面对的石子数是2x个，由于他第一次不能把石子都取完，所以他无论如何取都会把上述必胜状态留给对手。同样根据上述证明方法可以证明如果先手必胜，那么他第一次取的最少石子数就是石子数的二进制中，从低位数起的第一个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是文章长度，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 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) 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) wordt+ = 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) mid = (left + right) / 2; cunt = 0; leave = 0; for (ptr = 0; ptr n & cunt = vptr) leave -= vptr; else leave = mid - vptr; cunt+; if (cunt = m) right = mid; else left = mid + 1; printf(%dn, left); return 0;F-水晶球假设少女的相貌、智慧和财富分别是x、y和z。首先按x从大到小排序处理掉一维，然后建立一个map，它的key值是y，value值是z。然后从头到尾扫描所有少女。每扫描一个少女时，在map里找其y值的上界，如果它的上界对应的z要大于少女的z，则说明有少女无论x、y还是z都大于她。否则将这个少女的y值和z值插入到map里，并且将map里的无用数据删去，无论是y还是z都比少女小的值。当然这样粗略的讲，还有很多问题是被忽略过去的，比如说边界问题，两个值相同的问题，如何删去map中的无用数据等，这个大家可以参考标程。#include #include #include #include using namespace std;const int maxn = 50005;const int inf = 1000000005;struct Data int x, y, z; / 按x从大到小排，如果x相同，则按y从小到大排，如果y也相同，则按z从小到大排 bool operator oth.x; if (y != oth.y) return y oth.y; return z oth.z; datamaxn;int n, ans;map v;typedef map:iterator itr;int main() int i; while (scanf(%d, &n) != EOF) for (i = 0; i n; i+) scanf(%d, &datai.x); for (i = 0; i n; i+) scanf(%d, &datai.y); for (i = 0; i n; i+) scanf(%d, &datai.z);v.clear(); sort(data, data + n); vinf = -inf; v-inf = inf; for (i = 0, ans = 0; i n; i+) itr x = v.upper_bound(datai.y); if (datai.z second) ans+; else if (!v.count(datai.y) | vdatai.y second = datai.z; ) v.erase(x-); printf(%dn, ans); return 0;G-星际航行这题是后3题中唯一有队伍过的题，其实不算很难。只要把圆的向量和长方形的向量合并，然后把题目转换成圆在动，长方形静止或者长方形在动，圆静止这样的模型。然后问题就蜕化为圆与线段（长方形的边）相撞的问题。#include #include using namespace std;#define eps (1e-8)#define zero(x) (fabs(x)eps)struct point double x, y; point() point(double a, double b) x=a; y=b; point(point p1, point p2) x=p2.x-p1.x; y=p2.y-p1.y; point operator +(point p) return point( x+p.x, y+p.y); ;double xmult(point p1 ,point p2) return p1.x*p2.y-p2.x*p1.y;double xmult(point p1 ,point p2, point p0) return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);double dmult(point p1, point p2)return p1.x*p2.x+p1.y*p2.y;double dist(point a, point b) return sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);double disptoline(point p, point l1, point l2) return fabs( xmult(p,l1,l2) ) / dist(l1,l2); bool crossline(point o, double r, point v, point a, point b) if( zero(v.x) & zero(v.y) ) return false; double d = xmult( v, point(a,b) ); if( d=eps ) double da = xmult( v, point(o,a) ); double db = xmult( v, point(o,b) ); if( (da=eps) (db=eps) ) return true; point o1 = o+v; if( disptoline(a, o, o1)-r =-eps ) return true; if( disptoline(b, o, o1)-r -eps ) return false; return dmult(v, point(o,a) = eps;bool crossfull(point a, point b, point c, point v, point o, double r, point vo) point d = a+point(b,c); point vs(v,vo); return crossline(o, r, vs, a, c) | crossline(o, r, vs, b, d);int main() point a, b, c, v, o, vo; double r; while(cina.xa.yb.xb.yc.xc.yv.xv.yo.xo.yrvo.xvo.y) cout(crossfull(a,b,c,v,o,r,vo)?YES:NO)endl; return 0;H-技术员BangFu这题是状态DP，dp状态定为dp110107。第一维是二进制标记走过哪些节点，第二维是最后到达哪个节点，第三维是时间是星期几，而数组本身的值为最少花费了多少钱。最后用Spfa递推出所有状态即可。#include #include #include using namespace std;const int N = 15;const int D = 7;const int INF = 1000000000;struct Edge int y, p, t;struct Node int s, x, d;int n, m;int dp1NND, mk1NND;vector vN;queue q;void Init() int i, j, k, x; Edge tmp; for (i = 0; i n; i+) vi.clear(); for (i = 0; i m; i+) scanf(%d %d %d %d, &x, &tmp.y, &tmp.p, &tmp.t); vx.push_back(tmp); for (i = 0; i (1 n); i+) for (j = 0; j n; j+) for (k = 0; k D; k+) dpijk = INF, mkijk = 0; void Solve() Node now, nxt; now.s = 1, now.x = 0, now.d = 0; dpnow.snow.xnow.d = 0; mknow.xnow.xnow.d = 1; q.push(now); while (!q.empty() now = q.front(); q.pop(); int &x = now.x