闲言

呜，AB还好，C卡了一会儿（由于题意理解错误），D可以做差sort做，却模拟做，还WA了一发。

痛，太痛了。

E，赛时卡住没做出，看一个题解，差不多，但又差好多（（

然后，从E->G，把G在赛时最后1minA了。

DEF代码附在后面

A

题意：

判断字符串s是不是 Timur的某个排列。

赛时思路：

先判断个数对不对，在把字母都插到set里。（很蠢）

思路：

读入后，sort，字符串判等。

B

题意：

B与G一样，判断两个字符串是否相等

思路：

直接把B改正G，判等。

C

题意：

三个人各写了n个各长度为3的字符串。

如果那个字符串另外两人没有写，得3分；

如果那个字符串有一个人和他一样，得1分。

求每个人的分数。

赛时思路：

将每个人的词，分别用set记录下来，再每次都判断有没有在另外两人里面。

思路：

每个人写了哪些词记录下来，那个词的次数++，之后直接用那个词的次数判断加分就好。

D

题意：

给定一条线与这条线人的朝向，sum为所有人按照他的朝向能看到的人的总和。在进行最多1~n次改变任意一人的朝向的操作后，改变后的sum最大为多少。

赛时思路：

模拟，双指针。

显而易见，在左边的朝右看，在右边的朝左看最大。

左右两边扫过来，哪个离边缘越近改那个。（最终为RRR...LLL）

思路：

计算每个点修改前后的差值（后-前），sort，从1~n改过去。

（当然，只改>0的）

*E

题意：

你有i个高宽分别为hi, wi的矩形，现给出hs, ws, hb, wb,求所有满足hs<hi<hb且ws<wi<wb的矩阵的hi*wi之和。

思路：

不难发现，大的矩形包含小的矩形，且包含小矩形包含的所有矩形。

值得注意的是，重合的矩形不形成覆盖关系。

我们尝试设计状态。

状态表示：

设f[i][j]为大小为i*j的矩形所包含的之和。

状态转移：

f[i][j] = f[i][j-1]+f[i-1][j] - f[i-1][j-1] + g[i-1][j-1];

最终的结果为fhb - fhb - fhs+1 + fhs+1。

*F

题意：

给你一张n*m的图，图中 .代表空，*代表占据，请问图中占据的点，是否可以用L形占满且L形直接不互相接触（不share一个点or边）

思路：

遍历一遍，把过程中的(i, j)作为L的相连两条边的顶点。

L后，把三点都标记上，再check这个L有没有和别的L相邻。（用set存点）

如果有，返回false，flag = true;

再者，遍历下来可能没有问题，但是，有零散的 *，所以，再遍历一遍，若找到没有标记的 *，则flag = true;

补充jls的做法。

并查集，先把所有十字相邻的相同的点合并。

再遍历一遍，若字符为 *，集合大小却不等于3，false；若字符为 *，大小为3，但是是竖向或者横向的3个，false。

再遍历，合并斜线一格的点相同的点，再判断集合大小是否为3

G

题意：

给出n，求长度为n，奇数位上的异或和与偶数位上的异或和相等的序列。

思路：

首先，容易发现，一旦我们得到不含0的奇数位的结果，在末尾加0就可以得到偶数位的结果。

然后，我们同样可以发现，连续的1~n（n为偶数），在n为4的倍数的时候，我们发现奇数的0号为，异或和结果为0。

我们稍加思索，试着把这些奇数都减1，发现是0~n-2的偶数。

所以，第一种情况的答案出现了。

当 n%4 == 0，答案为0~n-1的序列。

同时，因为0的加入对异或和没有影响，我们顺势得出，

当 n%4 == 3时，答案为1~n的序列。

我们再顺着考虑 n%4==1的情况。

因为前面得出 n%4 == 0的情况，我们不妨从这个情况出发，看看能不能加一个数，使得它成立。

经过思考，发现，在第一种情况考虑的连续奇数和偶数的关系是一般性的，为了添加一个数，我们自然想要它在第一种的基础上，那么这个数最好为0，对原情况没有影响，那么我们再把第一种情况的序列整体加2，显然仍然满足第一类的性质（异或和相等）。

当 n%4 == 1时，答案为0, 2~n的序列。

再考虑 n%4 == 2的情况。

不难发现，这时候，不能继续从第一种情况出发了，因为，从第一种情况出发的话，前面的异或和相等，而最后两个数不能相等，那异或和必然不等。

所以，我们不妨让前面的异或和不等，再用最后两个数进行调和，因为调和可能会使其等于前面的数，我们再在调和的基础上加上1<<t（比n大的2的次方）避免冲突。

为了简单起见，我这边就选择1~n-2作为前面不等的序列，最后再加上前面的异或和，使得奇数位与偶数位的异或和都为1<<t。

CODE

D-sol1

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n;
    cin >> n;
    string str;
    cin >> str;
    LL tres = 0;
    for (int i = 0; i < n; i++)
    {
      if (str[i] == 'L')
        tres += i;
      else
        tres += n - i - 1;
    }
    vector<LL> ans;
    LL l = 0, r = n - 1, mid = n / 2;
    while (ans.size() < n && (l < mid || r > mid - (n % 2 == 0)))
    {
      while (l < mid && str[l] == 'R')
        l++;
      while (r > mid - (n % 2 == 0) && str[r] == 'L')
        r--;
      int dl = l, dr = n - r - 1;
      if (l < mid && dl <= dr && str[l] != 'R')
      {
        str[l] = 'R';
        tres -= l, tres += n - l - 1;
      }
      else if (r > mid - (n % 2 == 0) && str[r] != 'L')
      {
        str[r] = 'L';
        tres -= n - r - 1, tres += r;
      }
      ans.emplace_back(tres);
    }
    for (LL &x : ans)
      cout << x << ' ';
    for (int i = 0; i < n - ans.size(); i++)
      cout << tres << ' ';
    cout << '\n';
  }
  return 0;
}

D-sol2

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<LL> ans(n + 1), dx(n);
    for (int i = 0; i < n; i++)
    {
      if (s[i] == 'L')
        ans[0] += i, dx[i] = (n - i - 1) - i;
      else
        ans[0] += n - i - 1, dx[i] = i - (n - i - 1);
    }
    sort(all(dx), greater<int>());
    for (int i = 1; i <= n; i++)
      ans[i] = ans[i - 1] + max(dx[i - 1], 0LL);
    for (int i = 1; i <= n; i++)
      cout << ans[i] << " \n"[i == n];
  }
  return 0;
}

E

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010;

int n, q;
LL f[N][N];

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    memset(f, 0, sizeof f);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
      int x, y;
      cin >> x >> y;
      f[x + 1][y + 1] += x * y;
    }
    for (int i = 0; i <= 1001; i++)
      for (int j = 0; j <= 1001; j++)
        f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
    while (q--)
    {
      int h1, w1, h2, w2;
      cin >> h1 >> w1 >> h2 >> w2;
      cout << f[h2][w2] - f[h2][w1 + 1] - f[h1 + 1][w2] + f[h1 + 1][w1 + 1] << '\n';
    }
  }
  return 0;
}

F

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int dxy[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
};
char g[55][55];
bool vis[55][55];

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    memset(vis, 0, sizeof vis);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
      cin >> g[i];
    bool flag = false;
    auto check = [&](int x, int y)
    {
      set<PII> s;
      for (int i = 0; i < 4; i++)
      {
        int j = (i + 1) % 4;
        int x1 = x + dxy[i][0], y1 = y + dxy[i][1];
        int x2 = x + dxy[j][0], y2 = y + dxy[j][1];
        if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
          continue;
        if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m)
          continue;
        if (g[x1][y1] == '*' && !vis[x1][y1] && g[x2][y2] == '*' && !vis[x2][y2])
        {
          vis[x][y] = vis[x1][y1] = vis[x2][y2] = true;
          s.insert({x, y});
          s.insert({x1, y1});
          s.insert({x2, y2});
          break;
        }
      }
      for (auto &p : s)
      {
        for (int i = -1; i <= 1; i++)
          for (int j = -1; j <= 1; j++)
          {
            if (!i && !j)
              continue;
            int x = p.first + i, y = p.second + j;
            if (x < 0 || x >= n || y < 0 || y >= m)
              continue;
            if (g[x][y] == '*' && s.find({x, y}) == s.end())
              return false;
          }
      }
      return true;
    };
    for (int i = 0; i < n; i++)
    {
      if (flag)
        break;
      for (int j = 0; j < m; j++)
        if (g[i][j] == '*' && !vis[i][j] && !check(i, j))
        {
          flag = true;
          break;
        }
    }
    for (int i = 0; i < n; i++)
    {
      if (flag)
        break;
      for (int j = 0; j < m; j++)
        if (g[i][j] == '*' && !vis[i][j])
        {
          flag = true;
          break;
        }
    }
    if (flag)
      cout << "NO\n";
    else
      cout << "YES\n";
  }
  return 0;
}