A. 检测点查询

题意

求$n$个点中距离关键点最近的三个点。
若距离相同，则取编号小的。
$3\le n\le 200,0\le |x|,|y|\le 200$

题解

分别记录最小值，次小值，第三小值即可。
时间复杂度$O(n)$

#include <bits/stdc++.h>
#define sqr(x) ((x) * (x))
using namespace std;
typedef pair<int, int> Pii;
int n;
struct Point { int x, y; } p, q;
Pii m1 = {INT32_MAX, 0}, m2 = m1, m3 = m1;
inline int dis2(Point a, Point b) { return sqr(a.x - b.x) + sqr(a.y - b.y); }
inline void Ins(Pii x) {
    if (x < m1) m3 = m2, m2 = m1, m1 = x;
    else if (x < m2) m3 = m2, m2 = x;
    else if (x < m3) m3 = x;
}
int main() {
    scanf("%d%d%d", &n, &q.x, &q.y);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &p.x, &p.y), Ins({dis2(p, q), i});
    printf("%dn%dn%d", m1.second, m2.second, m3.second);
    return 0;
}

B. 风险人群筛查

题意

给定一个矩形左下角和右上角的坐标。
有$n$个人，给定这$n$个人在$1\sim t$时刻的坐标。
求有多少人某时刻在出现矩形内；求有多少人至少连续$k$个时刻在矩形内（边界也算）。
$1\le n\le 20,1\le k\le t\le 10^3$

题解

第一问直接判断；第二问判断每个人在矩形内的最长连续时间是否大于等于$k$即可。
时间复杂度$O(nt)$

#include <bits/stdc++.h>
using namespace std;
int n, k, t, Ans1, Ans2;
struct Point {
    int x, y;
    inline void init() { scanf("%d%d", &x, &y); }
    inline bool operator<=(const Point b) { return x <= b.x && y <= b.y; }
} LD, RU, p;
int main() {
    scanf("%d%d%d", &n, &k, &t);
    LD.init(), RU.init();
    while (n--) {
        int flag = 0, maxL = 0, L = 0;
        for (int i = 1; i <= t; ++i) {
            p.init();
            if (LD <= p && p <= RU)
                flag = 1, ++L;
            else
                maxL = max(maxL, L), L = 0;
        }
        maxL = max(maxL, L);
        Ans1 += flag, Ans2 += maxL >= k;
    }
    printf("%dn%d", Ans1, Ans2);
    return 0;
}

C. 点亮数字人生

题意

给定一个包含$n$个节点的逻辑电路，每个节点有一个算符（$\mathrm{N}\mathrm{O}\mathrm{T},\mathrm{X}\mathrm{O}\mathrm{R},\mathrm{A}\mathrm{N}\mathrm{D},\mathrm{O}\mathrm{R},\mathrm{N}\mathrm{A}\mathrm{N}\mathrm{D},\mathrm{N}\mathrm{O}\mathrm{R}$），共有$m$个输入端，每个节点至多有$k$个输入源。
$S$组询问，给定所有$m$个输入源的输入值$0/1$和$s_o$个节点的编号$s_1,s_2,...,s_{s_o}$。
若逻辑电路存在环，则输出$\mathrm{L}\mathrm{O}\mathrm{O}\mathrm{P}$；否则对于每组询问，求出节点$s_1,s_2,...,s_{s_o}$的结果。
$Q$组数据。
$Q\le 5,n\le 500,k\le 5,m\le kn,S\le 10^4$
样例一对应的逻辑电路：

题解

根据输入的关系建立出相应的有向图（所有的输入源也当成一个点），利用拓扑排序直接求解即可。
时间复杂度$O(QS(n+m))$

#include <bits/stdc++.h>
using namespace std;
const int N = 3000 + 5;
typedef int arr[N];
int n, m, S, Cnt, Loop;
arr in, deg, op, Ans, s_;
vector<int> G[N], input[N];
vector<int> I_[10005];
inline int f(vector<int> input, int op) {
    int y = 0;
    if (!op) return !input[0]; // NOT
    else if (op == 1) {   // XOR
        for (auto x : input)
            y ^= x;
        return y;
    } else if ((op | 1) == 3) { // AND,NAND
        y = input[0];
        for (int i = 1; i < (int)input.size(); ++i)
            y &= input[i];
        return op & 1 ? !y : y;
    } else { // OR,NOR
        for (auto x : input)
            y |= x;
        return op & 1 ? !y : y;
    }
}
inline void Topsort() {
    if (Loop == 1)
        return;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        deg[i] = in[i], input[i].clear();
    for (int i = n + 1; i <= n + m; ++i)
        q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : G[u]) {
            input[v].push_back(Ans[u]);
            if (!(--deg[v]))
                Ans[v] = f(input[v], op[v]), q.push(v);
        }
    }
    if (Loop == -1) {
        for (int i = 1; i <= n; ++i)
            if (deg[i])
                return (void)(Loop = 1, puts("LOOP"));
        Loop = 0;
    }
    for (int i = 1; i <= Cnt; ++i)
        printf("%d%c", Ans[s_[i]], " n"[i == Cnt]);
}
inline int GetOP(char *s) {
    if (s[0] == 'O') return 4;
    if (s[0] == 'X') return 1;
    if (s[0] == 'A') return 2;
    if (s[1] == 'A') return 3;
    if (s[2] == 'T') return 0;
    return 5;
}
inline void Solve() {
    for (int i = 1; i <= n + m; ++i)
        in[i] = 0, G[i].clear();
    for (int i = 1; i <= n; ++i) {
        char s[5];
        int u;
        scanf("%s%d", s, &in[i]);
        op[i] = GetOP(s);
        for (int j = 1; j <= in[i]; ++j) {
            scanf("%s", s);
            if (s[0] == 'O')
                sscanf(s, "O%d", &u), G[u].push_back(i);
            else
                sscanf(s, "I%d", &u), G[n + u].push_back(i);
        }
    }
    Loop = -1;
    scanf("%d", &S);
    for (int i = 1; i <= S; ++i) {
        I_[i].resize(m);
        for (int j = 0; j < m; ++j)
            scanf("%d", &I_[i][j]);
    }
    for (int i = 1; i <= S; ++i) {
        for (int j = n + 1; j <= n + m; ++j)
            Ans[j] = I_[i][j - n - 1];
        scanf("%d", &Cnt);
        for (int j = 1; j <= Cnt; ++j)
            scanf("%d", s_ + j);
        Topsort();
    }
}
int main() {
    scanf("%*d");
    while (~scanf("%d%d", &m, &n))
        Solve();
    return 0;
}

D. 星际旅行

题意

给定一个半径为$r$的$n$维球体和$m$个$n$维点。
求每个点到剩下$m-1$个点的不穿过球体的最短距离之和。
$2\le n\le 100,2\le m\le 2000,1\le r\le 10^3,0\le |x|,|y|\le 10^3$

题解

考虑二维的情况

其中
$$\begin{array}{rl}{\theta }_1& =\angle OAC=\arcsin \frac{r}{|AO|}\\ {\theta }_2& =\angle OBD=\arcsin \frac{r}{|BO|}\\ {\theta }_3& =\angle AOB=\arccos \frac{|AO{|}^2+|BO{|}^2-|AB{|}^2}{2|AO||BO|}\\ {\theta }_4& =\angle COD={\theta }_3-(\frac{\pi }{2}-{\theta }_1)-(\frac{\pi }{2}-{\theta }_2)={\theta }_1+{\theta }_2+{\theta }_3-\pi \end{array}$$

则$dis(A,B)=\overline{AC}+\stackrel{⌢}{\mathrm{CD}}+\overline{BD}=\sqrt{|AO{|}^2-r^2}+\sqrt{|BO{|}^2-r^2}+r{\theta }_4$.
当线段$AB$与圆不相交时，依照上式计算出来的${\theta }_4<0$，判断一下即可。
注意常数，时间复杂度$O(n{m}^2)$

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5, M = 2e3 + 5;
const double Pi = acos(-1);
int n, m, r, r2;
double dis[M][M];
struct Point {
    int a[N];
    inline void init() {
        for (int i = 1; i <= n; ++i)
            scanf("%d", a + i);
    }
} O, p[M];
#define sqr(x) ((x) * (x))
inline int Len(Point a, Point b) {
    int L = 0;
    for (int i = 1; i <= n; ++i)
        L += sqr(a.a[i] - b.a[i]);
    return L;
}
int main() {
    scanf("%d%d%d", &n, &m, &r);
    O.init();
    r2 = r * r;
    for (int i = 1; i <= m; ++i)
        p[i].init();
    for (int i = 1; i <= m; ++i)
        for (int j = i + 1; j <= m; ++j) {
            double AO2 = Len(p[i], O), BO2 = Len(p[j], O), AB2 = Len(p[i], p[j]),
				   t1 = asin(r / sqrt(AO2)), t2 = asin(r / sqrt(BO2)),
                   t3 = acos((AO2 + BO2 - AB2) / (2 * sqrt(AO2 * BO2))),
                   t4 = t1 + t2 + t3 - Pi;
            if (t4 < 0)
                dis[i][j] = dis[j][i] = sqrt(AB2);
            else
                dis[i][j] = dis[j][i] = sqrt(AO2 - r2) + sqrt(BO2 - r2) + r * t4;
        }
    for (int i = 1; i <= m; ++i)
        printf("%.10lfn", accumulate(dis[i] + 1, dis[i] + m + 1, 0.0));
    return 0;
}

E. 密信与计数

简要题意

给你一个解码本和一堆单词。
求长度为k的密文：不包含单词为子串，且解密后的明文是由单词组成的。这样的字符串有多少种。

题解

大佬的口糊题解：

解码本一页很简单
n页就多记一维状态就好了
考虑一页的情况
先把字典翻译回去
得到不超过38个的密文串
对字典建ac自动机
对于ac自动机上每个节点
我们dp
如果走到终止节点就不转移

最后

以上就是迅速啤酒为你收集整理的第二十次CCF计算机软件能力认证A. 检测点查询B. 风险人群筛查C. 点亮数字人生D. 星际旅行E. 密信与计数的全部内容，希望文章能够帮你解决第二十次CCF计算机软件能力认证A. 检测点查询B. 风险人群筛查C. 点亮数字人生D. 星际旅行E. 密信与计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。