11.18虐心赛

已经不知道这篇博客写给谁看的了。

T1 bracket

Sol
维护一个栈，计算每个位置被统计了多少次就是一个乘法原理，然后直接差分即可。
Code

#include
using namespace std;
#define int long long
namespace io
{}
using namespace io;
const int maxn=10000010,p=1000000007;
int st[maxn],head;
int lst[maxn],siz[maxn];
char s[maxn];
int pls[maxn];
bool ise[maxn];
char tp[2]={')','('};
signed main()
{
    freopen("bracket.in","r",stdin);
    freopen("bracket.out","w",stdout);
    scanf("%s",s+1);
    int l=strlen(s+1);
    for(int i=1;i<=l;i++)
    {
        if(s[i]=='(')st[++head]=i;
        if(s[i]==')'&&head)
        {
            lst[i]=st[head--];
            ise[i]=1;ise[lst[i]-1]=0;
            siz[i]=siz[lst[i]-1]+1;
        }
    }
    for(int i=l;i;i--)
    {
        if(ise[i])
        {
            for(int now=i,cnt=1;lst[now];now=lst[now]-1,cnt++)
            {
                pls[lst[now]]+=cnt*(siz[i]-cnt+1)%p;
                pls[now+1]-=cnt*(siz[i]-cnt+1)%p;
                if(pls[lst[now]]>=p)pls[lst[now]]-=p;
                if(pls[now+1]<=0)pls[now+1]+=p;
            }
        }
    }
    int ans=0,now=0;
    for(int i=1;i<=l;i++)
    {
        now+=pls[i];
        if(now>=p)now-=p;
        ans+=now*i%p;
    }
    put(ans);
    return 0;
}

T3 matrix

Sol
设\(f_{i,j}\)表示考虑到第i行，这行选第j个的选择方案数。显然\(f_{i,j}=\sum_{l=j-k}^{j+k}f_{i-1,l}\)。
但是有很多重复的地方。设\(g_{i,j}\)表示\(f_{i,j}\)和\(f_{i,j+1}\)方案中重复的部分。
如果\(s_{i,j}\ne s_{i,j+1}\)，那么显然不相同。
相同的时候有

\[g_{i,j}=\sum_{l=j-k}^{j+k-1}f_{i-1,l}-\sum_{l=j-k+1}^{j+k-1}g_{i-1,l}\\ f_{i,j}=\sum_{l=j-k}^{j+k}f_{i-1,l}-\sum_{l=j-k+1}^{j+k}g_{i-1,l} \]

注意到很大一部分式子内容都是相同区间和，所以考虑前缀和优化掉一维，复杂度降为\(\mathcal{O}(n^2)\)。
Code（贺码史诗）

#include
using namespace std;
namespace io
{}
using namespace io;
#define int long long
const int maxn=3010,p=1000000007;
int n,m,k;
int f[maxn][maxn],g[maxn][maxn],sum[maxn][maxn];
char s[maxn][maxn];//sum表示f-g前缀和 
signed main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=m;i++)f[n+1][i]=g[n+1][i]=1;
    for(int i=n;i;i--)
    {
        for(int j=1;j<=m;j++)//计算f 
        {
            int l=max(j-k,1ll),r=min(j+k,m);
            f[i][j]=(sum[i+1][r-1]-sum[i+1][l-1]+p)%p;
            f[i][j]+=f[i+1][r];
            if(f[i][j]>=p)f[i][j]-=p;
        }
        for(int j=1;j=p)g[i][j]-=p;
        }
        for(int j=1;j<=m;j++)sum[i][j]=(sum[i][j-1]+f[i][j]-g[i][j]+p)%p;//计算sum 
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans=(ans+f[1][i]-g[1][i]+p)%p;
    put(ans);
    return 0;
}

T4 path

Sol
正解是启发式合并，然而我不会。
70分的烂分如何恰满：50+20。
前50分的暴力有一万种做法。各种神仙的解法我完全不懂。我用的是简单的分层图。
求第二长的最小值，就是让最大的那条边免费，那就很容易想到分层图了。把dijkstra的距离和改成距离最大值即可。时间复杂度\(\mathcal{O}(q\,n\log n)\)。
剩下20分长一点不过思维难度很简单了：直接树上倍增求LCA维护最大次大即可。
拼起来4kb。
Code

#include
using namespace std;
namespace io
{}
using namespace io;
int n,m,q;
namespace sub1
{
    const int maxn=2010,maxm=4010;
    struct edge
    {
        int to,next,v;
    }e[maxm<<2];
    int h[maxn],ei;
    inline void add(int x,int y,int v)
    {
        e[++ei]=(edge){y,h[x],v};
        h[x]=ei;return;
    }
    struct node
    {
        int id,v;
        bool operator<(const node &x)const
        {
            return v>x.v;
        }
    };
    priority_queuequ;
    bool vis[maxn];
    int dis[maxn];
    inline void dijkstra(int s,int t)
    {
        memset(dis,0x3f,sizeof(dis));
        dis[s]=0;
        qu.push((node){s,0});
        while(!qu.empty())
        {
            int x=qu.top().id;qu.pop();
            vis[x]=0;
            for(int i=h[x];i;i=e[i].next)
            {
                int to=e[i].to,v=e[i].v;
                if(dis[to]>max(dis[x],v))
                {
                    dis[to]=max(dis[x],v);
                    if(!vis[to])
                    {
                        vis[to]=1;
                        qu.push((node){to,dis[to]});
                    }
                }
            }
        }
        put(dis[t+n]<=1e9?dis[t+n]:-1);
        return;
    }
    inline void work()
    {
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),z=read();
            add(x,y,z);add(y,x,z);
            add(x,y+n,0);add(y,x+n,0);
            add(x+n,y+n,z);add(y+n,x+n,z);
        }
        while(q--)
        {
            int x=read(),y=read();
            dijkstra(x,y);
        }
    }
}
namespace sub2
{
    const int maxn=200010;
    struct edge
    {
        int to,next,v;
    }e[maxn<<1];
    int h[maxn],ei;
    inline void add(int x,int y,int v)
    {
        e[++ei]=(edge){y,h[x],v};
        h[x]=ei;return;
    }
    int dep[maxn],fa[maxn][20],mx[maxn][20],mx2[maxn][20];
    inline void dfs(int x,int f)
    {
        for(int i=h[x];i;i=e[i].next)
        {
            int to=e[i].to;
            if(to==f)continue;
            dep[to]=dep[x]+1;
            fa[to][0]=x;mx[to][0]=e[i].v;
            for(int j=1;j<=18;j++)
            {
                fa[to][j]=fa[fa[to][j-1]][j-1];
                int a=mx[to][j-1],b=mx2[to][j-1],c=mx[fa[to][j-1]][j-1],d=mx2[fa[to][j-1]][j-1];
                if(a>c)
                {
                    mx[to][j]=a;
                    mx2[to][j]=b>c?b:c;
                }else
                {
                    mx[to][j]=c;
                    mx2[to][j]=a>d?a:d;
                }
            }
            dfs(to,x);
        }
        return;
    }
    inline int LCA(int x,int y)
    {
        if(dep[x]=dep[y])
            {
                if(mx[x][j]>an)
                {
                    as=max(an,mx2[x][j]);
                    an=mx[x][j];
                }else as=max(as,mx[x][j]);
                x=fa[x][j];
            }
        }
        if(x==y)return as;
        for(int j=18;~j;j--)
        {
            if(fa[x][j]!=fa[y][j])
            {
                if(mx[x][j]>an)
                {
                    as=max(an,mx2[x][j]);
                    an=mx[x][j];
                }else as=max(as,mx[x][j]);
                x=fa[x][j];
                if(mx[y][j]>an)
                {
                    as=max(an,mx2[y][j]);
                    an=mx[y][j];
                }else as=max(as,mx[y][j]);
                y=fa[y][j];
            }
        }
        if(mx[x][0]>an)
        {
            as=max(an,mx2[x][0]);
            an=mx[x][0];
        }else as=max(as,mx[x][0]);
        if(mx[y][0]>an)
        {
            as=max(an,mx2[y][0]);
            an=mx[y][0];
        }else as=max(as,mx[y][0]);
        return as;
    }
    inline void work()
    {
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),z=read();
            add(x,y,z);add(y,x,z);
        }
        dfs(1,0);
        while(q--)
        {
            int x=read(),y=read();
            put(LCA(x,y));
        }
        return;
    }
}
int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    n=read();m=read();q=read();
    if(n<=1000&&q<=1000&&m<=2000)
    {
        using namespace sub1;
        work();
        return 0;
    }
    if(m!=n-1)return puts("QAQ")&0;
    using namespace sub2;
    work();
    return 0;
}

退役前最后一次总结了罢。。。