问题标题: 这个贴废了

qwq，争取至少5days一题

day 1：

P2375动物园

qwq直接暴力kmp会爆TLE50，加了个玄学优化过了qaq

部分代码

long long get_num(){
    long long ans=1;
    int j=0;
    for(int i=1;i<s.size();i++){
        while(j && s[i]!=s[j])
            j=nxt[j];
        if(s[i]==s[j])
            ++j;
        while(j*2>i+1){
            j=nxt[j];
        }
        ans*=(num[j]+1);
        ans%=1000000007;
    }
    return ans;
}

明天我要钻研P1073

还有为啥kdt没有NOI得题

汪宇航在2023-08-06 09:52:28追加了内容

屮，P1073肝了半小时，强连通分量缩点+dfs暴力求解没过样例，调一个小时了，有奆佬帮帮me嘛qwq洛谷谷民都没人回我

qwq

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],idx[100005],cnt,colnum,col[100005],minx[100005],maxx[100005];
vector<int>g[100005];
vector<int>rg[100005];
vector<int>dg[100005];
bool vis[100005];
void dfs(int x){
    vis[x]=true;//标记
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(!vis[v])
            dfs(v);//深搜
    }
    idx[++cnt]=i;//标点
}
void rdfs(int x,int c){//染色
    vis[x]=true;//标记
    col[x]=c;//将x点染色为c
    for(int i=0;i<rg[x].size();i++){
        int v=g[x][i];
        if(!vis[v])
            dfs(v,c);
    }
}
int ddfs(int x,int mix,int mxx){//深搜遍历求解
    if(x==col[idx[n]])//到重点了
        return mxx-mix;
    int ans=0;
    for(int i=0;i<dg[x].size();i++){//取最大
        int v=dg[x][i];
        ans=max(ans,dfs(v,min(mix,minx[v]),max(mxx,maxx[v])));
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,u,v,op;i<=m;i++){//存图
        cin>>u>>v>>op;
        if(op==1){
            g[u].push_back(v);
            g[v].push_back(u);
        }else{
            g[u].push_back(v);
            g[v].push_back(u);
            rg[u].push_back(v);
            rg[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis(i)){
            dfs(i);//若未标记过，则标点
        }
    }
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=cnt;i++){
        if(!rdfs(idx[i])){
            rdfs(idx[i],++colnum);//若未标记过，则给此点染色
        }
    }
    for(int i=1;i<=n;i++){//存缩点后的图
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            if(col[idx[i]]!=col[idx[v]]){
                dg[col[idx[i]]].push_back(col[idx[v]]);
            }
        }
    }
    memset(minx,0x3f,sizeof(minx));
    for(int i=1;i<=n;i++){//取缩的每个点的水晶球价格的最大最小
        minx[col[idx[i]]]=min(minx[col[idx[i]]],a[i]);
        maxx[col[idx[i]]]=max(maxx[col[idx[i]]],a[i]);
    }
    cout<<ddfs(col[idx[1]],minx[col[idx[1]]],maxx[col[idx[1]]]);
    return 0;
}

汪宇航在2023-08-14 09:47:26追加了内容

现在，我洛谷的估值一下子涨了40！

昨晚还是199，一觉起来238！

瞬间红名！

而且，我的比赛情况估值是96分！96哪！

我太高兴了，改送豆

爱怎么水怎么水把