第七维度2020初赛题解


出题人:A星际穿越
验题人:TMXK2020
只有我一个出题人(被迫营业),所以对题目感到不满意的同学轻喷>﹏<
(其实我就是群里那个工作人员QAQ)

A

本来不想讲的,但是。。。
题目数据范围标错是我的问题[呜呜呜]
很多人写程序会输出一些类似于"Please input two integers"之类的提示语,这里要注意,算法竞赛中是严禁在题目没让你输出这些东西的情况下输出提示语的。题目让你输出一行一个整数,你就只能输出一行一个整数,不能输出其他东西了
输入也是类似,正常情况下,若题目无特殊说明,默认输入的两个相邻数据用空格分隔
给出标程
C:

#include<stdio.h>
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    printf("%d",a+b);
    return 0;
}

C++:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

B

手算,不讲
唯一要注意的是不要把竖式的横和撇也输出
答案是9709/12

C

其实就是洛谷P1008三连击
枚举这个1到9的排列,然后分成三段,每段组成1个数字,判断这三个数字是否成1:2:3的比例即可
或者也可以枚举第一个数,然后判断它的2倍、3倍是否符合题意
(从洛谷上扒拉下来的标程)
C:

#include <stdio.h>
int main()
{
    int a,b,c;
    for(a=123;a<=333;a++)
            {
                b=a*2;
                c=a*3;
                if((a/100+a/10%10+a%10+b/100+b/10%10+b%10+c/100+c/10%10+c%10==1+2+3+4+5+6+7+8+9)&&((a/100)*(a/10%10)*(a%10)*(b/100)*(b/10%10)*(b%10)*(c/100)*(c/10%10)*(c%10)==(1)*(2)*(3)*(4)*(5)*(6)*(7)*(8)*(9)))
                    printf("%d %d %d\n",a,b,c);
            }
    return 0;
}

C++:
代码和C类似,不放了

D

仔细看过那篇赛前指导的同学就应该知道这题怎么做了
什么?没看过不知道?那你赶紧回去看[滑稽]
直接给代码(从这题开始不提供c的代码,因为我懒得打C代码了)

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
#define N 1010
#define mod 19260817
//请无视这么多宏
int n,m,q,x,y;
int a[N][N],f[N][N];
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n){putchar('0');return 0;}
    if(n<0){putchar('-');write(-n);}else if(n>=10)write(n/10);
    putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
int main(){
    read(n),read(m),read(q);
    fui(i,1,q,1){
        read(x),read(y);
        a[x][y]=1;
    }
    f[1][1]=1;
    fui(i,1,n,1)fui(j,1,m,1)if(i!=1||j!=1)
        f[i][j]=(a[i][j]?0:f[i-1][j]+f[i][j-1])%mod;
    writeln(f[n][m]);
    return 0;
}

E

这道题是一道图论题,那就需要先简单讲讲图论
在图论中,一张图由若干个点和若干条边组成,每条边连接两个点。通常用V表示点集,E表示边集。一条路径表示从一个点到另一个点的这条路上所有点和边的总集合。根据题目的不同,点可能会有点权,边可能会有边权。在这道题中,每条路的时间就是边权,总时间就是这条路径上的所有边的边权之和。
要想做图论题,就要先把图存下来。在点比较少的时候,可以采用一种叫做邻接矩阵的东西存储图
邻接矩阵的每一个元素a[i][j]表示从点i到点j的边的边权,若为INF(意为无穷大)则表示从点i到点j没有边。特殊的,a[i][i]=INF
把图存下来了,接下来就要开始写算法写程序了

30分做法

dfs,从s开始搜索,一直到t

60分做法

每次询问都用一次bfs,从s开始搜索,每次取出队列中用时最小的点,从这个点开始搜索所有与他相连的且从他这里走用时更小的点,一直到搜索到t,那么此时t的用时就是最短用时
时间复杂度

或者对于有算法竞赛基础的同学可以用堆优化(Dijkstra),时间复杂度

100分做法

经典Floyd算法,复杂度

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
#define N 1010
#define mod 1000000007
int n,m,q;
ll a[N][N];
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n){putchar('0');return 0;}
    if(n<0){putchar('-');write(-n);}else if(n>=10)write(n/10);
    putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
int main(){
    read(n),read(m);
    fui(i,1,n,1)fui(j,1,n,1)a[i][j]=INF;
    fui(i,1,n,1)a[i][i]=0;
    fui(i,1,m,1){
        int x,y,t;read(x),read(y),read(t);
        a[x][y]=a[y][x]=t;
    }
    fui(k,1,n,1)fui(i,1,n,1)fui(j,1,n,1)
        a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    fui(i,1,n,1)fui(j,1,n,1)a[i][j]%=mod;
    read(q);
    fui(i,1,q,1){
        int s,t;
        read(s),read(t);
        writeln(a[s][t]);
    }
    return 0;
}

F

这道题可能对没学过高数的同学不太友好。。。

40分做法

按照行列式的定义,枚举所有1到n的排列进行计算
复杂度

用其他方法可以优化至

100分做法

高斯消元,利用行列式的初等变换,将行列式转化为上三角或者下三角或者对角线,复杂度

可能要简单讲一下模意义下的乘法逆元
如果

(表示a*b对p取模结果为1),则称b为a在模p意义下的乘法逆元(简称逆元),可以记为

而因为p是质数,所以求逆元可以用费马小定理

也就是说



至于求这个幂

可以用快速幂

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
#define Mod 19260817
#define N 110
int n;
ll a[N][N];
ll dv=1,ans;
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n)return 0*putchar('0');
    if(n<0){putchar('-');write(-n);return n;}
    if(n>=10)write(n/10);
    putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
ll mod(ll x){return (x%Mod+Mod)%Mod;}
ll power(ll x,ll y){
    ll an=1;
    while(y){
        if(y&1)an=mod(an*x);
        x=mod(x*x),y>>=1;
    }
    return an;
}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void swap_r(int x,int y){fui(i,1,n,1)swap(a[x][i],a[y][i]);}
void swap_l(int x,int y){fui(i,1,n,1)swap(a[i][x],a[i][y]);}
void deal(int now){
    if(now==n){
        ans=1;
        fui(i,1,n,1)ans=mod(ans*a[i][i]);
        ans=mod(ans*power(dv,Mod-2));
        return;
    }
    if(!a[now][now]){
        char flag=1;
            fui(i,1,n,1)if(a[i][now]){
            swap_r(now,i);
            dv=mod(-dv);
            flag=0;
            break;
        }
        if(flag)return;
    }
    ll g,gg,ggg;
    fui(i,1,n,1)if(i!=now){
        g=gcd(a[now][now],a[i][now]);
        gg=a[now][now]/g;ggg=a[i][now]/g;
        dv=mod(gg*dv);
        fui(j,1,n,1)a[i][j]=mod(a[i][j]*gg-a[now][j]*ggg);
    }
    deal(now+1);
}
int main(){
    read(n);
    fui(i,1,n,1)fui(j,1,n,1)read(a[i][j]);
    fui(i,1,n,1)fui(j,1,n,1)a[i][j]=mod(a[i][j]);
    deal(1);
    writeln(ans);
    return 0;
}

G

有算法竞赛经历的同学应该会发现,这道题目是从一本算法竞赛书上搬过来的。。。

40分做法

枚举每一个点是否要翻转,判断每一种方案是否可行,若存在可行方案则输出1,否则输出0
复杂度

100分做法

注意到剩下两部分数据中m都很小,所以就要以m为突破口
考虑前i行已经被翻转,我们发现如果确定了第i行的结果,那么第i+1行的翻转方案也就被唯一确定了
因此我们只枚举第一行的翻转方案,然后依次考虑每一行的方案,若存在某个方案使得棋盘全部为0,那么输出1;否则若没有方案能让棋盘全部是0,则输出0
复杂度

//出题人的代码有点丑,所以放了验题人的代码
#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
int n,m,T;
bool a[2000][20],b[2000][20];
bool ans;
void dd(int x,int y)
{
    if (x>1)
        b[x-1][y]=!b[x-1][y];
    if (y>1)
        b[x][y-1]=!b[x][y-1];
    b[x][y]=!b[x][y];
    if (y<m)
        b[x][y+1]=!b[x][y+1];
    if (x<n)
        b[x+1][y]=!b[x+1][y];
}
bool check()
{
    for (int i=2; i <= n; i++)
        for (int j=1; j <= m; j++)
            if (b[i-1][j])
                dd(i,j);
    for (int i=1; i <= m; i++)
        if (b[n][i])
            return 0;
    return 1;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        for (int i=1; i <= n; i++)
            for (int j=1;j <= m; j++)
                cin >> a[i][j];
        int X=(1<<m)-1;
        for (int i=0;i <= X; i++)
        {
            for (int x=1; x <= n; x++)
                for (int y=1; y <= m; y++)
                    b[x][y]=a[x][y];
            for (int j=0; j < m; j++)
                if (i&(1<<j))
                    dd(1,j+1);
            if (check())
            {
                ans=1;
                break;
            }
        }
        if (ans)
                printf("1\n");
            else
                printf("0\n");
    } 
    return 0;
}

H

首先先抱怨一下,本来这道题目是树的直径模板题,没这么难的,但是。。。我去参加了ACM协会的那个比赛,所以。。。我就把这道题目给改了

50分做法

邻接矩阵存图,每次炸毁一条路就是删一条边,每次询问就暴力dfs
复杂度

100分做法

注意到在一棵树上,任意一点出发的最长路径,终点必然是这棵树的直径两个端点之一;而如果连接两棵树,那么新的树的直径端点一定在原来两棵树两条直径的四个端点中产生。而这道题目没有增加边的操作也不强制在线,所以大方向确定下来了,就是倒序处理操作动态加边,用并查集维护树的直径
剩下的就是求树上两点的距离了。这里我采用的方法是LCT,复杂度为

#include<bits/stdc++.h>
using namespace std;
#define fui(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define fdi(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define INF 0x7fffffff
#define MEM(a,b) memset(a,b,sizeof(a))
#define lowbit(i) ((i)&(-(i)))
#define ll long long
#define N 10010
#define Q 100010
int n,x,q;
int que[Q],cnt;
int f[N],pnt[N][2];
int qst[Q][3],a[N],answer[Q],ant;
int edg[N][2],cut[N][2],ent,cct;
int srt[N][2];
struct Node{
    int f,son[2];
    int lgh,wgh;
    char siz;
}tree[N];
void update(int x){
    if(tree[x].siz){
        swap(tree[x].son[0],tree[x].son[1]);
        tree[x].siz=0;tree[tree[x].son[0]].siz^=1;tree[tree[x].son[1]].siz^=1;
    }
    tree[x].lgh=tree[tree[x].son[0]].lgh+tree[tree[x].son[1]].lgh+tree[x].wgh;
}
char which(int x){return x==tree[tree[x].f].son[1];}
char isroot(int x){return x!=tree[tree[x].f].son[which(x)];}
void rotate(int x){
    int t=which(x),ff=tree[x].f;
    if(!isroot(ff))tree[tree[ff].f].son[which(ff)]=x;
    tree[ff].son[t]=tree[x].son[t^1];tree[tree[x].son[t^1]].f=ff;
    tree[x].son[t^1]=ff;tree[x].f=tree[ff].f;tree[ff].f=x;
    update(ff);update(x);
}
void splay(int x){
    que[cnt=1]=x;int p;
    for(p=x;!isroot(p);p=tree[p].f)que[++cnt]=tree[p].f;
    fdi(i,cnt,1,1)update(que[i]);
    int fa;
    for(fa=tree[x].f;!isroot(x);fa=tree[x].f){
        if(!isroot(fa))(which(x)^which(fa))?rotate(x):rotate(fa);
        rotate(x);
    }
}
void access(int x){
    splay(x);tree[x].son[1]=0;update(x);
    while(tree[x].f){
        splay(tree[x].f);
        tree[tree[x].f].son[1]=x;
        update(tree[x].f);
        splay(x);
    }
}
void makeroot(int x){access(x);tree[x].siz=1;update(x);}
void link(int x,int y){makeroot(x);access(y);tree[x].f=y;}
int find(int x){return (f[x]==x)?x:(f[x]=find(f[x]));}
template<class T> T read(T &n){
    int t=1;double f=10;char ch;n=0;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    (ch=='-')?(t=-1):(n=ch-48);for(ch=getchar();isdigit(ch);ch=getchar())n=n*10+ch-48;
    if(ch=='.')for(ch=getchar();isdigit(ch);ch=getchar())n+=((ch-48)/f),f*=10;return (n*=t);
}template<class T> T write(T n){
    if(!n)return 0*putchar('0');
    if(n<0){putchar('-');write(-n);}else if(n>=10)write(n/10);
    putchar(n%10+48);n/=10;return n;
}template<class T> T writeln(T n){write(n);puts("");return n;}
int value(int x,int y){makeroot(x);access(y);return tree[y].lgh;}
int query(int x){return max(value(x,pnt[find(x)][0]),value(x,pnt[find(x)][1]));}
void merge(int x,int y){
    int dix[3],diy[3],dis[6],i,mx=0,my;
    dix[0]=value(x,pnt[find(x)][0]);
    dix[1]=value(x,pnt[find(x)][1]);
    dix[2]=value(pnt[find(x)][0],pnt[find(x)][1]);
    diy[0]=value(y,pnt[find(y)][0]);
    diy[1]=value(y,pnt[find(y)][1]);
    diy[2]=value(pnt[find(y)][0],pnt[find(y)][1]);
    dis[0]=dix[0]+diy[0];dis[1]=dix[0]+diy[1];
    dis[2]=dix[1]+diy[0];dis[3]=dix[1]+diy[1];
    dis[4]=dix[2];dis[5]=diy[2];
    for(i=0;i<6;i++)if(dis[i]>dis[mx])mx=i;
    switch(mx){
        case 0:mx=pnt[find(x)][0],my=pnt[find(y)][0];break;
        case 1:mx=pnt[find(x)][0],my=pnt[find(y)][1];break;
        case 2:mx=pnt[find(x)][1],my=pnt[find(y)][0];break;
        case 3:mx=pnt[find(x)][1],my=pnt[find(y)][1];break;
        case 4:mx=pnt[find(x)][0],my=pnt[find(x)][1];break;
        case 5:mx=pnt[find(y)][0],my=pnt[find(y)][1];
    }
    f[find(x)]=find(y);
    pnt[find(y)][0]=mx,pnt[find(y)][1]=my;
    link(x,y);
}
void sort1(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    sort1(l,mid);sort1(mid+1,r);
    int p1=l,p2=mid+1,p3=l;
    while(p1<=mid&&p2<=r){
        if(edg[p1][0]!=edg[p2][0]){
            if(edg[p1][0]<edg[p2][0])srt[p3][0]=edg[p1][0],srt[p3++][1]=edg[p1++][1];
            else srt[p3][0]=edg[p2][0],srt[p3++][1]=edg[p2++][1];
        }
        else if(edg[p1][1]<edg[p2][1])srt[p3][0]=edg[p1][0],srt[p3++][1]=edg[p1++][1];
        else srt[p3][0]=edg[p2][0],srt[p3++][1]=edg[p2++][1];
    }
    while(p1<=mid)srt[p3][0]=edg[p1][0],srt[p3++][1]=edg[p1++][1];
    while(p2<=r)srt[p3][0]=edg[p2][0],srt[p3++][1]=edg[p2++][1];
    fui(i,l,r,1)edg[i][0]=srt[i][0],edg[i][1]=srt[i][1];
}
void sort2(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    sort2(l,mid);sort2(mid+1,r);
    int p1=l,p2=mid+1,p3=l;
    while(p1<=mid&&p2<=r){
        if(cut[p1][0]!=cut[p2][0]){
            if(cut[p1][0]<cut[p2][0])srt[p3][0]=cut[p1][0],srt[p3++][1]=cut[p1++][1];
            else srt[p3][0]=cut[p2][0],srt[p3++][1]=cut[p2++][1];
        }
        else if(cut[p1][1]<cut[p2][1])srt[p3][0]=cut[p1][0],srt[p3++][1]=cut[p1++][1];
        else srt[p3][0]=cut[p2][0],srt[p3++][1]=cut[p2++][1];
    }
    while(p1<=mid)srt[p3][0]=cut[p1][0],srt[p3++][1]=cut[p1++][1];
    while(p2<=r)srt[p3][0]=cut[p2][0],srt[p3++][1]=cut[p2++][1];
    fui(i,l,r,1)cut[i][0]=srt[i][0],cut[i][1]=srt[i][1];
}
void init(){
    int p1=1,p2=1;
    while(p1<=ent&&p2<=cct){
        if(edg[p1][0]!=cut[p2][0]||edg[p1][1]!=cut[p2][1])merge(edg[p1][0],edg[p1][1]),p1++;
        else p1++,p2++;
    }
    while(p1<=ent)merge(edg[p1][0],edg[p1][1]),p1++;
}
int main(){
    read(n);
    fui(i,1,n,1){
        read(a[i]),f[i]=i,pnt[i][0]=pnt[i][1]=i;
        tree[i].wgh=tree[i].lgh=a[i];
    }
    fui(i,1,n-1,1){
        read(edg[++ent][0]),read(edg[ent][1]);
        if(edg[ent][0]>edg[ent][1])swap(edg[ent][0],edg[ent][1]);
    }
    read(q);
    fui(i,1,q,1){
        read(qst[i][0]),read(qst[i][1]);
        if(!qst[i][0]){
            read(qst[i][2]);
            cut[++cct][0]=min(qst[i][1],qst[i][2]);
            cut[cct][1]=max(qst[i][1],qst[i][2]);
        }
    }
    sort1(1,n-1);sort2(1,cct);
    init();
    fdi(i,q,1,1){
        if(qst[i][0])answer[++ant]=query(qst[i][1]);
        else merge(qst[i][1],qst[i][2]);
    }
    fdi(i,ant,1,1)writeln(answer[i]);
    return 0;
}

当然,处理树上距离不一定要用LCT,整道题也不一定要倒序处理。这里我把其他AC了这道题的选手的代码也放上来,供大家参考不同的方法

//by 20339070
#include<bits/stdc++.h>
#define add(u,v) to[++top]=head[u],head[u]=top,w[top]=v
#define For(x) for(int h=head[x],o=w[h];h;o=w[h=to[h]])
#define N 10050
using namespace std;
int top=0,head[N<<1],w[N<<1],to[N<<1];
int f[N],a[N],fi[N],se[N],bf[N];
int u,v,x,n,opt,q;
inline void dfs(int x,int fa){
    f[x]=a[x];
    fi[x]=se[x]=bf[x]=0;
    For(x) if (o && o!=fa){
        dfs(o,x);
        f[x]=max(f[x],a[x]+f[o]);
        if (f[o]>se[x] && f[o]<fi[x]) se[x]=f[o];
        if (f[o]>=fi[x]) se[x]=fi[x],fi[x]=f[o];
    }
}
inline void dfs2(int x,int fa){
    int tmp=bf[x];
    if (tmp>se[x] && tmp<fi[x]) se[x]=tmp;
    if (tmp>=fi[x]) se[x]=fi[x],fi[x]=tmp;
    For(x) if (o && o!=fa){
        if (f[o]==fi[x]) bf[o]=a[x]+se[x];
        else bf[o]=a[x]+fi[x];
        dfs2(o,x);
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    scanf("%d",&q),dfs(1,0),dfs2(1,0);
    while (q--){
        scanf("%d",&opt);
        if (opt==0){
            scanf("%d%d",&u,&v);
            For(u) if (o==v) w[h]=0;
            For(v) if (o==u) w[h]=0;
            dfs(u,0),dfs2(u,0);
            dfs(v,0),dfs2(v,0);
        }
        if (opt==1){
            scanf("%d",&x);
            printf("%d\n",max(bf[x]+a[x],f[x]));
        }
    }
}
//by 20319057
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int N=100005;
int a[N];
int n,m;
vector<int> vec[N];
int fa[N][21];
struct qq
{
    int x,y,last;
}e[N*2];int num,last[N];
void init (int x,int y)
{
    e[++num].x=x;e[num].y=y;
    e[num].last=last[x];last[x]=num;
}
int dep[N],d[N];
void dfs (int x,int ff)
{
//  printf("%d %d\n",x,ff);
    fa[x][0]=ff;
    for (int u=1;u<=20;u++) fa[x][u]=fa[ff][u-1];
    dep[x]=dep[fa[x][0]]+a[x];
    d[x]=d[ff]+1;
    for (int u=last[x];u!=-1;u=e[u].last)
    {
        int y=e[u].y;
        if (y==ff) continue;
        dfs(y,x);
    }
}
int get_lca(int x,int y)
{
    if (d[x]<d[y]) swap(x,y);
//  printf("%d %d %d %d\n",x,y,d[x],d[y]);
    for (int u=20;u>=0;u--)
    if (d[fa[x][u]]>=d[y])
    x=fa[x][u];
//  printf("%d %d\n",x,y);
    if (x==y) return x;
    for (int u=20;u>=0;u--)
    if (fa[x][u]!=fa[y][u])
    {x=fa[x][u];y=fa[y][u];}
    return fa[x][0];
}
map<pair<int,int>,int> mp;
int X[N],Y[N];
struct qt
{
    int op;
    int x,y;
}h[N];
int ff[N];
int p[N][2];
int find_fa (int x) {return ff[x]==x?x:ff[x]=find_fa(ff[x]);}
int get (int x,int y)
{
    int xx=get_lca(x,y);
/*  printf("%d %d %d %d\n",x,y,xx,dep[x]+dep[y]-2*dep[xx]+a[xx]);
    system("pause");*/
    return dep[x]+dep[y]-2*dep[xx]+a[xx];
}
void Merge (int x,int y)
{
//  printf("x:%d y:%d\n",x,y);
    x=find_fa(x);y=find_fa(y);
    ff[x]=y;
    int x1=p[x][0],x2=p[x][1],x3=p[y][0],x4=p[y][1];
    int mx=-1,xx,yy;
    if (get(x1,x2)>mx) {mx=get(x1,x2);xx=x1;yy=x2;}
    if (get(x1,x3)>mx) {mx=get(x1,x3);xx=x1;yy=x3;}
    if (get(x1,x4)>mx) {mx=get(x1,x4);xx=x1;yy=x4;}
    if (get(x2,x3)>mx) {mx=get(x2,x3);xx=x2;yy=x3;}
    if (get(x2,x4)>mx) {mx=get(x2,x4);xx=x2;yy=x4;}
    if (get(x3,x4)>mx) {mx=get(x3,x4);xx=x3;yy=x4;}
    p[y][0]=xx;p[y][1]=yy;
}
int query (int x)
{
    int xx=find_fa(x);
//  printf("%d %d %d\n",x,p[xx][0],p[xx][1]);
    return max(get(x,p[xx][0]),get(x,p[xx][1]));
}
int main()
{
    num=0;memset(last,-1,sizeof(last));
    scanf("%d",&n);
    for (int u=1;u<=n;u++) scanf("%d",&a[u]);
    for (int u=1;u<n;u++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        init(x,y);init(y,x);
        if (x>y) swap(x,y);
        X[u]=x;Y[u]=y;mp[make_pair(x,y)]=1;
    }
    dep[0]=0;d[0]=0;dfs(1,0);
    //printf("%d\n",get(1,2));
    scanf("%d",&m);
    for (int u=1;u<=m;u++)
    {
        scanf("%d",&h[u].op);
        if (h[u].op==1) scanf("%d",&h[u].x);
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (x>y) swap(x,y);
            mp[make_pair(x,y)]=0;
            h[u].x=x;h[u].y=y;
        }
    }
    for (int u=1;u<=n;u++) 
    {
        ff[u]=u;
        p[u][0]=u;p[u][1]=u;
    }
    for (int u=1;u<n;u++)
    {
        if (mp[make_pair(X[u],Y[u])]==1) Merge(X[u],Y[u]);
    }
    for (int u=m;u>=1;u--)
    {
        if (h[u].op==0) Merge(h[u].x,h[u].y);
        else
        {
            h[u].y=query(h[u].x);
            //printf("%d\n",query(h[u].x));
        }
    //  system("pause");
    }
    for (int u=1;u<=m;u++)   if (h[u].op==1) printf("%d\n",h[u].y);
    return 0;
}
//by 20342022
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
 
const int maxn=1e4+7;
 
using namespace std;
 
int n,m,x,y;
int a[maxn],dis[maxn],dep[maxn],f[maxn][15];
int p[maxn],l[maxn],r[maxn];
 
vector <int> g[maxn];
 
struct rec{
    int op,x,y;
}q[maxn*10];
 
struct edge{
    int x,y;
};
 
bool operator <(edge a,edge b)
{
    if (a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
 
set <edge> s;
set <edge> ::iterator it;
 
void dfs(int x,int fa)
{
    f[x][0]=fa;
    dis[x]=dis[fa]+a[x];
    dep[x]=dep[fa]+1;
    for (int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if (y==fa) continue;
        dfs(y,x);
    }
}
 
int lca(int x,int y)
{
    if (dep[x]>dep[y]) swap(x,y);
    int d=dep[y]-dep[x],k=14,t=1<<k;
    while (d)
    {
        if (d>=t) y=f[y][k],d-=t;
        t/=2; k--;
    }
    if (x==y) return x;
    k=14;
    while (k>=0)
    {
        if (f[x][k]!=f[y][k])
        {
            x=f[x][k];
            y=f[y][k];
        }
        k--;
    }
    return f[x][0];
}
 
int getdis(int x,int y)
{
    int p=lca(x,y);
    return dis[x]-dis[p]+dis[y]-dis[p]+a[p];
}
 
int find(int x)
{
    if (!p[x]) return x;
    return p[x]=find(p[x]);
}
  
void uni(int x,int y)
{
    int u=find(x),v=find(y);
    if (u==v) return;
    p[u]=v;
    int ax,ay,d=0,len;
    len=getdis(l[u],r[u]);
    if (len>d)
    {
        d=len;
        ax=l[u];
        ay=r[u];
    }
    len=getdis(l[v],r[v]);
    if (len>d)
    {
        d=len;
        ax=l[v];
        ay=r[v];
    }
    len=getdis(l[u],r[v]);
    if (len>d)
    {
        d=len;
        ax=l[u];
        ay=r[v];
    }
    len=getdis(l[v],r[u]);
    if (len>d)
    {
        d=len;
        ax=l[v];
        ay=r[u];
    }
    len=getdis(l[u],l[v]);
    if (len>d)
    {
        d=len;
        ax=l[u];
        ay=l[v];
    }
    len=getdis(r[u],r[v]);
    if (len>d)
    {
        d=len;
        ax=r[u];
        ay=r[v];
    }
    l[v]=ax,r[v]=ay;
}
 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
        if (x>y) swap(x,y);
        s.insert((edge){x,y});
    }
    dfs(1,0);
    for (int j=1;j<15;j++)
    {
        for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&q[i].op);
        if (!q[i].op)
        {
            scanf("%d%d",&x,&y);
            if (x>y) swap(x,y);
            it=s.lower_bound((edge){x,y});
            s.erase(it);
            q[i].x=x,q[i].y=y;
        }
        else scanf("%d",&q[i].x);
    }
    for (int i=1;i<=n;i++) l[i]=i,r[i]=i;
     
    it=s.begin();
    while (it!=s.end())
    {
        edge d=*it;
        uni(d.x,d.y);
        it++;
    }
     
    for (int i=m;i>0;i--)
    {
        if (q[i].op==0) uni(q[i].x,q[i].y);
        else
        {
            int p=find(q[i].x);
            q[i].y=max(getdis(q[i].x,l[p]),getdis(q[i].x,r[p]));
        }
    }
    for (int i=1;i<=m;i++)
    {
        if (q[i].op==1) printf("%d\n",q[i].y);
    }
}
//by 19340036
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define N 100110
 
struct note
{
    int y,next,s;
};
 
struct note2
{
    int s,x,y;
};
 
note2 re[N*10];
note side[N*2];
int f[N],last[N],v[N],t[N],s[N];
int n,q,l=1,se;
 
void add(int x,int y)
{
    l++;
    side[l].y=y;
    side[l].next=last[x];
    last[x]=l;
    side[l].s=1;
}
 
void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    int y,z;
    memset(last,0,sizeof(last));
    for (int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&y,&z);
        add(y,z);
        add(z,y);
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
    {
        scanf("%d",&re[i].s);
        if (re[i].s==0)
        { 
            scanf("%d%d",&re[i].x,&re[i].y);
            for (int j=last[re[i].x];j!=0;j=side[j].next)
                if (side[j].y==re[i].y)
                {
                    side[j].s=0;
                    side[j^1].s=0;
                }
        }
        else
            scanf("%d",&re[i].x);
    }
}
 
void dfs1(int x,int fl)
{
    t[x]=1;
    f[x]=v[x];
    if (fl==1) se=0;
    for (int i=last[x];i!=0;i=side[i].next)
    {
        if (side[i].s==0) continue;
        int j=side[i].y;
        if (t[j]==1) continue;
        dfs1(j,0);
        if (f[j]+v[x]>f[x])
        {
            se=f[x];
            f[x]=f[j]+v[x];
        }
        else if (f[j]+v[x]>se) se=f[j]+v[x];
    }
}
 
void dfs2(int x,int up,int fa)
{
    s[x]=max(f[x],up+v[x]);
    for (int i=last[x];i!=0;i=side[i].next)
    {
        if (side[i].s==0) continue;
        int j=side[i].y;
        if (j==fa) continue;
        dfs2(j,up+v[x],x);
    }
}
 
void dfs3(int x,int up,int fa)
{
    s[x]=max(s[x],up+v[x]);
    for (int i=last[x];i!=0;i=side[i].next)
    {
        if (side[i].s==0) continue;
        int j=side[i].y;
        if (j==fa) continue;
        dfs3(j,up+v[x],x);
    }
}
 
int main()
{
    init();
    memset(t,0,sizeof(t));
    for (int i=1;i<=n;i++)
        if (t[i]==0)
        {
            dfs1(i,1);
            //printf("--%d %d --\n",i,se);
            for (int j=last[i];j!=0;j=side[j].next)
            {
                int k=side[j].y;
                s[i]=f[i];
                if (side[j].s==0) continue;
                //printf("%d %d\n",k,se);
                if (f[k]+v[i]==f[i]) dfs2(k,se,i);
                    else dfs2(k,f[i],i);
            }
        }
    //for (int i=1;i<=n;i++)
    //  printf("%d %d\n",i,s[i]);
    int x,y;
    for (int ii=q;ii>=1;ii--)
    {
        if (re[ii].s==1) re[ii].y=s[re[ii].x];
        else
        {
            x=re[ii].x;
            y=re[ii].y;
            for (int i=last[x];i!=0;i=side[i].next)
                if (side[i].y==y) 
                {
                    side[i].s=1;
                    side[i^1].s=1;
                }
            int tt=s[x];
            dfs3(x,s[y],y);
            dfs3(y,tt,x);
            //printf("%d %d-----\n",x,y);
            //for (int i=1;i<=n;i++)
                //printf("%d %d\n",i,s[i]);
        }
    }
    for (int i=1;i<=q;i++)
        if (re[i].s==1)
            printf("%d\n",re[i].y);
    return 0;
}

相关推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注

微信扫一扫,分享到朋友圈

第七维度2020初赛题解
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close