牛客网 2009 problemA 本题是要求【a,b】范围中的完数，也就是6=1+2+3；除了该数本身的其他因子之和等于该数就是完数。 大部分人能写出这个程序，在自己的编辑器上都能通过。但是牛客网的测试样例都很大，本题我一开始按照下面的程序写的，超时不能通过。后来发现1-10000内的完数就4个，大家都直接拿这四个数来做一些判断得到答案，算是一种偷分的方法吧。 后来终于发现了下面这个方法，还是和之前求素数的时候一样，把求一个素数的时间复杂度从O(n/2)降到O(根号n)。 比如说28，只需要从2判断到5即可。后面的大因数（7，14），也就是28除以小因数（2，4）的商。 /* 2009 A [a,b]完数 6 = 1+2+3 */ #include using namespace std; int mark[100001]={0}; int len=0; void wan(){ for(int j=6;j<9999;j++){ int sum = 1; // 最最最关键的for循环 for(int i=2;i*i<=j;i++){ if(j%i==0){ sum = sum+i+(j/i); } } if(sum == j){ mark[len++]=j; } } } int main(){ int a,b; wan(); while(cin>>a>>b){ for(int i=0;i=a&&mark[i]<=b){ cout< /* 2009 A [a,b]完数 6 = 1+2+3 */ #include using namespace std; bool wan(int n){ int sum = 0; for(int i=1;i<=n/2;i++){ if(n%i==0){ sum+=i; } } if(sum == n){ return true; }else{ return false; } } int main(){ int a,b; cin>>a>>b; for(int i= a;i<=b;i++){ if(wan(i)){ cout< 牛客网 2009 problemB /* 2009 B m阶方阵（1，10） 每行每列及对角线元素之和 从大到小排列 用例1： 4 15 8 -2 6 31 24 18 71 -3 -9 27 13 17 21 38 69 */ #include #include #include using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ int n; cin>>n; int a[n][n]; vector b; for(int i = 0;i>a[i][j]; } } // 求行列元素的和 for(int i = 0 ;i::iterator it = b.begin(); for(;it!=b.end();it++){ cout<<*it<<" "; } return 0; } 牛客网链接2009 problem C /** 2009 C 从字符串中提取出所有的数字字符拼接成无符号整数 输出该整数的最大因子，素数的话输出本身 样例： 3 sdf0ejg3.f?9f ?4afd0s&2d79*(g abcde 输出 13 857 0 */ #include #include using namespace std; const int maxn = 101; // 提取数字 int pull(string str){ int num = 0; int len =str.length(); for(int i=0;i='0'&&str[i]<='9'){ num = num *10 +str[i]-48; } } return num; } // 求出最大因子 int max_factor(int num){ int factor= 1,i=2; for(;i*i<=num;i++){ while(num%i==0){ num/=i; factor = i; } } if(num!=1) factor = num; return factor; } int main(){ int n; cin>>n; char str[maxn]; for(int i =0;i>str; cout< 牛客网链接：2009 problemD 思想：通过中序遍历和先序遍历来构建一棵树，然后再后序遍历读取该tree. 先序的第一个字符肯定是数根root结点,运用递归的思想，在中序遍历中找到该节点，并以此结点为分界线得到这棵树的左子树和右子树，然后递归建树就可以啦。 本题一直没检查出来的错误是：后序遍历函数和变量重名了，哎呀！还研究了半天结构体指针！！ /* 2009 D 已知二叉树的先序和中序序列,输出后序遍历序列 方法：重建树，输出后序遍历 ABDGCEFH DGBAECHF */ #include #include #include using namespace std; const int maxn = 101; // 树的结构 struct BTree{ BTree *left; BTree *right; char val; BTree(char ch){ val = ch; left = right = NULL; } }; // 按照先序和中序进行重建二叉树 BTree* reConstructBinaryTree(string preorder,string inorder){ BTree* node = new BTree(preorder[0]); int len = preorder.length(); if(len == 0 || inorder.length()==0 ){ return NULL; } int i = inorder.find(preorder[0]); // string 提供的find方法很好用 // for(int i=0;ileft = reConstructBinaryTree(preorder.substr(1,i),inorder.substr(0,i)); node->right = reConstructBinaryTree(preorder.substr(i+1,len-i-1),inorder.substr(i+1,len-i-1)); // } // } return node; } // 后序遍历 void post_order(BTree* root){ if(root == NULL){ return; } post_order(root->left); post_order(root->right); cout<val; } int main(){ string preorder,inorder; while(cin>>preorder>>inorder){ BTree* tree = reConstructBinaryTree(preorder,inorder); post_order(tree); cout< 牛客网链接：2009 problemE 括号匹配问题数据结构课本中详细讲过，遍历读取所输入的字符串，如果是左括号，将其压栈，如果读到右括号，判断栈是否为空并且是否和栈顶元素匹配，如果符合条件，那么就将栈顶出栈，并继续判断。直到遍历完整个字符串，也就是for循环执行完毕，判断栈是否为空，如果是空，则说明已经完全匹配上啦。 要注意的一个点就是，其他元素不需要全都入栈，一开始我把表达式中的变量和常量都考虑进去了，程序就会变得很麻烦，并且做了很多无用功。读取到右括号的时候，需要将不是相应左括号的元素一一弹出栈，需要一个小的循环判断。。。 /* 2009 E 括号匹配判定 cin:n;n条表达式 cout:yes/no */ #include #include #include using namespace std; const int maxn =1001; stack st; // 表达式中的常量和变量不需要管，本题只要括号匹配即可 bool judge(char a[],int n){ for(int i=0;i>n; for(int i=0;i>str; while(!st.empty()){ st.pop(); } if(judge(str,strlen(str))==true){ cout<<"yes"<