降智场…

A. Ela Sorting Books

考虑MEX只和当前连续段的数量最少的元素有关，所以可以减1遍历寻找，不必模拟减够k，因为对结果不产生影响

ll tt,n,k,l,cnt[100];
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
    	cin>>n>>k>>s;
    	fill(cnt,cnt+30,0);
    	l=n/k;
    	vi ans;
    	for(auto it:s)cnt[it-'a']+=1;
    	for(int kk=1;kk<=k;++kk){
    		int st=0;
            while(cnt[st]&&st<l)cnt[st]-=1,st+=1;
            ans.push_back(st);
    	}
        for(auto it:ans)cout<<(char)('a'+it);
        cout<<"\n";
    }
    return 0;
}

B. Ela’s Fitness and the Luxury Number

手写结果发现每个平方根只会产生3个贡献，因为$a*(a+3)\geq (a+1)(a+1)$

所以接下来就是处理端点，我们可以联系数位dp的想法，类似整体解决$0~(l-1)$以及$0~r$，然后结果相减记得答案

ll tt,l,r; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto sqr=[](ll a){
        ll l=1,r=1e9;
        while(l<r){
            ll mid=(l+r+1)>>1;
            if(mid*mid<=a)l=mid;
            else r=mid-1;
        }
        return l;
    };
    cin>>tt;
    f(sb,1,tt){
        cin>>l>>r;
        auto st=sqr(l),en=sqr(r);
        ll ans=0;
        if(en*(en+2)<=r)ans+=3;
        else if(en*(en+1)<=r)ans+=2;
        else ans+=1;
        if(st*(st+2)<l)ans-=3;
        else if(st*(st+1)<l)ans-=2;
        else if(st*st<l)ans-=1;
        ans+=(en-1)*3ll-(st-1)*3ll;
        cout<<ans<<"\n";
    }
    return 0;
}

C. Ela and Crickets

手动模拟几下，发现不能到达的位置和起始空白位置的两坐标之差的绝对值均为偶数

然后就是样例给了个corner case，注意如果三个在棋盘一角，就只能水平或竖直走了

ll r[4],c[4],x,y,n,tt; 
pii dir[4]={{0,0},{1,0},{0,1},{1,1}};
 
bool solve(){
    cin>>n;
    ll mix=0x3f3f3f3f,miy=0x3f3f3f3f;
    f(i,1,3)cin>>r[i]>>c[i],mix=min(mix,r[i]),miy=min(miy,c[i]);
    cin>>x>>y;
    bool ck=true;
    f(i,1,3)if((r[i]!=1&&r[i]!=n)&&(c[i]!=1&&c[i]!=n))ck=false;
    if(ck){
        ll cn1=0,cn2=0;
        f(i,1,3)cn1+=r[i]==x,cn2+=c[i]==y;
        if(cn1>=2||cn2>=2)return true;
        else return false;
    }
 
    for(auto [xx,yy]:dir){
        xx+=mix,yy+=miy;
        bool ok=true;
        f(i,1,3)if(r[i]==xx&&c[i]==yy)ok=false;
        if(ok){
            mix=xx,miy=yy;
            break;
        }
    }
    ll tx=abs(x-mix),ty=abs(y-miy);
    return !(((tx&1)==0)&&((ty&1)==0));
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt)cout<<(solve()?"YES\n":"NO\n");
    return 0;
}
 

D. Ela and the Wiring Wizard

起初想到floyd的思路没错，但是处理要扩展的边不在$1~n$的路径上时失去了想法。

考虑图联通，应当想到枚举中介点来计算这种情况的答案

ll tt,n,m;
 
void solve(){
    cin>>n>>m;
    vector dis(n+1,vector<ll>(n+1,0x3f3f3f3f));
    vector<array<int,3>>g;
    for(int i=1,x,y,w;i<=m;++i){
        cin>>x>>y>>w;
        g.push_back({x,y,w});
        dis[x][y]=dis[y][x]=1;
    }
    for(int i=1;i<=n;++i)dis[i][i]=0;
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    ll ans=1e18;
    for(auto [aa,bb,cc]:g){
        ans=min({ans,(dis[aa][1]+dis[bb][n]+1ll)*cc,(dis[aa][n]+dis[bb][1]+1ll)*cc});
        for(int i=1;i<=n;++i){
            ans=min({ans,(dis[aa][i]+dis[1][i]+dis[n][i]+2ll)*cc,(dis[bb][i]+dis[1][i]+dis[n][i]+2ll)*cc});
        }
    }
    cout<<ans<<"\n";
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt)solve();
    return 0;
}

summary

昨晚属实状态差，欠完成的事：

• 服务器迁移
• 程序设计项目
• 数据结构实验报告
• 补ec H和csp T5（朋友圈看到强风吹拂想起）