第二十次CCF计算机软件能力认证

数学专场

第一题：称检测点查询

解题思路：计算欧几里得距离

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;typedef pair<int , int> PII;
int n , x , y;
vector<PII>v;int main()
{cin >> n >> x >> y;for(int i = 1;i <= n;i ++){int a , b;cin >> a >> b;v.push_back({(a - x) * (a - x) + (b - y) * (b - y) , i});}sort(v.begin() , v.end());for(int i = 0;i < 3;i ++)cout << v[i].second << endl;return 0;
}

第二题：风险人群筛查

解题思路：

对于每一个记录一定是连续的，因此查询逗留的就是检查每一条数据有几个连续的点在矩阵中即可

对于每一个点使用线性规划直接检查是否在矩阵中即可

#include<iostream>using namespace std;const int N = 1010;
int n , k , t , xl , yl , xr , yr;
int x[N] , y[N];
int throu = 0 , stay = 0;bool in(int u)
{if(x[u] >= xl && x[u] <= xr && y[u] >= yl && y[u] <= yr) return true;return false;
}bool check() // 检查是否经过
{for(int i = 0;i < t;i ++)if(in(i)) return true;return false;
}bool check1() // 检查连续
{for(int i = 0;i < t;i ++){int j = i;while(j < t && in(j)) j ++;if(j - i >= k) return true;i = j;}return false;
}int main()
{cin >> n >> k >> t >> xl >> yl >> xr >> yr;while(n --){for(int i = 0;i < t;i ++)cin >> x[i] >> y[i];if(check()) throu ++;if(check1()) stay ++;}cout << throu << endl << stay << endl;return 0;
}

第三题：点亮数字人生

解题思路：

直接模拟（真的阴间的模拟90分）

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
#include<cstring>
#include<sstream>
#include<queue>using namespace std;typedef unordered_map<int , int> MPII;
typedef vector<int> VI;
typedef pair<int , int> PII;
const int N = 5010 , M = 1e6 + 10;
int h[M] , ne[M] , e[M] , idx = 0;
MPII input;
int n , m , t , q;
unordered_map<int , vector<int>>input_num , query;
bool st[M];
int in[M] , copy_in[M];
int res[M];struct Logic
{string logic;int cnt;VI w;
}nodes[M];inline int change_input(int u)
{return 5000 + u;
}inline void add(int a , int b)
{e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}inline bool check()
{queue<int>q;int cnt = 0;for(int i = 1;i <= n;i ++)if(!in[i]) q.push(i) , cnt ++;while(!q.empty()){int t = q.front();q.pop();for(int i = h[t];~i;i = ne[i]){int j = e[i];in[j] --;if(!in[j]) q.push(j) , cnt ++;}}return cnt == n;
}inline void init()
{memset(h , -1 , sizeof h);memset(ne , 0 , sizeof ne);memset(e , 0 , sizeof e);memset(copy_in , 0 , sizeof copy_in);idx = 0;input.clear();memset(st , 0 , sizeof st);input_num.clear() , query.clear();memset(in , 0 , sizeof in);for(int i = 1;i <= n;i ++)nodes[i].logic = "" , nodes[i].cnt = 0 , nodes[i].w.clear();
}inline int eval(int j)
{int ans = 0;int cnt = nodes[j].cnt;if(nodes[j].logic == "NOT") ans = nodes[j].w[0] ^ 1;else if(nodes[j].logic == "AND"){ans = 1;for(int i = 0;i < cnt;i ++)ans &= nodes[j].w[i];}else if(nodes[j].logic == "OR"){for(int i : nodes[j].w)ans |= i;}else if(nodes[j].logic == "XOR"){ans = nodes[j].w[0];for(int i = 1;i < cnt;i ++)ans ^= nodes[j].w[i];}else if(nodes[j].logic == "NAND"){ans = 1;for(int i : nodes[j].w)ans &= i;ans = ans ^ 1;}else{for(int i : nodes[j].w)ans |= i;ans = ans ^ 1;}return ans;
}inline void cal(int u)
{queue<PII>q;int copy[M];memcpy(copy , copy_in , sizeof copy_in);for(int i = 1;i <= m;i ++) q.push({input_num[u][i - 1] , change_input(i)});while(!q.empty()){auto t = q.front();q.pop();int x = t.first , y = t.second;for(int i = h[y];~i;i = ne[i]){int j = e[i];copy[j] --;nodes[j].w.push_back(x);if(!copy[j]){int ans = eval(j);res[j] = ans;q.push({ans , j});}}}
}int main()
{scanf("%d" ,&t);while(t --){init();scanf("%d %d" ,&m ,&n);getchar();for(int i = 1;i <= n;i ++){char s[N];// getline(cin , s);fgets(s , 2000 , stdin);stringstream ss(s);string str;ss >> str;string logic = str;ss >> str;int cnt = stoi(str);nodes[i].logic = logic;nodes[i].cnt = cnt;while(ss >> str) {if(str[0] == 'O') // 表示第 n 个器件的输出连接到此输入端{int x = stoi(str.substr(1));add(x , i);in[i] ++;copy_in[i] ++;}else // 表示第 m 个输入信号连接到此输入端{int x = stoi(str.substr(1));int y = change_input(x);add(y , i);copy_in[i] ++;if(!input[y]) input[y] = x; // 将输入端进行重新编号}}}scanf("%d" ,&q);for(int i = 0;i < q;i ++)for(int j = 1;j <= m;j ++){int x;scanf("%d" ,&x);input_num[i].push_back(x);}for(int i = 0;i < q;i ++){int x;scanf("%d" ,&x);for(int j = 0;j < x;j ++){int y;scanf("%d" ,&y);query[i].push_back(y);}}if(!check()) // 检查是否自环{puts("LOOP");continue;}for(int i = 0;i < q;i ++) {memset(res , 0 , sizeof res);cal(i);for(int j = 1;j <= n;j ++)nodes[j].w.clear();for(int p : query[i])printf("%d " ,res[p]);puts("");}}
}

第四题：星际旅行

解题思路：

根据AB直线到圆心的距离和三角形的三边关系可以

两种情况：

（1）当两点A、B构成的直线不经过圆，最短距离 |AB| 的直线距离

（2）当两点A、B构成的直线经过圆，我们连接A点和圆心O点，B点和圆心O点，可以构成一个三角形，使用余弦定理可以得到AB边所对的角的弧度，然后可以求出所对应的弧长。

import mathdef SLdist(x , y):w = len(x)ans = 0for i in range(w):ans += (x[i] - y[i]) ** 2return ans ** 0.5n , m = map(int , input().split())
r = int(input())
black = list(map(int , input().split()))
l , d , tangent = [] , [] , []
for _ in range(m):temp = list(map(int , input().split()))l.append(temp)ans = 0for i in range(n):ans += (temp[i] - black[i]) ** 2# 点到圆心的距离d.append(ans ** 0.5)# 切线长tangent.append((ans - r * r) ** 0.5)res = [0 for i in range(m + 10)]
for i in range(m):A = l[i]for j in range(i):B = l[j]a , b , c = d[i] , d[j] , SLdist(A , B)# 海伦公式p = (a + b + c) / 2h = ((p * (p - a) * (p - b) * (p - c)) ** 0.5)h = h * 2if h >= r * c or a * a + c * c <= b * b or b * b + c * c <= a * a:res[i] += cres[j] += ccontinuealpha1 = math.acos(r / a)alpha2 = math.acos(r / b)beta = math.acos((a * a + b * b - c * c) / (2 * a * b))alpha = beta - alpha1 - alpha2x = (a * a - r * r) ** 0.5 + (b * b - r * r) ** 0.5 + alpha * rres[i] += xres[j] += x
for i in range(m):print(f'{res[i]:.15f}')

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;const int N = 110, M = 2010;int n, m;
double R;
double o[N], p[M][N];
double d[M], rd[M];
double ans[M];inline double sqr(double x)
{return x * x;
}int main()
{scanf("%d%d%lf", &n, &m, &R);for (int i = 0; i < n; i ++ ) scanf("%lf", &o[i]);for (int i = 0; i < m; i ++ ){double s = 0;for (int j = 0; j < n; j ++ ){scanf("%lf", &p[i][j]);s += sqr(p[i][j] - o[j]);}d[i] = sqrt(s);rd[i] = sqrt(s - sqr(R));}for (int i = 0; i < m; i ++ )for (int j = 0; j < i; j ++ ){double s = 0;for (int k = 0; k < n; k ++ ) s += sqr(p[i][k] - p[j][k]);double c = sqrt(s), a = d[i], b = d[j];double p = (a + b + c) / 2;double area = sqrt(p * (p - a) * (p - b) * (p - c));double h = area * 2 / c;if (h >= R || sqr(b) >= sqr(a) + s || sqr(a) >= sqr(b) + s){ans[i] += c, ans[j] += c;continue;}double angle1 = acos((sqr(a) + sqr(b) - s) / (2 * a * b));double angle2 = acos(R / a);double angle3 = acos(R / b);double t = (angle1 - angle2 - angle3) * R + rd[i] + rd[j];ans[i] += t, ans[j] += t;}for (int i = 0; i < m; i ++ )printf("%.12lf\n", ans[i]);return 0;
}

第五题：密信与计数

int p = tr[t][i];if (!p) tr[t][i] = tr[ne[t]][i];else{ne[p] = tr[ne[t]][i];cnt[p] += cnt[ne[p]];q[ ++ tt] = p;}}}
}int main()
{cin >> n >> m;for (int i = 0; i < 26; i ++ )for (int j = 1; j <= n; j ++ ){string str;cin >> str;g[str[0] - 'a'][j] = {i, stoi(str.substr(1))};}string str;while (cin >> str){insert(str);strs.push_back(str);}build();f[0][0][1] = 1;for (int i = 0; i <= m; i ++ ){int sum = 0;for (int j = 0; j <= idx; j ++ )for (int k = 1; k <= n; k ++ ){if (!f[i][j][k]) continue;sum = (sum + f[i][j][k]) % MOD;for (auto& s: strs){if (i + s.size() > m) continue;bool flag = true;int x = j, y = k;for (auto c: s){int u = c - 'a';auto& t = g[u][y];x = tr[x][t.row];if (cnt[x]){flag = false;break;}y = t.next;}if (flag){auto& v = f[i + s.size()][x][y];v = (v + f[i][j][k]) % MOD;}}}if (i) printf("%d\n", sum);}return 0;
}