9.1

闲话

做题纪要

9.2

闲话

做题纪要

牛客 NC278007 Wakey Wakey

• 手摸一下长度为 \(2\) 的区间发现只有两个数均相等才合法，进一步扩展可知当且仅当 \(a_{1}=a_{2}= \dots =a_{n}\) 才合法。

• 故 \(m \bmod p\) 即为所求。

  点击查看代码

  int main()
  {
      int t,n,m,p,i;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>n>>m>>p;
          cout<<m%p<<endl;
      }
      return 0;
  }
  

牛客 NC219949 会赢的！

• 走到终点需要 \(x+y\) 步，按照其奇偶性判断最终胜者。

• 如果某人在当前情况下无法取胜，那么在接下来的决策中一定会争取平局，使某一时刻所在点 \((i,j)\) 满足 \(i>x\) 或 \(j>y\) 即可，即当 \(|x-y|>1\) 时平局。

  点击查看代码

  int main()
  {
      int t,x,y,i;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>x>>y;
          if(x>=0&&y>=0)
          {
              if(abs(x-y)>1)
              {
                  cout<<"PING"<<endl;
              }
              else
              {
                  if((x+y)%2==1)
                  {
                      cout<<"YES"<<endl;
                  }
                  else
                  {
                      cout<<"NO"<<endl;
                  }
              }
          }
          else
          {
              cout<<"PING"<<endl;
          }
      }
      return 0;
  }
  

牛客 NC276193 好好好数

• \(n\) 是 \(k-\) 好数当且仅当 \(n\) 在 \(k\) 进制表示下各位都 \(\le 1\) 。

• 取 \(n\) 在 \(k\) 进制表示下数字最大的那一位即可。

• 每组询问时间复杂度为 \(O(\log_{k}p)\) ，需要特判 \(k=1\) 的情况。

  点击查看代码

  int main()
  {
      ll t,n,k,ans,i;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>n>>k;
          ans=1;
          if(k!=1)
          {
              while(n>0)
              {
                  ans=max(ans,n%k);
                  n/=k;
              }
          }
          cout<<ans<<endl;
      }
      return 0;
  }
  

牛客 NC277984 好好好数组

• 由题有 \(a_{i} \in [0,i)\) ，即已固定 \(a_{1}=0\) 。

• 手模样例发现至多有 \(3\) 个不同数字。

• 接着进行大力分讨。

  • 当有 \(1\) 个不同数字时，仅能构造出 \(\forall i \in [1,n],a_{i}=0\) ，故方案数为 \(1\) 。
  • 当有 \(2\) 个不同数字时，构造出的方案均形如 \(\begin{cases} \forall i \in [1,x),a_{i}=0 \\ \forall i \in [x,n],a_{i}=x \end{cases}\) ，其中 \(x \in [2,n]\) ，故方案数为 \(n-1\) 。
  • 当有 \(3\) 个不同数字时，仅能构造出 \(\begin{cases} a_{1}=0 \\ \forall i \in [2,n-1],a_{i}=1 \\ a_{n}=n \end{cases}\) ，故方案数为 \(1\) 。
  点击查看代码

  int main()
  {
      int t,n,m,i;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>n>>m;
          switch(m)
          {
              case 1:
                  cout<<n+1<<endl;
                  break;
              case 2:
                  cout<<n<<endl;
                  break;
              case 3:
                  cout<<1<<endl;
                  break;
              default:
                  cout<<0<<endl;
                  break;
          }
      }
      return 0;
  }
  

牛客 NC277688 随机化游戏时间？

• 静态区间第 \(k\) 大板子。

  点击查看代码

牛客 NC278058 随机化游戏时间！

CF1515E Phoenix and Computers

• 考虑预设性 \(DP\) 。
• 设 \(f_{i,j}\) 表示已经点亮了 \(i\) 盏灯，其中有 \(j\) 个手动点亮的连续段。
• 对第 \(i\) 个数填入的位置进行分讨。
  • 新开一段
  • 连接

CF704B Ant Man

luogu P9197 [JOI Open 2016] 摩天大楼

• 多倍经验： luogu P2612 [ZJOI2012] 波浪