randnameaaa 是魔法师

A 魔法药水

这道题的核心逻辑在于贪心策略：你只需先将所有访客的到访区间按起始时间（左端点）从小到大排序，然后维护一个记录当前药水效果截止时刻的变量，在遍历每个区间时，若当前效果未能完全覆盖该客人的停留时间，就从该客人的进入时刻或上一次效果结束的后一秒（两者取较大值）开始饮药，并利用向上取整的计算方式得出覆盖剩余长度所需的最少药水瓶数，随即更新截止时刻以最大限度地覆盖后续可能出现的重叠或相邻访客，从而确保每一瓶药水都尽可能向后延伸，实现全局消耗最少。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t,n,k;
struct node{
    int l, r;
}a[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i].l>>a[i].r;
        sort(a+1,a+n+1,[&](node a,node b){
            return a.l<b.l;
        });
        int ans=0,cur=-1;//cur为当前药水效果的结束点
        for(int i=1;i<=n;i++){
            if(cur>=a[i].r) continue;
            int res=max(a[i].l,cur+1);//从什么时候开始喝药
            if(res<=a[i].r){
                int need=a[i].r-res+1;
                int num=(need+k-1)/k;//向上取整
                ans+=num;
                cur=res+num*k-1;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

D 魔法树

这是经典的树形dp。定义 dp[u] 为：以 u 为根的子树中，从 u 出发且满足黑白相间条件的路径终点个数（即路径上的节点数）。在遍历树的过程中，当我们从节点 u 递归处理子节点 v 时，如果 u 和 v 的颜色不同，那么以 u 为端点的链与 以 v 为端点的链通过边 (u,v) 连接，会产生 dp[u]×dp[v] 条新的黑白相间路径。同时 dp[u]+=dp[v] 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n,he[N],ne[N<<1],go[N<<1],col[N],tot;
int ans,dp[N];
string s;
inline void add(int a,int b){
    ne[++tot]=he[a];he[a]=tot;go[tot]=b;
}
inline void dfs(int u,int fa){
    dp[u]=1;
    ans=(ans+1)%mod;//单点
    for(int i=he[u];i;i=ne[i]){
        int v=go[i];
        if(v==fa) continue;
        dfs(v,u);
        ans=(ans+dp[u]*dp[v])%mod;
        dp[u]=(dp[u]+dp[v])%mod;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>s;
        ans=tot=0;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='W') col[i]=0;
            else col[i]=1;
            he[i]=dp[i]=0;
        }
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            add(u,v);add(v,u);
        }
        dfs(1,0);
        cout<<ans<<"\n";
    }  
}

I 魔法水管

考虑图论建模。对每一个网格，将其四个流出方向看作点，每个点会与对应流出方向的相邻网格的三个流出方向（除了对着自己的）连边，边权为 如果不需要改变水管，则为0，否则为1。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+5;
typedef pair<int,int> pii;
int t,n,m;
int he[N],ne[N<<1],go[N<<1],val[N<<1],tot;
int dis[N],vis[N];
inline int get(int x,int y){
    return 4*(x*(m+1)+y);
}
inline void add(int a,int b,int c){
    ne[++tot]=he[a];he[a]=tot;go[tot]=b;val[tot]=c;
}
inline void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push({0,s});dis[s]=0;
    while(!q.empty()){
        auto t=q.top();q.pop();
        int u=t.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=he[u];i;i=ne[i]){
            int v=go[i];
            if(dis[v]>dis[u]+val[i]){
                dis[v]=dis[u]+val[i];
                q.push({dis[v],v});
            }
        }
    }
}
signed main()
{
    cin>>t;
    while(t--){
        cin>>n>>m;
        vector<vector<char>>v(n+1,vector<char>(m+1,'#'));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>v[i][j];
        tot=0;
        for(int i=0;i<=6*(n+1)*(m+1)+1;i++) he[i]=vis[i]=0,dis[i]=1e9;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                int p=get(i,j);//get函数找到(i,j)向上流出方向对应的点，+1,+2,+3代表向右，向下，向左
                int u=get(i-1,j);
                int r=get(i,j+1);
                int d=get(i+1,j);
                int l=get(i,j-1);
                int r1=1,r2=1,r3=1;//从左边来的，到自己，从上、右、下三个方向流出
                if(v[i][j]=='D') r1=0;//如果当前水管为D，连通左边和上边，那么从上边流出就不需要更换水管
                if(v[i][j]=='X') r2=0;//如果当前水管为X，连通左边和右边，那么从右边流出就不需要更换水管
                if(v[i][j]=='C') r3=0;//如果当前水管为C，连通左边和下边，那么从下边流出就不需要更换水管
                add(l+1,p,r1);add(l+1,p+1,r2);add(l+1,p+2,r3);//连边
                //下面同理
                r1=1,r2=1,r3=1;
                if(v[i][j]=='A') r1=0;
                if(v[i][j]=='Y') r2=0;
                if(v[i][j]=='D') r3=0;
                add(u+2,p+1,r1);add(u+2,p+2,r2);add(u+2,p+3,r3);
                r1=1,r2=1,r3=1;
                if(v[i][j]=='B') r1=0;
                if(v[i][j]=='X') r2=0;
                if(v[i][j]=='A') r3=0;
                add(r+3,p+2,r1);add(r+3,p+3,r2);add(r+3,p,r3);
                r1=1,r2=1,r3=1;
                if(v[i][j]=='C') r1=0;
                if(v[i][j]=='Y') r2=0;
                if(v[i][j]=='B') r3=0;
                add(d,p+3,r1);add(d,p,r2);add(d,p+1,r3);
            }
        dijkstra(get(1,0)+1);
        cout<<dis[get(n,m)+1]<<endl;
    }
}