「题解」欠钱 money(未完待续)

题目链接:JZOJ 6273

题目

题目描述

输入格式

第一行两个整数 $n$ 和 $m$,表示有 $n$ 只企鹅,$m$ 个操作。

接下来 $m$ 行,有两种可能的格式:
0 a b c:修改操作,企鹅 $a$ 向企鹅 $b$ 借了 $c$ 元钱。
1 a b:查询操作,询问假如 $a$ 有了 $+\infty$ 元钱,企鹅 $b$ 会净收入多少钱。

本题强制在线,也就是说:对于每个操作输入的变量 $a,b,c$ (如果没有 $c$,那就只有 $a,b$ )

都不是实际的 $a,b,c$,想获得实际的 $a,b,c$ 应当经过以下操作:

a = (a + lastans) % n + 1;
b = (b + lastans) % n + 1;
c = (c + lastans) % n + 1;

其中,lastans 是上一次询问的答案。如果没有上一次询问,lastans 为 $0$。

输出格式

对每个询问操作,输出一行一个数表示答案。

样例输入输出

#1

  • Input:
5 9
0 1 2 1
0 0 1 2
1 0 1
1 2 4
0 2 1 1
1 2 0
0 3 1 0
1 4 2
1 3 4
  • Output:
3
2
1

数据范围

数据分为以下几种:
第一种:占 $10\%$,$n\leq 5\times 10^3$ 且 $m\leq 10^4$;
第二种:占 $20\%$,所有借钱事件发生在所有询问事件之前;
第三种:占 $30\%$,对于一只企鹅 $A$,最多有一只企鹅向 $A$ 借钱;
第四种:占 $40\%$,没有特殊性质, $n,m$ 大小有一定梯度。
对于所有数据,满足 $n\leq 10^5,m\leq 10^6,0\leq a,b,c\leq n$ 且 $a\neq b$。

时空限制

$$1000\text{ms}/512 \text{MiB}$$

题解

本题有多种解法(暴力解法(10 ~ 20分)、离线解法(0分)、三种正解(100分))。

解法 A (暴力解法)

思路

思路非常简单,整体的思路就是:

  • 修改操作:加边, $a$ 向 $b$ 借 $c$ 元钱就加一条从 $a$ 到 $b$ 的权值为 $c$ 的有向边。
  • 查询操作:
    1. 如果 $a,b$ 不连通,输出 $0$;
    2. 否则输出 $a$ 到 $b$ 这条链上边权的最小值。
      那么我们就可以写出代码。

代码

时间复杂度为 $\Theta(n+mn)$,预计得分 $10$ 分,开 $\text{Ofast}$ 可以得到 $20$ 分。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
#define INF 0X3F3F3F3F
//以上为头文件
const int MAXN=100000+5;
int n,m;
int opt,a,b,c;
int to[MAXN],w[MAXN];
int dep[MAXN];//深度,用于判断a,b是否连通
int lastans;
void Add_Edge(int,int,int);
void Update(int,int,int);//修改操作
int Query(int,int);//查询操作
int main(void){
    //freopen("money.in","r",stdin);
    //freopen("money.out","w",stdout);
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        dep[i]=1;//初始化
    while(m--){
        scanf("%d",&opt);
        if(opt==0){
            scanf("%d%d%d",&a,&b,&c);
            a=(a+lastans)%n+1;
            b=(b+lastans)%n+1;
            c=(c+lastans)%n+1;
            Update(a,b,c);
        }
        if(opt==1){
            scanf("%d%d",&a,&b);
            a=(a+lastans)%n+1;
            b=(b+lastans)%n+1;
            printf("%d\n",lastans=Query(a,b));//记得更新lastans
        }
    }
    return 0;
}
void Update(int a,int b,int c){
    to[a]=b,w[a]=c;//加边
    dep[a]=dep[b]+1;//更新深度
    return;
}
int Query(int a,int b){
    register int i,f=INF;//f初始化为正无穷
    if(dep[a]<dep[b])//a比b更深,a不可能到b
        return 0;
    for(i=a;i!=b;i=to[i]){
        f=min((int)f,w[i]);//求最小值
        if(to[i]==0)//查到根了还没找到
            return 0;//返回0
    }
    return f;//返回答案
}

解法 B (离线算法)

未完待续

正解 A

LCT

正解 B

思路

代码

时间复杂度为 $\Theta(n\log _ 2^2n+m\log _ 2n)$,预计得分 $100$ 分。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using std::min;
using std::swap;
#define INF 0X3F3F3F3F
const int MAXN=100000+5;
const int MAXLOG2N=17+1;
int n,m;
int opt,a,b,c;
int cnt,head[MAXN],to[MAXN<<1],w[MAXN<<1],Next[MAXN<<1],Dir[MAXN<<1];
int fa[MAXN],dep[MAXN],size[MAXN];
int f[MAXN][MAXLOG2N],Min[MAXN][MAXLOG2N],dir[MAXN][MAXLOG2N];
void Add_Edge(int,int,int,int);
void DFS(int,int,int);
void Update(int,int,int);
int Query(int,int);
int main(void){
    //freopen("money.in","r",stdin);
    //freopen("money.out","w",stdout);
    register int i,lastans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        fa[i]=i,dep[i]=size[i]=1;//初始化
    while(m--){
        scanf("%d",&opt);
        if(opt==0){
            scanf("%d%d%d",&a,&b,&c);
            a=(a+lastans)%n+1;
            b=(b+lastans)%n+1;
            c=(c+lastans)%n+1;
            Update(a,b,c);
        }
        if(opt==1){
            scanf("%d%d",&a,&b);
            a=(a+lastans)%n+1;
            b=(b+lastans)%n+1;
            printf("%d\n",lastans=Query(a,b));
        }
    }
    return 0;
}
void Add_Edge(int u,int v,int len,int direction){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    Dir[cnt]=direction;
    head[u]=cnt;
    return;
}
void DFS(int ID,int father,int anc){
    register int i;
    fa[ID]=anc,dep[ID]=dep[father]+1;
    for(i=1;i<MAXLOG2N;++i){
        f[ID][i]=f[f[ID][i-1]][i-1];
        Min[ID][i]=min(Min[ID][i-1],Min[f[ID][i-1]][i-1]);
        dir[ID][i]=dir[ID][i-1]|dir[f[ID][i-1]][i-1];
    }
    for(i=head[ID];i;i=Next[i])
        if(to[i]!=father){
            f[to[i]][0]=ID;
            Min[to[i]][0]=w[i];
            dir[to[i]][0]=Dir[i]^3;
            DFS(to[i],ID,anc);
        }
    return;
}
void Update(int a,int b,int c){
    Add_Edge(a,b,c,1);
    Add_Edge(b,a,c,2);
    if(size[fa[a]]>size[fa[b]])//启发式合并
        swap(a,b);
    f[a][0]=b;
    Min[a][0]=c;
    dir[a][0]=Dir[head[a]];
    size[fa[b]]+=size[fa[a]];
    DFS(a,b,fa[b]);
    return;
}
int Query(int a,int b){
    if(fa[a]!=fa[b])//不连通
        return 0;
    register int i,res=n,d;
    if(dep[a]>dep[b])
        swap(a,b),d=0;
    else
        d=3;
    for(i=MAXLOG2N-1;i>=0;--i)
        if(dep[f[b][i]]>=dep[a]){
            if(dir[b][i]!=(1^d))//方向错误
                return 0;
            res=min((int)res,Min[b][i]);
            b=f[b][i];//跳
        }
    if(a==b)
        return res;
    for(i=MAXLOG2N-1;i>=0;--i)
        if(f[b][i]!=f[a][i]){
            if(dir[b][i]!=(1^d)||dir[a][i]!=(2^d))//方向错误
                return 0;
            res=min((int)res,min(Min[b][i],Min[a][i]));
            b=f[b][i];//跳
            a=f[a][i];//跳
        }
    if(dir[b][0]!=(1^d)||dir[a][0]!=(2^d))//方向错误
        return 0;
    else
        return min((int)res,min(Min[b][0],Min[a][0]));
}