2020-team2-091

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: ??/??

 rank: ??

= 流水账 =

~~这里是流水账~~

= 总结 =

=== pb： ===
~~这里是总结~~

=== Creatix： ===
~~这里是总结~~

= 题解 =

 * A：三个数以上相加不可能是质数，枚举一下即可。

 * B：经典结论：1. 下凸函数和下凸函数的和仍然是一个下凸函数。代数证明：求导关于加法运算具有分配律。几何直观：不可能会出现pg的形状。
2. 下凸函数经过翻转仍然是下凸函数。代数证明：记 R 表示翻转变换，D 表示求导变换，则有 D(R(f)) = -R(D(f)), 所以D(D(R(f))) = R(D(D(f)))，或 R(D(D(R(f)))) = D(D(f))，即f和R(f)的二阶导的正负性相同。

 * C：发现操作可以等价转换为：1.选一条三个点的链，然后端点异或，边权一个加一个减。2. 选定全局唯一一条边，端点异或，边权加。首先判掉点权异或和不为0，然后每次用新的1操作删掉一个叶子（四步内），最后剩下一条边使用2操作消除（如果最后奇偶性不对无解）。删掉一个叶子可以先判奇偶性，再把点权变成和边权绝对值一样，然后两个一起消掉

 * D：经典拿出来一个点，剩下偶数个点排成一个环，然后Z字型连边，然后转一转来拆分完全图

 * E：done

 * F：没补……这是什么毒题……把椭圆拆成若干个矩形……

 * G：对于每个数字，每次交换位置它上面的颜色都会翻转一次

 * H：观察到，如果我们把 x 最小的和 y 最小的和 z 最小的三个点（可能因为重合会只有两个甚至一个点）拿出来，就会发现这三个点中我们在不改变自己坐标的情况下一定要先拿掉一个点。那不妨贪心的选择所需要 k 最小的那个点。

 * I：分析一下后发现 f 的和有个上界 100*sqrt(n+2)。

 * J：题解里面写的很抽象但确实就是这么回事。思路应该说是考虑每种数对 b 数组带来的影响。
 upd，前面的转化很 nb，后面的贪心也很困难。感觉是道好题。
 [https://acm.hdu.edu.cn/viewcode.php?rid=36519145 代码]

 * K：如果一个点 (i, j) 任意走一步或任意走两步所到达的点都不是特殊点，那么经过简单的分类讨论，(i + 1, j − 1) 的胜负状态和 (i, j) 是相同的。

[/wiki/2020-team2 返回]

概述

solved: ??/??

rank: ??

流水账

这里是流水账

总结

pb：

这里是总结

Creatix：

这里是总结

题解

  • A：三个数以上相加不可能是质数，枚举一下即可。
  • B：经典结论：1. 下凸函数和下凸函数的和仍然是一个下凸函数。代数证明：求导关于加法运算具有分配律。几何直观：不可能会出现pg的形状。

2. 下凸函数经过翻转仍然是下凸函数。代数证明：记 R 表示翻转变换，D 表示求导变换，则有 D(R(f)) = -R(D(f)), 所以D(D(R(f))) = R(D(D(f)))，或 R(D(D(R(f)))) = D(D(f))，即f和R(f)的二阶导的正负性相同。

  • C：发现操作可以等价转换为：1.选一条三个点的链，然后端点异或，边权一个加一个减。2. 选定全局唯一一条边，端点异或，边权加。首先判掉点权异或和不为0，然后每次用新的1操作删掉一个叶子（四步内），最后剩下一条边使用2操作消除（如果最后奇偶性不对无解）。删掉一个叶子可以先判奇偶性，再把点权变成和边权绝对值一样，然后两个一起消掉
  • D：经典拿出来一个点，剩下偶数个点排成一个环，然后Z字型连边，然后转一转来拆分完全图
  • E：done
  • F：没补……这是什么毒题……把椭圆拆成若干个矩形……
  • G：对于每个数字，每次交换位置它上面的颜色都会翻转一次
  • H：观察到，如果我们把 x 最小的和 y 最小的和 z 最小的三个点（可能因为重合会只有两个甚至一个点）拿出来，就会发现这三个点中我们在不改变自己坐标的情况下一定要先拿掉一个点。那不妨贪心的选择所需要 k 最小的那个点。
  • I：分析一下后发现 f 的和有个上界 100*sqrt(n+2)。
  • J：题解里面写的很抽象但确实就是这么回事。思路应该说是考虑每种数对 b 数组带来的影响。

upd，前面的转化很 nb，后面的贪心也很困难。感觉是道好题。

代码

  • K：如果一个点 (i, j) 任意走一步或任意走两步所到达的点都不是特殊点，那么经过简单的分类讨论，(i + 1, j − 1) 的胜负状态和 (i, j) 是相同的。
附加文件