比赛链接
A 中位数(前缀和 二分)
额，确实没想到逼近...
然后写了n^2log的暴力,还CE了
只需要判断是否能有大于当前mid的中位数就好
这显然是可以二分的
代码
#include<bits/stdc++.h>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
li x = 0,y = 0,c = gc;
while(!isdigit(c)) y = c,c = gc;
while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
return y == '-' ? -x : x;
}
void print(li q){
if(q < 0){
pc('-');
q = -q;
}
if(q >= 10) print(q / 10);
pc(q % 10 + '0');
}
int n,m;
int a[100010],b[100010],c[100010],d[100010];
bool chk(int p){
int i,j;
for(i = 1;i <= n;++i) b[i] = a[i] >= p ? 1 : -1;
for(i = 1;i <= n;++i) c[i] = c[i - 1] + b[i];
for(i = 1;i <= n;++i) d[i] = min(d[i - 1],c[i]);
for(i = n,j = -n;i >= m;--i){
j = max(j,c[i]);
if(j - d[i - m] > 0) return 1;
}
return 0;
}
int main(){
int i,j;
n = read();m = read();
for(i = 1;i <= n;++i) a[i] = read();
int l = 1,r = 1000000000,mid,as = 1;
while(l <= r){
mid = l + r >> 1;
if(chk(mid)) as = mid,l = mid + 1;
else r = mid - 1;
}
print(as);
return 0;
}
B 数数字(数位DP)
数位DP不会
不过yy一下，写个暴力dp,map转移似乎就...过了
代码
#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
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 L, R, L1, R1;
map<LL, LL> f[20];
LL s[21], num = 0;
LL dfs(int x, int lim, LL mul) {
if(x < 0) return 0;
if(x == 0) {
if(mul == -1) mul = 0;
return mul >= L1 && mul <= R1;
}
if((!lim) && (f[x].find(mul) != f[x].end())) return f[x][mul];
LL ans = 0;
for(int i = 0; i <= (lim ? s[x] : 9); i++) {
if(mul == -1) {
if(i == 0) ans += dfs(x - 1, 0, -1);//tag
else ans += dfs(x - 1, lim && (i == s[x]), i);
} else ans += dfs(x - 1, lim && (i == s[x]), i * mul);
}
if(!lim) f[x][mul] = ans;
return ans;
}
LL solve(LL x) {
if(x == -1) return 0;
num = 0;
while(x) s[++num] = x % 10, x /= 10;
return dfs(num, 1, -1);
}
int main() {
L = read(); R = read(); L1 = read(); R1 = read();
LL ans = solve(R) - solve(L - 1);
cout << ans;
return 0;
}
C 保护(dfs序 主席树)
额，主席树维护一下子树中点能覆盖的第k小深度..就没了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
struct sj{int to,next;}line[maxn*2];
int size,n,m,num,q,siz[maxn];
int head[maxn],id[maxn],tot,idx[maxn];
int a[maxn],b[maxn],c[maxn],T[maxn];
int L[maxn * 64],R[maxn * 64],sum[maxn * 64];
void add(int x,int y) {
line[++size].to=y;
line[size].next=head[x];
head[x]=size;
}
int old[maxn],deep[maxn];
int dad[maxn][27];
void dfs(int x,int fa = 0) {
siz[x] = 1;
++ num;
id[x]=num;
old[num]=x;
deep[x] = deep[fa] + 1;
for(int i=head[x];i;i=line[i].next) {
int tt=line[i].to;
if(!siz[tt]) {dad[tt][0] = x;
dfs(tt,x);
siz[x]+=siz[tt];
}
}
}
inline int lca(int x,int y) {
if(deep[x] > deep[y]) std::swap(x,y);
for(int i = 20;i >= 0;-- i) if(deep[dad[y][i]] >= deep[x]) y = dad[y][i];
if(x == y) return x;
for(int i = 20;i >= 0;-- i)
if(dad[x][i] != dad[y][i])
x = dad[x][i],y = dad[y][i];
return dad[x][0];
}
int build(int l,int r) {
int rt=++tot;
if(l!=r) {
int mid=(l+r)/2;
L[rt]=build(l,mid);
R[rt]=build(mid+1,r);
}
return rt;
}
int update(int pre,int l,int r,int x) {
int rt =++ tot;
L[rt]=L[pre];
R[rt]=R[pre];
sum[rt]=sum[pre] + 1;
int mid=(l+r)/2;
if(l!=r) {
if (x<=mid) L[rt]=update(L[pre],l,mid,x);
else R[rt]=update(R[pre],mid+1,r,x);
}
return rt;
}
int query(int x,int y,int l,int r,int k) {
if(l==r)return l;
int now=sum[L[y]]-sum[L[x]];
int mid=(l+r)/2;
if(now>=k) return query(L[x],L[y],l,mid,k);
else return query(R[x],R[y],mid+1,r,k-now);
}
vector<int> qq[maxn];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++) {
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1);
for(int i = 1;i <= 20;++ i)
for(int x = 1;x <= n;++ x) dad[x][i] = dad[dad[x][i - 1]][i - 1];
for(int u,v,i = 1;i <= m;++ i) {
scanf("%d%d",&u,&v);
int l = lca(u,v);
qq[u].push_back(deep[l]);
qq[v].push_back(deep[l]);
}
T[0]=build(1,n + 1);
for(int i=1;i <= n;i ++) {
if(qq[old[i]].size()) {
for(int j = 0;j < qq[old[i]].size();++ j) {
if(j == 0) T[i] = update(T[i - 1],1,n + 1,qq[old[i]][j]);
else T[i] = update(T[i],1,n + 1,qq[old[i]][j]);
}
}
else T[i] = update(T[i - 1],1,n + 1,n + 1);
}
scanf("%d",&q);
while(q--) {
int x,k;
scanf("%d%d",&x,&k);
int p=query(T[id[x]-1],T[id[x]+siz[x] - 1],1,n + 1,k);
printf("%d
",std::max(deep[x] - p,0));
}
return 0;
}