T1.中位数
二分答案x，原序列大于x的置为1，小于x的置为-1，判断是否存在长度大于m的区间和大于0（也就是大于x的数多于小于x的数），若有，则ans>=x，否则ans<x
#include<iostream>
#include<cstdio>
using namespace std;
inline int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
const int MAXN=100005;
int n,m;
int a[MAXN],b[MAXN];
bool check(int x){
int mn=1<<30;
for(int i=1;i<=n;i++)b[i]=a[i]<x?-1:1;
for(int i=1;i<=n;i++){
if(i>=m) mn=min(mn,b[i-m]);
b[i]+=b[i-1];
if(i>=m&&b[i]>mn)return 1;
}
return 0;
}
int main(){
n=rd();m=rd();
int l=0,r=1<<29,mid,ans;
for(int i=1;i<=n;i++) a[i]=rd();
while(l<=r){
mid=l+r>>1;
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
T2.数数字
数位DP还行，记忆化搜索实现
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
inline ll rd(){
ll ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
const int MAXN=128;
int a[MAXN];
ll l,r,l1,r1;
map<ll,ll> mp[MAXN];
ll dfs(int cur,ll sum,ll lim,ll xzero){
if(!cur){
if(xzero) sum=0;
return (l1<=sum&&sum<=r1);
}
if(!xzero&&!lim&&mp[cur].count(sum))return mp[cur][sum];
ll ret=0;
int mx=9;
if(lim)mx=a[cur];
for(int i=0;i<=mx;i++){
if(xzero)ret+=dfs(cur-1,(i==0)?1ll:i*1ll,lim&&(i==mx),xzero&&(i==0));
else ret+=dfs(cur-1,sum*1ll*i,lim&&(i==mx),xzero&&(i==0));
}
if(!xzero&&!lim)mp[cur][sum]=ret;
return ret;
}
ll solve(ll x){
int cnt=0;
while(x){
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,1,1,1);
}
int main(){
l=rd();r=rd();l1=rd();r1=rd();
cout<<solve(r)-solve(l-1);
return 0;
}
T3.保护
ErkkiErkko的主席树想法
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
inline int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
const int MAXN=200005;
int n,m,q;
vector<int> vec[MAXN];
int rt[MAXN];
struct Edge{
int next,to;
}e[MAXN<<1];
int ecnt,head[MAXN];
inline void add(int x,int y){
e[++ecnt].next = head[x];
e[ecnt].to = y;
head[x] = ecnt;
}
int fa[MAXN],hson[MAXN],siz[MAXN],dep[MAXN];
int top[MAXN],id[MAXN],tim=0;
int ll[MAXN],rr[MAXN];
void dfs1(int x,int pre){
fa[x]=pre;siz[x]=1;dep[x]=dep[pre]+1;
ll[x]=++tim;id[tim]=x;
int mx=0;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs1(v,x);siz[x]+=siz[v];
if(siz[v]>mx){mx=siz[v];hson[x]=v;}
}
rr[x]=tim;
}
void dfs2(int x,int tp){
top[x]=tp;
if(hson[x])dfs2(hson[x],tp);
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==fa[x]||v==hson[x]) continue;
dfs2(v,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<=dep[y]?x:y;
}
int ch[MAXN*40][2],val[MAXN*40],tot;
void update(int x,int &cur,int l,int r){
int f=cur;cur=++tot;val[cur]=val[f]+1;
ch[cur][0]=ch[f][0];ch[cur][1]=ch[f][1];
if(l==r)return;
int mid=l+r>>1;
if(x<=mid)update(x,ch[cur][0],l,mid);
else update(x,ch[cur][1],mid+1,r);
}
int query(int cur,int l,int r,int f,int K){
if(val[f]-val[cur]<K) return -1;
if(l==r)return l;
int mid=l+r>>1;
if(K<=val[ch[f][0]]-val[ch[cur][0]])
return query(ch[cur][0],l,mid,ch[f][0],K);
return query(ch[cur][1],mid+1,r,ch[f][1],K-(val[ch[f][0]]-val[ch[cur][0]]));
}
int main(){
int x,y;
n=rd();m=rd();
for(int i=1;i<n;i++){
x=rd();y=rd();add(x,y);add(y,x);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=m;i++){
x=rd();y=rd();
int z=lca(x,y);
vec[x].push_back(dep[z]);
vec[y].push_back(dep[z]);
}
for(int i=1;i<=n;i++){
rt[i]=rt[i-1];
int up=vec[id[i]].size();
for(int j=0;j<=up-1;j++){
update(vec[id[i]][j],rt[i],1,n);
}
}
q=rd();
int ans=0;
for(int i=1;i<=q;i++){
x=rd();y=rd();
if(!y)ans=dep[x]-dep[1];
else{
int tmp=query(rt[ll[x]-1],1,n,rt[rr[x]],y);
if(tmp==-1||tmp>=dep[x])ans=0;
else ans=dep[x]-tmp;
}
printf("%d
",ans);
}
}