牛客网提高组Day2
T1 方差
第一眼看就知道要打暴力啊，然而并没有想到去化简式子。。。
可能因为昨晚没睡好，今天上午困死
导致暴力打了一个半小时，还不对。。。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int M = ;
int n, m;
double sum;
LL a[M], s[M], f[M]; double mul(double a, int b) {
double res = 0.0;
while (b) {
if (b & ) res += a;
a += a;
b >>= ;
}
return ;
} int main() {
scanf("%d", &n);
m = n - ;
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = ; i <= n; i++) {
if (f[a[i]] != ) {
if(i != n) printf("%lld ", f[a[i]]);
else return printf("%lld\n", f[a[i]]), ;
continue;
}
double tmp = 1.0 * (sum - a[i]) / m;
double ss;
for (int j = ; j <= n; j++) {
if (i == j) continue;
double t = abs(a[j] - tmp);
t = 1.0 * t * t;
ss += t;
}
f[a[i]] = mul(ss, m);
if(i != n) printf("%lld ", f[a[i]]);
else printf("%lld\n", f[a[i]]);
}
return ;
}
假的暴力
正解：
题中公式可进行化简，转化为只需维护序列元素的和，平方和即可
#include<iostream>
#include<cstdio>
using namespace std;
const int M = ;
int n;
long long s, s2, ans;
long long a[M]; int main() {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
s += a[i];
s2 += a[i] * a[i];
}
for (int i = ; i <= n; i++) {
ans = (n - ) * (s2 - a[i] * a[i]) - (s - a[i]) * (s - a[i]);
printf("%lld ", ans);
}
return ;
}
T2 分糖果
暴力搜索 然而并没有分 qwq。。。
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int M = ;
int n, ans;
int f[M], a[M], vis[M]; void dfs(int step) {
if(step == n + ) ans++;
else for(int j = ; j <= f[step]; j++) {
if(!vis[j] && step == n && (a[step - ] != j) && a[] != j) {
a[step] = j;
dfs(step + );
}
else if(!vis[j] && (a[step - ] != j) && step != n) {
a[step] = j;
dfs(step + );
}
} } int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++)
scanf("%d", &f[i]);
dfs();
printf("%d\n", ans);
return ;
}
暴力
正解：
暴力复杂度为O(n^2)，所以考虑优化：
线段树优化：O(nlogn) 80pts
单调队列优化：O(n) 100pts
#include<bits/stdc++.h>
using namespace std;
const int M = ;
const int P = 1e9 + ;
int n, B[M], A[M];
int dp[M], sum[];
int q[][M], val[][M], l[], r[]; void insert(int f, int x, int s) {
while (l[f] < r[f] && q[f][r[f] - ] >= x) {
r[f]--;
s = (s + val[f][r[f]]) % P;
sum[f] = (sum[f] - 1ll * val[f][r[f]] * q[f][r[f]] % P + P) % P;
}
val[f][r[f]] = s;
q[f][r[f]++] = x;
sum[f] = (sum[f] + 1ll * s * x % P) % P;
s = ;
while (l[ - f] < r[ - f] && q[ - f][r[ - f] - ] >= x) {
r[ - f]--;
s = (s + val[ - f][r[ - f]]) % P;
sum[ - f] = (sum[ - f] - 1ll * val[ - f][r[ - f]] * q[ - f][r[ - f]] % P + P) % P;
}
if (s) {
val[ - f][r[ - f]] = s;
q[ - f][r[ - f]++] = x;
sum[ - f] = (sum[ - f] + 1ll * s * x % P) % P;
}
} int main() {
scanf("%d", &n);
int mi = , ans = ;
for (int i = ; i <= n; i++) {
scanf("%d", &B[i]);
if (B[mi] > B[i])mi = i;
}
int len = ;
for (int i = mi; i <= n; i++) A[++len] = B[i];
for (int i = ; i < mi; i++) A[++len] = B[i];
dp[] = ;
l[] = r[] = l[] = r[] = ;
for (int i = ; i <= n; i++) {
int mi = A[i];
int f = i & ;
insert(i & , A[i], dp[i - ]);
dp[i] = (sum[f] - sum[ - f] + P) % P;
if (i > ) ans = (dp[i] - ans + P) % P;
}
printf("%d\n", ans);
return ;
}
T3 集合划分
直接输出“-1”没有分 差评。。
正解：
#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
using namespace std;
typedef long long li;
const int M = ;
bool fg[M], vst[M], pt[];
int n, m, k, mx, a[];
int h, t, ft, st[];
int q[M], f[M], tj[M], lst[M];
int as[M];
li s1 = , s2 = ;
li s3 = , srd; li read() {
li x = , y = , c = gc;
while (!isdigit(c)) y = c, c = gc;
while (isdigit(c)) x = (x << ) + (x << ) + (c ^ ''), c = gc;
return y == '-' ? -x : x;
} void print(li q) {
if (q < ) {
pc('-');
q = -q;
}
if (q >= ) print(q / );
pc(q % + '');
} li rd() {
return srd = (srd * s1 + s2 + rand()) % s3;
} int main() {
srand(time());
rd();
int i, j, l;
n = read(); m = read(); k = read();
mx = ( << n) - ;
for (i = ; i <= m; ++i)
a[i] = read(), f[a[i]] = a[i];
if (m > k) return puts("-1"), ;
for (i = ; i <= mx; ++i)
tj[i] = tj[i >> ] + (i & );
for (i = ; i <= mx; i <<= )
for (j = ; j <= mx; j += (i << ))
for (l = j; l < j + i; ++l)
f[l + i] |= f[l];
int q1 = , q2 = ;
for (i = ; i <= mx; ++i) fg[i] = ;
for (i = ; i <= n; ++i) {
if (k & ( << n - i)) ++q1;
else ++q2;
for (j = ; j <= mx; ++j)
if (n - tj[j] == q1 && tj[j] - tj[f[j]] < q2)
fg[j] = ;
}
if (!fg[mx]) {
puts("-1");
return ;
}
int nw, nxt;
q[++t] = mx;
vst[mx] = ;
while (h < t) {
nw = q[++h];
for (i = ; i <= n; ++i)
if (nw & ( << i - )) {
nxt = nw ^ ( << i - );
if (!fg[nxt] || vst[nxt]) continue;
vst[nxt] = ;
lst[nxt] = nw;
q[++t] = nxt;
} }
if (!vst[]) {
puts("-1");
return ;
}
for (nw = ; nw != mx; nw = lst[nw])
st[++ft] = nw;
st[++ft] = mx;
for (i = ; i <= n; ++i) {
if (k & ( << n - i)) {
while (pt[ft - ]) --ft;
nw = st[ft] ^ st[ft - ];
--ft;
for (j = ; j <= mx; ++j)
if (!as[j] && (j & nw)) as[j] = ;
}
else {
l = ;
for (j = ; j <= m; ++j)
if (!as[a[j]]) l |= a[j];
for (j = ; j < ft; ++j)
if (!pt[j] && ((st[j] ^ st[j + ]) & l) == ) {
nw = st[j] ^ st[j + ];
pt[j] = ;
break;
}
for (j = ; j <= mx; ++j)
if (!as[j] && (j & nw)) as[j] = ;
}
}
for(i = ; i <= mx; ++i)
pc(as[i] - + '');
pc('\n');
return ;
}