【省选模拟】20/03/04

​​

• 显然可以发现，出题人用了很多奇怪的方法包括增长题面，使题面晦涩难懂，定义新的位运算，输入一堆奇怪的式子来增加题面难度
• 题意，你有 个变元 ，分别可以取真或假，有两种运算 ，表示取反和 ，输入一个含变元和 的表达式，其中 为一串变元通过上述两种符号串成的表达式，并且 中包涵 个符号，我们需要确定有多少个 满足无论 怎么去结果都为真
  
• 暴力：枚举 及 种变元
• 优化，将 种变元排成一列状压每一种变元是真是假，枚举当前符号是 还是 转移，即：
  
  后面用 转移，只需要做 次 ， 剩余点乘，复杂度
  现在有了初始表达式的限制，我们枚举每一种变元看 是必须为 还是均可均不可
  这个可以直接用栈搞一个括号匹配模拟，复杂度
  ​​

---

：

• 
  维护后面的前缀和，复杂度
  ​​​

---

• 题意：3 棵树，求出以下 3 者的
• 第一棵树的两两距离和
• 第一棵树和第二棵树连一条边后两两距离和
• 第一棵和第二棵树连一条边，第二课树和第三棵连一条边后两两距离和

题解：

• 第一个是定值，假设三棵树的大小分别是，第二个选到点分别是，所有点到的距离和是，那么新增贡献是，分别取的最大最小
• 第三个，讨论的新增贡献，把常数项抛开
  
  分别取最大最小，那么还剩，最小化就是均取最小，最大化可以用点分治 树形，枚举，维护的最大值即可
  ​​​