Codeforces Round #561 (Div. 2)

C. A Tale of Two Lands【分类讨论+二分】

题意：计算满足$P=min(|x-y|,|x+y|);$ $Q=max(|x-y|,|x+y|);$$[|x|,|y|]\subseteq [P,Q]$ 的所有点对 $(x,y)$的数量。$x,y$ 不分顺序且 $x!=y$

分类讨论后发现，所有的情况都一样，对于每一个 $y$考虑计算 $Cnt[\frac{y}{2},y)$,该式子可通过二分解决。

注意数组大小、数据范围与元素正负是否等价的情况。

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<map> #include<cmath> #include<queue> #include<vector> //#include<Windows.h> //-10000 10000并不等价 using namespace std; #define ll long long int #define LL ll #define INF 0x3f3f3f3f const int maxn = 4e5 + 10; int a[maxn]; map <int, int> mp; int vis[maxn]; int main() { int n; memset(vis, 0, sizeof vis); scanf("%d", &n); int k = 0; map<int, int>::iterator it; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (mp.count(a[i]) == 0) { mp[a[i]] = ++k; } a[i] = abs(a[i]); } sort(a + 1, a + 1 + n); LL ans = 0; int cnt = 0; int res = 0; int tmp = 0; for (int i = 1; i <= n; i++) { //cout << a[i] << endl; if (a[i] == a[i - 1]) continue; if (a[i] % 2 == 0) { tmp = a[i] / 2; } else { tmp = a[i] / 2 + 1; } //cout << tmp << " " << a[i] << "---" << endl; int Top = a[i]; //int dec = mp[-a[i]]; cnt = lower_bound(a + 1, a + 1 + n, tmp) - a;//返回下标 res = lower_bound(a + 1, a + 1 + n, Top) - a;//返回下标 //cout << cnt << " " << res << endl; if (mp.count(a[i]) && mp.count(-a[i])) { ans += res - cnt; ans++; } ans += res - cnt; } cout << ans << endl; //system("pause"); return 0; }

E. The LCMs Must be Large【构造】

题意：告诉你一个有 $m$个元素的集合，每天给你一些集合中元素的下标，要求这些元素的 $LCM$要严格大于补集中所有元素的 $LCM$。如果你能找到一种方案使得每天都满足，输出$possible$，否则输出 $impossible$

这题属于$coding$五分钟，思考俩小时的那种… …

首先，如果存在两天，他们的元素下标的交集为空，那么他们肯定是不合法的。就成了第 $i$天的下标集合是第 $j$天下标集合补集的子集，显然他们能相等就不错了，根本不可能双方都严格大于彼此，所以这种情况不存在。

因此，任意两天的元素下标集合，交集都不为空。（需要注意的是，在这里只证明了有交集是有解的充分条件）

接下来证明是必要条件：

我们采用这样一种构造方案，我们任取 $m$个不相同的质数记作 $P_1,P_2...P_m$，枚举每一天，从 $i=1$ 枚举到 $i=n$，将第 $i$ 天集合中所有下标对应的元素，都乘以 $P_i$。直至构造完毕。

任取一天，以第 $i$ 天为例，它的补集中都至少缺失 $P_i$ 这个素数。 而 第 $i$ 天又必定包含 $P_1,P_2...P_m$中所有的元素，如果当前天和任意一天都有交集。

因此，只要任意两天元素下标集合交集不为空，必定有解（必要条件证毕）

懒得写 $LaTeX$公式，反正我觉得文字证明也听通俗易懂的= =

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<map> #include<cmath> #include<queue> #include<vector> //#include<Windows.h> using namespace std; #define ll long long int #define LL ll #define INF 0x3f3f3f3f const int maxm = 1e4 + 10; const int maxn = 65; int vis[maxn][maxm]; int com[maxn][maxn]; int main() { int n, m; memset(vis, 0, sizeof vis); memset(com, 0, sizeof com); scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { int cnt; int id; scanf("%d", &cnt); for (int j = 1; j <= cnt; j++) { scanf("%d", &id); vis[i][id] = 1; } } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { int flag = 0; for (int k = 1; k <= m; k++) { if (vis[i][k] && vis[j][k]) { flag = 1; break; } } if (!flag) { puts("impossible"); return 0; } } } puts("possible"); return 0; }