牛客NOIP提高组(二)题解

心路历程

预计得分:100 + 40 + 30 = 170

实际得分:100 + 30 + 0 = 140

T2有一个部分分的数组没开够RE了。

T3好像是思路有点小问题。。 思路没问题,实现的时候一个细节没想过来。。

Sol

T1

直接把式子化开,发现都可以$O(1)$维护,做完了。。。

#include<cstdio>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const LL MAXN = 1e5 + 10;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N, a[MAXN], sum, sump;
int main() {
    N = read();
    for(LL i = 1; i <= N; i++) a[i] = read(), sum += a[i], sump += a[i] * a[i];
    for(LL i = 1; i <= N; i++) {
        LL ans = (N - 1) * (sump - a[i] * a[i]) - 2 * (sum - a[i]) * (sum - a[i]) + (sum - a[i]) * (sum - a[i]);
        if(i != N) printf("%lld ", ans);
        else printf("%lld", ans);
    }
    return 0;
}

T2

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a_i^2)$

正解:

考虑容斥,令$f[i]$表示第$i$个位置的答案

什么都不考虑:$f[i] = f[i - 1] \times a[i]$

这时候会算重第$i$个位置和第$i - 1$个位置相同的情况,减去$f[i-2] * min(a[i], a[i - 1])$

然后会多减去$i - 2, i - 1, i$这三个位置相同的情况,加上$f[i - 3] * min(a[i], a[i  -1], a[i - 2])$

不断容斥下去。

$f[i] = \sum_{j} (-1)^{i - j} f[i - j + 1] * min(a_{(i - j)  \ to \  i})$

但是还有一个问题:这玩意儿是环形的,还需要考虑$1$和$i$不同的情况,。。。

这就很麻烦了,因为$1$和$i$的高度问题很难讨论。

我们直接把序列转一转,令$1$号位置的元素最小,这样$1$号元素不论取什么,$n$号位置一定会少一种取法

考虑如何优化这玩意儿,稍微化简一下,式子就变成了这样(负变正不影响奇偶性)

$f[i] = (-1)^i \sum_{j} (-1)^j f[i - j +1] \times min(a_{(i - j) \  to \  i})$

把$(-1)^j $和$f$看成一项,这东西显然有单调性。

考虑用单调栈去维护

具体做法是:考虑从$i$转移到$i+1$时答案的变化

一种情况是$a[i+1] > a[i]$这时候直接加上$i+1$的贡献即可

另一种情况是$a[i+1] < a[i]$,这时候前面的一些元素对答案的贡献会减小,用单调栈维护,找到第一个小于等于它的,减去这之间的位置的贡献即可。

时间复杂度:$O(n)$

T3

先考虑$m = 0$时。

定义$lowbit(i)$表示$i$的二进制下第一个为$1$的位置,很显然,如果我们把$lowbit(x)$相等的元素全都分给其中一个玩家这样一定是合法的。

每一个$i$能够贡献的数量为$2^{n - i}$。直接对$k$二进制拆分即可。考场上想到了,但是实现的时候傻乎乎的以为每次拆分的时候二进制位不能有重叠。。

$m \not = 0$的时候好像是个神仙dp,明天再看。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

深入理解树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之...

2687
来自专栏漫漫深度学习路

pytorch学习笔记(九):PyTorch结构介绍

PyTorch结构介绍 对PyTorch架构的粗浅理解,不能保证完全正确,但是希望可以从更高层次上对PyTorch上有个整体把握。水平有限,如有错误,欢迎指错,...

3126
来自专栏Python中文社区

Python文档精要研读系列:hash函数

hash(object) Return the hash value of the object (if it has one). Hash values ar...

25210
来自专栏蜉蝣禅修之道

Python递归求矩阵的行列式

2334
来自专栏开发 & 算法杂谈

凸包问题之GrahamScan解法

当沿着Convex hull逆时针漫游时,总是向左转在极坐标系下按照极角大小排列,然后逆时针方向漫游点集,去除非Convex hull顶点(非左 转点)。

994
来自专栏CDA数据分析师

资源 | 23种Pandas核心操作,你需要过一遍吗?

Pandas 是基于 NumPy 构建的库,在数据处理方面可以把它理解为 NumPy 加强版,同时 Pandas 也是一项开源项目。它基于 Cython,因此读...

972
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

1031
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3437
来自专栏软件开发 -- 分享 互助 成长

注意:C++中double的表示是有误差的

注意:C++中double的表示是有误差的,直接通过下面的例子看一下 1 #include<iostream> 2 using namespace std;...

1966
来自专栏欢乐玩转技术

Leetcode 137. 只出现一次的数字 II - 题解

https://leetcode.com/problems/single-number-ii/

8454

扫码关注云+社区

领取腾讯云代金券