TCO17 final SplittingFoxes4 题解
题目链接首先我们先考虑一维，并且坐标全都非负，有一个点在 $0$ 的情况。可以将每次的操作抽象成乘上一个多项式 $(1+x^p)$，然后系数在 $\bmod 2$ 意义下运算，要求等于最终的多项式。（所以操作顺序其实是没关系的）那么我们每次只需要找到一个能除的多项式尽量除就好了。具体地，我们每次找到距离 $1$ 最近的位置 $p$，然后除掉 $(1+x^p)$ 即可。如果有负数怎么办？发现这...
题目链接首先我们先考虑一维，并且坐标全都非负，有一个点在 $0$ 的情况。可以将每次的操作抽象成乘上一个多项式 $(1+x^p)$，然后系数在 $\bmod 2$ 意义下运算，要求等于最终的多项式。（所以操作顺序其实是没关系的）那么我们每次只需要找到一个能除的多项式尽量除就好了。具体地，我们每次找到距离 $1$ 最近的位置 $p$，然后除掉 $(1+x^p)$ 即可。如果有负数怎么办？发现这...
题意平面上有 $m$ 个特殊点，每个点有一个颜色。还有 $n$ 个点均匀分布在半径为 $r$ 的圆上，认为有一个点在 $(r,0)$。现在问有多少种方式，可以在这些点之间连线，满足：每个点度数是 $0$ 或 $2$这些线段与点构成了若干个封闭的简单多边形，并且互不相交，互不包含所有相同颜色的特殊点必须在同一个多边形内每一个多边形内部至少要有一个特殊点每一个特殊点至少要在一个多边形内部问这样分...
题意你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。$1 \leq n \...
题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2...
题意有一个长度为 $n$ 的排列 $p_i$，你可以执行以下操作任意次：将数字 $x$ 移动到任意一个位置，花费 $A_x$将数字 $x$ 移动到开头，花费 $B_x$将数字 $x$ 移动到结尾，花费 $C_x$求排序最小代价。$n \leq 2 \times 10^5$。题解首先 $B_x,C_x$ 都要和 $A_x$ 取 $\min$。手动模拟一下，我们先固定一些不动的数 $a_1,a_...