Codeforces Round #553 (Div. 2)

A. Maxim and Biology

　　题意：

　　　　给出一个串s，问最少需要多少步操作使得串s包含"ACTG"这个子串，输出最少操作次数；

　　题解：

　　　　枚举每个位置 i，求出将 i,i+1,i+2,i+3 变为 "ACTG" 所需的最少操作次数即可；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define ll long long

 #define mem(a,b) memset(a,b,sizeof(a))

 int n;

 char s[];

 int Step(char x1,char x2)//求解x1变为x2所需的最少操作步骤

 {

     if(x1 <= x2)

         return min(x2-x1,x1-'A'+'Z'-x2+);

     else

         return min(x1-x2,'Z'-x1+x2-'A'+);

 }

 //求解以index位置开始使得其连续的四个字符变为"ACTG"所需的最小操作步骤

 int F(int index)

 {

     int ans=;

     ans += Step(s[index],'A');

     ans += Step(s[index+],'C');

     ans += Step(s[index+],'T');

     ans += Step(s[index+],'G');

     return ans;

 }

 int Solve()

 {

     int ans=INF;

     int len=strlen(s);

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

         ans=min(ans,F(i));

     return ans;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

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

     {

         scanf("%s",s);

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

     }

     return ;

 }

B. Dima and a Bad XOR

　　题意：

　　　　给出一个 n*m 的矩阵a[][]，每一行任选一个元素，判断选出的这 n 个元素的异或和是否大于0；

　　　　如果存在大于0的选法，输出 "TAK" ，并且输出每一行选择的元素的列标；

　　　　如果不存在，输出 "NIE"；

　　题解：

　　　　令 ans = a[1][1]^a[2][1]^........^a[n][1]；

　　　　①ans > 0 : 输出 n 个 1

　　　　②ans == 0 : 判断是否可以将a[1][1] 或 a[2][1] 或 ..... 或 a[n][1] 变成同一行的其他元素；

　　　　　　　　　如果可以，输出 "TAK"，并将任意一个a[ i ][1]变为同行中的其他元素；

　　　　　　　　　　反之，输出"NIE"；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int n,m;

 int a[][];

 int tmp[];

 bool isSat()//判断是否存在去重后的元素个数 > 1 的行

 {

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

     {

         /**

             如果想要从tmp[1]位置作为起始位置，第一个参数为tmp+1

             a[i]数组第一个位置的下标为a[i][1],所以第二个参数为a[i]+1

             第三个参数不是指数组个数，而是指要复制的数据的总字节数长度

         */

         memcpy(tmp+,a[i]+,m*sizeof(int));//将a[i]数组拷贝给tmp数组

         sort(tmp+,tmp+m+);

         int t=unique(tmp+,tmp+m+)-tmp;//去重

         t--;

         if(t > )

             return true;

     }

     return false;

 }

 void Solve()

 {

     int ans=;

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

         ans ^= a[i][];

     if(ans !=  || ans ==  && isSat())

     {

         printf("TAK\n");

         bool flag=(ans != );//如果ans != 0,输出n个1

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

         {

             if(!flag)

             {

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

                     if(a[i][j] != a[i][])

                     {

                         flag=true;//如果ans=0,找到第一个相异与a[i][1]的元素的列标即可

                         printf("%d ",j);

                         break;//记得break,不然，printf("%d ",j) 可能会调用多次

                     }

                 if(!flag)

                     printf("1 ");

             }

             else

                 printf("1 ");

         }

         printf("\n");

     }

     else

         printf("NIE\n");

 }

 int main()

 {

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

     {

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

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

                 scanf("%d",a[i]+j);

         Solve();

     }

     return ;

 }

C. Problem for Nazar

　　题意：

　　　　给定奇数集和偶数集；

　　　　现构造一个数组：

　　　　先取奇数集中 2⁰ 个元素1，再取偶数集中 2¹ 个元素2，4；

　　　　再取奇数集中 2²素 {3,5,7,9}，再取偶数集中 2³ 个元素 {6,8,10……}；

　　　　............

　　　　得到 {1,2,4,3,5,7,9,6,8,10,12……} ；

　　　　问这个数组的某一区间 [l,r] 的区间和是多少，并对1e9+7取模。

　　思路一：

　　　　分别求出区间[l,r]对应的 {oddS,oddE},{evenS,evenE}

　　　　oddS:区间[l,r]的第一个奇数

　　　　oddE:区间[l,r]的最后一个奇数

　　　　evenS,evenE同理；

　　　　(oddSum:{oddS,....,oddE}之间的奇数个数，evenSum同理)

　　　　最后输出ans%mod即可；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int mod=1e9+;

 ll l,r;

 ll fOdd(int x)///找2^x个连续的奇数开始的奇数

 {

     ll tot=((1ll*<<x)-)/;

     return +(tot<<);

 }

 ll fEven(int x)///找2^x个连续的偶数开始的偶数

 {

     ll tot=((1ll*<<x)-)/;

     return +(tot<<);

 }

 ll quickPower(ll _a,ll _b,ll _mod)

 {

     ll ans=;

     while(_b)

     {

         if(_b&)

             ans=ans*_a%mod;

         _a=(_a*_a)%mod;

         _b >>= ;

     }

     return ans;

 }

 ll Solve()

 {

     int x,y;

     for(x=;(1ll*<<(x+))- < l;++x);///包含l的最大的x

     for(y=;(1ll*<<(y+))- < r;++y);///包含r的最大的y

     ll oddS=!(x&)/**判断x是否为偶数*/ ? fOdd(x)+(l-(1ll*<<x))*:fOdd(x+);

     ll evenS=(x&)/**判断x是否为奇数*/ ? fEven(x)+(l-(1ll*<<x))*:fEven(x+);

     ll oddE=!(y&) ? fOdd(y)+(r-(1ll*<<y))*:fOdd(y+)-;

     ll evenE=(y&) ? fEven(y)+(r-(1ll*<<y))*:fEven(y+)-;

     ll ans=;

     if(oddE >= oddS)

     {

         ll n=((oddE-oddS)>>)+;

         ll d=oddE+oddS;

         ///被除数2可以将其约掉(d肯定为偶数)

         ///也可以用逆元进行除法取模

         ///我用的是逆元除法取模（有点麻烦）

         ans += ((n%mod)*(d%mod)%mod)*(quickPower(,mod-,mod))%mod;

     }

     if(evenE >= evenS)

     {

         ll n=((evenE-evenS)>>)+;

         ll d=evenE+evenS;

         ans += ((n%mod)*(d%mod)%mod)*(quickPower(,mod-,mod))%mod;

     }

     return ans%mod;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     scanf("%lld%lld",&l,&r);

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

     return ;

 }

　思路二：

　　　　前 i 个偶数的和为 i*(i+1)

　　　　前 i 个奇数的和为 i*i

　　　　求解出前 r 个奇数，偶数个数，求出答案

　　　　求解出前 l-1 个奇数，偶数个数，求出答案，两者做差便是最终答案

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int mod=1e9+;

 ll l,r;

 ll Solve(ll x)///分别求解出[1,x]中奇数个数，偶数个数

 {

     ll oddSum=;

     ll evenSum=;

     for(int i=;;i++)

     {

         if((1ll*<<(i+))- >= x)///包含x的最大的2^i

         {

             if(i&)

                 evenSum += (x-(1ll*<<i)+)%mod;

             else

                 oddSum += (x-(1ll*<<i)+)%mod;

             break;

         }

         if(i&)

             evenSum += (1ll*<<i)%mod;

         else

             oddSum += (1ll*<<i)%mod;

         evenSum %= mod;

         oddSum %= mod;

     }

     ///[1,x]的区间和

     return (evenSum%mod*(evenSum+)%mod%mod+oddSum%mod*(oddSum%mod)%mod)%mod;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     scanf("%lld%lld",&l,&r);

     ///注意，取模做减法有可能变成负值，需要再加个mod，再模一次mod

     printf("%lld\n",(Solve(r)-Solve(l-)+mod)%mod);

     return ;

 }

巴特西

Codeforces Round #553 (Div. 2)

最新文章

热门文章