牛客练习赛132
2024.11.29 rank137
A
在坐标轴1到n每个点有一根高度为a[i]的木棒，相邻2根木棒最高点相连同坐标轴会构成一个梯形/矩形，你可以多次交换不同相邻的木棒，问所有图形面积和的最大值。
B
有n(1e5)张牌和k(1e9)张任意牌，组成不超过m(1e9)的最大长度顺子(连续数)
C
圆上n点(n等分点)选k点，求有两点与圆心共线的方案数。
------------------------独自思考分割线------------------------
-
这三道题都比较有意思。
A 2点
1.多次交换相邻代表可以任意排列。
2.考虑贡献：面积(a+b)/2，发现两端只贡献一次，中间贡献2次，因此只需要把最短的放在两端即可。
B 4点
1.排序去重后更易操作。
2.依次枚举纸牌a[i]作为顺子中最小纸牌，二分最大可以达到的顺子长度并更新答案对m取min。前缀维护区间所需费用。
3.另解：双指针维护费用最大为k的区间长度。
赛时的思路是将已经连续的块看成一个点，计算块之间的费用，前缀和维护。题意转化为在费用k之内将某些块合并使块最大。贪心发现被连接的块需要相邻，就枚举每一个块为起点二分到最远的块，注意一个点就是把k用完最优。闲时重写一下。
C 3点
1.k奇数无解。
2.k>n/2 无论如何选点均可，C(n,k)。
3.k<=n/2直接计算方案有重合比较难计算。考虑补集：总方案C(n,k),不满足的方案数(n/2,k)*2k。
------------------------代码分割线------------------------
A
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
vector<int> a(n);
for (int &a : a)
scanf("%lld", &a);
if (n == 1)
{
puts("0.00");
return;
}
sort(a.begin(), a.end());
a.push_back(a[0]);
auto cal = [](int a, int b)
{
return (double)(a + b) / 2;
};
double res = 0;
for (int i = 1; i < n; i++)
res += cal(a[i], a[i + 1]);
printf("%.2f", res);
}
B
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (auto &a : a)
cin >> a;
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
vector<int> e, w;
e.push_back(0);
w.push_back(0);
w.push_back(0);
int cnt;
for (int i = 0; i < a.size(); i++)
{
cnt = 1;
int j = i + 1;
for (; j < a.size() && a[j] == a[j - 1] + 1; j++)
cnt++;
// if (j < a.size())
{
e.push_back(cnt);
w.push_back(a[j] - a[j - 1] - 1); // last
}
i = j - 1;
}
n = e.size() - 1;
// for (int i = 1; i <= n; i++)
// cout << e[i] << ' ';
// cout << endl;
// for (int i = 1; i <= n; i++)
// cout << w[i] << ' ';
vector<int> pre_w(n + 1), pre_e(n + 1);
for (int i = 1; i <= n; i++)
pre_w[i] = pre_w[i - 1] + w[i], pre_e[i] = pre_e[i - 1] + e[i];
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, min(m, e[i] + k));
for (int i = 1; i <= n; i++)
{
int l = i, r = n + 1;
while (r - l - 1)
{
int mid = l + r >> 1;
if (pre_w[mid] - pre_w[i] <= k)
l = mid;
else
r = mid;
}
// bug2(l, pre_e[l] - pre_e[i]);
res = max(res, min(m, pre_e[l] - pre_e[i - 1] + k));
}
cout << res << endl;
}
C
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
const int N = 1e7 + 10, mod = 1e9 + 7;
void _();
void init();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
init();
cin >> T;
while (T--)
_();
return 0;
}
// 组合数
int qm(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int fac[N], inv[N];
void init()
{
fac[0] = inv[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[N - 1] = qm(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 1; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m)
{
if (n == 0)
return 1ll;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void _()
{
int n, k;
cin >> n >> k;
int res = 0;
if (n % 2 == 0)
{
res = C(n, k);
if (k > n / 2)
res = C(n, n - k);
else
res = (res - C(n / 2, k) * qm(2, k) % mod + mod) % mod;
}
cout << res << endl;
}