CH Round #58 - OrzCC杯noip模拟赛day2

时间：2024-01-04 13:49:44

A:颜色问题

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/颜色问题

题解：算一下每个仆人到它的目的地的时间取max即可

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1500000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,f[maxn],head[maxn];

 struct edge{int go,next;}e[maxn];

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     for1(i,n)

     {

         int x=read();

         e[i].go=i;e[i].next=head[x];head[x]=i;

         f[i]=inf;

     }

     for1(i,n)

     {

         int x=read();

         for(int j=head[x];j;j=e[j].next)

          {

              int y=e[j].go;

              if(y>=i)f[y]=min(f[y],y-i+);else f[y]=min(f[y],n-i+y+);

          }

     }

     int ans=;

     for1(i,n)ans=max(ans,f[e[i].go]);

     printf("%d\n",ans==inf?-:ans);

     return ;

 }

B：树的问题

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/树的问题

题解：如果x和y的LCA不是其中任意一个，那么答案显然是s[x]+s[y]，画一下图就知道

否则不妨设LCA(x,y)=x，则ans=n-（s[son[x]]-s[y]) 其中son[x]是 x 走向 y的第一个点，画一下图就可以知道。。。

而son[x]不能dfs求，只要把y倍增上去即可。需要思考一下。

具体看代码

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 300000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,head[maxn],tot,fa[maxn],s[maxn],f[maxn][],dep[maxn];

 struct edge{int go,next;}e[*maxn];

 inline void insert(int x,int y)

 {

     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;

     e[++tot].go=x;e[tot].next=head[y];head[y]=tot;

 }

 void dfs(int x)

 {

     s[x]=;

     for1(i,)

      if((<<i)<=dep[x])f[x][i]=f[f[x][i-]][i-];

      else break;

     for(int i=head[x],y;i;i=e[i].next)

      if(!dep[y=e[i].go])

       {

           dep[y]=dep[x]+;

           f[y][]=x;

           dfs(y);

           s[x]+=s[y];

       }

 }

 bool lca(int x,int y)

 {

     int ans=;

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

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

     for0(i,)

      if(t&(<<i))x=f[x][i];

     return x==y;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

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

     for1(i,n-)insert(read(),read());

     dep[]=;

     dfs();

     while(m--)

     {

         int x=read(),y=read();

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

         if(!lca(x,y))printf("%d\n",s[x]+s[y]);

         else

          {

             int t=dep[y]-dep[x]-,w=y;

             for0(i,)if(t&(<<i))w=f[w][i];

             printf("%d\n",n-(s[w]-s[y]));

          }

     }

     return ;

 }

C:比赛问题

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/比赛问题

题解：刚开始把题看简单了，直接一个n*m*k*k的DP。。。还感叹怎么这么水。。。

后来发现这k*k个方格的状态是有后效性的T_T

然后发现好像可以状压得70，但我感觉我写不出来或者写出来调不出来，然后就交了错误的程序弃疗了。。。

最后居然有40QAQ

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 150

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,k,x,y,xx,yy,f[maxn][maxn];

 bool a[maxn][maxn],b[maxn][maxn];

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();k=read();x=read();y=read();xx=read();yy=read();

     for1(i,k)for1(j,k)

     {

         char ch=' ';

         while(ch!=''&&ch!='')ch=getchar();

         a[i][j]=ch=='';

     }

     for1(i,n)for1(j,m)

     {

         char ch=' ';

         while(ch!='B'&&ch!='W')ch=getchar();

         b[i][j]=ch=='W';

     }

     memset(f,,sizeof(f));

     f[x][y]=;

     for1(i,k)

      for1(j,k)

       if(a[i][j]&&b[x+i-][y+j-])f[x][y]++;

     for2(i,x,xx)

      for2(j,y,yy)

       if(i!=x||j!=y)

        {

            int tmp=;

            for1(ii,k-)

             for1(jj,k)

              if(a[ii][jj]&&!a[ii+][jj]&&b[i+ii-][j+jj-])tmp++;

         for1(jj,k)if(a[k][jj]&&b[i+k-][j+jj-])tmp++;

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

            tmp=;

            for1(ii,k)

             for1(jj,k-)

              if(a[ii][jj]&&!a[ii][jj+]&&b[i+ii-][j+jj-])tmp++;

            for1(ii,k)if(a[ii][k]&&b[i+ii-][j+k-])tmp++;

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

         //cout<<i<<' '<<j<<' '<<f[i][j]<<endl;

        }

     printf("%d\n",f[xx][yy]);

     return ;

 }

相关文章