CF1956E1 Nene vs. Monsters (Easy Version) 题解

FFTotoro · 2024-04-15 14:27:12 · 题解

考虑暴力。直接模拟是不可取的，因为会被 \ldots,0,1,V,\ldots 这种数据直接卡飞（其中 V 为 a 的值域）。

但是观察到对于两个相邻的怪兽 x 和 y（x 为攻击方），如果 a_x=0，那么 a_y 就永远不变；进而考虑 y 的攻击对象 z，如果 a_y 非 0 且不变，那么 z 必然在有限次操作内死亡。

于是考虑用这条性质减少操作——我们只需不断模拟使得序列中不存在三个相邻的 a_i 满足三者均非零；然后根据上面的性质，如果有两个相邻且均存活的怪兽，那么攻击方必活，防守方必死。

考虑该做法的时间复杂度。使用刚才卡暴力的方法（构造许多 a_i=1 且 a_{i+1}=V）卡这种做法，发现对于三个数，只能构造 a_i=1，a_{i+1}=\sqrt{V}，a_{i+2}=V 这样的数据能使操作轮数最多，为 \sqrt{V} 量级的。由于 Easy Version 里 V 很小，所以时间复杂度为 O(n\sqrt{V}) 的做法可以通过。

注意特判 n=2 的情况。

放代码（C++17）：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n),r;
    for(auto &i:a)cin>>i;
    if(n==2){
      while(a[0]&&a[1])
        a[1]=max(0,a[1]-a[0]),a[0]=max(0,a[0]-a[1]);
      if(a[1])cout<<"1\n2\n";
      else if(a[0])cout<<"1\n1\n";
      else cout<<"0\n\n";
      continue;
    } // 此时直接模拟即可
    while([&](){
      for(int i=0;i<a.size();i++)
        if(a[i]&&a[(i+1)%a.size()]&&a[(i+2)%a.size()])
          return true;
      return false;
    }()) // 判断序列是否合法
      for(int i=0;i<n;i++)
        a[(i+1)%n]=max(0,a[(i+1)%n]-a[i]);
    for(int i=0;i<n;i++)
      if(a[i]&&!a[(i+n-1)%n])r.emplace_back(i);
    cout<<r.size()<<'\n';
    for(int i:r)cout<<i+1<<' ';
    cout<<'\n';
  }
  return 0;
}