CSP202206

前言

CSP 2022-06 算法题解析

能力有限仅能做出前 3 题

归一化处理

链接：http://118.190.20.162/view.page?gpid=T148

时间限制：500ms
空间限制：512.0MB

问题描述

题目背景

在机器学习中，对数据进行归一化处理是一种常用的技术。将数据从各种各样分布调整为平均值为 0、方差为 1 的标准分布，在很多情况下都可以有效地加速模型的训练。

问题描述

题目背景在机器学习中，对数据进行归一化处理是一种常用的技术。将数据从各种各样分布调整为平均值为 0、方差为 1 的标准分布，在很多情况下都可以有效地加速模型的训练。问题描述这里假定需要处理的数据为 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

这组数据的平均值： \[ \bar{a} = \frac{a_1 + a_2 + \cdots + a_n}{n} \] 方差： \[ D(a) = \frac{1}{n} \sum_{i=1}^{n} \left( a_i - \bar{a} \right)^2 \] 使用如下函数处理所有数据，得到的 $n$ 个浮点数 $f(a_1), f(a_2), \cdots, f(a_n)$ 即满足平均值为 $0$ 且方差为 $1$： \[ f(a_i) = \frac{a_i - \bar{a} }{\sqrt{D(a)} } \]

输入格式

从标准输入读入数据。

第一行包含一个整数 $n$，表示待处理的整数个数。

第二行包含空格分隔的 $n$ 个整数，依次表示 $a_1, a_2, \cdots, a_n$。

输出格式

输出到标准输出。

输出共 $n$ 行，每行一个浮点数，依次表示按上述方法归一化处理后的数据 $f(a_1), f(a_2), \cdots, f(a_n)$。

样例输入

1 2	7 -4 293 0 -22 12 654 1000

样例输出

-0.7485510379073613
0.04504284674812264
-0.7378629047806881
-0.7966476369773906
-0.7057985054006686
1.0096468614303775
1.9341703768876082

样例解释

平均值：$\bar{a} \approx 276.14285714285717$

方差：$D(a) \approx 140060.69387755104$

标准差：$\sqrt{D(a)} \approx 374.24683549437134$

子任务

全部的测试数据保证 $n, \left | a_i \right | \le 1000$，其中 $\left | a_i \right |$ 表示 $a_i$ 的绝对值。

且输入的 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 满足：方差 $D(a) \ge 1$。

评分方式

如果你输出的每个浮点数与参考结果相比，均满足绝对误差不大于 $10^{-4}$，则该测试点满分，否则不得分。

提示

C/C++：建议使用 double 类型存储浮点数，并使用 printf("%f", x);$$' 进行输出。
Python：直接使用 print(x) 进行输出即可。
Java：建议使用 double 类型存储浮点数，可以使用 System.out.print(x); 进行输出。

问题解析

极其简单的模拟题

Python代码

def main():
    n = int(input())
    dat = list(map(float, input().split()))
    mean = sum(dat) / n
    deviation = (sum((a - mean) ** 2 for a in dat) / n) ** 0.5
    dat = list((a - mean) / deviation for a in dat)
    print(" ".join(map(str, dat)))
main()

运行结果

提交编号	用户名	姓名	试题名称	提交时间	代码长度	编程语言	评测结果	得分	时间使用	空间使用
*	*	*	归一化处理	09-09 12:45	257B	PYTHON	正确	100	31ms	8.089MB

C++代码

#include <bits/stdc++.h>
using namespace std;

int dat[5555];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &dat[i]);
    }
    double mean = .0, dev = .0;
    for (int i = 0; i < n; ++i) mean += dat[i];
    mean /= n;
    for (int i = 0; i < n; ++i) dev += pow(dat[i] - mean, 2);
    dev = pow(dev / n, 0.5);
    for (int i = 0; i < n; ++i) {
        printf("%f\n", (dat[i] - mean) / dev);
    }
    return 0;
}

运行结果

提交编号	用户名	姓名	试题名称	提交时间	代码长度	编程语言	评测结果	得分	时间使用	空间使用
*	*	*	归一化处理	09-09 13:08	466B	CPP14	正确	100	0ms	2.957MB

寻宝！大冒险！

链接：http://118.190.20.162/view.page?gpid=T147

时间限制：500ms
空间限制：512.0MB

问题描述

题目背景

暑假要到了。可惜由于种种原因，小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……

某天，小 P 获得了一张神秘的藏宝图。

问题描述

西西艾弗岛上种有 $n$ 棵树，这些树的具体位置记录在一张绿化图上。简单地说，西西艾弗岛绿化图可以视作一个大小为 $(L+1) \times (L+1)$ 的 $01$ 矩阵 $A$，地图左下角（坐标 $(0,0)$）和右上角（坐标 $(L,L)$）分别对应 $A[0][0]$ 和 $A[L][L]$。其中 $A[i][j]=1$ 表示坐标 $(i, j)$ 处种有一棵树，$A[i][j]=0$ 则表示坐标 $(i,j)$ 处没有树。换言之，矩阵 $A$ 中有且仅有的 $n$ 个 $1$ 展示了西西艾弗岛上 $n$ 棵树的具体位置。

传说，大冒险家顿顿的宝藏就埋藏在某棵树下。并且，顿顿还从西西艾弗岛的绿化图上剪下了一小块，制作成藏宝图指示其位置。具体来说，藏宝图可以看作一个大小为 $(S+1) \times (S+1)$ 的 $01$ 矩阵 $B$（$S$ 远小于 $L$），对应着 $A$ 中的某一部分。理论上，绿化图 $A$ 中存在着一处坐标 $(x, y)(0 \le x, y \le L-S)$ 与藏宝图 $B$ 左下角 $(0,0)$ 相对应，即满足：对 $B$ 上任意一处坐标 $(i,j)$（$0 \le i, j \le S$），都有 $A[x+i][y+j] = B[i][j]$。当上述条件满足时，我们就认为藏宝图 $B$ 对应着绿化图 $A$ 中左下角为 $(x,y)$、右上角为 $(x+S, y+S)$ 的区域。

实际上，考虑到藏宝图仅描绘了很小的一个范围，满足上述条件的坐标 $(x,y)$ 很可能存在多个。请结合西西艾弗岛绿化图中 $n$ 棵树的位置，以及小 $P$ 手中的藏宝图，判断绿化图中有多少处坐标满足条件。

特别地，藏宝图左下角位置一定是一棵树，即 $A[x][y] = B[0][0] = 1$，表示了宝藏埋藏的位置。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的三个正整数 $n$、$L$ 和 $S$，分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。

由于绿化图尺寸过大，输入数据中仅包含 $n$ 棵树的坐标而非完整的地图；即接下来 $n$ 行每行包含空格分隔的两个整数 $x$ 和 $y$，表示一棵树的坐标，满足 $0 \le x, y \le L$ 且同一坐标不会重复出现。

最后 $(S+1)$ 行输入小 P 手中完整的藏宝图，其中第 $i$ 行（$0 \le i \le S$）包含空格分隔的 $(S+1)$ 个 $0$ 和 $1$，表示 $B[S-i][0] \cdots B[S-i][S]$。 需要注意，最先输入的是 $B[S][0] \cdots B[S][S]$ 一行，$B[0][0] \cdots B[0][S]$ 一行最后输入

输出格式

输出到标准输出。

输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。

样例1输入

样例1输出

样例1解释

绿化图上 $(0,0)$、$(1,1)$ 和 $(2,2)$ 三处均可能埋有宝藏。

样例2输入

样例2输出

样例2解释

如果将藏宝图左下角与绿化图 $(3,3)$ 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

子任务

$40\%$ 的测试数据满足：$L \le 50$；

$70\%$ 的测试数据满足：$L \le 2000$；

全部的测试数据满足：$n \le 1000$、$L \le 10^9$ 且 $S \le 50$。

提示

实际测试数据中不包括答案为 $0$ 的用例。

问题解析

关键在于如何进行藏宝图和地图之间的快速匹配

因为地图太大了，所以对每个点逐一匹配肯定不用考虑，但对于 $70\%$ 的子任务这种简单方法是可以的
进一步考虑将藏宝图进行哈希，并用与藏宝图等大的块在地图中进行滚动哈希匹配，但地图太大了，这个想法同样只能通过 $70\%$ 的子任务而且设计哈希函数比前面的麻烦得多
注意到地图中最多有 1000 颗树且藏宝图 $S$ 仅仅才 50，且藏宝图左下角肯定有一颗树，所以我们可以以这颗树为锚点进行匹配，最多进行 $1000$ 次匹配，每次匹配代价为 $S^2$ 次，这个代价是可以接受的，这个想法的最大问题是如何保存地图使得快速确定地图中某个位置是否有树，显然，哈希表是很好的选择

PS: 地图是我们惯用的左下角为原点的坐标系，但矩阵的坐标系是与惯用坐标系上下对称的，为了方便不混淆，代码中的坐标系按照矩阵坐标系进行运算，这并不影响结果

运行结果

提交编号	用户名	姓名	试题名称	提交时间	代码长度	编程语言	评测结果	得分	时间使用	空间使用
*	*	*	寻宝！大冒险！	09-09 20:34	1.275KB	CPP14	正确	100	15ms	2.886MB
*	*	*	寻宝！大冒险！	09-09 16:52	960B	PYTHON	正确	100	125ms	8.074MB

Python代码

MOD = int(2e9) + 7

def loc2num(x, y):
    return x * MOD + y

def match(A, B, x, y, L):
    """在 (x, y) 进行地图匹配

    Args:
        A (set): 存储树的坐标的集合
        B (List): 藏宝图
        x (int): 坐标
        y (int): 坐标
    """
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if not 0 <= x + i <= L and 0 <= y + j <= L:
                return False
            true_loc = loc2num(x + i, y + j)
            if c == 1 and true_loc in A:
                continue
            elif c == 0 and true_loc not in A:
                continue
            else:
                return False
    return True

def main():
    n, L, S = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [list(map(int, input().split())) for _ in range(S + 1)]
    B.reverse()
    tree = {loc2num(x, y) for x, y in A}
    print(sum(match(tree, B, x, y, L) for x, y in A))
main()

C++代码

#include <cstdio>
#include <unordered_set>
using namespace std;

using ll = long long;

ll MOD = 2000000007;

int n, L, S;
int A[1007][2], B[55][55];
unordered_set<ll> tree;

void get_A() {
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &A[i][0], &A[i][1]);
    }
}

void get_B() {
    for (int i = 0; i <= S; ++i) {
        for (int j = 0; j <= S; ++j) {
            scanf("%d", &B[S - i][j]);
        }
    }
}

ll loc2num(int x, int y) {
    ll ans = x;
    return ans * MOD + y;
}

bool match(int x, int y) {
    for (int i = 0; i <= S; ++i) {
        for (int j = 0; j <= S; ++j) {
            int a = x + i, b = y + j;
            if (a < 0 || a > L || b < 0 || b > L) return false;
            ll key = loc2num(a, b);
            if (B[i][j] == 0 && tree.find(key) == tree.end())
                continue;
            else if (B[i][j] == 1 && tree.find(key) != tree.end())
                continue;
            else
                return false;
        }
    }
    return true;
}

int main() {
    scanf("%d %d %d", &n, &L, &S);

    get_A();
    get_B();

    for (int i = 0; i < n; ++i) {
        tree.emplace(loc2num(A[i][0], A[i][1]));
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (match(A[i][0], A[i][1])) ++cnt;
    }

    printf("%d", cnt);

    return 0;
}

角色授权

链接：http://118.190.20.162/view.page?gpid=T146

时间限制：5.0s
空间限制：512.0MB

问题描述

题目背景

为了响应国家发展新基建的倡议，西西艾弗岛上兴建了西西艾弗数据中心，并以此为基础运营了西西艾弗云。作为数据中心的运营和维护方，西西艾弗云公司十分重视西西艾弗云的网络安全管理工作。众所周知，安全性和便捷性难以兼得，同时，一个混乱的权限模型可能会导致人员被授予不必要的权限，从而造成安全风险。因此在西西艾弗云公司的网络安全部工作的小 C 专门设计了一种科学的权限模型。

这种安全模型将验证流程分为两个步骤。第一步是验证用户的身份（鉴别），第二步是验证用户的权限（授权）。在第一步，首先验证一个用户是否是该用户所声称的那个身份。例如，通过验证用户提供的口令（Password）是否正确，或者通过验证用户提供的智能卡是否合法有效。接下来，在授权的步骤中，权限策略会被检索以便判断来访的用户是否能够操作系统中的某个资源。

为了能够灵活地表达用户和授权之间的关系，西西艾弗云公司设计了一种简洁而灵活的授权模型：基于角色的授权模型。它的思路是：首先设定若干角色，每个角色中指明了一个清单，表明允许访问的资源的种类、资源的名称和对资源的操作；然后将被前一步骤已经鉴别过的用户和一个或多个角色相关联。某个用户能够执行的操作，即为与其关联的全部角色中允许的操作的并集。

小 C 将实现授权模型的工作交给了你，希望你能够把它们实现出来。

问题描述

用户表示授权模型中的一个已识别的主体，该识别过程由此前的鉴别过程完成。一个用户具有下列要素：

名称：是一个字符串，用于唯一标识一个用户；
用户组：是一个数组，包含若干个字符串，表示该用户所属的用户组。

一个待授权的行为，包括下列要素：

主体：是一个用户，包括试图进行该行为的用户的名称和该用户所属的用户组；
操作：是一个字符串，一般是一个动词，例如 Read、Open、Close 等；
资源：表示该行为的操作对象，由资源种类和资源名称描述。资源种类例如 Door、File 等；在一个特定的资源种类中，资源名称唯一确定了一个资源。

需要注意的是，一个待授权的行为的主体信息，即用户名称和所属用户组，是由前一步骤的鉴别过程完成的。因此，每次授权过程中，每个待授权的行为都会包含主体用户和其关联的用户组的信息。由于鉴权过程中的其它因素，同一个名称的用户在先后两次待授权的行为中所属的用户组可能有区别，不能存储或记忆此前每个待授权的行为中，用户与用户组的关联情况，而是要按照每次待授权的行为中给出的信息独立判断。

角色是这种授权模型的基本单位，它指明了一个用户可以执行的操作，角色的清单中描述了角色所允许的操作。一个角色包含下列要素：

名称，是一个字符串，用于唯一标识一个角色；
操作清单，是一个数组，包含一个或多个操作，表示该角色允许执行的操作集合；
资源种类清单，是一个数组，包含一个或多个资源种类，表示该角色允许操作的资源的种类集合；
资源名称清单，是一个数组，包含若干个资源名称，表示该角色允许操作的资源的名称集合。

判断一个角色能否对某个资源执行某个操作的过程是：

检查该角色的操作清单，如果该角色的操作清单中不包含该操作，且该角色的操作清单中也不包含字符串 *，那么不能执行该操作；
检查该角色的资源种类清单，如果该角色的资源种类清单中不包含该资源的种类，且该角色的资源种类清单中也不包含字符串 *，那么不能执行该操作；
检查该角色的资源名称清单，如果该角色的资源名称清单中不包含该资源的名称，且该角色的资源名称清单不是空数组，那么不能执行该操作；
允许执行该操作。

例如，假设有某个角色 Doorman，其允许执行的操作有 Open 和 Close，其允许操作的资源类型有 Door，其允许操作的资源名称有 FrontDoor 和 BackDoor。如果某用户与这个角色关联，那么该用户可以对名为 FrontDoor 的 Door 执行 Open 操作，但是不能对 BackDoor 的 Door 执行 Delete 操作。同时，一个角色能允许进行的操作可以用通配符来表示。例如，另有一个角色 Admin，其允许执行的操作有 *，允许操作的资源类型是 *，其允许操作的资源名称列表为空，那么与该角色关联的所有用户可以执行任何操作。值得注意的是，一个角色的操作清单，只能用允许列表的方式列举该角色允许进行的操作，而不能禁止角色进行某个操作。

角色关联指明了一个用户和一个或多个角色之间的关系。一个角色关联包含下列要素：

角色名称，是一个字符串，用于指明一个角色；
授权对象清单，是一个数组，包含一个或多个用户名称或者用户组名称，表示该角色关联的用户和用户组的集合。

判断一个用户能否执行某个操作的过程是：

检查所有的角色关联的授权对象清单，如果清单中包含该用户的名称，或者该清单中包含该用户所属的某一个用户组的名称，那么选取该角色关联所关联的角色；
对于所有被选取的角色，判断这些角色是否能对该资源执行该操作，如果所有角色都不能执行该操作，那么不能执行该操作；
允许执行该操作。

由此可见，一个角色关联可以将一个角色与多个用户或用户组关联起来。例如，如果有一个角色关联，其关联的角色名称为 Doorman，其关联的用户和用户组清单为用户 foo1、用户 foo2、用户组 bar。那么这些用户会与 Doorman 角色关联：

名为 foo1 的用户，属于用户组 bar；
名为 foo2 的用户，属于用户组 barz；
名为 foo3 的用户，属于用户组 bar 和 barz。

但是，属于用户组 barz 的名为 foo4 的用户不能与 Doorman 的角色关联。

从上述判断规则可以知道，一个用户可能与多个角色相关联，在这种情况下，该用户允许进行的操作是这些角色被允许进行的操作集合的并集。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n$、$m$、$q$，分别表示角色数量、角色关联数量和待检查的操作数量。

输入接下来的 $n$ 行中，每行表示一个角色，包括空格分隔的若干元素，依次为：

一个字符串，表示该角色的名称；
一个正整数 $nv$，表示操作清单中包含的操作数量；
$nv$ 个字符串，依次表示操作清单中的操作；
一个正整数 $no$，表示资源种类清单中包含的资源种类的数量；
$no$ 个字符串，依次表示资源种类清单中的资源种类；
一个非负整数 $nn$，表示资源名称清单中包含的资源名称的数量；
$nn$ 个字符串，依次表示资源名称清单中的资源名称。

输入接下来的 $m$ 行中，每行表示一个角色关联，包括空格分隔的若干元素，依次为：

一个字符串，表示该角色关联的角色名称；
一个正整数 $ns$，表示授权对象清单中包含的授权对象的数量；
$2ns$ 个字符串，每两个表示授权对象清单中的授权对象，前一个字符串为 u 或 g，分别表示这个授权对象是一个用户名称或者用户组名称，后一个字符串为用户名称或者用户组名称。

输入接下来的 $q$ 行中，每行表示一个待授权的行为，包括空格分隔的若干元素，依次为：

一个字符串，表示执行该操作的用户名称；
一个正整数 $ng$，表示该用户所属的用户组的数量；
$ng$ 个字符串，依次表示该用户所属的用户组的名称；
一个字符串，表示待查操作的名称；
一个字符串，表示被操作的资源种类；
一个字符串，表示被操作的资源名称。

输出格式

输出到标准输出。

输出 $q$ 行，每行表示一个操作是否可以被执行，0 表示不能执行，1 表示可以执行。

样例输入

1 2 3
op 1 open 1 door 0
op 1 g sre
op 1 u xiaop
xiaoc 2 sre ops open door room302
xiaop 1 ops open door room501
xiaoc 2 sre ops remove door room302

样例输出

1
2
3

1
1
0

样例解释

在本例中，定义了一个名为 op 的角色，授予了对任意 door 类型的对象的 open 操作的权限，同时定义了两个指向 op 的角色关联。注意，可以针对一个角色定义多于一个角色关联。本例给出了三个待授权的行为。其中，第一个行为，授权的主体用户是 xiaoc，该用户所属的用户组 sre 被关联 op 角色，因此可以执行开门动作。第二个行为中，授权的主体用户是 xiaop，该用户被直接关联了 op 角色，因此也可以执行开门动作。第三个行为中，授权的主体用户仍是 xiaoc，关联的角色仍为 op。但是，由于 op 角色并未被授予 remove 操作的权限，因此该动作被拒绝。

子任务

对于 20% 的数据，有 $n=m=1$，且给出的角色类似于题目正文中用于举例的 Admin，允许执行任何操作，且 $nv=no=ns=ng=1$、$nn=0$。

对于 40% 的数据，有 $1\le n, m \le 50$，且 $nv = no = ns = 1$、$ng \le 40$、$nn=0$。

对于 70% 的数据，有 $1\le n, m \le 50$，且 $nv, no, ns, ng \le 40$。

对于 100% 的数据，有：

$1\le n, m \le 500$；
$1\le q \le 5000$；
$1\le nv, no, ns, ng \le 400$；
$0\le nn \le 400$；
全部字符串或为 *，或仅包含大写字母、小写字母、数字（A-Za-z0-9），且字符数目不超过 10。

问题解析

大模拟题，难度在读题和理解题意，首先理顺思路

从背景和输出格式中，我们了解到，算法要实现的功能是判断给出的操作能否执行，在题目背景中，我们了解到其大致流程

用户不直接与操作是否可以执行相关联，而是使用了角色作为中转
所谓角色，我觉得可以认为是代理，用户执行操作需要委托代理进行操作，而每一种代理能执行哪些操作是已经固定的

而在描述中，我们了解到

已知条件：角色、角色关联、操作
目标：判断给出的操作是否可以执行

而具体对象有：

用户：名称、用户组
行为：主体（用户）、操作、资源
角色：名称、操作清单、资源种类清单、资源名称清单
关联：角色名称、授权对象清单

如何判断判断一个用户能否执行某个操作呢？

检查所有的角色关联的授权对象清单，如果清单中包含该用户的名称，或者该清单中包含该用户所属的某一个用户组的名称，那么选取该角色关联所关联的角色；
对于所有被选取的角色，判断这些角色是否能对该资源执行该操作
1. 检查该角色的操作清单，如果该角色的操作清单中不包含该操作，且该角色的操作清单中也不包含字符串 *，那么不能执行该操作；
2. 检查该角色的资源种类清单，如果该角色的资源种类清单中不包含该资源的种类，且该角色的资源种类清单中也不包含字符串 *，那么不能执行该操作；
3. 检查该角色的资源名称清单，如果该角色的资源名称清单中不包含该资源的名称，且该角色的资源名称清单不是空数组，那么不能执行该操作；
如果所有角色都不能执行该操作，那么不能执行该操作；
允许执行该操作。

总的来说，我们实现的内容其实也很简单，根据用户查找角色（代理），判断代理能否执行操作即可，关键是用户与角色之间的关系是通过关联来建模的，其中还有动态的用户组在其中。

因为我们的要求是根据用户查找角色，所以必须建立用户 $\rightarrow$ 角色以及用户组 $\rightarrow$ 角色的映射，随后遍历所有关联的角色判断是否可以执行操作。

运行结果

提交编号	用户名	姓名	试题名称	提交时间	代码长度	编程语言	评测结果	得分	时间使用	空间使用
*	*	*	角色授权	09-10 15:44	3.250KB	PYTHON	正确	100	4.296s	126.7MB

Python代码

from collections import defaultdict

class role:
    """ 角色, 包含 name, op, source_type, source_name 四个属性，name 是字符串其他三个都是集合 """
    def __init__(self, info: str):
        """ 解析 角色 的输入 """
        info = iter(info.split())

        self.name = next(info)
        nv = int(next(info))
        self.op = set(next(info) for _ in range(nv))
        no = int(next(info))
        self.source_type = set(next(info) for _ in range(no))
        nn = int(next(info))
        self.source_name = set(next(info) for _ in range(nn))

def get_role_link(info: str):
    """ 解析 角色关联 的输入 """
    info = iter(info.split())
    name = next(info)
    ns = int(next(info))
    group = [(next(info), next(info)) for _ in range(ns)]
    return name, group

def get_act(info: str):
    """ 解析 待授权的行为 的输入 """
    info = iter(info.split())
    user_name = next(info)
    ng = int(next(info))
    group = [next(info) for _ in range(ng)]
    op_name = next(info)
    source_type = next(info)
    source_name = next(info)
    return user_name, group, op_name, source_type, source_name

def get_role_list(roles: dict, users: dict, user_name: str, group: list):
    """ 获取用户及用户组对应的角色 """
    r = users["u_" + user_name]
    for g in group:
        r = r | users["g_" + g]
    for rr in r:
        yield roles[rr]

def check_op(r: role, op, source_type, source_name) -> bool:
    """ 判断角色能否执行某个操作 """
    # 1. 检查该角色的操作清单，如果该角色的操作清单中不包含该操作，且该角色的操作清单中也不包含字符串 `*`，那么不能执行该操作；
    if op not in r.op and '*' not in r.op:
        return False
    # 2. 检查该角色的资源种类清单，如果该角色的资源种类清单中不包含该资源的种类，且该角色的资源种类清单中也不包含字符串 `*`，那么不能执行该操作；
    if source_type not in r.source_type and '*' not in r.source_type:
        return False
    # 3. 检查该角色的资源名称清单，如果该角色的资源名称清单中不包含该资源的名称，且该角色的资源名称清单不是空数组，那么不能执行该操作；
    if source_name not in r.source_name and r.source_name:
        return False
    return True

def check_user(role_list, op_name, source_type, source_name) -> bool:
    """ 检测 role_list 中的角色能否执行操作 """
    return any(check_op(r, op_name, source_type, source_name) for r in role_list)

def main():
    # Get input
    n, m, q = map(int, input().split())
    # n 个角色
    roles = dict()
    for _ in range(n):
        r = role(input())
        roles[r.name] = r
    # m 个角色关联, 用哈希表做 用户/用户组 -> 角色 的映射
    users = defaultdict(set)
    for _ in range(m):
        role_name, group = get_role_link(input())
        for user in group:
            users["_".join(user)].add(role_name)
    # q 个行为
    for _ in range(q):
        user_name, group, op_name, source_type, source_name = get_act(input())
        if check_user(get_role_list(roles, users, user_name, group), op_name, source_type, source_name):
            print(1)
        else:
            print(0)

if __name__ == '__main__':
    main()

太麻烦了懒得码其他语言的代码了

光线追踪

链接：http://118.190.20.162/view.page?gpid=T145

时间限制：2.0s
空间限制：512.0MB

问题描述

光线追踪是计算机图形学领域的一个重要算法，其原理是追踪一束从光源发出的光，经过不同的反射面，最终到达摄像机处的过程。

在这道问题中，你需要实现一段程序来处理一个简易的光线追踪模型。

在平面中有一些反射面，为方便起见，我们设这些反射面都是线段，与坐标轴成 $45$ 度角摆放，且两个端点的坐标均为整数。为进一步简化问题，我们假设所有的反射表面都是镜面反射。任何一束光线照射到反射面上（为避免讨论，假设反射面不含端点）时，都会改变方向为相应的镜面反射方向。注意，反射面的两侧都可以反射光线。

平面中还有一些激光光源，每个光源位于一个坐标为整数的点上，会向某个水平或竖直的方向发射一定强度的激光。

所有的反射面都不是完美的，每个反射面有一个折损系数 $a$ ，当强度为 $I$ 的光线照射上去时，反射光线的强度会变成 $aI$ 。为了便于处理，你可以认为所有反射面的材质均不算太好也不算太糟，因此所有的 $a$ 均在 $0.2\sim0.8$ 的范围内。

在一些超高速摄影问题中，有时甚至连光速都要考虑在内。在这个问题中，我们不妨假设激光在 $1$ 单位时间内恰好移动 $1$ 单位距离。然而，超高速摄影带来的往往是采样精度的损失，因此对于一束激光，最终采样到的光线强度都是向下取整后的数值。特别地，当一束激光的强度小于 $1$ 时，认为其已经完全耗散。

问题的最开始，平面上没有反射面也没有光源。接下来你需要处理若干个操作，每个操作形如：

1 x1 y1 x2 y2 a：在平面上插入一个分别以 $(x1,y1)$ 和 $(x2,y2)$ 为端点，反射系数为 $a$ 的反射面，保证反射面与坐标轴成 $45$ 度角摆放，且不与先前已经存在、且还没有被删除的反射面在非端点处相交；另外受到渲染效率的影响，问题中的所有反射面的总长度（可以理解为所有的 $|x1-x2|$ 之和）不会太大。

2 k：删除第 $k$ 个操作插入的反射面，保证第 $k$ 个操作发生在当前操作之前且为一个插入操作，且这个反射面还没有被删除；

3 x y d I t：在 $(x,y)$ 位置放置一个光源，发射光线的方向为 $d$ ，强度为 $I$ ，求其所经 $t$ 时刻后光线到达的坐标以及采样得到的光线强度。其中 $d$ 的含义为：$d=0$ 表示沿 $x$ 坐标增加的方向，$d=1$ 表示沿 $y$ 坐标增加的方向，$d=2$ 表示沿 $x$ 坐标减小的方向，$d=3$ 表示沿 $y$ 坐标减小的方向。另外，保证光源不位于当前存在的某个反射面（不含端点）上。注意：如果 $t$ 时刻后光线刚好到达某个反射面，则其强度取反射后的强度。

输入格式

从标准输入读入数据。

第 $1$ 行，一个正整数 $m$ 表示操作的总数量。

接下来 $m$ 行，每行描述一个操作，格式如题目描述。

其中，除了所有的 $a$ 和 $I$ 以外的输入均为绝对值不超过 $10^9$ 的整数，其中 $k$ 和 $t$ 为正整数；$a$ 和 $I$ 均为小数点后不超过 $6$ 位的正实数，其中 $a$ 在 $0.2\sim0.8$之间， $I\leq 10^9$。

输出格式

输出到标准输出。

对于每个查询操作输出一行，$3$ 个整数，形如 x y I 表示激光最终到达的位置为 $(x,y)$ ，采样得到的光线强度为 $I$ 。特别地，如果采样到的光线强度为 $0$ （即光线已耗散），你也就无需关心最终到达的坐标，而只需要输出0 0 0即可。

题目数据保证，你可以在计算时直接使用 $64$ 位浮点数的运算和取整操作，而无需担心可能的精度误差问题。

样例输入

7
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5

样例输出

数据范围

测试点编号	$m \le$	特殊性质
$1\sim3$	$1000$	所有光线 $t\le 1000$ ，所有输入坐标的绝对值 $\le 1000$
$4\sim7$	$1000$	无
$8\sim10$	$10^5$	所有光线的 $t\le10$
$11\sim13$	$10^5$	所有 $1$ 操作在所有 $3$ 操作之前，且无 $2$ 操作
$14\sim16$	$10^5$	所有光线的 $I=1$
$17\sim20$	$10^5$	无

对于 $100\%$ 的数据，保证 $m\le10^5$ ，所有反射面的 $|x1−x2|$ 之和不超过 $3∗10^5$ 。

问题解析

将样例示意图画了一下(没画最后一条光线)

其实比较有疑惑的只有第二个操作，$k$ 到底表示的是什么，从示例中至少可以看出一定，$k$ 等于 $1$ 时删掉的是第 $1$ 个操作的反射面，这里的操作编号是从 $1$ 开始的。

其实不难看出因为反射面都是 $45$ 度的所有光线一定是沿坐标轴方向的，也就是所反射面起到了一个改变光线前进方向的作用，这是有规律可循的。

所以难点在于

如何判断光线在前进过程中会碰到哪些反射面，从数据范围 $10^5$ 可以看出，每次判断光线的运行时间复杂度必须控制在 $O(\log n)$
如何确定反射点，这个其实不是特别难，可以通过数学方法进行计算

其实不难看出反射面能反射光线的范围，就是一个十字型的区域，如下图所示

即对于某个方向来说，只要在一定区间内的光线都会碰到反射镜，但实际上我们的行为是反过来的，要通过判断光线是否在某个反射镜的区间内，这就要求我们建立一种可以进行区间查找的数据结构来存储反射镜

好吧，想不到了，看了下网上的解析

注意到题目中这么一句话：所有反射面的 $|x1−x2|$ 之和不超过 $3∗10^5$ ，考虑将所有反射点存下来然后光线直接利用二分查找来查询。按照这个思路，可以将反射面分为 "\", "/" 两种，我们使用有序结构（例如红黑树）对反射点进行存储，此时插入和查找的复杂度都是 $O(\log n)$ （但如果频繁进行大镜面的插入和删除的话还是有 TLE 风险的）

运行结果

提交编号	用户名	姓名	试题名称	提交时间	代码长度	编程语言	评测结果	得分	时间使用	空间使用
*	*	*	光线追踪	09-12 14:41	4.504KB	CPP14	错误	15	578ms	39.23MB
*	*	*	光线追踪	09-12 12:40	4.619KB	PYTHON	运行错误	0	31ms	7.820MB

Python

似乎 Python 环境不允许使用 sortedcontainers 所以会报错（推测，我本地Python 3.9 环境是可以通过样例的，但网上一些在线 Python3 环境会报运行错误），但是吧，手写红黑树实在是做不到🤦‍♀️

from sortedcontainers import SortedList
from collections import defaultdict

def get_mirror(info: list):
    """ 解析插入反射面 """
    info = iter(info)
    _ = next(info)
    x1, y1, x2, y2 = map(int, (next(info) for _ in range(4)))
    a = float(next(info))
    return (x1, y1), (x2, y2), a

def get_remove(info):
    """ 解析移除反射面 """
    two, k = info
    return int(k)

def get_light(info):
    """ 解析添加光源 """
    info = iter(info)
    _  = next(info)
    x, y, d = map(int, (next(info) for _ in range(3)))
    i = float(next(info))
    t = int(next(info))
    return (x, y), d, i, t

def add_mirror(step, points_x, points_y, points, mirrors, p1, p2, a):
    """ 添加反射面 """
    mirrors[step] = (p1, p2, a)
    x1, y1 = p1
    x2, y2 = p2
    mirror_type = (y2 - y1) // (x2 - x1)
    if x1 > x2:
        x1, x2 = x2, x1
    if (mirror_type == -1 and y1 < y2) or (mirror_type == 1 and y1 > y2):
        y1, y2 = y2, y1
    for x, y in zip(range(x1 + 1, x2), range(y1 + mirror_type, y2, mirror_type)):
        points_x[x].add(y)
        points_y[y].add(x)
        points[x][y] = (mirror_type, a)

def del_mirror(points_x, points_y, points, mirrors, k):
    p1, p2, a = mirrors[k - 1]
    x1, y1 = p1
    x2, y2 = p2
    mirror_type = (y2 - y1) // (x2 - x1)
    if x1 > x2:
        x1, x2 = x2, x1
    if (mirror_type == -1 and y1 < y2) or (mirror_type == 1 and y1 > y2):
        y1, y2 = y2, y1
    for x, y in zip(range(x1 + 1, x2), range(y1 + mirror_type, y2, mirror_type)):
        points_x[x].remove(y)
        points_y[y].remove(x)
        del points[x][y]

def search_x_right(points_y: dict, x: int, y: int):
    """ 沿着 x 增加方向前进的最近反射点 """
    cur: SortedList = points_y[y]
    if not cur:
        return None
    t = cur.bisect_left(x)
    if t >= len(cur):
        return None
    return cur[t]

def search_x_left(points_y: dict, x: int, y: int):
    """ 沿着 x 减小方向前进的最近反射点 """
    cur: SortedList = points_y[y]
    if not cur:
        return None
    t = cur.bisect_left(x) - 1
    if t == -1:
        return None
    return cur[t]

def search_y_down(points_x: dict, x: int, y: int):
    """ 沿着 y 减小方向前进的最近反射点 """
    cur: SortedList = points_x[x]
    if not cur:
        return None
    t = cur.bisect_left(y) - 1
    if t == -1:
        return None
    return cur[t]

def search_y_up(points_x: dict, x: int, y: int):
    """ 沿着 y 增加方向前进的最近反射点 """
    cur: SortedList = points_x[x]
    if not cur:
        return None
    t = cur.bisect_left(y)
    if t >= len(cur):
        return None
    return cur[t]

def start_light(points_x, points_y, points, p, d, i, t):
    x, y = p
    while True:
        # 完全耗散
        if i < 1:
            print(0, 0, 0)
            return
        if t <= 0:
            print(x, y, int(i))
        # 根据方向查找最近的反射点
        nx, ny = x, y
        if d == 0:
            nx = search_x_right(points_y, x, y)
        elif d == 1:
            ny = search_y_up(points_x, x, y)
        elif d == 2:
            nx = search_x_left(points_y, x, y)
        else:
            ny = search_y_down(points_x, x, y)
        # 不会遇到反射点，那么直接计算终点坐标即可
        if nx is None or ny is None or abs(nx - x) > t or abs(ny - y) > t:
            if d == 0:
                x += t
            elif d == 1:
                y += t
            elif d == 2:
                x -= t
            else:
                y -= t
            print(x, y, int(i))
            return
        mirror_type, a = points[nx][ny]
        t -= abs(nx - x) + abs(ny - y)
        i *= a
        x, y = nx, ny
        if mirror_type == 1:
            if d == 0:
                d = 1
            elif d == 1:
                d = 0
            elif d == 2:
                d = 3
            elif d == 3:
                d = 2
        else:
            if d == 0:
                d = 3
            elif d == 1:
                d = 2
            elif d == 2:
                d = 1
            elif d == 3:
                d = 0

def main():
    m = int(input())
    # 储存反射点的数据结构
    points_x, points_y = defaultdict(SortedList), defaultdict(SortedList)
    points = defaultdict(dict)
    mirrors = dict()
    for step in range(m):
        info = input().split()
        if info[0] == '1':
            add_mirror(step, points_x, points_y, points, mirrors, *get_mirror(info))
        elif info[0] == '2':
            del_mirror(points_x, points_y, points, mirrors, get_remove(info))
        else:
            start_light(points_x, points_y, points, *get_light(info))

if __name__ == '__main__':
    main()

C++

只得了 15 分姑且记录一下吧


#include <bits/stdc++.h>
using namespace std;

const int MAX_STEP = 100007, MAX_VAL = 2000000007;
int m;
unordered_map<int, set<int>> points_x, points_y;
unordered_map<int, unordered_map<int, int>> points;
int mirror[MAX_STEP][5];
double mirror_s[MAX_STEP];

inline void add_mirror(int step, int x1, int y1, int x2, int y2, double a) {
    int dtype = (y2 - y1) / (x2 - x1);
    mirror[step][0] = x1;
    mirror[step][1] = y1;
    mirror[step][2] = x2;
    mirror[step][3] = y2;
    mirror[step][4] = dtype;
    mirror_s[step] = a;
    if (x1 > x2) swap(x1, x2);
    if ((dtype == 1 && y1 > y2) || (dtype == -1 && y1 < y2)) swap(y1, y2);
    for (int x = x1 + 1, y = y1 + dtype; x < x2; ++x, y += dtype) {
        points_x[x].emplace(y);
        points_y[y].emplace(x);
        points[x][y] = step;
    }
}

inline void del_mirror(int step) {
    int x1 = mirror[step][0], y1 = mirror[step][1], x2 = mirror[step][2], y2 = mirror[step][3], dtype = mirror[step][4];
    if (x1 > x2) swap(x1, x2);
    if ((dtype == 1 && y1 > y2) || (dtype == -1 && y1 < y2)) swap(y1, y2);
    for (int x = x1 + 1, y = y1 + dtype; x < x2; ++x, y += dtype) {
        points_x[x].erase(y);
        points_y[y].erase(x);
    }
}

// 沿着 x 增加方向前进的最近反射点
inline int search_x_right(const int x, const int y) {
    auto& cur = points_y[y];
    if (cur.empty()) return MAX_VAL;
    auto nxt = cur.lower_bound(x);
    if (nxt == cur.end()) return MAX_VAL;
    return *nxt;
}

// 沿着 x 减小方向前进的最近反射点
inline int search_x_left(const int x, const int y) {
    auto& cur = points_y[y];
    if (cur.empty()) return MAX_VAL;
    auto nxt = cur.lower_bound(x);
    if (nxt == cur.begin()) return MAX_VAL;
    return *(--nxt);
}

// 沿着 y 增加方向前进的最近反射点
inline int search_y_up(const int x, const int y) {
    auto& cur = points_x[x];
    if (cur.empty()) return MAX_VAL;
    auto nxt = cur.lower_bound(y);
    if (nxt == cur.end()) return MAX_VAL;
    return *nxt;
}

// 沿着 y 减小方向前进的最近反射点
inline int search_y_down(const int x, const int y) {
    auto& cur = points_x[x];
    if (cur.empty()) return MAX_VAL;
    auto nxt = cur.lower_bound(y);
    if (nxt == cur.begin()) return MAX_VAL;
    return *(--nxt);
}

void start_light(int x, int y, int d, double i, int t) {
    while (true) {
        // printf("Before: %d %d %d %lf %d\n", x, y, d, i, t);
        // 完全耗散
        if (i < 1.) {
            printf("0 0 0\n");
            return;
        }
        if (t <= 0) {
            printf("%d %d %d\n", x, y, (int)i);
            return;
        }
        // 根据方向查找最近的反射点
        int nx = x, ny = y;
        if (d == 0)
            nx = search_x_right(x, y);
        else if (d == 1)
            ny = search_y_up(x, y);
        else if (d == 2)
            nx = search_x_left(x, y);
        else
            ny = search_y_down(x, y);
        // printf("mid: %d %d\n", nx, ny);
        // 不会遇到反射点，那么直接计算终点坐标即可
        if (abs(nx - x) > t || abs(ny - y) > t) {
            if (d == 0)
                x += t;
            else if (d == 1)
                y += t;
            else if (d == 2)
                x -= t;
            else
                y -= t;
            printf("%d %d %d\n", x, y, (int)i);
            return;
        }
        int step = points[nx][ny];
        int dtype = mirror[step][4];
        double a = mirror_s[step];
        t -= abs(nx - x) + abs(ny - y);
        i *= a;
        x = nx;
        y = ny;
        if (dtype == 1) {
            if (d == 0)
                d = 1;
            else if (d == 1)
                d = 0;
            else if (d == 2)
                d = 3;
            else if (d == 3)
                d = 2;
        } else {
            if (d == 0)
                d = 3;
            else if (d == 1)
                d = 2;
            else if (d == 2)
                d = 1;
            else if (d == 3)
                d = 0;
        }
        // printf("After: %d %d %d %lf %d\n", x, y, d, i, t);
    }
}

int main() {
    scanf("%d", &m);
    int k, x1, y1, x2, y2, x, y, d, t;
    double a, i;
    for (int step = 1; step <= m; ++step) {
        scanf("%d", &k);
        if (k == 1) {
            scanf("%d%d%d%d%lf", &x1, &y1, &x2, &y2, &a);
            add_mirror(step, x1, y1, x2, y2, a);
        } else if (k == 2) {
            scanf("%d", &k);
            del_mirror(k);
        } else {
            scanf("%d%d%d%lf%d", &x, &y, &d, &i, &t);
            start_light(x, y, d, i, t);
        }
    }
    return 0;
}

测试点编号	\(m \le\)	特殊性质
\(1\sim3\)	\(1000\)	所有光线 \(t\le 1000\) ，所有输入坐标的绝对值 \(\le 1000\)
\(4\sim7\)	\(1000\)	无
\(8\sim10\)	\(10^5\)	所有光线的 \(t\le10\)
\(11\sim13\)	\(10^5\)	所有 \(1\) 操作在所有 \(3\) 操作之前，且无 \(2\) 操作
\(14\sim16\)	\(10^5\)	所有光线的 \(I=1\)
\(17\sim20\)	\(10^5\)	无