第37次csp认证

• 考了280，做了第一题、第二题和第三题的一部分

  第一题

• 简单题，有手就行

  第二题

• 题目：给你n个苹果，一天内最多吃m个（m<=n），一天内吃了i个苹果可以获得a[i]的喜悦值（i<=m），n个苹果怎么吃分几天吃才能获得最大的喜悦值
• 答案：完全背包，w[i]=i，c[i]=a[i]，v=n，容量为n，耗费为i，价值为c[i]
• 板子代码如下

  for(int i=1;i<=m;i++){
  for(int j=1;j<=v;j++){
    if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+c[i]);
  }
  }
  

• 写到这又翻了一下自己带的板子，动态规划学得真的很差

  第三题

• 题目：输入数字n，代表接下来有n条语句
• 若语句以1开头，形如1 var expr，则代表给变量var赋值expr
  • expr若是$val，则将变量val对应的表达式值赋给var
  • expr若是hello world，则将helloworld赋给var（组合去掉空格）
• 若语句以2开头，形如2 var expr，则代表var对应的expr是可变的
  • 形如 2 var $val，若val改变，则var跟着改变
• 若语句以3开头，形如3 var，输出var对应表达式的长度
• 思路：
  • 第一步是读入带空格的超长字符串，getline
  • 第二步是拆分读到的超长字符串为vector
  • 第三步就分析表达式，若直接赋值，则存入unordered_map<string,int>中，int记录对应字符串的长度；若间接赋值，则存入unordered_map<string,vector>中，vector中存对应的变量
• 注意事项：
  • 为什么用int，因为表达式很长，直接存会爆内存，只能过40%的点
  • 按照这个思路可以过80%的点，剩下两个点TLE了
  • 读入数字，再getling，中间需要加cin.ignore()

    第四题

• 题目：给定数组，让你算$\sum_{l=1}^n\sum_{r=l}^n rlgcd(a[l],a[r])$
• 最大公约数不会算，😔
• 我的想法是找质因数，按照质因数对应数量最小乘起来就行，寄了

  第五题

• n个景点，n-1条路，景点有门票也有送钱的，耗费可以为正也可以为负，首先从1开始算跑到末端的基础耗费最大值
• 操作1，从i点的子树找基础耗费最大值
  • 最抽象就是这是双向的图
  • 结果这一问不让往上走，只让往下走，我就寄了
  • 现在想想还是不太会，一开始就单项？新建一个边图，只存从1开始的，可能能混15分-操作1和操作2
• 操作2，改变u的节点耗费为x，重新算基础耗费
• 操作3，改变根节点为u，重新算基础耗费
• 操作4，删掉a、b之间的路，增加c、d之间的路，重新算基础耗费
• 除了操作1不改变树本身，剩下的都改变。
• 思路：
  • 还是dfs
  • 不过0分遗憾退场