前言
虽然说有点难受, 但是还是好好考
考试只需要管考试相关的即可, 别想太多
冷静, 就这样
看题
先过一遍吧, 看看感觉怎么样, 今天时间要短一点, 不开心
\(\rm{T1}\)
至少题意清楚, 不管了
\(\rm{T2}\)
这么有实力, 很像 \(\rm{Indec \ Sequence}\)
\(\rm{T3}\)
多半要观察性质
\(\rm{T4}\)
这个打个模拟分就行了
\(\rm{T1}\)
思路
冷静, 好好看
用数学语言转化一下,
对于长为 \(n\) 的数列 \(b\) , 从中选出大小为 \(k (1 \leq k \leq n)\) 的非空可重子集 \(b\)
求 \(\displaystyle \max_b \sum_{i = 1}^{\lvert b \rvert} \left[ b_i > \frac{\sum_{j = 1}^{\lvert b \rvert} b_j}{\lvert b \rvert} \right]\)
玩一下样例 \(2\) 看下性质
好像一边从小往大选, 一遍从大往小选很对啊
打个 \(\mathcal{O} (n^2)\) 看下对不对, 再想优化, 要是不对只能寄
怎么和大样例差了 \(2\) , 难崩
那怎么办, 容易想到一些构造方法把刚刚的做法卡掉, 难受
贪心不行考虑 \(\rm{dp}\)
考虑两个 \(\rm{dp}\) 合并答案
令 \(l_{i, j}\) 表示序列中最大值为 \(j\) , 选了 \(i\) 个数时最大的和, \(r_{i, j}\) 表示序列中最小值为 \(j\) , 选了 \(i\) 个数时最小的和
哪些状态是可以合并计算答案的, 显然的, 如果对于 \(r_{i, j}\) 可以找到 \(l_{k, j}\) 满足
\[\frac{r_{i, j} + l_{k, j}}{i + k} < j \]那么其对答案的贡献就是 \(i\)
又感觉很对啊, 但是还是先打个 \(\mathcal{O} (n^2)\) 出来检查一下
然后发现 \(l, r\) 都不好转移, 但是你发现好像可以直接 \(\mathcal{O} (n^2)\) 算
反正现在也最多达到暴力分, 想想这个不亏
形式化一下就是枚举 \(j\) 然后计算贡献, 和之前的贪心很像, 只是换了枚举方向
现在我们的做法是, 枚举分割点 \(p\) , 然后对于 \(p\) 右侧我们从小到大找 \(i\) 个数字, 其和为 \(sum\) , 然后在 \(p\) 左侧从小到大找 \(j\) 个数字看是否符合要求, 如果用 \(Pre\) 表示前缀和, 即检查 \(\displaystyle\frac{Pre_j + sum}{i + j} < a_p\)
这个是 \(\mathcal{O} (n^3)\) 的, 考虑优化
直觉上是有单调性的, 但是仔细分析了一下又不存在
看起来没时间了, 先把暴力打了再说
实现
\(\mathcal{O} (n^3)\) 算法
框架
按照上面说的模拟即可
代码
class Brute_Force
{
private:
int Ans = 0;
public:
void solve() {
std::sort(a + 1, a + n + 1);
for (int p = n; p >= 1; p--) {
int rsum = 0;
for (int r = p; r <= n; r++) {
rsum += a[r];
int lsum = 0; bool flag = false;
for (int l = 1; l < p; l++) {
lsum += a[l];
if ((r - p + 1ll + l) * a[p] > lsum + rsum) {
Ans = std::max(Ans, r - p + 1ll);
}
}
}
}
printf("%lld", Ans);
}
} BF;
\(\rm{T2}\)
思路
这个题和之前做过的一题很像, 说不定可以冲正解?
唯一的区别就是差 , 而且每次可以 \(\pm k\)
分数组第一位一定要是 \(0\)
你发现在序列之中匹配完了之后, 剩下 \(k\) 个数就要做 \(k\) 次操作
如果匹配了 \(i\) 对, 剩下来 \(k\) 个数, 总花费为 \(k + i\)
你发现时间复杂度给的可以放过 \(\mathcal{O} (n 2^n)\) , 往这个方向想
你又发现一次操作至少可以消掉一个数, 那么肯定是尽可能匹配优先
用 \(\rm{dp}\) 的方法做, 差不多会了, 一会继续推, 实在太难受了先打暴力
打了 \(70 \rm{pts}\) 的暴力, 过来全力冲这个题
首先规定负数为绝对值小的那一方, 方便处理
令 \(dp_{i, \mathbb{S}}\) 表示考虑到第 \(i\) 个负数, 当前余下的正数集合为 \(\mathbb{S}\) , 当前的匹配花费最少是多少加上余下了多少个负数 (其实就是最后的花费)
这个地方值得注意的是如果一个数没法全匹配, 那可以直接跳过把这个都放到最后来计算贡献
还有一个地方是你需要预处理每个负数可以被哪些正数拼起来消掉, 方便处理 \(\rm{dp}\) 转移中的 \(\mathbb{S} ^ {\prime}\)
\(\rm{dp}\) 柿子差不多长这样:
\[\begin{cases} \begin{aligned} & dp_{i, \mathbb{S}} \stackrel{min}{\longleftarrow} dp_{i - 1, \mathbb{S}} + 1 \\ & dp_{i, \mathbb{S}} \stackrel{min}{\longleftarrow} dp_{i - 1, \mathbb{S} ^ {\prime}} + cost \end{aligned} \end{cases} \]总时间复杂度 \(\mathcal{O} (n^2 2^n) - \mathcal{O} (n 2^n)\)
其实实际上要比预计的复杂度更高, 但总体上差不多这样, 能打出来就谢天谢地了, 还是别管挂分了
然后挂了, 进一步发现还是假的, 哈哈哈哈哈
实现
框架
首先把所有数据处理成符合上文正负数的性质
然后预处理每个负数可以被哪些数拼起来
然后转移 \(\rm{dp}\) 方程, 滚一下降成双维
代码
#include <bits/stdc++.h>
#define int long long
const int MAXN = 25;
const int MAXVAL = (1 << 23);
int n;
int a[MAXN], dif[MAXN];
std::vector<int> pos, neg;
std::vector<int> divide[MAXN];
/*将所有数据预处理好*/
void init() {
/*预处理正负数*/
int suma = 0, sumb = 0; // 表示正负数的绝对值之和
for (int i = 1; i <= n; i++) {
if (dif[i] < 0) sumb += -dif[i];
if (dif[i] > 0) suma += dif[i];
}
if (suma > sumb) {
for (int i = 1; i <= n; i++) {
if (dif[i] < 0) neg.push_back(-dif[i]);
if (dif[i] > 0) pos.push_back(dif[i]);
}
} else {
for (int i = 1; i <= n; i++) {
if (dif[i] > 0) neg.push_back(dif[i]);
if (dif[i] < 0) pos.push_back(-dif[i]);
}
}
/*预处理每个负数可以被那些数拼起来*/
for (int i = 0; i < neg.size(); i++) {
for (int S = 0; S < (1 << pos.size()); S++) {
int cnt = 0, nowS = S, sum = 0;
while (nowS) {
if (nowS & 1) sum += pos[cnt];
cnt++, nowS >>= 1;
}
if (sum == neg[i]) divide[i].push_back(S);
}
}
}
int dp[2][MAXVAL];
/*处理 dp*/
void solve() {
int now = 0, nxt = 1;
/*初始化*/
memset(dp, 0x3f, sizeof dp);
dp[now][(1 << pos.size()) - 1] = 0;
/*递推*/
for (int i = 0; i < neg.size(); i++) {
std::swap(now, nxt); memset(dp[now], 0x3f, sizeof dp[now]);
for (int S = 0; S < (1 << pos.size()); S++) {
dp[now][S] = std::min(dp[now][S], dp[nxt][S] + 1);
for (int j = 0; j < divide[i].size(); j++) {
int Splus = divide[i][j];
if (S & Splus) continue;
int Sp = S | Splus;
dp[now][S] = std::min(dp[now][S], dp[nxt][Sp] + std::__popcount(Splus));
}
}
}
/*计算答案*/
int Ans = 0x3f3f3f3f3f3f3f3f3f;
for (int S = 0; S < (1 << pos.size()); S++) {
Ans = std::min(Ans, dp[now][S] + std::__popcount(S));
}
printf("%lld", Ans);
}
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); dif[i] = a[i] - a[i - 1]; }
init();
solve();
return 0;
}
\(\rm{T3}\), \(\rm{T4}\)
时间肯定不够了, 把模拟分打完就没有了
状态太差了, 现在想题需要分精力出来控制呼吸 \(\cdots\)
#include <bits/stdc++.h>
const int MAXN = 10;
int n;
int aimc[MAXN];
int Ans = 0;
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d", &aimc[i]);
int now[MAXN], p[MAXN]; for (int i = 1; i <= n; i++) p[i] = i;
do {
for (int i = 1; i <= n; i++) now[i] = p[i];
int c[MAXN];
for (int i = 1; i < n; i++) {
c[i] = 0;
for (int j = i + 1; j <= n; j++)
if (now[i] > now[j])
{
std::swap(now[i], now[j]);
c[i]++;
}
}
bool same = true;
for (int i = 1; i < n; i++) {
if (c[i] != aimc[i]) { same = false; break; } }
if (same) Ans++;
} while (std::next_permutation(p + 1, p + n + 1));
printf("%d", Ans);
return 0;
}
\(\rm{T4}\) 没时间了
总结
方法是好的, 下午好好补题
标签：mathbb,赛时,int,Ans,12.26,mathcal,rm,CW,dp From： https://www.cnblogs.com/YzaCsp/p/18632854