A. Ezzat and Two Subsequences
题意：将n个数分为两组不为空的数的集合，输出两组数中平均数和的最大值，误差不超过1e-6
分析：首先进行所有数全是正数的讨论，一组为单个的最大值，右边为剩余n-1个的值，从右边拿出比平均值大的数放左边，两边平均值都会下降，从右边拿出比平均值小的数，右边会微量提高，左边会降极多，故不换最优，而对于有负数的情况，我们总可以将所有数加一个值使得所有数变为正数，而平均值是不会有影响的，加上的值最后减去，所以同理，故结论就是，两组分为单个最大的值，和其他所有元素，这样分最优。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k, a;
int s[N], g[N], dp[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
sort(s + 1, s + n + 1);
ll sum = 0;
for (int i = 1; i < n; i++)
sum += s[i];
printf("%.9f\n", 1.0 * sum / (n - 1) + s[n]);
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
B. Moamen and k-subarrays
题意：要将给定的n个数分为k组，使得将k组排序后，所有数成非递减序列，题目保证所有数都不相同
分析：显然直接将原数组排序，保存下每个数后面应该是哪个数，就可以在原数组中查询当前是否必须分割，不是必须分割就不分，会得出最少需要分割几组才会使得排序后原数组非递减，显然当最小组数大于k时，不成立，小于等于k时，再次分割，一定可以等于k组
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k, a;
int s[N], g[N], dp[N];
unordered_map<int, int> ma;
void solve()
{
cin >> n >> k;
ma.clear();
for (int i = 1; i <= n; i++)
cin >> s[i], g[i] = s[i];
sort(s + 1, s + 1 + n);
s[n+1] = mod;
for (int i = 1; i <= n; i++)
ma[s[i]] = s[i+1];
int cnt = 1;
for (int i = 2; i <= n; i++)
if (ma[g[i-1]] != g[i])
cnt++;
if (cnt <= k) puts("Yes");
else puts("No");
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
C. Moamen and XOR
题意：给定n和k，意义为由n个数，每个数严格小于\(2^{k}\)，问有多少数满足：
a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an，答案取模1e9+7
分析：如果k为0，没得讨论，所有数唯一，绝对成立，输出1即可，然后要根据大小原理，要根据最高位进行分析，当最高位全1时，前者的结果为1，后者的结果根据奇偶性为1或0，所以要分类讨论，首先讨论奇数的情况，奇数时，全1的话，前后的这一位都是1，然后讨论前后均为0的情况，显然，均为0的情况就是这一位有偶数个1，所以枚举\(\sum_{0}^{n/2}C_{n}^{2i}\),等于的情况就是都为1和都为0的情况，因为前者在奇数的情况下不可能大于后者，所以只有等于的情况，而所有位置情况相同，就是k个ans相乘，快速幂算一下就好，接下来讨论偶数的情况，全1的话，必胜，当前数量乘后面所有位置任意排列的情况数，不必胜的时候讨论当前平局，胜利状态转移到下一轮进行，到某一位就计算当前行全为1,的必胜情况数，叠加一起，最后要加上平局的情况数，计算过程中取模
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, t, k, a;
int s[N], g[N], in[N], inv[N];
int ksm(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
void init()
{
in[0] = in[1] = inv[1] = inv[0] = 1;
for (int i = 2; i < N; i++)
{
in[i] = 1ll * in[i-1] * i % mod;
inv[i] = 1ll * inv[i-1] * ksm(i, mod - 2) % mod;
}
}
int C(int a, int b)
{
if (b == 0) return 1;
return 1ll * in[a] * inv[a-b] % mod * inv[b] % mod;
}
void solve()
{
cin >> n >> k;
if (k == 0)
{
puts("1");
return;
}
int ans = 0, cnt = 0;
if (n & 1)
{
cnt++;
for (int i = 0; i < n; i += 2)
cnt = (cnt + C(n, i)) % mod;
cout << ksm(cnt, k) << endl;
}
else
{
for (int i = 0; i < n; i += 2)
cnt = (cnt + C(n, i)) % mod;
g[0] = 1;
int cnt3 = ksm(2, n), cnt4 = 1;
for (int i = 1; i <= k; i++)
g[i] = 1ll * g[i-1] * cnt3 % mod;
int cnt2 = 1;
for (int i = 1; i <= k; i++)
{
ans = (1ll * ans + 1ll * cnt2 * g[k-i] % mod) % mod;
cnt2 = 1ll * cnt2 * cnt % mod;
}
cout << (1ll * ans + cnt2) % mod << endl;
}
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}