当前位置:Gxlcms > mysql > SRM543Div2

SRM543Div2

时间:2021-07-01 10:21:17 帮助过:14人阅读

决定以后多做一些TC,即使做不了比赛,也要多做一些TC上的题,顺便写一些结题报告什么的。不过像我这种在Div2混的弱菜,也写不出什么高质量的结题报告,而且1000pt的题,我基本都不用看了,尽量把250和500的题写一下,1000的题目,能做出来的话就写一下。 25

决定以后多做一些TC,即使做不了比赛,也要多做一些TC上的题,顺便写一些结题报告什么的。不过像我这种在Div2混的弱菜,也写不出什么高质量的结题报告,而且1000pt的题,我基本都不用看了,尽量把250和500的题写一下,1000的题目,能做出来的话就写一下。

250:

题意:给一个字符串,由‘C’和‘V’组成,一个人只能从‘C’到‘V’,或者从‘V’到‘C’,且可以从任意一个‘C’到达另一个‘V’,但是走过的字母不能再走,也就是说一个字母只能走一次。问:最多能走多少个字母。

解法:其实是道水题了,字符串中的哪个字母少,便以哪个为起点,之后乘2加1就可以了。代码:

class EllysTSP
{
        public:
        int getMax(string places)
        {
            int i,j,k;
            int len = places.size();
            int sumv = 0,sumc = 0;
            for(i = 0;i < len;++i)
            {
                if(places[i] == 'V')
                {
                    sumv++;
                }
            }
            sumc = len - sumv;
            int flag = 0;
            if(sumc > sumv)
            {
                flag = 1;
            }
            else if(sumc < sumv)
            {
                flag = 0;
            }
            else
            {
                flag = 2;
            }
            if(flag == 1)
            {
                return sumv*2+1;
            }
            else if(flag == 0)
            {
                return sumc*2+1;
            }
            else
            {
                return len;
            }
        }
       // $TESTCODE$
};

500:

题意:题意较简单,就是给你两个数a和b,求a^(a+1)^(a+2)...^(b)的结果。

解法:由于数据范围比较大,普通方法肯定会超时。我们仔细观察可发现,如果前一个数是偶数,后一个数是奇数,且两个数相邻,则两个数异或后的结果为1。如:4和5异或结果为1,6和7异或结果为1.。。。。再仔细观察,发现,偶数个1异或后的结果为0,奇数个1异或后的结果为1,有了这两个结论,就可以做出来了,分清情况就可以了。

代码:

class EllysXors
{
        public:
        long long getXor(long long L, long long R)
        {
            int i,j,k;
            if(L == R) return L;
            else
            {
               if(L%2 && R%2)
               {
                  long long s = (R - L)/2;
                  long long k = L;
                  long long m = 0;
                  if(s % 2)
                  {
                      m = 1;
                  }
                  return k^m;
               }
               else if(L%2 && (!(R%2)))
               {
                   long long s = (R-L)/2;
                   long long k = L^R;
                   long long m = 0;
                   if(s % 2)
                   {
                       m = 1;
                   }
                   return k^m;
               }
               else if((!(L%2))&& (R%2))
               {
                   long long s = (R-L)/2+1;
                   long long k = 1;
                   long long m = 0;
                   if( (s-1)%2)
                   {
                       m = 1;
                   }
                   return k^m;
               }
               else if((!(L%2)) && (!(R%2)))
               {
                   long long s = (R-L)/2;
                   long long k = R;
                   long long m = 0;
                   if(s%2)
                   {
                       m = 1;
                   }
                   return k^m;
               }
            }
        }
        //$TESTCODE$
};

人气教程排行