ARC 115 题解
A先将其压成二进制数,考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数,也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下,发现两个数不同,当且仅当一个是 $1$ 一个是 $0$,我们只考虑这些不同的位置,发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A先将其压成二进制数,考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数,也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下,发现两个数不同,当且仅当一个是 $1$ 一个是 $0$,我们只考虑这些不同的位置,发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A如果 $x > k$ 那么可以随便选。$[1,k]$ 我们选择后一半,这样保证任意两个数字相加都 $> k$ 就好了。B直接枚举即可。$0,1,8$ 反转后不变,$2,5$ 反转后互换。C$\geq s$ 最小,也就是尽量靠近 $s$。于是从大到小枚举相同的前缀长度,每次暴力看一下是否有一种方案可行,如果有的话就直接贪心按照字典序放置剩下的字符。D我赛时的做法:对于 $\leq...
A暴力枚举每个字母对应的括号即可。$O(2^3 n)$CodeB发现行列之间的影响只会在于四个角上,所以暴力枚举四个角是否填,然后确定上下界判断即可。$O(2^4)$。CodeC显然 $a_i,b_i > 0$ 和 $a_i,b_i < 0$ 可以分开做:我们只考虑 $a_i,b_i > 0$ 的情况。排序之后,我们枚举「推」到的最后一个位置是 $b_x$,那么我们找到 $...
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back...
题意要求构造大小为 $n$ 的排列,要求至少 $\lceil \frac{m}{2} \rceil$ 条限制:第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。题解神仙题。这个题一般确定排列的方法都不能用了,我们考虑这个在两个数中间的限制:考虑用按照顺序每次将一个数放到前面或者后面的方式。因为保证有解,所以肯定能搞出来一...