【考试总结】2022-04-05
虚数之树
建出点分树之后无论是修改还是查询都可以每次在点分树上跳祖先，并且用线段树维护
Code Display
const int N=1e5+10,M=N*200;
vector G[N];
int rt[N];
int n,Q,typ;
struct Seg{
int mn[M],tot,ls[M],rs[M];
inline void push_up(int x){mn[x]=min(mn[ls[x]],mn[rs[x]]);}
inline void upd(int pos,int v,int &p,int l,int r){
if(!p) p=++tot;
if(l==r) return mn[p]=v,void();
int mid=(l+r)>>1;
if(pos<=mid) upd(pos,v,ls[p],l,mid);
else upd(pos,v,rs[p],mid+1,r);
return push_up(p);
}
inline int query(int p,int l,int r,int st,int ed){
if(!p) return n+1;
if(st<=l&&r<=ed) return mn[p];
int mid=(l+r)>>1,res=n+1;
if(st<=mid) ckmin(res,query(ls[p],l,mid,st,ed));
if(ed>mid) ckmin(res,query(rs[p],mid+1,r,st,ed));
return res;
}
}T;
vector dis[N];
bool vis[N];
int f[N],siz[N],root,nsum,fa[N];
inline void findrt(int x,int fat){
f[x]=0; siz[x]=1;
for(auto t:G[x]) if(!vis[t]&&t!=fat){
findrt(t,x);
siz[x]+=siz[t];
ckmax(f[x],siz[t]);
}
ckmax(f[x],nsum-siz[x]);
if(f[x]=1&&x<=n);
int anc=x,pter=dis[x].size()-1;
while(anc){
T.upd(x,dis[x][pter],rt[anc],1,n);
pter--;
anc=fa[anc];
}
}else if(opt==2){
int x=read()^(typ*lans);
int anc=x,pter=dis[x].size()-1;
while(anc){
T.upd(x,n+1,rt[anc],1,n);
pter--;
anc=fa[anc];
}
}else{
int l=read(),r=read(),x=read()^(typ*lans);
int anc=x,pter=dis[x].size()-1,ans=n+1;
while(anc){
ckmin(ans,T.query(rt[anc],1,n,l,r)+dis[x][pter]);
pter--;
anc=fa[anc];
}
print(ans==n+1?-1:(lans=ans));
}
}
return 0;
}
速通
和前两天 【舰队游戏】 一题是一致的，设 \(f_{x,i}\) 表示从 \(x\) 在不超过 \(i\) 步走到一个叶子的期望步数，二分 \(f_{1,lim}\)
这次甚至不用维护 \(f_{1,lim}\) 的系数，直接比较大小即可
Code Display
const int N = 110;
int n, lim, L[N], R[N];
vector G[N];
double p[N];
double f[N][1010];
inline double calc(double x){
memset(f,0,sizeof(f));
Down(i,n,1){
for(int j=0;j<=lim;++j){
for(int k=L[i];k<=R[i];++k){
if(k>j){
f[i][j]+=x+k;
continue;
}
if(G[i].size()==0){
f[i][j]+=k;
continue;
}
double cur=0;
for(auto t:G[i]) cur+=p[t]*f[t][j-k];
ckmin(cur,x);
f[i][j]+=cur+k;
}
f[i][j]/=R[i]-L[i]+1;
}
}
return f[1][lim];
}
signed main(){
freopen("isaac.in","r",stdin); freopen("isaac.out","w",stdout);
n=read(); lim=read();
rep(i,1,n) L[i]=read(),R[i]=read();
for(int i=2;i<=n;i++) G[read()].push_back(i),scanf("%lf", &p[i]);
if(calc(1e9)>1e9) puts("Remake"),exit(0);
double ans=1e9,l=0,r=1e9;
while(r-l>1e-9){
double mid = (l + r) / 2;
if (calc(mid)>mid) l=mid;
else ans=r=mid;
}
printf("%.10lf\n",ans);
return 0;
}
叮叮车
本质上是求 \([L,R]\) 中的 \(x\) 在 \(7\) 进制下 \(x+x\) 的最大进位次数
考虑贪心，找到 \(L,R\) 的 \(\rm LCP\) 后一位，如果不能造成进位或者减一仍然可以造成进位那么直接减
否则找到这个能连续进位段里面最大的一个数减 \(1\)，后面全置 \(6\)，如果从末尾到这个数字都能进位就直接选 \(r\) 即可
Code Display
const int Bas=40353607;
struct node{
vector a;
inline int size(){return a.size();}
inline void adjust(){
int siz=a.size();
for(int i=0;i=Bas){
a.emplace_back(a[siz-1]/Bas);
a[siz-1]%=Bas;
++siz;
}
while(siz>1&&!a[siz-1]) a.pop_back(),--siz;
return ;
}
inline void init(string x){
vector num[2]; num[0].resize(x.size());
int cur=0;
int len=x.size();
for(int i=len-1;i>=0;--i) num[cur][i]=x[i]-'0';
reverse(num[cur].begin(),num[cur].end());
while(num[cur].size()>1||num[cur][0]>0){
num[cur^1].clear();
int tmp=0,siz=num[cur].size();
bool flag=0;
for(int i=siz-1;i>=0;--i){
tmp=tmp*10+num[cur][i];
if(tmp>=Bas) flag=1;
if(flag) num[cur^1].emplace_back(tmp/Bas),tmp%=Bas;
}
a.emplace_back(tmp);
cur^=1;
reverse(num[cur].begin(),num[cur].end());
siz=num[cur].size(); num[cur].emplace_back(0);
for(int i=0;i>str_L>>str_R;
L.init(str_L); R.init(str_R);
for(auto t:L.a){
int v=t;
for(int j=0;j<9;++j) down[++len]=v%7,v/=7;
}
while(len>1&&down[len]==0) --len;
len=0;
for(auto t:R.a){
int v=t;
for(int j=0;j<9;++j) up[++len]=v%7,v/=7;
}
while(len>1&&up[len]==0) --len;
reverse(up+1,up+len+1);
reverse(down+1,down+len+1);
vector six(len+2);
six[len+1]=len+1;
int inc=0;
for(int i=len;i>=1;--i){
if(up[i]+up[i]+inc>=7){
six[i]=six[i+1];
inc=1;
}else{
six[i]=i;
inc=0;
}
}
for(int i=1;i<=len;++i){
if(down[i]!=up[i]){
if(six[i]==len+1){
rep(j,i,len) n[j]=up[j];
break;
}
if(up[i]>4||six[i]==i){
n[i]=up[i]-1;
rep(j,i+1,len) n[j]=6;
break;
}
if(up[six[i]-1]>4){
rep(j,i,six[i]-2) n[j]=up[j];
i=six[i]-1; n[i]=up[i]-1;
rep(j,i+1,len) n[j]=6;
}else{
n[i]=up[i]-1;
rep(j,i+1,len) n[j]=6;
}
break;
}else{
n[i]=up[i];
}
}
int ans=0;
inc=0;
for(int i=len;i>=1;--i) ans+=(inc=(2*n[i]+inc>=7));
print(ans);
return 0;
}