南外Day15

A&B&C&D&E 全满分

还挺水
E题n^2带log能过

F 40->满分

倍增，记录i开头使用了(j^2)个区间覆盖最大长度
断环为链

for(int i=1;i<=k;i++){
    cin>>a[i].l>>a[i].r;
    if(a[i].l>a[i].r) a[i].r+=n;
}
sort(a+1,a+1+k,cmp);
int jmpr=-1,qd=1;
for(int i=1;i<=n*2;i++){
    while(qd<=k && a[qd].l<=i){jmpr=max(jmpr,a[qd].r);qd++;}
    f[i][0]=jmpr+1;
}
for(int j=1;j<=jmp;j++)
for(int i=1;i<=n*2;i++)
    f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=n;i++){
    int mans=0,id=i;
    for(int j=jmp;j>=0;j--){
        if(f[id][j]<i+n){
            id=f[id][j];
            mans+=(1<<j);
        }
    }
    ans=min(ans,mans+1);
}
if(ans>k) cout<<"impossible\n";
else cout<<ans<<&#039;\n&#039;;

G 40

费用流往上搞
要满分需要线段树优化建图，但是线段树杀我

H 0

6