牛客网提高组Day1
T1 中位数
这好像是主席树??听说过,不会啊。。。
最后只打了个暴力,可能是n2logn?
只过了前30% qwq
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int M = ;
int n, len;
int tmp, ans;
int a[M];
struct nond {
int id, num;
}e[M]; bool cmp1(nond x, nond y) {
return x.num < y.num;
}
bool cmp2(nond x, nond y) {
return x.id < y.id;
} int main() {
scanf("%d%d", &n, &len);
for (int i = ; i <= n; i++) {
scanf("%d", &e[i].num);
e[i].id = i;
}
for (int i = ; i + len - <= n; i++)
for (int j = i + len - ; j <= n; j++) {
sort(e + i, e + j + , cmp1);
if ((j - i + ) & ) tmp = e[(j + i) / ].num;
else tmp = e[(j + i - ) / ].num;
ans = max(ans, tmp);
sort(e + i, e + j, cmp2);
}
printf("%d\n", ans);
return ;
}
考场代码
正解:
二分求最终可能的答案x,把>x的数字记为1,<=x的数字记为-1。检验是否存在和>=0的区间。可以维护前缀和的前缀最小值
复杂度:O(nlogA[i])
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int a[maxn], n, L; bool test(int z) {
static int b[maxn];
for(int i = ; i <= n; i ++)
if (a[i] >= z) b[i] = ;
else b[i] = -;
for(int i = , mi = ( << ); i <= n; i ++) {
if (i >= L) mi = min(mi, b[i - L]);
b[i] += b[i - ];
if (i >= L && b[i] - mi > ) return ;
}
return ;
} int main() {
// freopen("median.in","r",stdin);
// freopen("median.out","w",stdout);
scanf("%d%d", &n, &L);
for(int i = ; i <= n; i ++) scanf("%d", &a[i]);
int l = , r = int(1e9), tmp;
for(int mid; l <= r;) {
mid = l + r >> ;
if (test(mid)) tmp = mid, l = mid + ;
else r = mid - ;
}
printf("%d\n", tmp);
return ;
}
std
T2 数数字
暴力枚举区间[L, R]中的每一个数,用一个check函数判断每个数的每个位上的数的乘积是否在区间[L1, R1]中,记录答案
本来还想拿L1, R1<=1000的20分来,然后。。。yy了一会,没想出来咋写,so。。只交了40分暴力
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
LL l, r, l1, r1;
LL ans; LL check2(int x) {
LL res = ;
while(x) {
int tmp = x % ;
res *= tmp;
x /= ;
}
if(res >= l1 && res <= r1) return ;
else return ;
} int main() {
scanf("%lld%lld%lld%lld", &l, &r, &l1, &r1);
for(int i = l; i <= r; i++)
if(check2(i)) ans++;
printf("%lld\n", ans);
return ;
}
考场代码
正解:
记忆化搜索或数位DP
这几天刚好在做数位DP的题,然而并不会 qwq
DP做法:
由于数位乘积只是由0到9,可以把L1,R1分类讨论,假如区间包含0,则原来的数字分为包含至少一个零,和完全不包含0两类。前一类可以使用简单的数位DP计算。接下来介绍后一类。
由于只包含1到9,所以只用记录乘积的质因数分解中,出现了多少2,3,5,7。题目中的L1,R1不超过10^18,可以计算出2最多为59个,3最多为37, 5最多为26,7最多为21。设F[i][c_2][c_3][c_5][c_7]表示考虑到第i位,乘积状态为c_2,c_3,c_5,c_7的数位DP情况。接着就是经典数位DP做法。空间可能比较紧,需要用滚动数组。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int co[][];
ll l, r, l1, r1;
ll pw[][]; inline int merge(int i, int cr, int b) {
return (cr > b ? : (cr == b ? i : ));
} ll calc_no_zero(ll x) {
if (x <= ) return ;
static ll f[][][][][][];
memset(f,,sizeof f);
int cr = ;
f[][][][][][] = ;
ll ans = , val;
for(; x; x /= , cr ^= ) {
int bit = x % ;
memset(f[cr ^ ], , sizeof f[cr]);
for(int i = ; i < ; i ++)
for(int n_2 = ; n_2 < ; n_2 ++)
for(int n_3 = ; n_3 < ; n_3 ++)
for(int n_5 = ; n_5 < ; n_5 ++)
for(int n_7 = ; n_7 < ; n_7 ++)
if (val = f[cr][i][n_2][n_3][n_5][n_7]) {
ll q1 = r1 / pw[][n_2] / pw[][n_3] / pw[][n_5] / pw[][n_7];
ll p1 = (l1 - ) / pw[][n_2] / pw[][n_3] / pw[][n_5] / pw[][n_7];
if (q1 >= && p1 <= ) ans += val;
if (q1 <= ) continue;
for(int p = ; p < ; p ++) {
int ni = merge(i, p, bit);
int c_2 = n_2 + co[p][];
int c_3 = n_3 + co[p][];
int c_5 = n_5 + co[p][];
int c_7 = n_7 + co[p][];
if (c_2 >= || c_3 >= || c_5 >= || c_7 >= ) continue;
f[cr ^ ][ni][c_2][c_3][c_5][c_7] += val;
}
}
}
for(int i = ; i < ; i ++)
for(int n_2 = ; n_2 < ; n_2 ++)
for(int n_3 = ; n_3 < ; n_3 ++)
for(int n_5 = ; n_5 < ; n_5 ++)
for(int n_7 = ; n_7 < ; n_7 ++)
if (val = f[cr][i][n_2][n_3][n_5][n_7]) {
ll q1 = r1 / pw[][n_2] / pw[][n_3] / pw[][n_5] / pw[][n_7];
ll p1 = (l1 - ) / pw[][n_2] / pw[][n_3] / pw[][n_5] / pw[][n_7];
if (q1 >= && p1 <= ) ans += val;
}
return ans;
} ll calc_with_zero(ll x) {
if (l1) return ;
static ll g[][][][];
memset(g, , sizeof g);
int cr = ;
ll ans = ;
g[][][][] = ;
for(; x; x /= , cr ^= ) {
int bit = x % ;
memset(g[cr ^ ], , sizeof g[cr]);
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
for(int hd = ; hd < ; hd ++)
if (g[cr][i][j][hd]) {
if (hd && j) ans += g[cr][i][j][hd];
for(int p = ; p < ; p ++) {
int ni = merge(i, p, bit);
int nj = (j | (p == ));
int hdt = (p > );
g[cr ^ ][ni][nj][hdt] += g[cr][i][j][hd];
}
}
}
return ans + g[cr][][][] + g[cr][][][];
} ll calc(long long x) {
return calc_no_zero(x) + calc_with_zero(x);
} int main() {
// freopen("count.in","r",stdin);
// freopen("count.out","w",stdout);
for(int i = ; i < ; i ++) {
for(int j = ; j < ; j ++)
for(int k = i; k % j == ; k /= j)
co[i][j] ++;
pw[i][] = ;
for(int j = ; j <= ; j ++)
pw[i][j] = pw[i][j - ] * i;
}
cin >> l >> r >> l1 >> r1;
ll ans = ;
if (!l) ans += (l1 == ), ++ l;
if (l <= r) ans += calc(r) - calc(l - );
cout << ans << endl;
return ;
}
std
T3 保护
表示只能想到最暴力的方法:
建树后,根据军队保护的范围枚举,为边加边权,然后每个重要人物到根节点的路径也挨个枚举 但是好像写挂了,一分没有 qwq
想过树剖+线段树的做法:
树剖,然后线段树维护区间最小值,军队的保护可以做线段树的区间加法
也不知道对不对的做法,关键是不会啊 弱的一批
好像还有些用倍增做的童鞋,然而出了奇奇怪怪的错误,导致。。。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
const int M = ;
int n, m, t, tot;
int cap[M*];
int to[M*], net[M*], head[M];
int deep[M], top[M], size[M], dad[M];
struct nond {
int id, sum;
int v, k;
} e[M]; void add(int u, int v) {
to[++tot] = v; net[tot] = head[u]; head[u] = tot;
to[++tot] = u; net[tot] = head[v]; head[v] = tot;
} void dfs(int now) {
size[now] = ;
deep[now] = deep[dad[now]] + ;
for (int i = head[now]; i; i = net[i])
if (to[i] != dad[now]) {
dad[to[i]] = now;
dfs(to[i]);
size[now] += size[to[i]];
}
} void dfsl(int now) {
int t = ;
if (!top[now]) top[now] = now;
for (int i = head[now]; i; i = net[i])
if (to[i] != dad[now] && size[t] > size[to[i]])
t = to[i];
if (t) {
top[t] = top[now];
dfsl(t);
}
for (int i = head[now]; i; i = net[i])
if (to[i] != dad[now] && to[i] != t)
dfsl(to[i]);
} int lca(int x, int y) {
while (top[x] != top[y]) {
if (deep[top[x]] < deep[top[y]])
swap(x, y);
x = dad[top[x]];
}
return deep[x] > deep[y] ? y : x;
} void change(int u, int v) {
for (int i = head[v]; i; i = net[i]) {
if (to[i] == u) {
for (int j = head[u]; j; j = net[j])
if (to[j] == v) { cap[j]++; break; }
cap[i]++; return ;
}
if (to[i] = dad[v]) {
cap[i]++;
for (int j = head[u]; j; j = net[j])
if (to[j] == v) cap[j]++;
} v = dad[v];
}
} void fun(int now) {
int u = e[now].v, tmp = e[now].k;
for (int i = head[u]; i; i = net[i]) {
if (to[i] == ) if (cap[i] >= tmp) { e[now].sum++; return ; }
if (to[i] == dad[u])
if (cap[i] >= tmp) e[now].sum++, u = dad[u];
}
} bool cmp1(nond x, nond y) {
if (deep[x.v] == deep[y.v]) return x.k > y.k;
return deep[x.v] > deep[y.v];
}
bool cmp2(nond x, nond y) {
return x.id < y.id;
} int main() {
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
dfs(); dfsl();
for (int i = ; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
if (u == v) continue;
int S = lca(u, v);
// printf("%d\n", S);
if (S == u) change(S, v);
else if (S == v) change(S, u);
else change(S, u), change(S, v);
}
scanf("%d", &t);
for (int i = ; i <= t; i++)
scanf("%d%d", &e[i].v, &e[i].k);
sort(e + , e + t + , cmp1);
for (int i = ; i <= t; i++)
if (e[i].v == e[i - ].v) e[i].sum = e[i - ].sum;
else fun(i);
sort(e + , e + t + , cmp2);
for (int i = ; i <= t; i++)
printf("%d\n", e[i].sum);
return ;
}
考场代码,求路过dalao指正 qwq
正解:
启发式合并维护子树的线段树。询问时可以在维护出来的u的那棵线段树上走,相当于找第k小数。复杂度O((n+q)logn)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
struct node {
int l,r,cnt;
} T[maxn * ]; vector<int> lk[maxn];
int fa[maxn][], dep[maxn], ord[maxn], cnt, n, m, ans[maxn]; void dfs(int now, int pre) {
dep[now] = dep[pre] + ;
fa[now][] = pre;
for (int i = ; ( << i) <= dep[now]; i++) fa[now][i] = fa[fa[now][i - ]][i - ];
for (int i = ; i < lk[now].size(); i ++)
if (lk[now][i] != pre)
dfs(lk[now][i], now);
} void insert(int l, int r, int p, int &jd) {
if (!jd) jd = ++ cnt;
T[jd].cnt ++;
if (l == r) return;
int mid = l + r >> ;
if (p <= mid) insert(l, mid, p, T[jd].l);
else insert(mid + , r, p, T[jd].r);
} int merge(int l, int r, int a, int b) {
if ((!a) || (!b)) return a + b;
int jd = ++ cnt;
T[jd].cnt = T[a].cnt + T[b].cnt;
if (l == r) return jd;
int mid = l + r >> ;
T[jd].l = merge(l, mid, T[a].l, T[b].l);
T[jd].r = merge(mid + , r, T[a].r, T[b].r);
return jd;
} int find_k(int l, int r, int k, int jd) {
if (T[jd].cnt < k) return ( << );
if (l == r) return l;
int mid = l + r >> ;
if (T[T[jd].l].cnt >= k) return find_k(l, mid, k, T[jd].l);
return find_k(mid + , r, k - T[T[jd].l].cnt, T[jd].r);
} void dfs_w(int now, int pre) {
for(int i = ; i < lk[now].size(); i ++)
if (lk[now][i] != pre) {
dfs_w(lk[now][i], now);
ord[now] = merge(, n, ord[now], ord[lk[now][i]]);
}
} int get_lca(int u, int v) {
if (dep[u] > dep[v]) swap(u,v);
for(int i = ; i + ; i --)
if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
if (u == v) return u;
for(int i = ; i + ; i --)
if (fa[v][i] != fa[u][i]) v = fa[v][i], u = fa[u][i];
return fa[u][];
} int main() {
// freopen("guard.in","r",stdin);
// freopen("guard.out","w",stdout);
scanf("%d%d", &n, &m);
for(int i = , u, v; i < n; i ++) {
scanf("%d%d", &u, &v);
lk[u].push_back(v), lk[v].push_back(u);
}
dfs(, );
for(int i = , u, v; i <= m; i ++) {
scanf("%d%d", &u, &v);
int p = get_lca(u, v);
insert(, n, dep[p], ord[u]), insert(, n, dep[p], ord[v]);
}
dfs_w(, );
int q;
scanf("%d", &q);
for(int i = ; i <= q; i ++) {
int u, k;
scanf("%d%d", &u, &k);
printf("%d\n", max(, dep[u] - find_k(, n, k, ord[u])));
}
return ;
}
std