Edu Round 173
C. Sums on Segments
至多有1个数不是1或-1，分开考虑。首先，对于只有1和-1的数组，它们所能表示的数是一段连续的含0的区间。这是因为，每添加一个1或者-1，就相当于对于已经能表示的区间整体+1或-1，然后再添加一个0进去。我们用 $l$ 和 $r$ 来记录考虑当前下标及其左侧所能表示的区间，然后历史的 $l_{min}$ 和 $r_{max}$ 就是所有能表示的数。其次，对于存在不是正负1的数 $x$ 的情况，对其左右两段区间单独考虑，考虑其左侧的后缀和右侧的前缀所能表示的两段区间，由于区间包含0，直接将区间两端点相加，再加上 $x$ 就是含 $x$ 的区间。
另外，由于有些数可能重复考虑，鉴于数据范围并不是很大，一个简单的方法是加到数组里，排序然后去重。复杂度 $O(n \cdot \log{n})$
本题中，出错是因为将左右区间相加错误地写成了取交集。
Submission #300470970 - Codeforces
D. Problem about GCD
首先，只需要考虑 $[l, r]$ 中 G 的倍数，对这段区间除以 G，然后找区间中互素的两个数使得其距离最大，这个距离再乘以 G 就是所求的答案。对于寻找互素的数对，直觉上互素是一个比较容易做到的事，我尝试遍历所有端点及其邻近的15个数，然后就通过了。
几次错误的提交是因为遍历的数过多导致超时。
Submission #300476149 - Codeforces
E. Matrix Transformation
本题我只想到了可以按位考虑两个01矩阵是否满足要求。在看了题解之后，我发现这是一个类似2-SAT的问题。从A变换到B，有些操作时必做的，然后当进行了某些操作后，可能弄乱了某些位置，需要进行另外的操作来复原。由于操作无非把行变成0，把列变成1，我们把行数和列数看成节点（表示操作了这一行/列），操作看成连边。再由一个超级源点连向必须操作的行和列，然后通过dfs去判环，如果存在环说明不可能满足。对于有向图的判环，有一个简单的三色dfs方法，未访问的点初始化成0，正在访问的点置为1，已访问的点置为2，如果访问到一个颜色为1的点，说明存在环，代码如下。
// 判断从点x出发有没有环
bool cycle(int x, const ugraph &g, vector<int> &color) {
if (color[x] == 1) {
return true;
} else if (color[x] == 2) {
return false;
}
color[x] = 1;
for (auto y : g[x]) {
if (cycle(y, g, color)) return true;
}
color[x] = 2;
return false;
}
本题出错是因为上面的判环写错，只有两种标记是不够的，因为有向图中存在共用两个节点的两条链，这并不是环。
Submission #300492790 - Codeforces
Edu Round 172
C. Competitive Fishing
考虑把一个隔板从右往左移动，遇到1对该位置加1，遇到0对该位置减1，维护一个后缀和的数组。由此，得到一系列连续的整数，由1到max，中间可能有些数重复。现在问题转化为，选取一些隔板，也就是选取一些整数，使其加和为k。我们只需排序后由大到小考虑即可，如果大的数加起来已经超过k，必存在把一个大的数替换成小一点的数使其正好等于k。
本题的出错在于：
ll sum = accumulate(b.begin(), b.end(), 0);
应为：
ll sum = accumulate(b.begin(), b.end(), 0LL);
Submission #300504362 - Codeforces
D. Recommendations
由于求出每个区间的所有predictor就需要 $O(n^2)$ 我考虑的是扫描线的做法，但是没有想出来。在看了题解之后，发现和扫描线类似，解决本题的关键在于按照一定的顺序去考虑问题。当我们把区间按照左端点由小到大，右端点由大到小进行排序之后，考虑到每个区间时它的所有predictor一定都已经考虑过了，那么维护一个已经考虑过的右端点的set R，每次右端点贡献的答案就是R.lower(r) - r。考虑左端点时也是类似的，不过这里有一个巧妙的方法是将原先的所有区间取反，例如 $[2, 3]$ 变为 $[-3, -2]$ 那么就可以直接使用计算右端点贡献的函数去计算左端点了。其次，对于存在重复的区间，答案为0需要跳过。
本题的出错在于直接跳过了相同的区间，其实它们的右端点也需要加入到R里面。
Submission #300519535 - Codeforces
E. Vertex Pairs
2900，太难，不会做，甚至看了题解也不想写，之后再补吧。