[CodeVS 1217]借教室

很容易想到线段树水过。

很可惜,这样估计也就70分。

然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定?

不知道诸位还记得差分序列?记得就好,用差分序列的方法维护即可。

等等,我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的,能过?

推荐一个行之有效的优化:注意一下每一次修改都是在之前的基础上反悔或前进几次,所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~

代码:

#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
    register int i,cnt=0;
    if(x>last)
        for(i=last+1;i<=x;i++){
            C[l[i]]+=d[i];
            C[r[i]+1]-=d[i];
        }
    if(x<last)
        for(i=x+1;i<=last;i++){
            C[l[i]]-=d[i];
            C[r[i]+1]+=d[i];
        }
    last=x;
    for(i=1;i<=n;i++){
        cnt+=C[i];
        if(cnt>A[i])
            return false;
    }
    return true;
}

int main(){
    register int i,L,M,R;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=m;i++){
        scanf("%lld%d%d",&d[i],&l[i],&r[i]);
    }
    L=1;
    R=m+1;
    while(L<R){
        M=L+(R-L)/2;
        if(Check(M)){
            L=M+1;
        }else{
            R=M;
        }
    }
    if(L==m+1)
        puts("0");
    else
        printf("-1\n%d\n",L);
    return 0;
}

[CodeVS 3729]飞扬的小鸟

论如何把一个完全背包出的高大上……

这个题啊……细节特别多……

首先,不建议开滚动数组,细节处理就会疯。

然后呢……真的不太好说了……还是看代码吧(尽管代码还是有明显的滚动数组痕迹)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)

int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
    int n,m,k,temp;
    register int i,j,v,now,pre,ans=INF,cnt;
    scanf("%d%d%d",&n,&m,&k);
    cnt=k;
    REP(i,n){
        scanf("%d%d",&A[i][0],&A[i][1]);
    }
    for(i=0;i<=n;i++){
        GZ[i][0]=0;
        GZ[i][1]=m+1;
    }
    REP_B(i,k){
        scanf("%d",&temp);
        haveGZ[temp]=true;
        scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
    }
    memset(d,0x7f,sizeof(d));
    memset(d[0],0,sizeof(d[0]));
    d[0][0]=INF;
    REP_B(i,n){
        now=i;
        pre=i-1;
        d[now][0]=INF;
        int& X=A[i-1][0];
        int& Y=A[i-1][1];
        REP_B(j,m){
            if(j-X>0 && d[pre][j-X]<INF)
                d[now][j]=min(d[now][j],d[pre][j-X]+1);
            if(j-X>0 && d[now][j-X]<INF)
                d[now][j]=min(d[now][j],d[now][j-X]+1);
            if(j==m)
                for(v=j-X;v<=m;v++){
                    if(d[pre][v]<INF)
                        d[now][j]=min(d[now][j],d[pre][v]+1);
                    if(d[now][v]<INF)
                        d[now][j]=min(d[now][j],d[now][v]+1);
                }
        }
        for(j=GZ[i][0]+1;j<GZ[i][1];j++){
            if(j+Y<=m && d[pre][j+Y]<INF)
                d[now][j]=min(d[now][j],d[pre][j+Y]);
        }
        if(haveGZ[i]){
            REP_B(j,GZ[i][0])
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
            for(j=GZ[i][1];j<=m;j++)
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
        }
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            ans=min(ans,d[i][j]);
        }
        if(ans<INF)
            break;
        if(haveGZ[i])
            cnt--;
    }
    if(cnt==k){
        printf("1\n%d\n",ans);
    }else{
        printf("0\n%d\n",cnt);
    }
    return 0;
}

[CodeVS 1098]均分纸牌

很妙的一个贪心啊……

根据题意,易求平均值。然后每个数减去平均值表示这个数和平均数的“差异”。然后呢?如果每个数的差异值不为0,就直接摊给下一堆。

这种做法最大的精髓在于,即使差异值为负,也能摊给下一堆,从而避免了各种复杂操作。

代码:

#include <iostream>
using namespace std;
const int maxn=105;
int A[maxn];
int main(){
	register int i,sum=0,ans=0;
	int n;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	sum/=n;
	for(i=1;i<=n;i++){
		A[i]-=sum;
	}
	for(i=1;i<=n;i++){
		if(A[i]!=0){
			ans++;
			A[i+1]+=A[i];
			A[i]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

[UOJ 19]寻找道路

这个题难就难在,别说重边自环,就是简单有向环,也会让DFS爆炸。所以考虑BFS。

但……BFS怎么判断其他点到[tex]t[/tex]的联通?

方法是,把边都反过来!这样BFS一遍就可以判联通了。

然后接下来BFS最短路就简单了,注意一些特判。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=10005,maxm=400005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
bool rev[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v,bool reverse=false){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
    rev[graph_tot]=reverse;
}

int s,t;
bool vis[maxn];
bool LT[maxn];
bool bfs_1(){
    register int i,u;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t]=true;
    LT[t]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        GRAPH_REP(i,u){
            if(rev[i] && !vis[to[i]]){
                LT[to[i]]=true;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return LT[s];
}

int dep[maxn];
int bfs_2(){
    register int i,u;
    bool Allow;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s]=true;
    dep[s]=0;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        Allow=true;
        GRAPH_REP(i,u){
            if(!rev[i] && !LT[to[i]]){
                Allow=false;
                break;
            }
        }
        if(!Allow)
            continue;
        GRAPH_REP(i,u){
            if(!rev[i] && !vis[to[i]]){
                dep[to[i]]=dep[u]+1;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return vis[t]?dep[t]:-1;
}

int main(){
    int n,m,u,v;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u,true);
    }
    scanf("%d%d",&s,&t);
    if(!bfs_1()){
        puts("-1");
    }else{
        printf("%d\n",bfs_2());
    }
    return 0;
}

[UOJ 16]联合权值

这个题的关键啊……就在于那个中间点。

我们可以枚举中间点,然后进行统计。

至于最大联合权值,直接找中间点相邻点中最大权值和次大权值的积的最大值。至于联合权值之和,可以推出这样一个式子([tex]x[/tex]与中间点相邻,其中[tex]s[/tex]是所有和中间点相邻的点的权值和):

[tex]\Sigma x\mul (s-x)[/tex]

这就好弄多了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2*1e5+5;
const int maxm=maxn*2,MOD=10007;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}

// int pow_mod(int a,int b){
//     if(!b){
//         return 1;
//     }
//     int x=pow_mod(a,b>>1);
//     long long ans=(((long long)x)*((long long)x))%MOD;
//     if(1&b)
//         ans=ans*(a%MOD)%MOD;
//     return (int)ans;
// }
int d[maxn];
int main(){
    int n,u,v,temp,temp2;
    register int i,j,ans1=0,ans2=0,sum,maxv,smax;
    scanf("%d",&n);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    REP(i,n){
        scanf("%d",&d[i]);
    }
    REP(i,n){
        sum=maxv=smax=0;
        GRAPH_REP(j,i){
            temp=to[j];
            sum=(d[temp]%MOD+sum)%MOD;
            if(d[temp]>maxv){
                smax=maxv;
                maxv=d[temp];
            }else{
                if(d[temp]>smax)
                    smax=d[temp];
            }
        }
        ans1=max(ans1,maxv*smax);
        temp2=0;
        GRAPH_REP(j,i){
            temp=to[j];
            temp2=(temp2+(d[temp]%MOD)*((sum-(d[temp]%MOD)+MOD)%MOD)%MOD)%MOD;
        }
        ans2=(ans2+temp2)%MOD;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}

[BZOJ 4326]运输计划

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的,有点吃不消,再加上会被卡常,咔嚓掉。

考虑二分答案。我们可以直接二分最终答案,那么如何验证?

假设验证谓词为[tex]C(t)[/tex],表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢?可以考虑树上差分,对于每次计划[tex](u,v)[/tex],我们求出其最近公共祖先[tex]L[/tex],然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一,对[tex]d[L][/tex]则减二。随后将d上标记上推,可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确:二分答案,树上差分验证,同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法,倍增也可。

代码:

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}

[洛谷 P2312]解方程

最凶残的NOIP题。

首先我们可能会想到暴力枚举验证(枚举[tex][1,m][/tex]带入),然后我们很快就会想到用几个素数取模乱搞。然后嘛……

对于我们用到的取模数[tex]k[/tex],带入任意[tex]x[/tex],都有[tex]x^{a}\ mod\ k \in Z_{k} (a \in N^{0})[/tex](废话),所以说实际上我们枚举带入的是[tex][1,k)[/tex]。

这个题可以不开高精,因为可以一边读入一边取模

代码:

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105,maxm=1000005;
const int P1=3079,P2=3083,P3=1000000207;

int X1[maxn],X2[maxn],X3[maxn];
bool Ac_1[P1],Ac_2[P2];

typedef long long ll;

inline ll mul_mod(ll a,ll b,ll Mod){
    return ((a%Mod)*(b%Mod))%Mod;
}

inline int readint(){
    register int ans=0;
    register char c=getchar();
    while(!isdigit(c)){
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}
inline void read_mod(int& a,int& b,int& c){
    a=b=c=0;
    bool flag=false;
    register char cr=getchar();
    while(!isdigit(cr)){
        if(cr=='-')
            flag=true;
        cr=getchar();
    }
    while(isdigit(cr)){
        a=(mul_mod(10,a,P1)+cr-'0')%P1;
        b=(mul_mod(10,b,P2)+cr-'0')%P2;
        c=(mul_mod(10,c,P3)+cr-'0')%P3;
        cr=getchar();
    }
    if(flag){
        a=(P1-a)%P1;
        b=(P2-b)%P2;
        c=(P3-c)%P3;
    }
}

int n;
bool check(int* A,int x,int Mod){
    int now=0;
    register int i;
    for(i=n;i>=0;i--){
        now=(mul_mod(now,x,Mod)+A[i])%Mod;
    }
    return now==0;
}

vector<int> AnsList;
int main(){
    int m;
    register int i,ans_count=0;
    n=readint();
    m=readint();
    for(i=0;i<=n;i++)
        read_mod(X1[i],X2[i],X3[i]);
    for(i=1;i<P1;i++)
        Ac_1[i]=check(X1,i,P1);
    for(i=1;i<P2;i++)
        Ac_2[i]=check(X2,i,P2);
    for(i=1;i<=m;i++){
        if(Ac_1[i%P1] && Ac_2[i%P2] && check(X3,i,P3)){
            ans_count++;
            AnsList.push_back(i);
        }
    }
    printf("%d\n",ans_count);
    for(i=0;i<AnsList.size();i++){
        printf("%d\n",AnsList[i]);
    }
    return 0;
}

[洛谷 P2679]子串

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}

[BZOJ 4325]斗地主

是的你没有看错!就是这道坑提!

这题基本是个半成品,歧义真的,真的,真的很大。

至于方法?我们注意到同样的牌能一起出就尽可能避免拆开。例如,四带二分成炸弹加两单点(对子)肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解,并据此进行深度限制,再考虑出顺子。

然后,DFS暴搜即可。

顺便讲一下坑点:

  1. 顺子可以有A。
  2. 三带一,三带二,四代二都可以有头。但是大小头要区别开。

代码:

/**************************************************************
    Problem: 4325
    User: danihao123
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
    if(x>ans)
        return;
    int i,j,rest=0;
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=14;i++){
        cnt[hand[i]]++;
    }
    while(cnt[4]>0){
        cnt[4]--;
        rest++;
        if(cnt[2]>=2)
            cnt[2]-=2;
        else
            if(cnt[1]>=2)
                cnt[1]-=2;
    }
    while(cnt[3]>0){
        cnt[3]--;
        rest++;
        if(cnt[2]>0)
            cnt[2]--;
        else
            if(cnt[1]>0)
                cnt[1]--;
    }
    if(hand[0] && hand[1] && cnt[1]>=2)
        rest--;
    ans=min(ans,cnt[1]+cnt[2]+rest+x);
    for(i=3;i<=10;i++){
        for(j=i;j<=14 && hand[j];j++){
            hand[j]--;
            if(j-i+1>=5)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]++;
    }
    for(i=3;i<=12;i++){
        for(j=i;j<=14 && hand[j]>=2;j++){
            hand[j]-=2;
            if(j-i+1>=3)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=2;
    }
    for(i=3;i<=13;i++){
        for(j=i;j<=14 && hand[j]>=3;j++){
            hand[j]-=3;
            if(j-i+1>=2)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=3;
    }
}
int main(){
    int T,u,v;
    register int i;
    scanf("%d%d",&T,&n);
    while(T--){
        ans=n;
        memset(hand,0,sizeof(hand));
        for(i=1;i<=n;i++){
            scanf("%d%d",&u,&v);
            if(!u){
                if(v==2)
                    hand[1]++;
                else
                    hand[0]++;
            }else{
                if(u==1)
                    hand[14]++;
                else
                    hand[u]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

[洛谷 P2661]信息传递

bi了doge了……图论基本不会了……

这提可以直接循环删除所有入度为0的边,这样就只剩环了。然后DFS嘿嘿嘿。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200001;
int G[maxn];
int to[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !to[i]){
            ans=true;
            to[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
int dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
int getchen(){
    register int i,ans=0x5ffffff;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i])
            ans=min(ans,dfs(i,i));
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        to[G[i]]++;
    }
    printf("%d\n",getchen());
    return 0;
}