题解：P7309 [COCI2018-2019#2] Kocka

wandereman · 2025-01-21 15:46:28 · 题解

思路

我们想要知道怎么成功，不如知道怎么失败，那么我们就把失败的情况列出来：

• 一条行或列有堵塞的记录，而另一条行或列没有，如下情况：

  if(l[i] != r[i] && (l[i] == -1 || r[i] == -1)){
  cout<<"NE"<<endl;
  return 0;
  }
  if(u[i] != d[i] && (u[i] == -1 || d[i] == -1)){
  cout<<"NE"<<endl;
  return 0;
  }

• 一边是空的，却把另一边堵塞的覆盖了，如下情况：

  if(l[i] + r[i] >= n){
  cout<<"NE"<<endl;
  return 0;
  }
  if(u[i] + d[i] >= n){
  cout<<"NE"<<endl;
  return 0;
  }

• 某一行的堵塞把另一行的堵塞覆盖了，如下情况：

  if(u[l[i] + 1] > i && d[l[i] + 1] > (n - i + 1){
  cout<<"NE"<<endl;
  return 0;
  }

  最后如果这些情况都不满足，就直接输出 DA。

  AC code

  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int N = 1e5+15;
  ll n;
  ll l[N],r[N],u[N],d[N];
  int main() {
  for(i = 1;i <= n;i++){
      cin>>l[i];
  }
  for(i = 1;i <= n;i++){
      cin>>r[i];
  }
  for(i = 1;i <= n;i++){
      cin>>u[i];
  }
  for(i = 1;i <= n;i++){
      cin>>d[i];
  }
  for(i = 1;i <= n;i++){
      if(l[i] + r[i] >= n){
          cout<<"NE"<<endl;
          return 0;
      }
      if(u[i] + d[i] >= n){
          cout<<"NE"<<endl;
          return 0;
      }
      if(l[i] != r[i] && (l[i] == -1 || r[i] == -1)){
          cout<<"NE"<<endl;
          return 0;
      }
      if(u[i] != d[i] && (u[i] == -1 || d[i] == -1)){
          cout<<"NE"<<endl;
          return 0;
      }
  
      if(u[l[i] + 1] > i && d[l[i] + 1] > (n - i + 1)){
          cout<<"NE"<<endl;
          return 0;
      }
  }
  cout<<"DA"<<endl;
  return 0;
  }