Codeforces Round #327 (Div2) A~E

CodeForces 591A

题意：在距离为L的两端A,B，相向发射魔法，a(以P1的速度)-->B,A<--b（以P2的速度）。假设a-->B，途中相遇，则返回到原点A<--a. 后又继续，a-->B,速度不变。

b亦是如此。求第二次相遇时a的位移。

思路：因为速度不变，所以第二次相遇地点与第一次相遇地点一样。

res= n/(Va+Vb)*Va

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int main()

 {

     double n,a,b;

     while(cin>>n>>a>>b)

         cout<<n/(a+b)*a<<endl;

     return ;

 }

CodeForces 591B

题意：给一个长度为n的字符串s，进行m (1 ≤ n, m ≤ 200 000)次操作。即：s: aba 操作m1:a b 则s变成：bab.求m次变换后的s.

思路：首先想到的是暴力模拟，但是n,m都是1e5，O(n*m)=1e10，会超时。

所以需要有技巧的暴力。

字符串由26个字母组成，每次操作我们只需将字母数组进行操作，保存下字母变换后的字母。最后扫一遍根据字母数组将s改过来就ok了

注意：处理字母变换后的字母时，每次需先找要变化的值，记录下标，最后再进行交换。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 char c[],s[];

 int n,m;

 int main()

 {

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

         c[i]=char('a'+i);

     while(~scanf("%d%d",&n,&m))

     {

         scanf("%s",s);

         char x[],y[];

         int p1,p2;

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

         {

             scanf("%s%s",x,y);

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

             {

                 if(c[i]==x[])

                     p1=i;

                 if(c[i]==y[])

                     p2=i;

             }

             c[p1]=y[];

             c[p2]=x[];

         }

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

             s[i]=c[s[i]-'a'];

         printf("%s\n",s);

     }

     return ;

 }

CodeForces 590A

题意：n个数字，只由0、1组成。数字进行0\1变换。

变换规则：1、首末数字保持不变B[1]=A[1],B[n]=A[n]

2、从左至右，第二个数A[i]开始，B[i]变成（A[i-1],A[i],A[i+1]）的中位数

A->B一直变换，求达到稳定状态，即不能再变的变换次数，并输出最终变换后的B[]数字。

案例解释：

Case 1： 4

         0 0 1 1
         A[1-4]={0,0,1,1}
         B[1]=A[1]，B[4]=A[4]  
         A[1]:0  A[2]:0  A[3]:1 中位数为0，所以B[2]=0
         A[2]:0  A[3]:1  A[4]:1 中位数为！，所以B[3]=1
           B[1-4]={0,0,1,1}
         A==B，所以无法变换

思路:每次都变换成中位数，最终要求是不变。

我们可发现连续两个0 0时第二个0不管右边为0还是1，该位都不会改变。1,1同理。

所以会发现：连续的0 或连续的1 都是肯定不会变的。

那么我们可以找到所有连续的0、1，在剩下的数字中进行变换。并且剩下的数字中每个数一定会变，0->1,1->0。

再仔细一点会发现：最接近连续部分的数进行一次变换后一定会与相邻连续数一样。每个不连续数区间每次变换后不连续数分别从两端各减1；

因此我们可以根据不连续数长度求变换次数。

变换次数=max{不连续区间长度}/2+max{不连续区间长度}%2;

例如：1 1 0 1 0 1 1 不连续区间长度为3 1 1 0 1 0 1 1 0 1 0 0 最大不连续区间长度=max(3,2)=3

变更后，可以根据数字所在区间的长度及位置计算变换次数，奇变偶不变。

因此可转换成一般的模拟题。

注意：在进行变换的时候要多加注意。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn=*1e5+;

 int b[maxn],c[maxn],n;

 int deal()

 {

     int maxlen=,maxx=-;

     int s,e,k;

     c[]=b[];c[n-]=b[n-];

     b[n+]=b[n]=b[n-];

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

     {

         if(b[i]==b[i-])

         {

             c[i-]=b[i];k=;

             e=i-;s=e-maxlen+;

             while(s<e)

             {

                 c[s]=abs(b[s]-(k%));

                 c[e]=abs(b[e]-(k%));

                 s++;e--,k++;

             }

             if(s==e)

                 c[s]=abs(b[s]-(k%));

         }

         while(i<=n&&b[i]==b[i-])

         {

             c[i]=b[i];

             i++;

             maxx=max(maxx,maxlen/+maxlen%);

             maxlen=;

         }

         if(i<=n&&b[i]!=b[i+])

             maxlen++;

         i++;

     }

     return maxx;

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         int g=;

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

             scanf("%d",&b[i]);

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

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

             if(g++)

                 printf(" %d",c[i]);

             else

                 printf("%d",c[i]);

         printf("\n");

     }

     return ;

 }

CodeForces 590B

题意：一个飞船从起始点（x1,y1）飞向目标点(x2,y2)，最大速度为V，方向不定，但是会刮风，风的速度向量在t前为（vx,vy），之后变为(Vx,Vy).现给定相应坐标以及速度大小，求从起始点飞向目标点最少需要多长时间。

思路：二分时间。枚举时间tt,求出在tt时间内，风力单独在起始点作用产生的新位置，作为新的起点，再单独求飞船在tt时间内是否能从新起点至目标点。直到找到精度范围内最小的tt.

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 double x1,y1,x2,y2,t,v,p1,q1,p2,q2;

 const double d=0.000001;

 double dis(double x1,double y1,double x2,double y2)

 {

     return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

 }

 bool solve(double tt)

 {

     double stx,sty;

     if(tt<=t)

     {

         stx=x1+p1*tt;

         sty=y1+q1*tt;

     }

     else

     {

         stx=x1+p1*t+p2*(tt-t);

         sty=y1+q1*t+q2*(tt-t);

     }

     double distance=dis(stx,sty,x2,y2);

     if(distance<=tt*tt*v*v)

         return ;

     return ;

 }

 int main()

 {

     while(~scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2))

     {

         scanf("%lf%lf%lf%lf%lf%lf",&v,&t,&p1,&q1,&p2,&q2);

         double L=,R=1e8,m;

         while((R-L)>d)

         {

             m=(R+L)/;

             if(solve(m))

                 R=m;

             else

                 L=m;

         }

         printf("%.18lf\n",m);

     }

     return ;

 }

CodeForces 590C

题意：在n*m的地图上，有三个州“1”，“2”，“3”，每个州是一个整体。除了州，“#”不可开拓道路，“."可开拓道路。求使三个州连通（任一州可到达另一州）最少需要多少个.“

思路：三个州之间的道路，一定会有一个公共点。所以只需要求每个州到该点的最短路径，进行相加。

BFS，记录每个州到每个点的最短路径。

技巧：把所有“1”放入队列后开始搜，同理对“2”，“3”进行一样的操作。

注意：记录路径的时候，到当位置的路径=到前一位置路径+（前一位置=='.') 最后ans=min(ans,f[0][i][j]+f[1][i][j]+f[2][i][j]+(mp[i][j]=='.'))

或者按平常的记录方法，ans=min(ans,f[0][i][j]+f[1][i][j]+f[2][i][j]+(mp[i][j]=='.')-2)

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int maxn=+;

 const int inf=1e7;

 int n,m,pre[][]={,,,,,-,-,};

 int f[][maxn][maxn];

 char mp[maxn][maxn];

 struct node

 {

     int x,y;

 }pos[maxn*maxn];

 void init()

 {

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

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

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

                 f[i][j][k]=inf;

 }

 bool judge(int xx,int yy)

 {

     if(xx<||xx>=n||yy<||yy>=m)

         return ;

     return ;

 }

 queue<node> q;

 void bfs(int c)

 {

     char ch=c+'';

     while(!q.empty())

         q.pop();

     node a,b;

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

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

             if(mp[i][j]==ch)

             {

                 a.x=i;a.y=j;

                 q.push(a);

                 f[c][i][j]=;

             }

     while(!q.empty())

     {

         a=q.front();

         q.pop();

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

         {

             int xx=a.x+pre[i][];

             int yy=a.y+pre[i][];

             if(!judge(xx,yy)||mp[xx][yy]=='#')

                 continue ;

             if(f[c][xx][yy]>f[c][a.x][a.y]+(mp[a.x][a.y]=='.'))

             {

                 f[c][xx][yy]=f[c][a.x][a.y]+(mp[a.x][a.y]=='.');

                 b.x=xx,b.y=yy;q.push(b);

             }

         }

     }

 }

 int deal()

 {

     int minn=inf;

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

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

             minn=min(minn,f[][i][j]+f[][i][j]+f[][i][j]+(mp[i][j]=='.'));

     return minn;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

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

             scanf("%s",mp[i]);

         init();

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

             bfs(i);

         int mm=deal();

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

     }

     return ;

 }

巴特西

Codeforces Round #327 (Div2) A~E

最新文章

热门文章