NOIP2013Day1解题报告

时间：2022-09-22 04:16:11

　　本来今天晚上拿13年NOIP的题目来做一下，测测能够得多少分，结果一晚上把Day1写完竟然AK了，吼吼吼

　　D1T1，题目：http://codevs.cn/problem/3285/

　　很水的一道快速幂啊，题目竟然还刚好有0号节点来降低难度，记住对于转圈之后的位置要往取模方面想

　　ans=(x+m*10k)%n，原本是x号位置，每次往前走m个位置，共走了10k，最后再对于圈的大小取模即为最终位置

　　模意义下可变形，ans=x+m*10k%n=x+m*(10k%n)%n

　　其中10k%n不就是个快速幂取模吗？直接上模板：http://www.cnblogs.com/hadilo/p/5719139.html

　　简单AC

 // Copyright(c) Hadilo.All Rights Reserved.

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<ctime>

 #define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

 using namespace std;

 typedef long long LL;

 typedef double db;

 const long double CPS=CLOCKS_PER_SEC,TL=0.998;

 const int oo=;

 inline int read()

 {

     int re=;

     bool fu=;

     char ch=getchar();

     while ((ch>''||ch<'')&&ch!='-') ch=getchar();

     if (ch=='-')

     {

         fu=;

         ch=getchar();

     }

     while (ch>=''&&ch<='')

     {

         re=re*+ch-'';

         ch=getchar();

     }

     return fu?-re:re;

 }

 int n;

 inline int mi(LL a,int b)

 {

     LL k=;

     a%=n;

     while (b)

     {

         if (b&) k=k*a%n;

         b>>=;

         a=a*a%n;

     }

     return (int)k;

 }

 int main()

 {

     fre("circle");

     n=read();

     cout<<(read()*mi(,read())+read())%n<<endl;

     return ;

 }

　　D1T2，题目：http://codevs.cn/problem/3286/

　　其实看完题目我是先写的T3再写的T2，因为感觉这个不是太好证明

　　可伪证一下，把两个数组排序后对应位置即为最终答案，因为找不出反例而且感觉很正确

　　则对于两个数组a、b分别离散化一下，再记一个数组c[i]为b[i]离散化的值在a[i]中的位置

　　最后对 c 数组求逆序对即可，归并排序或树状数组都可以，我写的是归并排序

 // Copyright(c) Hadilo.All Rights Reserved.

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<ctime>

 #define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

 using namespace std;

 typedef long long LL;

 typedef double db;

 const long double CPS=CLOCKS_PER_SEC,TL=0.998;

 const int oo=,N=,mo=;

 inline int read()

 {

     int re=;

     bool fu=;

     char ch=getchar();

     while ((ch>''||ch<'')&&ch!='-') ch=getchar();

     if (ch=='-')

     {

         fu=;

         ch=getchar();

     }

     while (ch>=''&&ch<='')

     {

         re=re*+ch-'';

         ch=getchar();

     }

     return fu?-re:re;

 }

 struct gap

 {

     int x,num;

 };

 gap a[N];

 int b[N],c[N],p[N],ans;

 inline void gb(int l,int r)

 {

     if (l==r) return;

     int mid=(l+r)>>,i,j,top=;

     gb(l,mid);

     gb(mid+,r);

     for (i=l,j=mid+;i<=mid&&j<=r;)

     {

         if (c[i]<=c[j]) b[++top]=c[i++];

         else

         {

             b[++top]=c[j++];

             if ((ans+=mid-i+)>mo) ans-=mo;

         }

     }

     while (i<=mid) b[++top]=c[i++];

     while (j<=r) b[++top]=c[j++];

     for (;top;top--,r--) c[r]=b[top];

 }

 inline bool cmp(gap x,gap y)

 {

     return x.x<y.x;

 }

 int main()

 {

     fre("math");

     int i,n=read();

     for (i=;i<=n;i++) a[i]=(struct gap){read(),i};

     sort(a+,a+i,cmp);

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

     {

         b[a[i].num]=i;

         p[i]=a[i].num;

         a[i]=(struct gap){read(),i};

     }

     sort(a+,a+i,cmp);

     for (i=;i<=n;i++) c[a[i].num]=p[i];

     gb(,n);

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

     return ;

 }

　　D1T3，题目：http://codevs.cn/problem/3287/

　　题目要求路径上的所有边权的最小值最大

　　对于两点之间的路径，不就是走最大的那几个边可以保证答案最大

　　而在一棵树中是能保证图刚好连通的，做一颗最大生成树

　　然后对于每组询问直接倍增求LCA即可，记得统计路径上的边权最小值

 // Copyright(c) Hadilo.All Rights Reserved.

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<ctime>

 #define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

 using namespace std;

 typedef long long LL;

 typedef double db;

 const long double CPS=CLOCKS_PER_SEC,TL=0.998;

 const int oo=,N=,M=,L=,N2=;

 inline int read()

 {

     int re=;

     bool fu=;

     char ch=getchar();

     while ((ch>''||ch<'')&&ch!='-') ch=getchar();

     if (ch=='-')

     {

         fu=;

         ch=getchar();

     }

     while (ch>=''&&ch<='')

     {

         re=re*+ch-'';

         ch=getchar();

     }

     return fu?-re:re;

 }

 struct gap

 {

     int u,v,w;

 };

 gap e[M];

 int first[N],f[N][L],g[N][L],next[N2],v[N2],w[N2],d[N],fa[N],t;

 inline int log2(int x)

 {

     int k=-;

     while (x)

     {

         k++;

         x>>=;

     }

     return k;

 }

 inline int find(int x)

 {

     return fa[x]==x?x:fa[x]=find(fa[x]);

 }

 inline void dfs(int x,int last)

 {

     if (last) fa[x]=find(last);

     t=max(t,d[x]=d[last]+);

     f[x][]=last;

     for (int i=first[x];i;i=next[i])

         if (v[i]!=last)

         {

             g[v[i]][]=w[i];

             dfs(v[i],x);

         }

 }

 inline bool cmp(gap x,gap y)

 {

     return x.w>y.w;

 }

 int main()

 {

     fre("truck");

     int n=read(),m=read(),i,j,x,y,top=,ans;

     for (i=;i<=m;i++) e[i]=(struct gap){read(),read(),read()};

     sort(e+,e++m,cmp);

     for (i=;i<=n;i++) fa[i]=i;

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

     {

         x=find(e[i].u);

         y=find(e[i].v);

         if (x!=y)

         {

             fa[x]=y;

             top++;

             next[top]=first[v[top+n]=e[i].u];

             first[e[i].u]=top;

             next[top+n]=first[v[top]=e[i].v];

             first[e[i].v]=top+n;

             w[top]=w[top+n]=e[i].w;

         }

     }

     for (i=;i<=n;i++) fa[i]=i;

     for (i=;i<=n;i++) if (fa[i]==i) dfs(i,);

     t=log2(t);

     for (i=;i<=t;i++)

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

         {

             f[j][i]=f[f[j][i-]][i-];

             g[j][i]=min(g[j][i-],g[f[j][i-]][i-]);

         }

     m=read();

     while (m--)

     {

         x=read();

         y=read();

         if (find(x)==find(y))

         {

             ans=oo;

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

             for (i=log2(d[x]-d[y]);i>=;i--)

                 if (f[x][i]&&d[f[x][i]]>=d[y])

                 {

                     ans=min(ans,g[x][i]);

                     x=f[x][i];

                 }

             if (x==y)

             {

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

                 continue;

             }

             for (i=log2(d[x]);i>=;i--)

                 if (f[x][i]&&f[x][i]!=f[y][i])

                 {

                     ans=min(ans,min(g[x][i],g[y][i]));

                     x=f[x][i];

                     y=f[y][i];

                 }

             printf("%d\n",min(ans,min(g[x][],g[y][])));

         }

         else printf("-1\n");

     }

     return ;

 }

版权所有，转载请联系作者，违者必究

联系方式：http://www.cnblogs.com/hadilo/p/5932395.html

相关文章