代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> long long n,L,R; long long f[1000]; void print(long long x,long long l,long long r){ if(x==0){ printf("0"); return; } if(x==1){ printf("1"); return; } if(l>=f[x-2]) print(x-1,l-f[x-2],r-f[x-2]); else if(r<f[x-2]) print(x-2,l,r); else print(x-2,l,f[x-2]-1),print(x-1,0,r-f[x-2]); } int main(){ std::cin>>n>>L>>R; if(n==0) {printf("0\n");return 0;} if(n==1) {printf("1\n");return 0;} f[0]=1;f[1]=1; int i; for(i=2;i<=n;i++){ f[i]=f[i-1]+f[i-2]; if(f[i]>R) break; } if(L==0){ if(n%2==0){ if(R==0) {printf("0\n");return 0;} else printf("01"); }else{ if(R==0) {printf("1\n");return 0;} else printf("10"); } L=2; }if(L==1){ if(n%2==0) printf("1"); else printf("0"); L=2; } print(i,L,R); std::cout<<std::endl; return 0; }
代码：
#include<cstdio> #include<algorithm> #include<iostream> const int inf=2147483647; const int N=200100; int fa[N],dep[N],mindep[N]; int e[N*2],next[N*2],point[N],t; int n,k; void merge(int u,int v){ e[++t]=v; next[t]=point[u]; point[u]=t; } void build(int x){ int ok=0; for(int i=point[x];i;i=next[i]){ int v=e[i]; if(v==fa[x]) continue; fa[v]=x; dep[v]=dep[x]+1; ok=1; build(v); mindep[x]=std::min(mindep[x],mindep[v]+1); } if(!ok){ mindep[x]=0; return; } } int dfs(int x){ if(dep[x]>=mindep[x]) return 1; int ret=0; for(int i=point[x];i;i=next[i]){ int v=e[i]; if(v==fa[x]) continue; ret+=dfs(v); } return ret; } int main(){ std::cin>>n>>k; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); merge(u,v); merge(v,u); } for(int i=1;i<=n;i++) mindep[i]=inf; dep[k]=0; build(k); std::cout<<dfs(k)<<std::endl; return 0; }
#include<bits/stdc++.h> using namespace std; #define maxn 100005 #define ll long long #define inf 100000000 int n,m,k,l,a,b,c,ins[maxn],scc[maxn],cnt=0,num=0,dfn[maxn],low[maxn],in[maxn],dmi[maxn],dmx[maxn],visit[maxn] ,sv[maxn],val[maxn]; struct edge{ int from,to; };vector<edge>edges;vector<int>g[maxn];vector<edge>mp[maxn];vector<edge>mp2[maxn]; void add_edge(int f,int t){edges.push_back({f,t});g[f].push_back(k++); }stack<int>s; void tarjan(int u){ low[u]=dfn[u]=++num;ins[u]=1;s.push(u); for(int i=0;i<g[u].size();i++){ edge &e=edges[g[u][i]]; if(!dfn[e.to]){tarjan(e.to); low[u]=min(low[u],low[e.to]); }else if(ins[e.to]) low[u]=min(low[u],dfn[e.to]); }if(low[u]==dfn[u]){ int y;cnt++; do{y=s.top();ins[y]=0;scc[y]=cnt; val[cnt]+=sv[y];s.pop(); }while(u!=y); } }int main(){ cin>>n>>m;for(int i=1;i<=n;i++)sv[i]=1; for(int i=1;i<=m;i++)cin>>a>>b,add_edge(a,b); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=0;i<edges.size();i++){ int f=edges[i].from,t=edges[i].to; if(scc[f]!=scc[t]){mp[scc[f]].push_back({scc[f],scc[t]}); mp2[scc[t]].push_back({scc[t],scc[f]}); } }queue<int>q;memset(dmx,0,sizeof(dmx));q.push(scc[1]);dmx[scc[1]]=val[scc[1]];visit[scc[1]]=1; while(!q.empty()){ int u=q.front();q.pop();visit[u]=0; for(int i=0;i<mp[u].size();i++){ edge &e=mp[u][i]; if(dmx[e.to]<dmx[u]+val[e.to]){ dmx[e.to]=dmx[u]+val[e.to]; if(visit[e.to]==0){ q.push(e.to); } } } }for(int i=1;i<=n;i++)dmi[i]=0; q.push(scc[1]);dmi[scc[1]]=val[scc[1]];visit[scc[1]]=1; memset(visit,0,sizeof(visit)); while(!q.empty()){ int u=q.front();q.pop();visit[u]=0; for(int i=0;i<mp2[u].size();i++){ edge &e=mp2[u][i]; if(dmi[e.to]<dmi[u]+val[e.to]){ dmi[e.to]=dmi[u]+val[e.to]; if(visit[e.to]==0){ q.push(e.to); } } } } int ans=-inf; for(int i=0;i<edges.size();i++){ edge &e=edges[i]; if(dmi[scc[e.to]]!=inf&&dmx[scc[e.from]]!=0)ans=max(dmi[scc[e.to]]+dmx[scc[e.from]]-val[scc[1]],ans); if(dmi[scc[e.from]]!=inf&&dmx[scc[e.to]]!=0)ans=max(dmi[scc[e.from]]+dmx[scc[e.to]]-val[scc[1]],ans); }cout<<ans<<endl; return 0; }