CF 417 D 题解
题意构造一个 $n \times m$ 的正整数组成的矩形 $A_{i,j}$，设 $row_i = \sum_{j=1}^m a_{i,j},col_j = \sum_{i=1}^n a_{i,j}$，要求满足 $\sum_{i=1}^n row_i^2,\sum_{i=1}^m col_i^2$ 都是平方数。题解一步都想不到我自闭了。一个想法是先考虑一行的情况再看看能否能推广：现在我们的...
题意构造一个 $n \times m$ 的正整数组成的矩形 $A_{i,j}$，设 $row_i = \sum_{j=1}^m a_{i,j},col_j = \sum_{i=1}^n a_{i,j}$，要求满足 $\sum_{i=1}^n row_i^2,\sum_{i=1}^m col_i^2$ 都是平方数。题解一步都想不到我自闭了。一个想法是先考虑一行的情况再看看能否能推广：现在我们的...
A设第 $i$ 个女生的限制为 $mx_i$，意思是存在一个男生给她 $mx_i$ 的礼物。设第 $i$ 个男生的限制为 $mn_i$，意思是要给所有女生 $mn_i$ 的礼物。设男女生都根据限制大小从小到大排序，首先如果 $mx_n > b_1$ 那么就无解（所有女生至少收到了 $mx_n$ 的礼物，但是第一个女生说她没收到，矛盾了）对于每个女生，我们都要钦定好一个男生送给他礼物，我...
A贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。B枚举我们强制让这个人 $A \to B$ 选择那一班航班起飞（这样就相应 ban 掉了一些航班），然后双指针维护处对应的 $B \to C$ 最近能从哪里开始起飞，就是查一个第 $x$ 大的问题了。因为排好序了可以 $O(1)$ ...
A如果满足条件可以注意到一定有 $a_i = a_{i+k} = a_{i+2k} = \ldots$，所以先判断这个，然后只需要判断 $[1 \ldots k]$ 能否被填成平衡的串即可。B如果先手一步能抓住后手，那么先手必胜。如果 $db \leq 2da$，那么一定存在一个时间后手被先手逼到角落里但是后手无法通过向先手的范围跳跃而跳出攻击范围。那么按照后手的意愿，先后手最后的稳定状态一...
A根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_i}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define...