预计得分:100 + 40 + 30 = 170
实际得分:100 + 30 + 0 = 140
T2有一个部分分的数组没开够RE了。
T3好像是思路有点小问题。。 思路没问题,实现的时候一个细节没想过来。。
直接把式子化开,发现都可以$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;
}
好难啊,$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)$
先考虑$m = 0$时。
定义$lowbit(i)$表示$i$的二进制下第一个为$1$的位置,很显然,如果我们把$lowbit(x)$相等的元素全都分给其中一个玩家这样一定是合法的。
每一个$i$能够贡献的数量为$2^{n - i}$。直接对$k$二进制拆分即可。考场上想到了,但是实现的时候傻乎乎的以为每次拆分的时候二进制位不能有重叠。。
$m \not = 0$的时候好像是个神仙dp,明天再看。。