龙岩网站开发wordpress搜索代码制做

龙岩网站开发,wordpress搜索代码制做,wordpress关键词屏蔽,wordpress文章公众号1 单选题#xff08;每题 2 分#xff0c;共 30 分#xff09;第1题 下列关于类的说法#xff0c;错误的是( )。A. 构造函数不能声明为虚函数#xff0c;但析构函数可以。B. 函数参数如声明为类的引用类型#xff0c;调用时不会调用该类的复制构造函数。C. 静态方法属于…1单选题每题 2 分共 30 分第1题 下列关于类的说法错误的是( )。A. 构造函数不能声明为虚函数但析构函数可以。B. 函数参数如声明为类的引用类型调用时不会调用该类的复制构造函数。C. 静态方法属于类而不是某个具体对象因此推荐用 类名::方法(...) 调用。D. 不管基类的析构函数是否是虚函数都可以通过基类指针/引用正确删除派生类对象。解析答案D。构造函数不能是虚函数因为对象构造时虚表未建立但析构函数可以且应该声明为虚函数以实现多态安全所以A说法无误参数声明为引用如 void foo(MyClass obj)时传递的是对象别名不会触发复制构造函数只有值传递如 void foo(MyClass obj)才会调用复制构造函数所以B说法正确静态方法属于类本身而非实例对象。推荐用 类名::方法(...) 调用如 MyClass::staticFunc()这能明确区分静态与实例方法所以C说法合理‌关键问题‌如果基类析构函数‌不是虚函数‌通过基类指针删除派生类对象时只会调用基类析构函数导致派生类资源泄露如内存泄漏。正确做法是当基类可能被继承时‌必须声明虚析构函数‌如 virtual ~Base() {}所以D说法错误。故选D。第2题 假设变量 veh 是类 Car 的一个实例我们可以调用 veh.move() 是因为面向对象编程有( )性质。1│class Vehicle {2│private:3│string brand;4│5│public:6│Vehicle(string b) : brand(b) {}7│8│void setBrand(const string b) { brand b; }9│string getBrand() const { return brand; }10│11│void move() const {12│cout brand is moving... endl;13│}14│};15│16│class Car : public Vehicle {17│private:18│int seatCount;19│20│public:21│Car(string b, int seats) : Vehicle(b), seatCount(seats) {}22│23│void showInfo() const {24│cout This car is a getBrand()25│ with seatCount seats. endl;26│}27│};A. 继承 (Inheritance) B. 封装 (Encapsulation)C. 多态 (Polymorphism) D. 链接 (Linking)解析答案A。由Vehicle 类创建Car 类即Car 类通过 class Car : public Vehicle 继承了 Vehicle 类第16行。move() 方法是 Vehicle 类中定义的公共方法第11-13行而 Car 类‌没有重写它‌。因此Car 的实例 veh‌自动继承了‌Vehicle的 move() 方法所以能直接调用 veh.move()。继承允许派生类如 Car复用基类如 Vehicle的属性和方法无需重复代码。这里 veh.move() 能运行正是因为 Car 继承了 Vehicle 的 move() 实现体现了OOP的“代码复用”特性。封装关注数据隐藏如 brand 是 private但调用 move() 是方法访问与封装无关多态需要虚函数重写move()方法如 virtual void move()但 move() 不是虚函数Car 也未重写它因此不涉及多态链接不是OOP标准性质它属于编译/系统概念与本题无关。故选A。第3题 下面代码中 v1 和 v2 调用了相同接口 move() 但输出结果不同这体现了面向对象编程的( )特性。1│class Vehicle {2│private:3│string brand;4│5│public:7│Vehicle(string b) : brand(b) {}7│8│void setBrand(const string b) { brand b; }9│string getBrand() const { return brand; }10│11│virtual void move() const {12│cout brand is moving... endl;13│}14│};15│16│class Car : public Vehicle {17│private:18│int seatCount;19│20│public:21│Car(string b, int seats) : Vehicle(b), seatCount(seats) {}22│23│void showInfo() const {24│cout This car is a getBrand()25│ with seatCount seats. endl;26│}27│28│void move() const override {29│cout getBrand() car is driving on the road! endl;30│}31│};32│33│class Bike : public Vehicle {34│public:35│Bike(string b) : Vehicle(b) {}36│37│void move() const override {38│cout getBrand() bike is cycling on the path! endl;30│}40│};41│42│int main() {43│Vehicle* v1 new Car(Toyota, 5);44│Vehicle* v2 new Bike(Giant);45│46│v1-move();47│v2-move();48│49│delete v1;50│delete v2;51│return 0;52│}A. 继承 (Inheritance) B. 封装 (Encapsulation)C. 多态 (Polymorphism) D. 链接 (Linking)解析答案C。这道题的核心在于‌多态Polymorphism‌。‌相同调用‌v1-move() 和 v2-move() 都是通过 Vehicle* 指针调用的同一接口 move()。‌不同输出‌v1实际指向 Car输出Toyota car is driving on the road!v2实际指向 Bike输出Giant bike is cycling on the path!基类 Vehicle 的 move() 声明为虚函数‌virtual‌第11行派生类 Car 和 Bike 分别重写‌override‌了 move()第28行、37行。通过基类指针调用虚函数时实际执行的是‌对象重写的方法‌如 v1 实际是 Car故调用 Car::move()。这就是‌动态多态‌同一接口move()不同行为开车 vs 骑行。Car/Bike 继承 Vehicle 是基础但本题重点在于‌同一接口的差异化实现‌而非单纯继承而是虚函数重写实现多态封装体现在 brand 私有化第3行但不体现在move()上链接与编译/系统相关与OOP特性无关。所以选C。第4题 栈的操作特点是( )。A. 先进先出 B. 先进后出 C. 随机访问 D. 双端进出解析答案B。‌栈Stack的操作特点是先进后出FILO最先进入栈的元素最后才能被取出就像叠放的盘子先放的在下层最后才能拿到。先进先出‌是‌队列Queue的特性如排队先来先服务栈‌不支持。随机访问‌是‌数组Array的特性栈‌不支持‌随机访问元素只能访问栈顶元素。双端进出是‌双端队列Deque的特性两端都可操作栈‌不支持。故选B。第5题 循环队列常用于实现数据缓冲。假设一个循环队列容量为 5即最多存放 4 个元素留一个位置区分空与满依次进行操作入队数据123出队1个数据再入队数据4和5此时队首到队尾的元素顺序是( )。A. [2, 3, 4, 5] B. [1, 2, 3, 4] C. [3, 4, 5, 2] D. [2, 3, 5, 4]解析答案A。可以‌模拟循环队列的操作流程逐步推演出结果。‌初始化‌如图1①队列空front 0, rear 0rear指向下一个插入位置图1 程序生成的二叉树入队1,2,3‌如图1②入1 → rear (01)%5 1入2 → rear (11)%5 2入3 → rear (21)%5 3。‌出队1个‌数据如图1③移除队首(front0位置的元素1)→ front (01)%5 1‌入队4和5‌如图1④入4 → rear (31)%5 4 入5 → rear (41)%5 0 (‌循环到数组开头‌)。此时队首到队尾的元素顺序是[2, 3, 4, 5]。故选A。第6题 以下函数 createTree() 构造的树是什么类型1│struct TreeNode {2│int val;3│TreeNode* left;4│TreeNode* right;5│TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}6│};7│8│TreeNode* createTree() {9│TreeNode* root new TreeNode(1);10│root-left new TreeNode(2);11│root-right new TreeNode(3);12│root-left-left new TreeNode(4);13│root-left-right new TreeNode(5);14│return root;15│}A. 满二叉树 B. 完全二叉树 C. 二叉排序树 D. 其他都不对解析答案B。按程序所建的二叉树结构如图2所示。图2 程序生成的二叉树满二叉树的定义为一棵深度为k层数为k且具有2ᵏ- 1个节点的二叉树其中所有层的节点数都达到最大值即每个非叶节点都有两个子节点且所有叶子节点都位于最深层。‌显然图2不符合满二叉树的定义。完全二叉树的定义为深度为k且有n个节点的二叉树当且仅当其每个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时称为完全二叉树。‌即除最后一层外其他层的节点数都达到最大值且最后一层的节点都集中在最左边。‌显然图2符合完全二叉树的定义。选B。二叉排序树又称二叉搜索树的定义为一棵空树或满足以下性质的二叉树若左子树不为空则左子树上所有节点的值均小于根节点的值若右子树不为空则右子树上所有节点的值均大于根节点的值左、右子树也分别为二叉排序树且没有键值相等的节点。显然图2不符合二叉排序树的定义。第7题 已知二叉树的 中序遍历 是 [D, B, E, A, F, C]先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果 是( )。A. [D, E, B, F, C, A] B. [D, B, E, F, C, A] C. [D, E, B, C, F, A] D. [B, D, E, F, C, A]解析答案A。中序遍历先左树再根节点然后是右树所有子树仍按先左树再根然后是右树规则遍历。选(前)序遍历先根节点再是左树然后是右树所有子树仍按先根节点再左树然后是右树规则遍历由先序遍历可知A是根节点由中序遍历可知[D, B, E]是左树[F, C]是右树。由先序遍历可知B是左子树的根节点由中序遍历可知D是左树E上右树此时左、右树都只有一个点整棵左子树结束。由先序遍历可知C上右子树的根节点由中序遍历可知F是左树此时左树只有一个点无右树整棵右子树结束。所构成的二叉树如图3所示。图3 按题意构建的哈夫曼树后序遍历选是先左树、次右树、再根节点D、E、B、F、C、A故选A。第8题 完全二叉树可以用数组连续高效存储如果节点从 1 开始编号则对有两个孩子节点的节点 i ( )。A. 左孩子位于 2i 右孩子位于 2i1B. 完全二叉树的叶子节点可以出现在最后一层的任意位置C. 所有节点都有两个孩子D. 左孩子位于 2i1 右孩子位于 2i2解析答案A。在完全二叉树中如果节点编号从1开始按层次遍历顺序编号则对于任意节点i‌左孩子节点的编号为 (2i)‌‌右孩子节点的编号为 (2i1)‌。故选A。第9题 设有字符集 {a, b, c, d, e, f} 其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码以下哪一组可能是对应的哈夫曼编码非叶子节点左边分支记作 0右边分支记作 1左右互换不影响 正确性。A. a: 00b: 01c: 10d: 110e: 111f: 0B. a: 1100b: 1101c: 100d: 101e: 111f: 0C. a: 000b: 001c: 01d: 10e: 110f: 111D. a: 10b: 01c: 100d: 101e: 111f: 0解析答案B。以最小频率合并频率左小右大为原则建哈夫曼树如图4所示图4 按题意构建的哈夫曼树a(5)和b(9)合并为14c(12)和d(13)合并为2514和e(16)合并为3025和30合并为55f(45)和55合并为100构成图4所示哈夫曼树。a: 1100b: 1101c: 100d: 101e: 111f: 0故选B。第10题 下面代码生成格雷编码则横线上应填写( )。1│vector grayCode(int n) {2│if (n 0) return {0};3│if (n 1) return {0, 1};4│5│vector prev grayCode(n-1);6│vector result;7│for (string s : prev) {8│result.push_back(0 s);9│}10│for (_______________) { // 在此处填写代码11│result.push_back(1 prev[i]);12│}13│return result;14│}A. int i 0; i prev.size(); i B. int i prev.size()-1; i 0; i--C. auto s : prev D. int i prev.size()/2; i prev.size(); i解析答案B。格雷编码要求相邻编码只有一位不同。递归生成n-1位编码后通过镜像对称构造n位编码前半部分0前缀保持原顺序后半部分1前缀逆序添加确保相邻编码差异。‌代码实现‌for (int i prev.size()-1; i 0; i--) { //逆序遍历result.push_back(1 prev[i]);}逆序遍历prev确保1前缀部分与0前缀部分对称例如n2时prev {00, 01, 11, 10}前半部分{000, 001, 011, 010}后半部分{110, 111, 101, 100}逆序添加A选项为正序遍历会导致相邻编码差异超过一位故错误B选项为逆序遍历符合镜像对称要求故正确C选项范围错误无法遍历所有元素故错误D选项部分逆序仅逆序一半元素无法保证对称性故错误。故选B。第11题 请将下列树的深度优先遍历代码补充完整横线处应填入( )。1│struct TreeNode {2│int val;3│TreeNode* left;4│TreeNode* right;5│TreeNode(int x): val(x), left(nullptr), right(nullptr) {}6│};7│8│void dfs(TreeNode* root) {9│if (!root) return;10│______ temp; // 在此处填写代码11│temp.push(root);12│while (!temp.empty()) {13│TreeNode* node temp.top();14│temp.pop();15│cout node-val ;16│if (node-right) temp.push(node-right);17│if (node-left) temp.push(node-left);18│}19│}A. vector B. list C. queue D. stack解析答案D。这道题考察的是深度优先遍历(DFS)的非递归实现初步判断横线处应填stack‌(栈)。看第10行声明 temp 后第11行用temp.push()推入节点第13行用temp.top()访问栈顶第14行用temp.pop()弹出节点——这些操作是栈(stack)的典型方法(后进先出LIFO)。非递归DFS依赖栈模拟递归调用栈。这里先推入根节点循环中弹出节点并打印前序遍历再按“右子节点先入栈、左子节点后入栈”的顺序推入子节点第16-17行。这样左子节点先出栈处理确保遍历顺序是根-左-右。‌vector需用push_back()和back()/pop_back()但代码用的是push()/top()不匹配故A错误list类似vector无top()方法操作不直接B错误queue用于广度优先搜索(BFS)是先进先出(FIFO)访问用front()而非top()这里明显是DFS的栈行为C错误。故选D。第12题 令是树的节点数目下列代码实现了树的广度优先遍历其时间复杂度是( )。1│void bfs(TreeNode* root) {2│if (!root) return;3│queueTreeNode* q;4│q.push(root);5│while (!q.empty()) {6│TreeNode* node q.front();7│q.pop();8│cout node-val ;9│if (node-left) q.push(node-left);10│if (node-right) q.push(node-right);11│}12│}A. () B. (log) C. (²) D. (2ⁿ)解析答案A。所有节点(包括root)均被‌入队一次(q.push())和‌出队一次‌(q.front())。每个节点的值输出(cout)和子节点检查(if判断)均为常数时间操作(1)。总操作次数入队次出队次访问节点值次检查子节点2次每个节点最多检查左右两个子节点。总时间() ×(1) ×(1) ×(1) 2×(1) ()。故选A。第13题 在二叉排序树(Binary Search Tree, BST)中查找元素50从根节点开始若根值为60则下一步应去搜索A. 左子树 B. 右子树 C. 随机 D. 根节点解析答案A。二叉排序树满足以下性质的二叉树左子树所有节点值均小于根节点右子树所有节点值均大于根节点且左右子树本身也为二叉排序树。由于根节点是60查询元素为50所示查询元素在左树。故选A。第14题 删除二叉排序树中的节点时如果节点有两个孩子则横线处应填入( )其中findMax和findMin分别为寻找树的最大值和最小值的函数。1│struct TreeNode {2│int val;3│TreeNode* left;4│TreeNode* right;5│TreeNode(int x): val(x), left(nullptr), right(nullptr) {}6│};7│8│TreeNode* deleteNode(TreeNode* root, int key) {9│if (!root) return nullptr;10│if (key root-val) {11│root-left deleteNode(root-left, key);12│}13│else if (key root-val) {14│root-right deleteNode(root-right, key);15│}16│else {17│if (!root-left) return root-right;18│if (!root-right) return root-left;19│TreeNode* temp ____________; // 在此处填写代码20│root-val temp-val;21│root-right deleteNode(root-right, temp-val);22│}23│return root;24│}A. root-left B. root-rightC. findMin(root-right) D. findMax(root-left)‌解析答案C。当二叉排序树的节点有两个子节点时删除策略是‌用中序后继或中序前驱来替代当前节点‌。在题目提供的代码中第21行显示删除操作是在右子树中进行的因此这里选择的是‌中序后继‌。中序后继是右子树中的最小节点它的值大于当前节点但小于右子树中的其他所有节点替换后仍然保持二叉排序树的性质。删除逻辑‌当节点有两个子节点时用右子树最小值(中序后继)替换当前节点值再递归删除右子树中该最小值节点。所以选C。第15题 给定个物品和一个最大承重为的背包每个物品有一个重量[]和价值[]每个物品只能选择放或不放。目标是选择若干个物品放入背包使得总价值最大且总重量不超过则横线上应填写( )。1│int knapsack(int W, vector wt, vector val, int n) {2│vector dp(W1, 0);3│for (int i 0; i n; i) {4│for (int w W; w wt[i]; --w) {5│________________________ // 在此处填写代码6│7│}8│}9│return dp[W];10│}A. dp[w] max(dp[w], dp[w] val[i]);B. dp[w] dp[w - wt[i]] val[i];C. dp[w] max(dp[w - 1], dp[w - wt[i]] val[i]);D. dp[w] max(dp[w], dp[w - wt[i]] val[i]);解析答案D。题目程序算法原理分析这是经典的‌0-1背包问题‌的动态规划解法采用‌空间优化的一维数组实现‌‌dp[w]表示当前承重限制为w时能获得的最大价值‌外层循环‌遍历每个物品i‌内层循环‌从最大承重W倒序遍历到当前物品重量wt[i]。dp[w] max(dp[w], dp[w - wt[i]] val[i])的含义‌dp[w]‌不放入当前物品i时的最大价值(保持原值)dp[w - wt[i]] val[i]放入当前物品i时的价值即腾出wt[i]重量后的最大价值加上当前物品价值‌max‌比较两种情况选择价值更大的方案。A选项dp[w] val[i]错误这会重复计算当前物品价值‌B选项‌缺少max比较无法保证是最优解C选项dp[w-1]无意义重量减少1不一定对应有效状态。故选D。2判断题每题 2 分共 20 分第1题 当基类可能被多态使用其析构函数应该声明为虚函数。解析答案正确。当基类可能被多态使用时其析构函数应该声明为虚函数。这是因为如果通过基类指针删除派生类对象非虚析构函数会导致派生类的析构函数不被调用从而引发资源泄漏。声明为虚函数后会触发正确的多态析构行为先调用派生类析构函数再调用基类析构函数。第2题 哈夫曼编码是最优前缀码且编码结果唯一。解析答案错误。哈夫曼编码是最优前缀码(其带权路径长度WPL最小)但编码结果不唯一。当字符频率相同时合并顺序不同会导致不同的树结构从而产生不同的编码方案但它们都能保证最优性。第3题 一个含有100个节点的完全二叉树高度为8。解析答案错误。一个含有100个节点的完全二叉树如高度为h则节点数在2ʰ⁻¹-2ʰ-1之间2⁸⁻¹1282⁸-1255。所以100个节点的完全二叉树不可能高度为8。第4题 在C STL中栈(std::stack)的pop操作返回栈顶元素并移除它。解析答案错误。C STL中std::stack的pop()操作仅移除栈顶元素不返回任何值(返回类型为void)要获取栈顶元素的值应使用top()成员函数。第5题 循环队列通过模运算循环使用空间。解析答案正确。循环队列通过模运算(取余)实现头尾相接的逻辑结构当指针到达数组末尾时会通过取模运算回到数组起始位置从而循环使用已释放的空间。这是解决顺序队列“假溢出”问题的标准方法。第6题 一棵有个节点的二叉树一定有-1条边。解析答案正确。根据树的性质一棵有个节点的树其边数恒为-1。这可以通过数学归纳法证明当1时边数为0假设时成立则增加一个节点时需增加一条边使其连通且无环此时边数为符合(1)-1。因此对于任何个节点的树边数都是-1。第7题 以下代码实现了二叉树的中序遍历。输入以下二叉树中序遍历结果是 4 2 5 1 3 6。1│// 12│// / \3│// 2 34│// / \ \5│// 4 5 66│7│struct TreeNode {8│int val;9│TreeNode* left;10│TreeNode* right;11│TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}12│};13│14│void inorderIterative(TreeNode* root) {15│stack st;16│TreeNode* curr root;17│18│while (curr || !st.empty()) {19│while (curr) {20│st.push(curr);21│curr curr-left;22│}23│curr st.top(); st.pop();24│cout curr-val ;25│curr curr-right;26│}27│}解析答案正确。题目提供的代码使用栈模拟递归调用栈先遍历左子树再访问根节点最后遍历右子树。对示例二叉树输出4 2 5 1 3 6 (符合中序遍历规则左-根-右)。第8题 下面代码实现的二叉排序树的查找操作时间复杂度是(ℎ)其中ℎ为树高。1│TreeNode* searchBST(TreeNode* root, int val) {2│while (root root-val ! val) {3│root (val root-val) ? root-left : root-right;4│}5│return root;6│}解析答案正确。题目所给程序代码实现二叉排序树(BST)的查找操作。BST性质左子树值根值右子树值。程序中循环迭代每次比较后直接跳转到左/右子树最坏需遍历树高ℎ。最坏/平均情况(ℎ)最坏()退化为链表此时ℎ第9题 下面代码实现了动态规划版本的斐波那契数列计算其时间复杂度是(2ⁿ)。1│int fib_dp(int n) {2│if (n 1) return n;3│vector dp(n1);4│dp[0] 0;5│dp[1] 1;6│for (int i 2; i n; i) {7│dp[i] dp[i-1] dp[i-2];8│}9│return dp[n];10│}解析答案错误。题目所给程序是‌动态规划实现的斐波那契数列‌其时间复杂度为()并不是(2ⁿ)‌。输入规模‌输入为整数目标是计算第个斐波那契数。‌初始化操作(第2~5行)常数时间(1)第7行循环体(1)操作循环体行6~8行共执行了n-1次时间复杂度为()。第10题 有一排香蕉每个香蕉有不同的甜度值。小猴子想吃香蕉但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。1│// bananas香蕉的甜度2│void findSelectedBananas(vector bananas, vector dp) {3│vector selected;4│int i bananas.size() - 1;5│6│while (i 0) {7│if (i 0) {8│selected.push_back(0);9│break;10│}11│12│if (dp[i] dp[i-1]) {13│i--;14│} else {15│selected.push_back(i);16│i - 2;17│}18│}19│20│reverse(selected.begin(), selected.end());21│cout 小猴子吃了第: ;22│for (int idx : selected)23│cout idx1 ;24│cout 个香蕉 endl;25│}26│27│int main() {28│vector bananas {1, 2, 3, 1}; // 每个香蕉的甜29│30│vector dp(bananas.size());31│dp[0] bananas[0];32│dp[1] max(bananas[0], bananas[1]);33│for (int i 2; i bananas.size(); i) {34│dp[i] max(bananas[i] dp[i-2], dp[i-1]);35│}36│findSelectedBananas(bananas, dp);37│38│return 0;39│}解析答案正确。题目所给程序代码实现‌动态规划解决小猴子吃香蕉问题‌核心功能包括‌动态规划数组初始化‌dp[i]表示前i个香蕉中能吃到的最大甜度‌状态转移方程‌dp[i] max(dp[i-1], bananas[i] dp[i-2])选择不吃当前或吃当前跳过下一个‌结果回溯‌通过dp数组反向推导最优选择的香蕉索引‌输出结果‌打印小猴子选择的香蕉编号从1开始计数3编程题每题 25 分共 50 分3.1 编程题1试题名称划分字符串时间限制1.0 s内存限制512.0 MB3.1.1题目描述小A有一个由个小写字母组成的字符串。他希望将划分为若干个子串使得子串中每个字母至多出现一次。例如对于字符串street来说street是满足条件的划分而 street不是因为子串tree中e出现了两次。额外地小A还给出了价值₁, ₂, ..., ₙ表示划分后长度为的子串价值为ᵢ。小A希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗3.1.2 输入格式第一行一个正整数表示字符串的长度。第二行一个包含个小写字母的字符串。第三行 个正整数₁, ₂, ..., ₙ表示不同长度的子串价值。3.1.3 输出格式一行一个整数表示划分后子串价值之和的最大值。3.1.4 样例3.1.4.1 输入样例11│62│street3│2 1 7 4 3 33.1.4.2 输出样例11│133.1.4.3 输入样例21│82│blossoms3│1 1 2 3 5 8 13 213.1.4.4 输出样例21│83.1.5 数据范围对于40%的测试点保证1≤≤10³。对于所有测试点保证1≤≤10⁵1≤ᵢ≤10⁹。3.1.6 编写程序编程思路这道题使用动态规划(Dynamic Programming)。贪心在—般情况下不能保证正确。如样例2随子串长度增加子串价值是增加的(1 1 2 3 5 8 13 21)对字符串blossoms会拆成blos som s价值为3216不如每个字符一个子串价值8*18更高。由于数据量1≤≤10⁵只能采用()、()或(log)的方法。本方法采用标准的自底向上DP加上位掩码(mask)来快速判断某—段子串中是否有重复字母并在发现重复时剪枝(break)从而把时间复杂度控制在(26)级别。由于只有小写字母子串中每个字母用第1~26位置1的32位整数mask表示a为1(10)b为2(11)c为4(12)…z为2²⁵(125)。如子串中已存在某字母则mask中对应位置1设cur为当前字母的位置置1值则mask cur为1则字母重复。核心代码for(int i1; in; i){int mask 0;for(int ji; j; j--){int cur 1 (s[j-1] - a); // s[j-1] - a为第j个字母的序号0~25if (mask cur) break;mask | cur;f[i] max(f[i], f[j - 1] a[i - j 1));}}外层i表示在求f[i]也就是前缀s[1..i]的最优值(注意代码中s用的是索引从0开始和a用的是索引从1开始)。mask用32位整数的位表示法记录当前子串里已经出现的字母(a对应第0位置1b对应第1位置1……z对应第25位置1)。这样检测重复和加入新字母都能用位运算(1)完成。内层j从i向前遍历尝试把s[j..i]当成最后—个子串cur 1 (s[j-1] - a)当前字符对应的位(0~25)cur当前字符对应的位置1if (mask cur) break;如果该位已在mask中说明s[j..i]有重复字母更往前的j会使子串更长且仍包含这个重复字符因此向前继续尝试更小j没必要——可以break(剪枝)否则把该字母加入mask然后更新f[i] max(f[i], f[j-1] a[i- j1])i- j1为子串长度。 f[0]默认为0。最终答案是f[n]。动态规划的四个要素1)状态(State)设f[i]为前i个字符(s[1..i])能取得的最大价值和。这是标准的“前缀最优”定义。2)转移(Transition)对于f[i]枚举最后—个子串s[j..i] (1≤j≤i)且要求s[0..i-1]每个字母不重复f[i]max(f[j-1]a[i-j-1)如果j≤i, s[j..i]无重复也就是最后这个子串要么从某个j开始把前缀s[0..j-2]的最优f(j-1)加上这个子串的值a[len]所有可行的j取最大值。3)初始条件(Basacases)f[0] 0(空串价值为0)。4)计算顺序(Order)自底向上i从1到n对每个i内部j从i递减到1(遇到重复直接break)。因为f[i]依赖f[i-1]而j-1i保证这些状态已被计算过。完整代码如下#include iostream using namespace std; const int N 1e5 5; // n≤10⁵ int n; char s[N]; // s字符串用字符数组 int a[N]; // n个长度为的子串价值为ᵢ long long f[N]; // ᵢ≤10⁹f[i]为前i个字符(s[1..i])能取得的最大价值和 int main() { cin n; cin s; // s中只有小写字母如含空格要用cin.getline() for (int i 1; i n; i) // a索引(下标)从1开始s索引(下标)从0开始 cin a[i]; for (int i 1; i n; i) { int mask 0; for (int j i; j; j--) { int cur 1 (s[j-1] - a); // s[j-1] - a为第j个字母的序号0~25 if (mask cur) break; // 第j个字符重复则结束(剪枝) mask | cur; // 将第j个字符标记在mask中(指定位置1) f[i] max(f[i], f[j - 1] a[i - j 1]); // i-j1为子串长度 } } cout f[n]; // 当i为n时便是结果 return 0; }3.2 编程题2试题名称货物运输时间限制1.0 s内存限制512.0 MB3.2.1题目描述A国有座城市依次以1,2,…,编号其中1号城市为首都。这座城市由-1条双向道路连接第条道路(1≤≤)连接编号为ᵢ, ᵢ的两座城市道路长度为ᵢ。任意两座城市间均可通过双向道路到达。现在A国需要从首都向各个城市运送货物。具体来说满载货物的车队会从首都开出经过一座城市时将对应的货物送出因此车队需要经过所有城市。A国希望你设计一条路线在从首都出发经过所有城市的前提下最小化经过的道路长度总和。注意一座城市可以经过多次车队最后可以不返回首都。3.2.2 输入格式第一行一个正整数表示A国的城市数量。 接下来-1行每行三个整数ᵢ, ᵢ, ᵢ表示一条双向道路连接编号为ᵢ, ᵢ的两座城市道路长度为ᵢ。3.2.3 输出格式一行一个整数表示你设计的路线所经过的道路长度总和。3.2.4 样例3.2.4.1 输入样例11│42│1 2 63│1 3 14│3 4 53.2.4.2 输出样例11│183.2.4.3 输入样例21│72│1 2 13│2 3 14│3 4 15│7 6 16│6 5 17│5 1 13.2.4.4 输出样例21│93.2.5 数据范围对于30%的测试点保证1≤≤8。对于另外30%的测试点保证仅与一条双向道路连接的城市恰有两座。对于所有测试点保证1≤≤10⁵1≤ᵢ, ᵢ≤1≤ᵢ≤10⁹。3.2.6 编写程序编程思路这道题树的最远距离节点(边权和最大)搜索问题。先看样例1图5从1号根节点出发返回根节点图6从1号根节点出发不返回根节点按样例1数据构造的树如图5所示如从根节点1出发返回根节点则每条边都得走两遍。由于车队最后可以不返回首都(根节点)求从首都(根节点)出发经过所有城市的前提下最小化经过的道路长度总和那就在返回首都(根节点)的基础上减去从根节点去往最远节点的距离如图6所示从1号出发到3再从3出发到4返回4返回1从1号出发到2路程是1551618(615)*2-6。由于此样例从1到6距离是6从1到4距离也是6所以走法不是唯一的结果是相同的。表明每条边走两次减去从根节点到最远节点的距离就是结果。因此问题变成求从根节点到最远距离的节点的距离可用深度优先(dfs)遍历节点记录距离然后求最大距离。读取数据的时间复杂度为()深度优先(dfs)遍历个节点-1条边的时间复杂度为(-1)→()求最大距离的时间复杂度为()总体时间复杂度为()不会超时。参考程序代码如下#includeiostream using namespace std; const int MAXN 1e5 5; int n, head[MAXN], nxt[MAXN * 2], to[MAXN * 2], tot 0; long long d[MAXN], w[MAXN * 2], ans 0; void add(int x, int y, int z) { // 构建树 to[tot] y; // 边终点。tot为边的编号每条来去两个编号 w[tot] z; // 此边长度 nxt[tot] head[x]; // 边起点编号 head[x] tot; // 边起点节点编号(双向边每个节点编两次x⇋y) } void dfs(int u, int fa) { // 深度优先求从u单向到最后节点的距离 for (int i head[u]; i; i nxt[i]) { if (to[i] fa ) continue; // 如到达节点是父节点(非单向) d[to[i]] d[u] w[i]; // 计算距离 dfs(to[i], u); // 递归直到to[i]0, 无节点结束 } } int main() { cin n; // 节点数(城市数) int u, v, l; for (int i 1; i n ; i) { // n-1条双向道路(双向边) cin u v l; add(u, v, l); // 添加u到v的边 add(v, u, l); // 因为双向再添加v到u的边 ans l * 2; // 每条边走两遍 } dfs(1, 0); // 从1号首都(根节点)开始父节点01均可 long long max_len 0; // 最长路径长度(根节点到最远节点距离) for (int i 1; i n; i ) max_len max(max_len, d[i]); // 求max_len cout ans - max_len; // ans为返回首都(根节点)的距离。 return 0; }