Codeforces Round #420 (Div. 2)

/******************************************************************************************************************

因为发现不敲题会变蠢...所以没事还是做两道题吧....

很久没做过题然后发现C和E全都是因为没用LL给卡住了...... 我真的是太蠢了

*******************************************************************************************************************/

A. Okabe and Future Gadget Laboratory

暴力判断就行了

 #include<stdio.h>

 #include<string.h>

 #include<iostream>

 using namespace std;

 int Map[][];

 int main()

 {

     int n;

     scanf("%d",&n);

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

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

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

     int Ans=;

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

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

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

      {

          int flag=;

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

          if(k!=i&&!flag)

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

           if(q!=j&&Map[i][q]+Map[k][j]==Map[i][j]&&!flag)

               flag=;

          if(!flag)

              Ans=;

      }

      printf("%s\n",Ans?"Yes":"No");

     return ;

 }

B. Okabe and Banana Trees

发现高度会很小,所以直接遍历高度,然后就是一个等差数列求前缀和了

 #include<stdio.h>

 #include<string.h>

 #include<iostream>

 using namespace std;

 #define LL long long

 LL Sum[];

 int main()

 {

     int m,b;

     scanf("%d%d",&m,&b);

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

     Sum[i]=Sum[i-]+i;

     LL Ans=;

     for(LL i=;i<=b;++i)

     {

         LL x=m*(b-i);

         LL tmp=;

         tmp+=(i+)*Sum[x];

         tmp+=(i*(i+))*(x+)/;

         Ans=max(Ans,tmp);

     }

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

     return ;

 }

C. Okabe and Boxes

这道题比较巧妙

暴力解法：(当然是不行滴

1.如果刚好能拿走就拿走

2.不能拿走我就排序

题目说肯定存在一个答案能满足条件,就说明在第i次remove的时候i一定在序列里

所以我们在remove的时候栈顶只有两种情况

1.刚好是我们需要的

2.是我们不需要的值(这时候就直接排序

然后我们考虑之前说过的条件,remove时候i一定在序列里,然后我们考虑把所有排过序的数字给标记一下(并不排序,只是标记一下

就有了第三种情况

3.遇到了我们标记过的值

这时候因为i一定在序列里,然后考虑比i小的全都remove走了,所以如果遇到了标记的说明这时候直接把i拿走就好了,因为这时候栈里面肯定全都是排好序的

然后我们就发现了栈的相对顺序是不变的,所以每次排序我们只需要标记栈顶的那个元素

然后说是要取i,其实就是假装i取取走了,其实还是在栈里

总的来说就是当delete的时候

1.如果刚好能拿走就拿走

2.不能拿走我就标记一下栈顶(假装排序

 #include<stdio.h>

 #include<string.h>

 #include<iostream>

 using namespace std;

 #define LL long long

 #define maxn 500005

 int stac[maxn];

 char str[];

 int main()

 {

     int n;

     int st=,ed=;

     scanf("%d",&n);

     int pos=,Ans=;

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

     {

         scanf("%s",str);

         if(str[]=='a')

         {

             int x;

             scanf("%d",&x);

             stac[ed++]=x;

         }

         else

         {

             pos++;

             if(stac[ed-]==pos)

             {

                 ed--;

                 continue;

             }

             else if(stac[ed-]==)

             {

                 continue;

             }

             else

             {

                 Ans++;

                 stac[ed-]=;

             }

         }

     }

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

     return ;

 }

D. Okabe and City

待补

E. Okabe and El Psy Kongroo

这道题第一眼递推,然后发现k有点大.然后发现n特别小,所以就很明显的按阶段来跑矩阵快速幂

f[i+1][j]=f[i][j-1] + f[i][j] + f[i][j+1]然后判断一下会不会溢出就好了,中间用个数组存放中间值,主要是害怕用到本来应该溢出的值

 #include<stdio.h>

 #include<string.h>

 #include<iostream>

 #include<algorithm>

 #include<math.h>

 #include<queue>

 #include<stack>

 #include<string>

 #include<vector>

 #include<map>

 #include<set>

 using namespace std;

 #define lowbit(x) (x&(-x))

 typedef long long LL;

 const int maxn = ;

 const int inf=(<<)-;

 #define Matrix_Size 20

 LL MOD=;

 int Size;

 struct Matrix

 {

     LL mat[Matrix_Size][Matrix_Size];

     void clear()

     {

         memset(mat,,sizeof(mat));

     }

     void output()

     {

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

         {

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

                 printf("%d ",mat[i][j]);

             printf("\n");

         }

     }

     Matrix operator *(const Matrix &b)const

     {

         Matrix ret;

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

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

             {

                 ret.mat[i][j] = ;

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

                 {

                     long long tmp = (long long)mat[i][k]*b.mat[k][j]%MOD;

                     ret.mat[i][j] = (ret.mat[i][j]+tmp);

                     if(ret.mat[i][j]>=MOD)

                         ret.mat[i][j] -= MOD;

                 }

             }

         return ret;

     }

 };

 Matrix pow_M(Matrix a,long long n)

 {

     Matrix ret;

     ret.clear();

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

         ret.mat[i][i] = ;

     Matrix tmp = a;

     while(n)

     {

         if(n&)ret = ret*tmp;

         tmp = tmp*tmp;

         n>>=;

     }

     return ret;

 }

 int S[];

 int main()

 {

     Matrix A,B;

     S[]=;

     LL n,k;

     scanf("%lld%lld",&n,&k);

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

     {

         LL st,ed,h;

         scanf("%lld%lld%lld",&st,&ed,&h);

         if(i==n)

             ed=k;

         Size=h+;

         B.clear();

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

         {

             B.mat[][j]=S[j];

         }    

         A.clear();

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

         {

             if(j>)

                 A.mat[j-][j]=;

             A.mat[j][j]=;

             if(j<h)

                 A.mat[j+][j]=;

         }

         A=pow_M(A,ed-st);

         B=B*A;

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

             S[j]=;

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

             S[j]=B.mat[][j];

     }

     printf("%d\n",B.mat[][]);

     return ;

 }

巴特西

Codeforces Round #420 (Div. 2)

最新文章

热门文章