牛马小合集
校内模拟赛中一些牛马题的合集
第一题:
题意:
给定 \(n\) 个数,分别为 \(a_1,a_2,a_3,\dots,a_{n-1},a_n\)。将这 \(n\) 个数随机分成两堆,且每堆数都至少有一个。求能使两堆分别进行与运算后值相同的方案数。
其中,\(1\le n\le60,0\le a_i<2^{17}?\)。
分析:
我们假设两堆进行与运算后值分别为 \(x\) 和 \(y\)。若方案合法,则 \(x=y\)。
设 \(S=a_1\&a_2\&a_3\&\dots\&a_{n-1}\&a_n\)。若方案合法,则 \(x\&S=x\)。
显然,合法方案数=总方案数-不合法方案数,且总方案数为 \(2^n-2\)(去掉空堆的情况)。
我们可以发现,\(S\) 中为 \(1\) 的位置在数列中每一个数的这一位也是 \(1\),为 \(0\) 的位置在数列中的数的这一位为 \(0\) 为 \(1\) 皆可(但每一堆中都必有一个数这一位为 \(0\))。
因此,我们无需枚举与 \(S\) 在相同位上同为 \(1\) 的状态。
若方案合法,且 \(x,y\) 在某一位上都为 \(0\),则两堆数中都至少有一个数这一位为 \(0\)。因此,如果我们将某一位为 \(0\) 的数放入同一堆,则可以使 \(x\ne y\)(即方案不合法)。
我们枚举每一个状态,记为 \(i\),其中 \(i\in[0,2^{17})\)。设 \(i\) 中有 \(m\) 位为1。由上可得,\(S\) 与 \(i\) 至少有 \(m\) 为不同,即至少有 \(m\) 位不合法。
由容斥原理可得:合法方案数=总方案数-至少1位不合法+至少2位不合法-至少3位不合法+至少4位不合法-至少5位不合法...
接下来,我们计算状态为 \(i\) 时,至少有 \(m\) 位不合法的方案数。
初始:将 \(n\) 个数分别自己构成一个集合。
我们枚举 \(i\) 的每一位,若枚举的这一位(记为 \(j\))为 \(1\),我们可以不去管它;反之我们将第 \(j\) 位为 \(0\) 的序列中的数合并进同一个集合。
我们设枚举完 \(i\) 的每一位后,还剩下 \(num\) 个集合。我们将这 \(num\) 个集合放入两堆且无空堆的方案数为 \(2^{num}-2\)。因此,状态为 \(i\) 时,至少有 \(m\) 位不合法的方案数为 \(2^{num}-2\) 个。
维护集合用并查集即可。最终总复杂度为 \(O(n\log n\times a\log a)\)。
Code:
/*
user:xcj
time:2022.4.14
*/
#include
#define int long long
#define M 131072
#define N 100
using namespace std;
int n, ans, sum = M - 1, a[N], fa[N];
bool flag;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; w *= ch == '-' ? -1 : 1, ch = getchar());
for (; ch >= '0' && ch <= '9'; s = s * 10 + ch - '0', ch = getchar());
return s * w;
}
int find_f(int x){return x == fa[x] ? x : fa[x] = find_f(fa[x]);}
int cnt(int x, int res = 0){
for (; x; x -= x & (-x)) ++res;
return res;
}
signed main(){
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), sum &= a[i];
for (int i = 0, num = n; i < M; ++i, flag = 0, num = n){
for (int j = 0; j < 17; ++j)
if ((i >> j & 1) && (sum >> j & 1)) flag = 1;
if (flag) continue;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int j = 0, st = 0; j < 17; ++j, st = 0)
if (i >> j & 1)
for (int i = 1; i <= n; ++i)
if (!(a[i] >> j & 1))
if (!st) st = i;
else if (find_f(st) != find_f(i)) --num, fa[find_f(st)] = find_f(i);
if (cnt(i) & 1) ans -= (1ll << num) - 2;
else ans += (1ll << num) - 2;
}
printf("%lld\n", ans);
return 0;
}
第二题:
题意:
给定 \(n\) 个数,为 \(a_1,a_2,a_3,\dots,a_{n-1},a_{n}\)。并给定三个整数 \(m,L,R\),求\(\underset{L\le r-l+1\le R}{\max} \dfrac{Max(l,r)-Min(l,r)}{r-l+k}\)。
其中,\(Max(l,r)\) 表示区间 \([l,r]\) 中的最大值,\(Min(l,r)\) 表示区间 \([l,r]\) 中的最小值。
分析:
考虑一段使答案最大化的区间,两端点必为最值,除非长度小于 \(L\),被迫加入其他数。
所以先预处理出 $ r - l + 1 = L$ 的情况,然后使用单调队列优化。
使用二分答案,处理下界为长度等于 \(L\) 的情况,并记答案为 \(x\),同时需要判断是否存在 \(\frac{Max(l,r)-Min(l,r)}{r-l+k} \geq x\)。
移项,得:
由于两端点必为最值,不妨设 \(a_l \leq a_r\)(\(a_l\ge a_r\) 的情况可以通过翻转区间再做一遍),则上式变为:
\[a_r-a_l+lx-rx \ge kx\\a_r-rx-(a_l-lx) \ge kx \]令 \(b_i = a_i-ix\),则上式变为 \(b_r - b_l \geq kx\)。
可用单调队列存储。
Code:
/*
user:xcj
time:2022.4.21
*/
#include
#define int long long
#define N 50010
using namespace std;
deque < int > dq, maxn, minn, __;
int n, m, l, r, a[N];
double ans, b[N];
inline int read(){
int s = 0, w = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; w *= ch == '-' ? -1 : 1, ch = getchar());
for (; ch >= '0' && ch <= '9'; s = s * 10 + ch - '0', ch = getchar());
return s * w;
}
bool chck(double x, bool flag = 0){//滑动窗口判答案
dq = __;
for (int i = 1; i <= n; ++i) b[i] = a[i] - x * i;
for (int i = l; i <= n; ++i){//枚举右端点
while (dq.size() && b[dq.back()] > b[i - l + 1]) dq.pop_back();
while (dq.size() && i - dq.front() + 1 > r) dq.pop_front();
dq.push_back(i - l + 1), flag |= (b[i] - b[dq.front()]) >= x * m;//使b[左端点]最小
}
return flag;
}
double work(double res = 0){//滑动窗口存最值
maxn = minn = __;
for (int i = 1; i <= n; ++i){
while (maxn.size() && a[maxn.back()] < a[i]) maxn.pop_back();
while (maxn.size() && i - maxn.front() + 1 > l) maxn.pop_front();
while (minn.size() && a[minn.back()] > a[i]) minn.pop_back();
while (minn.size() && i - minn.front() + 1 > l) minn.pop_front();
maxn.push_back(i), minn.push_back(i);
res = max(res, (a[maxn.front()] - a[minn.front()]) * 1.0 / (l + m - 1));
}
return res;
}
double calc(double L = work(), double R = 2e9, double res = 0){//二分答案
for (res = L; R - L > 1e-7; ){
double mid = (L + R) / 2;
if (chck(mid)) L = res = mid;
else R = mid;
}
return res;
}
signed main(){
for (int _ = read(); _--; ){
n = read(), m = read(), l = read(), r = read();
for (int i = 1; i <= n; ++i) a[i] = read();
ans = calc(), reverse(a + 1, a + n + 1), ans = max(ans, calc());
printf("%.4lf\n", ans);
}
return 0;
}