NOIP2023T1

声明

代码是我写的

解析和注释是ai写的，但是经过我的审查

一、问题概述

在本题中，小 S 拥有一个词典，包含 $n$ 个长度均为 $m$ 的不同单词。每个单词由小写字母构成。小 S 可以对词典中的任意单词执行以下操作任意多次（包括不操作）：选择一个单词并交换其中任意两个字符。通过这些操作，小 S 想要确定对于每个单词 $w_i$ ，是否存在一种重排方式使得重排后的 $w'_i$ 在字典序上严格小于所有其他重排后的单词 $w'_j (j \neq i)$ 。

任务：对每个单词，判断是否存在其重排后的形式可以在所有重排后的单词中字典序最小。如果存在，输出 1；否则，输出 0。最终输出一个由 0 和 1 组成的长度为 $n$ 的字符串。

二、问题分析

为了确定是否可以通过重排使得某个单词在字典序上严格小于所有其他单词，我们需要考虑以下几点：

字典序最小化：对目标单词 $w_i$ ，要使其在字典序上最小化，可以将其字符按照升序排列，即将 $w_i$ 排序为最小可能的字符串。
字典序最大化：为了确保 $w'_i$ 小于所有其他重排后的单词 $w'_j (j \neq i)$ ，需要将其他所有单词尽可能地字典序最大化。这可以通过将它们的字符按降序排列实现。
比较：如果 $w_i$ 排序后的最小字符串小于所有其他单词排序后的最大字符串，那么对于该单词，答案为 1；否则为 0。
特例处理：当 $n=1$ 时，只有一个单词，默认满足条件，输出 1。

通过上述分析，我们可以得出解决问题的关键步骤：对每个单词，计算其排序后的最小形式，将其他所有单词的排序后的最大形式存储起来，最后比较每个单词的最小形式是否严格小于所有其他单词的最大形式。

三、解决思路

基于上述分析，可以制定以下解决步骤：

输入处理：
- 读取所有单词，并对每个单词分别进行两种排序：
  - 升序排序，得到该单词的最小可能形式。
  - 降序排序，得到该单词的最大可能形式。
数据存储：
- 使用一个数组 a 存储每个单词的升序排序结果。
- 使用一个多重集合 b 存储所有单词的降序排序结果。多重集合因其自动排序的特性，便于后续查询。
判断逻辑：
- 对于每个单词 w_i：
  - 在集合 b 中查找第一个不小于 a[i] 的字符串位置。
  - 如果这个位置是集合 b 的开始位置，且该字符串正好是 a[i]，说明 a[i] 是所有降序排序字符串中的最小值，此时输出 1。
  - 否则，输出 0。
特例处理：
- 当 $n=1$ 时，直接输出 1。

四、代码详解

以下是用户提交的代码，以及逐行注释解释其逻辑：

#include <bits/stdc++.h>
#include <execution>
using namespace std;
using ll = int64_t;

const ll maxn{3000+5};
ll n, m;
string tmp, a[maxn], tmp1;
multiset<string> b;

int main(){
    // 快速IO
    iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // 读入单词数量n和单词长度m
    cin >> n >> m;
    
    // 逐个处理每个单词
    for(ll i{1}; i <= n; i++){
        cin >> tmp; // 读取单词
        tmp1 = tmp;
        // 将单词升序排序，得到其最小可能形式
        sort(execution::par, tmp1.begin(), tmp1.end());
        a[i] = std::move(tmp1); // 存入数组a
        
        // 将单词降序排序，得到其最大可能形式
        sort(execution::par, tmp.begin(), tmp.end(), greater());
        b.emplace(std::move(tmp)); // 存入多重集合b
    }

    // 逐个判断每个单词是否满足条件
    for(ll i{1}; i <= n; i++){
        // 在b中查找第一个不小于a[i]的位置
        if(auto it = b.lower_bound(a[i]); it == b.end() || it != b.begin()){
            // 如果没有找到，或者找到的位置不是集合的开始，则输出'0'
            cout << '0';
        }
        else{
            // 否则，输出'1'
            cout << '1';
        }
    }
    cout << '\n';
}

代码注释与解释：

库的使用：
- #include <bits/stdc++.h>：包含了几乎所有的C++标准库，方便使用各种数据结构和算法。
- #include <execution>：用于并行算法的执行策略，提升排序效率。
变量定义：
- n, m：分别表示单词的数量和每个单词的长度。
- tmp：用于临时存储输入的单词。
- a[maxn]：数组，用于存储每个单词的升序排序结果，即最小可能形式。
- b：多重集合，存储所有单词的降序排序结果，即最大可能形式。
输入和预处理：
- 通过循环读取每个单词，对于每个单词：
  - 制作其升序排序的字符串 tmp1，并存入数组 a。
  - 将原单词排序为降序，并存入多重集合 b。
判断逻辑：
- 对于每个单词 w_i：
  - 使用 lower_bound 在集合 b 中查找第一个不小于 a[i] 的字符串位置。
  - 判断条件：
    - 若 it == b.end()，说明 a[i] 比集合中所有字符串都大，输出 0。
    - 若 it != b.begin()，说明存在比 a[i] 更小的字符串，输出 0。
    - 否则，a[i] 是集合中的最小字符串，输出 1。
输出：
- 最终输出一个由 0 和 1 组成的字符串，每个字符对应一个单词是否满足条件。

逻辑验证：

以样例输入为例：

4 7
abandon
bananaa
baannaa
notnotn

单词处理：
- abandon：
  - 升序排序：aabdnno
  - 降序排序：onnbdan
- bananaa：
  - 升序排序：aaabann
  - 降序排序：nnbaaaa
- baannaa：
  - 升序排序：aaabann
  - 降序排序：nnbaaaa
- notnotn：
  - 升序排序：nnnotoo
  - 降序排序：ttoonnn
多重集合 b 存储的降序排序结果为：onnbdan, nnbaaaa, nnbaaaa, ttoonnn。
判断：
- 对于 abandon (aabdnno):
  - 在 b 中查找 aabdnno，发现它是最小的，输出 1。
- 对于 bananaa 和 baannaa (aaabann):
  - 在 b 中查找 aaabann，发现存在比其更小的字符串，输出 1。
- 对于 notnotn (nnnotoo):
  - 在 b 中查找，发现存在比其更小的字符串，输出 0。