USACO18FEB Platinum

SlingShot 求数轴上从x到y的最短路（边长为1），有若干个从xi到yi长度为ti的传送门，每次只能选择其中一个使用。

即求min(|x-y|,min{|a-x|+|b-y|+c})，拆开绝对值，根据相对位置分开讨论，转换成二维数点问题。

MLE的主席树版本：

 #include<bits/stdc++.h>

 #define P pair<ll,ll>

 #define fir first

 #define sec second

 using namespace std;

 typedef long long ll;

 int read()

 {

     int x=;char ch=getchar();

     while (ch<''||ch>'') ch=getchar();

     while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

     return x;

 }

 const int N=1e9,T=6e6,M=1e5+;

 const ll inf=1ll<<;

 P Min[T];

 int ls[T],rs[T],A[M],x,y,sc,n,rt0[M],rt1[M],m;

 struct node{ll a,b,c;}p[M];

 bool cmp(const node &A,const node &B) {return A.a<B.a;}

 P fmin(P a,P b){

     return P(min(a.fir,b.fir),min(a.sec,b.sec));

 };

 void ins(int &k,int pk,int l,int r,int x,P y)

 {

     k=++sc;ls[k]=ls[pk];rs[k]=rs[pk];Min[k]=Min[pk];

     if (l==r) {Min[k]=fmin(Min[k],y);return;}

     int mid=(l+r)>>;

     if (x<=mid) ins(ls[k],ls[pk],l,mid,x,y);

     else ins(rs[k],rs[pk],mid+,r,x,y);

     Min[k]=fmin(Min[ls[k]],Min[rs[k]]);

 }

 P qry(int k,int l,int r,int L,int R)

 {

     if (!k) return P(inf,inf);

     if (L<=l&&r<=R) return Min[k];

     int mid=(l+r)>>;P mn=P(inf,inf);

     if (L<=mid) mn=fmin(mn,qry(ls[k],l,mid,L,R));

     if (R>mid) mn=fmin(mn,qry(rs[k],mid+,r,L,R));

     return mn;

 }

 int main()

 {

     n=read();m=read();Min[]=P(inf,inf);

     for (int i=;i<=n;i++)

       p[i].a=read(),p[i].b=read(),p[i].c=read(),A[i]=p[i].a;

     sort(p+,p+n+,cmp);

     sort(A+,A+n+);//寻址数组

     for (int i=n;i>=;i--)

         ins(rt0[i],rt0[i+],,N,p[i].b,P(p[i].a-p[i].b+p[i].c,p[i].a+p[i].b+p[i].c));

     for (int i=;i<=n;i++)

         ins(rt1[i],rt1[i-],,N,p[i].b,P(-p[i].a-p[i].b+p[i].c,-p[i].a+p[i].b+p[i].c));

     while (m--)

     {

         x=read();y=read();

         ll ans=abs(x-y);

         int k=upper_bound(A+,A+n+,x)-A-;

         ans=min(ans,qry(rt0[k+],,N,,y).fir-x+y);

         ans=min(ans,qry(rt1[k],,N,,y).fir+x+y);

         ans=min(ans,qry(rt0[k+],,N,y,N).sec-x-y);

         ans=min(ans,qry(rt1[k],,N,y,N).sec+x-y);

         printf("%lld\n",ans);

     }

     return ;

 }

正常二维数点的树状数组版本（AC）：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int read()

 {

     int x=;char ch=getchar();

     while (ch<''||ch>'') ch=getchar();

     while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

     return x;

 }

 const int M=1e5+;

 const ll inf=1ll<<;

 int A[M],n,m,tot,t,B[M*]; ll ans[M],bit[M*];

 vector<int> vec1[M],vec2[M];

 struct node{ll a,b,c,d;}p[M],q[M];

 bool cmp(const node &A,const node &B) {return A.a<B.a;}

 int lowbit(int x) {return x&(-x);}

 void add1(int x,ll y){while (x<=tot) bit[x]=min(bit[x],y),x+=lowbit(x);}//前缀最小值

 ll qry1(int x){ll res=inf;while (x) res=min(res,bit[x]),x-=lowbit(x);return res;}

 void add2(int x,ll y){while (x) bit[x]=min(bit[x],y),x-=lowbit(x);}//后缀最小值

 ll qry2(int x){ll res=inf;while (x<=tot) res=min(res,bit[x]),x+=lowbit(x);return res;}

 void init(){for (int i=;i<=tot;i++) bit[i]=inf;}

 int main()

 {

     n=read();m=read();

     for (int i=;i<=n;i++)

       p[i].a=read(),p[i].b=B[++tot]=read(),p[i].c=read(),A[i]=p[i].a;

     sort(p+,p+n+,cmp);sort(A+,A+n+);//寻址数组

     for (int i=;i<=m;i++)

     {

         q[i].a=read(),q[i].b=B[++tot]=read();ans[i]=abs(q[i].a-q[i].b);

         int k=upper_bound(A+,A+n+,q[i].a)-A-;

         vec1[k+].push_back(i);

         vec2[k].push_back(i);

     }

     sort(B+,B+tot+);tot=unique(B+,B+tot+)-B-;

     for (int i=;i<=n;i++) p[i].d=lower_bound(B+,B+tot+,p[i].b)-B;

     for (int i=;i<=m;i++) q[i].d=lower_bound(B+,B+tot+,q[i].b)-B;

     init();

     for (int i=n;i>=;i--)

     {

         add1(p[i].d,p[i].a-p[i].b+p[i].c);

         for (int j=;j<vec1[i].size();j++)

           t=vec1[i][j],ans[t]=min(ans[t],qry1(q[t].d)-q[t].a+q[t].b);

     }

     init();

     for (int i=n;i>=;i--)

     {

         add2(p[i].d,p[i].a+p[i].b+p[i].c);

         for (int j=;j<vec1[i].size();j++)

           t=vec1[i][j],ans[t]=min(ans[t],qry2(q[t].d)-q[t].a-q[t].b);

     }

     init();

     for (int i=;i<=n;i++)

     {

         add1(p[i].d,-p[i].a-p[i].b+p[i].c);

         for (int j=;j<vec2[i].size();j++)

           t=vec2[i][j],ans[t]=min(ans[t],qry1(q[t].d)+q[t].a+q[t].b);

     }

     init();

     for (int i=;i<=n;i++)

     {

         add2(p[i].d,-p[i].a+p[i].b+p[i].c);

         for (int j=;j<vec2[i].size();j++)

           t=vec2[i][j],ans[t]=min(ans[t],qry2(q[t].d)+q[t].a-q[t].b);

     }

     for (int i=;i<=m;i++) printf("%lld\n",ans[i]);

     return ;

 }

Newbarn 加点x，询问x在树上能走的最远距离

最远距离一定会走到直径端点。维护每棵树的直径（维护一条就够了）。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;

 int q,x,dep[N],fa[N][],id,bel[N],sc,Max,u[N],v[N],tmp;

 char s[];

 int lca(int x,int y)

 {

     if (dep[x]<dep[y]) swap(x,y);

     int del=dep[x]-dep[y];

     for (int i=;i>=;i--)

       if (del&(<<i)) x=fa[x][i];

     if (x==y) return x;

     for (int i=;i>=;i--)

       if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 int dis(int x,int y) {return dep[x]+dep[y]-*dep[lca(x,y)];}

 int main()

 {

     scanf("%d",&q);

     while (q--)

     {

         scanf("%s%d",s,&x);

         if (s[]=='B')

         {

             id++;

             if (x!=-)

             {

                 dep[id]=dep[x]+,fa[id][]=x; bel[id]=bel[x];

                 for (int j=;j<=;j++)

                   fa[id][j]=fa[fa[id][j-]][j-];

                 Max=dis(u[bel[id]],v[bel[id]]);

                 if (tmp=dis(id,u[bel[id]]),tmp>Max) Max=tmp,v[bel[id]]=id;

                 if (tmp=dis(id,v[bel[id]]),tmp>Max) Max=tmp,u[bel[id]]=id;

             }else bel[id]=++sc,u[sc]=v[sc]=id;

         }else printf("%d\n",max(dis(x,u[bel[x]]),dis(x,v[bel[x]])));

     }

     return ;

 }

Cow Gymnasts 求有多少个数组A任意位i都满足A[i]=sigma[A[i-j+1]>=j](i-j+1<=0时从N开始往下)？(1<=A[i]<=N)

关键点在发现循环节。大胆从最小位置x入手，设其值为m，则满足y=x(mod gcd(N,m)的位置y的值都为m。

同样也可以归纳证明，所有位置的值都<=m+1。（注意一个循环节中有一个m+1，那么就不会出现m）

枚举m，$Ans=\sum_{m=1}^{n-1}(2^{\gcd(n,m)}-1)+1$。m=n的情况只有可能全是m，故加1。

把gcd提出来，$Ans=\sum_{d|n}2^d*\varphi(N/d)-N+2-2^N$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod=1e9+;

 #define P pair<ll,int>

 ll n,ans,sum;

 map<ll,ll> Phi;

 vector<P> vec;

 ll ksm(ll x,ll y) {

     ll res=;

     while (y) {if (y&) res=res*x%mod; x=x*x%mod;y>>=;}

     return res;

 }

 void dvd(ll x)

 {

     for (int i=;i<=sqrt(x);i++)

       if (x%i==)

       {

           sum*=i-;int cnt=;x/=i;

           while (x%i==) x/=i,cnt++,sum*=i;

           vec.push_back(P(i,cnt));

       }

     if (x!=) vec.push_back(P(x,));

 }

 void dfs(ll x,int d,ll phi)

 {

     if (d==vec.size()) {Phi[x]=phi;return;}

     dfs(x,d+,phi);

     ll t=vec[d].first,sum=t-;

     for (int i=;i<=vec[d].second;i++)

     {

         x*=t;

         dfs(x,d+,phi*sum);

         sum*=t;

     }

 }

 int main()

 {

     scanf("%lld",&n);

     if (n==) return puts(""),;

     sum=;dvd(n);

     dfs(,,);ans=((-n-ksm(,n))%mod+mod)%mod;

     for (int i=;i<=sqrt(n);i++)

       if (n%i==){

           ans+=ksm(,i)*Phi[n/i]%mod; ans%=mod;

           if ((ll)i*i!=n) ans+=ksm(,n/i)*Phi[i]%mod,ans%=mod;

       }

     printf("%lld\n",ans);

     return ;

 }

巴特西

USACO18FEB Platinum

最新文章

热门文章