2020牛客暑期多校训练营(第四场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第四场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJ
场上
zyj
wrf
lmj

题目

A.Ancient Distance

zyj (赛后)

题意

给一个有根树,在树上选择$k$个关键点(根必须选),最小化点到最近关键祖先距离的最大值,求出$k$分别为$1,2,…,n$时答案的和。

题解

我们先考虑暴力的情况,如果是求单个k的答案,显然可以二分答案。
我们每次选择当前深度最深的点,将它的第x个祖先设为关键点,并且删除这个关键点的子树(子树内的点都合法了),直到整棵树被删完,然后比较关键点数量和$k$的大小关系,来改变二分的范围。
显然这么做单次复杂度是$O(nlogn)$的,无法接受

重要结论:
当答案为x时,关键点数量$\leq n/((x+1))+1$,因为按照上面的贪心,每次挑选一个关键点时,至少能删除$x+1$个节点。所以对于一个$k$,二分上界是$O(n/k)$。

那么我们按顺序枚举$1~k$,争取每次验证二分时,把复杂度和$N$剥离开来,搞成和关键点数量有关。如果每次验证的复杂度是「关键点数量*log」,那么容易证明总复杂度是$N log^2(N)$的(还有一个$log$是调和级数)。

要使复杂度和最终放置的关键点个数有关,我们就用一颗线段树去维护整棵树的DFS序。
我们每次的操作是:
1.找到最深的还未被染色的节点p。
2.将$p$向上$x$步的节点$q$置为关键点,把$q$的子树区间染色。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int n;
int fa[N][20];
vector<int>v[N];
int L[N],R[N];
int dep[N];
int tot;
int ans[N];
int max_id[N<<2];
int cons_max_id[N<<2];
int lazy[N<<2];
int q[N];
void dfs(int x)
{
    q[++tot]=x;
    L[x]=tot;
    for(int i=0;i<v[x].size();i++){
        dep[v[x][i]]=dep[x]+1;
        dfs(v[x][i]);
    }
    R[x]=tot;
}
void pushup(int rt)
{
    max_id[rt]=dep[max_id[rt<<1]]>dep[max_id[rt<<1|1]]?max_id[rt<<1]:max_id[rt<<1|1];
}
void pushdown(int rt)
{
    if(lazy[rt]==-1)return;
    lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
    if(lazy[rt])max_id[rt<<1]=max_id[rt<<1|1]=0;
    else max_id[rt<<1]=cons_max_id[rt<<1],max_id[rt<<1|1]=cons_max_id[rt<<1|1];
    lazy[rt]=-1;
}
void build(int l,int r,int rt)
{
    lazy[rt]=-1;
    if(l==r){
        max_id[rt]=q[l];
        cons_max_id[rt]=q[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    cons_max_id[rt]=dep[cons_max_id[rt<<1]]>dep[cons_max_id[rt<<1|1]]?cons_max_id[rt<<1]:cons_max_id[rt<<1|1];
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int x)
{
    if(L<=l&&R>=r){
        if(x){
            max_id[rt]=0;
        }else{
            max_id[rt]=cons_max_id[rt];
        }
        lazy[rt]=x;
        return;
    }
    pushdown(rt);
    int m=(l+r)>>1;
    if(L<=m)update(l,m,rt<<1,L,R,x);
    if(R>m) update(m+1,r,rt<<1|1,L,R,x);
    pushup(rt);
}
int getfa(int x,int k)
{
    for(int i=0;i<=int(log2(k));i++){
        if((1<<i)&k){
            x=fa[x][i];
        }
    }
    return x;
}
int cal(int k)
{
    int x;
    int cnt=0;
    while(x=max_id[1]){
        cnt++;
        int tmp=getfa(x,k);
        update(1,n,1,L[tmp],R[tmp],1);
    }
    //printf("---%d %d %d\n",cnt,s,k);
    return cnt;
}
void work()
{
    while(~scanf("%d",&n)){
        tot=0;
        fa[1][0]=1;
        dep[1]=1;
        for(int i=1;i<=n;i++){
            v[i].clear();
        }
        for(int i=2;i<=n;i++){
            scanf("%d",&fa[i][0]);
            v[fa[i][0]].push_back(i);
        }
        dfs(1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<20;j++){
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
        build(1,n,1);
        int maxx=dep[max_id[1]];
        //printf("%d-%d\n",max_id[1],maxx);
        for(int i=0;i<=maxx;i++){
            ans[i]=cal(i);
            update(1,n,1,1,n,0);
        }
        int tmp=maxx;
        int sum=0;
        for(int i=1;i<=n;i++){
            while(tmp>-1&&ans[tmp]<=i)tmp--;
            sum+=tmp+1;
        }
        printf("%d\n",sum);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Basic Gcd Problem

lmj 00:13:19 +0

题意

$f_c(x)=max_{i=1……x-1}c*f_c(gcd(i,x)$x>1
$f_c(x)=1$x=1

题解

显然答案为c的n的质因子个数次方。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
bool check[N];//第i个数是否为素数
int prime[N],ans[N];//每个数的最小素因数
int Prime(int n){ //返回n中素数的个数
    memset(check,true,sizeof(check));
    int sum=0;
    for(int i=2;i<=n;i++){
        if(check[i]) {
            prime[sum++]=i;
            ans[i]=1;
        }
        for(int j=0;j<sum&&i*prime[j]<=n;j++){
            check[i*prime[j]]=false;
            ans[i*prime[j]]=ans[i]+1;
            if(i%prime[j]==0) break;
        }
    } return sum;
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%lld\n",qpow(m,ans[n])%p);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    Prime(1e6);
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Count New String

题意

对字符串定义函数f(S,x,y),表示对子串S[x,y],求一个等长的字符串,每一位都是该子串中到这一位的前缀中的最大字符。
求所有本质不同的f(f(a,b),c,d)的个数。
串长不超过 $10^5$,字符集大小不超过 10。

题解

做法

考虑求前缀最大值的过程,显然函数f可以被递推定义:

$$ f(s,x,y)[i]=\left\{ \begin{aligned} &S[x] &i=0 \\ &max(S[x+i],f(s,x,y)[x+i-1]) &otherwise \end{aligned} \right. $$

由此我们可以发现:

问题就化为,求所有f(S,x,n)的后缀的本质不同子串个数。

从后往前遍历原串,通过单调栈可以找出每一位i之后第一个不小于它的值的位置t[i]。由递推式,f(S,x,n)的前t位必然都是S[i],之后的位『继承』f(S,t[i],n)。这样我们就处理出了所有的f(S,x,n)
接下来考虑f(S,x,n)的某一个后缀。由递推式可知,该后缀仅由开头字母的绝对位置和值唯一确定,所以最多只有 $n\Sigma$ 个后缀。
那么我们就可以记录每个后缀开头的信息,并枚举每个f(S,x,n)的后缀。如果该后缀已经被枚举过了,就放弃这个f的其他后缀,否则就将它加入答案中。
最后对收集到的所有后缀进行排序,构成后缀数组,求本质不同子串即可。

时间复杂度

$O(n\Sigma^2(\log n+log \Sigma))$

代码

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N=100020;
 
struct node
{
    int q[10];
    int end;
 
    node(): end(0)
    {
        for(int i=0;i<10;i++) q[i]=0;
    }
};
 
char ch[N];
int t[N];
int q[N][10];
bool f[N][10];
 
bool cmp(const node& i,const node& j)
{
    for(int k=0;k<10;k++)
    {
        if(i.q[k]<j.q[k])
        {
            return i.end<=k;
        }
        else if(i.q[k]>j.q[k])
        {
            return !(j.end<=k);
        }
    }
    return false;
}
 
int main(void)
{
    scanf("%s",ch);
    stack<int> s;
    int n=strlen(ch);
    for(int i=n-1;i>=0;i--)
    {
        while(!s.empty())
        {
            if(ch[s.top()]<ch[i]) s.pop();
            else break;
        }
        if(s.empty())
        {
            t[i]=n;
        }
        else t[i]=s.top();
         
        s.push(i);
    }
     
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<10;j++)
        {
            q[i][j]+=q[t[i]][j];
        }
        q[i][ch[i]-'a']+=t[i]-i;
    }
    vector<node> v;
    for(int i=0;i<n;i++)
    {
        for(int j=0,k=i;k<n;k++)
        {
            while(q[i][j]==0) j++;
            if(f[k][j]) break;
            else
            {
                f[k][j]=true;
                node t;
                for(int l=0;l<10;l++)
                {
                    t.q[l]=q[i][l];
                }
                for(t.end=9;t.end>=0;t.end--) if(t.q[t.end]!=0) break;
                q[i][j]--;
                v.push_back(t);
            }
        }
    }
 
    sort(v.begin(),v.end(),cmp);
 
    ll a=0,b=0;
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<10;j++)
        {
            a+=v[i].q[j];
        }
    }
    for(int i=1;i<v.size();i++)
    {
        for(int j=0;j<10;j++)
        {
            if(v[i].q[j]==v[i-1].q[j]) b+=v[i].q[j];
            else
            {
                b+=min(v[i-1].q[j],v[i].q[j]);
                break;
            }
        }
    }
 
    printf("%lld",a-b);
     
    return 0;
}

D.Dividing Strings

lmj (赛后)

题意

将一个数字序列进行分割,不存在前导零,求分割后最大值减最小值的最小值

题解

显然答案在0-9之间,难点是有可能出现进位。我们考虑进位后数字的样子XXXXX00000Y,进位前XXXXX(x-1)99999Y,可以发现如果要对答案有影响那么前面很多位都要是相同的,那么考虑使用SA去记录前缀相同的数量,然后对后面连续相同值进行预处理,然后就可以尽量的只比较最后1、2位,反正我是写成了大模拟,写法有点傻逼。

代码

270+行,不放了


E.Eliminate++

zyj (赛后) +1e5

题意

黑板上有$N$个互不相同的数,且$N$是奇数。每次选取连续的三个数,只将它们的中位数保留。重复上述操作直到剩下一个数字。对于原来的每一个数字$x$都询问:是否存在一种擦除方法,使得最终剩下的数是$x$。$N<1000000$

题解

    列出所有的转换为:
    000->0 , 010->0 , 011->1 , 111->1 , 01x->x , 00x->0 , 11x->1

一个重要的引理:

$x$左右的$01$无关。即如果原问题有解,一定存在一个方案是:把左右单独做一遍消除(只剩下一个或者两个数字),最后左右和中间的$x$再合并消除剩下$x$。

我们可以认为,在左右各自消了一会的某个时间点后都是跨$x$的消除(我们总能把之后的左右单独消这一步提前做),注意:左边提供两个数结合$x$的消法也可以看做是左右单独的消除(而不是跨$x$的消除),因为这样只能是$01x$或者$10x$,可以在一开始就结合那一侧的数消掉这对$01$。由于$0x0$ 和$1x1$会使$x$消失,跨区间的只能形如$0x1$或$1x0$(然后$01$同时消失)。所以在最后跨区间消的时候,左右$01$的个数一样且互补。如果跨区间消出现了至少三次,我们可以单独把左边的三个和右边的三个在之前单独消,所以在最后的互补状态里,左右最多两个数字。基于引理和跨区间消除的性质,我们可以把原问题转化成一些左右独立的询问(每次问消到这种状态是否可行):

可行方案为:

如果能满足以上的某一条(左右都能消成对应状态),就有解。先考虑如何判断一侧是否能留下全$0$(全$1$也一样)

如果原来就有连续三个$1$相邻,直接消除肯定没问题。存在一种情况类似于$11011$,这时候是两段$1$要合并再一起消除。这样损耗了3个$1$和1个$0$。从左到右贪心做,维护前缀0 的个数$zero$(0我们都留着不消)以及紧接着一段连续1的个数$one$($one$的值最多只会是2,一旦大于等于3就立刻消除)。如果新来的数是$0$且$one$有值,带来的效果就是$one--$(这组$01$被消掉,以利于$one$这段$1$和后面的$1$合并)。做到最后如果$one > zero$,那么能留下全$0$。

重要性质:如果0 和1 的个数一样,一定能消除成01/10。

证明:因为我们每次可以选择相邻的$01$,再随便加一个数就可以把他们成对地消除。

考虑之前的的贪心做法,它极大地留下了$0$的个数。所以对于一个$01$序列(假设$0$出现的多),我们可以先套用上述算法,直到做到某个时刻$01$个数一样时就合法了。这些做法都是线性的,总复杂度$O(N^2)$,需要优化。用一定顺序去枚举$x$假设我们从小到大去枚举$x$,那么相当于是$01$序列里不断有$1$变成$0$,每次要快速做之前的两种判断。我们用$(zero_i, one_i)$代表之前的贪心算法做完第$i$个数后的状态。 随着$x$的枚举,这些$pair$的前者变大后者变小。

当第$i$个数从$1$变成$0$后,考虑$(zero_{i-1}, one_{i-1})$:
1.如果$one_{i-1}=2$,则$one_i - one_n$ 不变,$zero_i - zero_n$ 不变。
2.如果$one_{i-1}=0$,则$one_i - one_n$ 不变,$zero_i - zero_n$ 加一。
3.如果$one_{i-1}=1$,则要不$zero_{i+1} - zero_n$ 加一(如果$a_{i+1}=0$)要不$one_{i+1} - one_n$ 不变,$zero_{i+1} - zero_n$ 不变(如果$a_{i+1}=1$)

当第$i$位从$1$变成$0$后,我们从第$i$位开始重新修改。由以上分析,要不($zero, one$) 的值迅速收敛(和上一次保持一致),那我们就直接$break$;要不$zero$的值全都集体$+1$,这样这次更新的确可能影响$O(N)$个位置。第一种贪心算法要求判断$zero > one$是否可行。所以当$zeroi >=3$后,$i$以及$i$之后的点必然合法。每个点的$zero$最多增加三次,由均摊分析复杂度是线性的。对于第二种贪心算法,我们只需在$1$比$0$多的时候调用$zero >= one$,$0$比$1$多时反一下。出题人在这里偷懒用了一个树状数组,总复杂度是$O(N log⁡N)$

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,a[maxn],id[maxn];
char ans[maxn];
struct node{int a[5],b[5];}t[maxn<<2],tmp;
node A=(node){{0,3,1,0,0},{0,0,0,0,0}},B=(node){{1,2,1,1,2},{0,0,1,0,0}};
node pushup(const node &a,const node &b){
    node c;
    rep(i,0,4) c.a[i]=b.a[a.a[i]],c.b[i]=a.b[i]+b.b[a.a[i]];
    return c;
}
void build(int l=1,int r=n,int rt=1){
    if(l==r){t[rt]=B;return;}
    int mid=(l+r)>>1;
    build(l,mid,lson);build(mid+1,r,rson);t[rt]=pushup(t[lson],t[rson]);
}
void add(int pos,int l=1,int r=n,int rt=1){
    if(l==r){t[rt]=A;return;}
    int mid=(l+r)>>1;
    if(pos<=mid) add(pos,l,mid,lson);
    else add(pos,mid+1,r,rson);
    t[rt]=pushup(t[lson],t[rson]);
}
void query(int l,int r,int rt,int ql,int qr){
    if(ql<=l&&r<=qr){tmp=pushup(tmp,t[rt]);return;}
    int mid=(l+r)>>1;
    if(ql<=mid) query(l,mid,lson,ql,qr);
    if(qr>mid) query(mid+1,r,rson,ql,qr);
}
int ask(int l,int r){
    tmp=A;
    if(l<=r) query(1,n,1,l,r);
    return tmp.b[0];
}
void solve(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]),id[a[i]]=i;
    build();
    rep(i,1,n/2){
        ans[id[i]]=((ask(1,id[i]-1)+ask(id[i]+1,n))*2>=(n-i-i+1))?'1':'0';
        add(id[i]);
    }build();
    dep(i,n,(n+3)/2){
        ans[id[i]]=((ask(1,id[i]-1)+ask(id[i]+1,n))*2>=(i-1-n+i))?'1':'0';
        add(id[i]);
    }ans[id[n/2+1]]='1';
    rep(i,1,n) printf("%c",ans[i]);puts("");

}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

F.Finding the Order

wrf (00:23:18) +2

题意

有两条平行的直线AB和CD。
给出AC, AD, BC, BD 四个距离,问是AB//CD 还是AB//DC。

题解

找到这四个距离的最大值。如果最大值来自AD或BC,则AB//CD,否则AB//DC。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
 
const int N=100020;
 
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
int main(void)
{
    //ios::sync_with_stdio(false);
     
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
     
    for(int _=read();_>0;_--)
    {
        int ac=read(),ad=read(),bc=read(),bd=read();
 
        bool cl=(ac<=bc),dl=(ad<=bd),cr=(ac>=bc),dr=(ad>=bd);
 
        if(cl && dl)
        {
            if(bc>bd) printf("AB//CD");
            else printf("AB//DC");
        }
        else if(cr && dr)
        {
            if(ac<ad) printf("AB//CD");
            else printf("AB//DC");
        }
        else if(cl && dr) printf("AB//CD");
        else if(cr && dl)printf("AB//DC");
        printf("\n");
    }
     
    return 0;
}

H.Harder Gcd Problem

lmj 01:05:54 +2

题意

给1-n的序列配对,使得对应的对的两个值的gcd不为1,求最多的对数和如何配对

题解

将所有元素存到其最小的质因子的vector中,从大到小枚举,如果这个vector内元素为偶数,那么直接两两配对,否则两两配对完再取出该点的2倍(要求存在),和多余的另一个配对,最后配对2的时候注意不要将已配对的算入。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int vis[N];
int vis1[N];
struct node
{
    int x;
    int y;
}ans[N];
vector<int>v[N];
void work()
{
    int tot=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        vis[i]=0;
        vis1[i]=0;
        v[i].clear();
    }
    for(int i=2;i<=n;i++){
        if(vis[i])continue;
        int f=0;
        for(int j=i;j<=n;j+=i){
            if(vis[j])continue;
            v[i].push_back(j);
            vis[j]=1;
        }
    }
    for(int i=n;i>=3;i--){
        if(v[i].size()==0)continue;
        if(v[i].size()%2==0){
            for(int j=0;j<v[i].size();j+=2){
                ans[++tot].x=v[i][j];
                ans[tot].y=v[i][j+1];
            }
        }else{
            for(int j=1;j<v[i].size();j+=2){
                ans[++tot].x=v[i][j];
                ans[tot].y=v[i][j+1];
            }

            if(2*i<=n){
                ans[++tot].x=i;
                ans[tot].y=2*i;
                vis1[2*i]=1;
            }
        }
    }
    int f=0;
    for(int i=0;i<v[2].size();i++){
        if(vis1[v[2][i]])continue;
        if(!f){
            f=v[2][i];
        }else{
            ans[++tot].x=f;
            ans[tot].y=v[2][i];
            f=0;
        }
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++){
        printf("%d %d\n",ans[i].x,ans[i].y);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.Investigating Legions

lmj 02:36:17 +4

题意

给了个n个人的两两关系,关系为是否在同一组内,当每个关系有1/S的概率取反,求所有人的组别(最小表示)

题解

由于数据随机,所以直接考虑暴力搞一搞。从0到n-1进行枚举,先当其的关系全为真,将其同组的加入其所在的集合,然后进行判断是否有错误信息,枚举所有点(如果已经被判断过的就不用了)判断他和当前枚举的这个点的关系是否是真,那么就是判断该点和该集合中的点的关系,如果超过一半有连接,那么说明该点是在这个集合内,否则不在,进行修改即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
char a[N];
int b[305][305];
set<int>s[305];
int vis[305];
int ans[305];
void work()
{
    int n,S;
    scanf("%d%d",&n,&S);
    scanf("%s",a);
    int tot=0;
    memset(b,0,sizeof(b));
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof(ans));
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<n;i++){
        s[i].clear();
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            b[j][i]=b[i][j]=a[tot++]-'0';
            //printf("%d %d %d\n",i,j,b[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        b[i][i]=1;
    }
    int sum=0;
    for(int j=0;j<n;j++){
        if(vis[j]!=-1)continue;
        vis[j]=j;
        s[j].insert(j);
        for(int i=j+1;i<n;i++){
            if(b[j][i]==1&&vis[i]==-1){
                s[j].insert(i);
                vis[i]=j;
            }
        }
        for(int i=j+1;i<n;i++){
            int cnt=0;
            if(vis[i]!=-1&&vis[i]!=j)continue;
            if(b[j][i]){
                for(auto x:s[j]){
                    if(b[i][x])cnt++;
                }
                //printf("--%d %d %d\n",i,j,cnt);
                if(cnt<s[j].size()/2){
                    sum++;
                    //printf("%d %d\n",i,j);
                    b[j][i]=b[i][j]=0;
                    s[j].erase(i);
                    vis[i]=-1;
                }
            }else{
                for(auto x:s[j]){
                    if(b[i][x])cnt++;
                }
                if(cnt>s[j].size()/2){
                    sum++;
                    //printf("%d %d\n",i,j);
                    b[j][i]=b[i][j]=1;
                    s[j].insert(i);
                    vis[i]=j;
                }
            }
        }
    }
    assert(sum<=100);
    int cnt=0;
    for(int i=0;i<n;i++){
        if(s[i].size()){
            ans[i]=cnt;
            for(auto x:s[i]){
                ans[x]=cnt;
            }
            cnt++;
        }
    }
    for(int i=0;i<n;i++){
        printf("%d ",ans[i]);
    }
    printf("\n");
}
int main()
{
    //freopen("1.in","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Jumping on the Graph

zyj (赛后)

题意

给出一张无向带权图,定义一条路径的权值为所有经过边的权值中的次大值。求两两点对之间次大值之和。

题解

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e6+100;
const int mod=(int)1e9+7;
int n,m,sta[maxn],top;
struct node{
    int u,v;ll w;
    bool operator<(const node& b)const{return w<b.w;}
}g[maxn<<2];
unordered_set<int> e[maxn];
ll fa[maxn],deg[maxn],big[maxn],ans[maxn],sz[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void getdeg(int x){
    deg[x]=0;
    for(auto v:e[x]) deg[x]+=sz[v];
}
int main(){
    scanf("%d%d",&n,&m);
    int lim=1200;
    rep(i,1,m){
        scanf("%d%d%lld",&g[i].u,&g[i].v,&g[i].w);
        if(g[i].u!=g[i].v) e[g[i].u].insert(g[i].v),e[g[i].v].insert(g[i].u);
    }sort(g+1,g+1+m);
    rep(i,1,n){
        fa[i]=i;deg[i]=(int)e[i].size();sz[i]=1;
        ans[0]+=deg[i];big[i]=(deg[i]>lim);
        if(big[i]) sta[++top]=i;
    }
    rep(i,1,m){//当前边作为次大边
        ans[i]+=ans[i-1];
        int x=find(g[i].u),y=find(g[i].v);
        if(x==y) continue;
        if(sz[x]<sz[y]) swap(x,y);
        if(!big[x]) getdeg(x); getdeg(y);
        ans[i]+=1ll*sz[x]*(deg[y]-sz[x])+1ll*sz[y]*(deg[x]-sz[y]);//此时还有重复的答案
        e[x].erase(y);
        for(auto v:e[y]) if(v!=x){//处理小点
            e[v].erase(y);
            if(!e[x].count(v)){
                e[x].insert(v);e[v].insert(x);
                deg[x]+=sz[v];deg[v]+=sz[x];
            } else ans[i]-=1ll*(sz[x]+sz[y])*sz[v];//重复部分
            deg[v]-=sz[y];
        }
        e[y].clear();fa[y]=x;sz[x]+=sz[y];deg[x]-=sz[y];
        if(!big[x]&&e[x].size()>lim) big[x]=1,sta[++top]=x;
        if(big[y]){
            int pos=0;
            rep(j,1,top) if(sta[j]==y){pos=j;break;}
            memmove(sta+1,sta+1+pos,(top-pos)<<2);top--;
        }
        rep(j,1,top) if(sta[j]!=x&&e[x].count(sta[j])) deg[sta[j]]+=sz[y];
    }ll cnt=0;
    rep(i,1,m) cnt+=(ans[i]-ans[i-1])*g[i].w;
    printf("%lld\n",cnt);

}
Responses