Powered by:NEFU AB_IN

2021 ICPC网络赛第二场

J

• 题意

  

  有一个 n × n n×n n×n的房顶，每个位置都相当于会有个高为 h i , j h_{i,j} hi,j​的水杯，水往低处流。在高度为 0 0 0处为泄漏，问会泄露多少水

• 思路

  写个排序，高处的水优先往低处流，有 0 0 0就有答案，没 0 0 0没有答案

• 代码

  /*
   * @Author: NEFU AB-IN
   * @Date: 2021-09-25 14:08:39
   * @FilePath: \Contest\J.cpp
   * @LastEditTime: 2021-09-25 14:27:06
   */
  #include <bits/stdc++.h>
  using namespace std;
  const int N = 505;
  struct sa
  {
      int height;
      int x;
      int y;
  };
  bool cmp(const sa &a, const sa &b)
  {
      return a.height > b.height;
  }
  int n, m, cnt = 0, h[N][N];
  double a[N][N];
  sa b[N * N];
  int f(int x, int y)
  {
      if (x >= 1 && x <= n && y >= 1 && y <= n)
          return 1;
      return 0;
  }
  void add(int x, int y)
  {
      int sum = 0;
      if (f(x - 1, y) && h[x - 1][y] < h[x][y])
          sum++;
      if (f(x + 1, y) && h[x + 1][y] < h[x][y])
          sum++;
      if (f(x, y - 1) && h[x][y - 1] < h[x][y])
          sum++;
      if (f(x, y + 1) && h[x][y + 1] < h[x][y])
          sum++;
      double hh = a[x][y];
      if (f(x - 1, y) && h[x - 1][y] < h[x][y])
          a[x - 1][y] += hh / sum;
      if (f(x + 1, y) && h[x + 1][y] < h[x][y])
          a[x + 1][y] += hh / sum;
      if (f(x, y - 1) && h[x][y - 1] < h[x][y])
          a[x][y - 1] += hh / sum;
      if (f(x, y + 1) && h[x][y + 1] < h[x][y])
          a[x][y + 1] += hh / sum;
  }
  
  int main()
  {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
  
      cin >> n >> m;
      for (int i = 1; i <= n; i++)
      {
          for (int j = 1, x; j <= n; j++)
          {
              cin >> h[i][j];
              b[++cnt] = {h[i][j], i, j};
          }
      }
      sort(b + 1, b + 1 + cnt, cmp);
      memset(a, 0, sizeof(a));
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
              a[i][j] += m;
      for (int i = 1; i <= cnt; i++)
      {
          if (b[i].height == 0)
              break;
          add(b[i].x, b[i].y);
      }
      for (int i = 1; i <= n; i++)
      {
          for (int j = 1; j <= n; j++)
          {
              if (h[i][j] == 0)
                  printf("%.6f ", a[i][j]);
              else
                  printf("0 ");
          }
          printf("\n");
      }
      return 0;
  }
             

G

• 题意

  

• 思路

  一步步进行 t t t次洛必达即可，每次在循环里判断分子是否为 0 0 0，如果不为 0 0 0且不是最后一次洛必达，那么就是 i n f i n i t y infinity infinity

  

• 代码

  /*
   * @Author: NEFU AB-IN
   * @Date: 2021-09-25 12:11:45
   * @FilePath: \Contest\g.cpp
   * @LastEditTime: 2021-09-27 19:23:03
   */
  #include <bits/stdc++.h>
  using namespace std;
  #define LL long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                      \
      ios::sync_with_stdio(false); \
      cin.tie(0);                  \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  
  int n, t;
  const int N = 105;
  int a[N], b[N];
  
  signed main()
  {
      IOS;
      cin >> n >> t;
      for (int i = 1; i <= n; ++i)
      {
          cin >> a[i] >> b[i];
      }
      int fm = 1, now = 0;
      for (int i = 1; i <= t; ++i)
      {
          now = 0;
          fm *= i;
          if (i == 1)
          {
              for (int j = 1; j <= n; j++)
                  now = now + a[j] * b[j];
          }
          else if (i == 2)
          {
              for (int j = 1; j <= n; j++)
                  now = now + a[j] * b[j] * b[j] * (-1);
          }
          else if (i == 3)
          {
              for (int j = 1; j <= n; j++)
                  now = now + a[j] * b[j] * b[j] * 2 * b[j];
          }
          else if (i == 4)
          {
              for (int j = 1; j <= n; j++)
                  now = now + a[j] * b[j] * b[j] * (-6) * b[j] * b[j];
          }
          else
          {
              for (int j = 1; j <= n; j++)
                  now = now + a[j] * b[j] * b[j] * 24 * b[j] * b[j] * b[j];
          }
          if (now != 0 && i != t)
          {
              cout << "infinity" << endl;
              return 0;
          }
      }
      int gcd = __gcd(now, fm);
      fm /= gcd;
      now /= gcd;
      if (fm == 1)
          cout << now << '\n';
      else
          cout << now << "/" << fm << '\n';
      return 0;
  }
             

M

• 题意

  

• 思路

  • 如果 a [ i ] + b [ i ] = 1 a [ i ] + b [ i ] = 1 a[i]+b[i]=1，则 c [ i ] = 1 c [ i ] = 1 c[i]=1；
  • 如果 a [ i ] + b [ i ] = 2 a [ i ] + b [ i ] = 2 a[i]+b[i]=2，就要开始进位了，再来一层循环，从 j = i + 1 j = i + 1 j=i+1开始循环，
  • 如果 s i g n [ j ] = s i g n [ i ] sign [ j ] = sign [ i ] sign[j]=sign[i]，那么就像普通的二进制加法一样，该进位就进位，不该进位就不用进位，这里不再细谈。
  • 如果 s i g n [ j ] ≠ s i g n [ i ] sign[ j ] \ne sign [ i ] sign[j]​=sign[i]了，因为符号不同了，相当于出现了减法，不再是单纯的二进制加法，所以就要像十进制减法一样，我们考虑“借位”。

• 代码

  /*
   * @Author: NEFU AB-IN
   * @Date: 2021-09-27 16:57:43
   * @FilePath: \Contest\m1.cpp
   * @LastEditTime: 2021-09-27 17:07:39
   */
  #include <bits/stdc++.h>
  using namespace std;
  #define LL long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                      \
      ios::sync_with_stdio(false); \
      cin.tie(0);                  \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  
  const int N = 205;
  LL a[N], b[N], n, sg[N], c[N];
  
  void opt(LL c[])
  {
      for (int i = 0; i < n; ++i)
      {
          printf("%ld", c[i]);
          if (i != n - 1)
              putchar(' ');
      }
  }
  signed main()
  {
      cin >> n;
      for (int i = 0; i < n; ++i)
          cin >> sg[i];
      for (int i = 0; i < n; ++i)
          cin >> a[i];
      for (int i = 0; i < n; ++i)
          cin >> b[i];
  
      for (int i = 0; i < n; ++i)
      {
          c[i] += a[i] + b[i];
          while (c[i] >= 2)
          {
              c[i] -= 2;
              for (int j = i + 1; j < n; ++j)
              {
                  c[j] += 1;
                  if (sg[j] == sg[i])
                      break;
              }
          }
      }
      opt(c);
      return 0;
  }