当前位置: 首页 > news >正文

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

第一题:灰度直方图

解题思路:

哈希表即可

#include<iostream>
#include<cstring>using namespace std;const int N = 610;
int a[N];
int n , m , l;int main()
{memset(a , 0 , sizeof a);cin >> n >> m >> l;for(int i = 0;i < n;i ++)for(int j = 0;j < m;j ++){int x;cin >> x;a[x] ++;}for(int i = 0;i < l;i ++)cout << a[i] << " ";return 0;
}

第二题:邻域均值 

解题思路:

二维前缀和

#include<iostream>
#include<cstring>using namespace std;const int N = 610;
int s[N][N];
int n , l , r , t;int main()
{memset(s , 0 , sizeof s);cin >> n >> l >> r >> t;for(int i = 1;i <= n;i ++)for(int j = 1;j <= n;j ++){int x;cin >> x;s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + x;}int res = 0;for(int i = 1;i <= n;i ++)for(int j = 1;j <= n;j ++){int x1 = max(1 , i - r) , y1 = max(1 , j - r);int x2 = min(n , i + r) , y2 = min(n , j + r);int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);if(sum <= t * cnt) res ++;}cout << res << endl;return 0;
}

第三题:DHCP服务器

解题思路:

认真读题,题目描述的非常清楚更具题目进行求解即可,

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;int n , tdef , tmax , tmin;
string h; // 本机名称struct IP
{int st; // 0表示未分配、1表示待分配、2表示占用、3表示过期string owner; // 未分配状态没有占用者int t; // 待分配和占用状态拥有一个大于零的过期时刻
}ip[N];int get_ip_d(string c)
{for(int i = 1;i <= n;i ++)if(ip[i].owner == c) return i;return 0;
}int get_ip(int state)
{/*若没有,则选取最小的状态为未分配的 IP 地址若没有,则选取最小的状态为过期的 IP 地址*/for(int i = 1;i <= n;i ++)if(ip[i].st == state) return i;return 0;
}void update(string send)
{/*若不是,则找到占用者为发送主机的所有 IP 地址,对于其中状态为待分配的,将其状态设置为未分配,并清空其占用者,清零其过期时刻,处理结束*/for(int i = 1;i <= n;i ++)if(ip[i].owner == send) {if(ip[i].st == 1){ip[i].st = 0;ip[i].owner = "";ip[i].t = 0;}}
}void change(int tc)
{/*在到达该过期时刻时,若该地址的状态是待分配,则该地址的状态会自动变为未分配,且占用者清空,过期时刻清零;否则该地址的状态会由占用自动变为过期,且过期时刻清零。*/for(int i = 1;i <= n;i ++)if(ip[i].t && ip[i].t <= tc){if (ip[i].st == 1){ip[i].st = 0;ip[i].owner = "";ip[i].t = 0;}else{ip[i].st = 3;ip[i].t = 0;}}
}int main()
{cin >> n >> tdef >> tmax >> tmin >> h;int q;cin >> q;while(q --){// <发送主机> <接收主机> <报文类型> <IP 地址> <过期时刻>string send , get , type;int x , tc , te;cin >> tc >> send >> get >> type >> x >> te;if(get != h && get != "*") {// 判断接收主机是否为本机,或者为 *,若不是,则判断类型是否为 Request,若不是,则不处理;if(type != "REQ") continue; }// 若类型不是 Discover、Request 之一,则不处理if(type != "REQ" && type != "DIS") continue;// 若接收主机为 *,但类型不是 Discover,或接收主机是本机,但类型是 Discover,则不处理。if(get == "*" && type != "DIS" || get == h && type == "DIS") continue;change(tc);// discover 报文if(type == "DIS"){int k = get_ip_d(send);if(!k) k = get_ip(0);if(!k) k = get_ip(3);if(!k) continue;// 将该 IP 地址状态设置为待分配,占用者设置为发送主机ip[k].st = 1 , ip[k].owner = send;// 若报文中过期时刻为 0 ,则设置过期时刻为 t+tdefif(!te) ip[k].t = tc + tdef;else{int w = te - tc;w = min(w , tmax) , w = max(w , tmin);ip[k].t = w + tc;}cout << h << " " << send << " OFR " << k << " " << ip[k].t << endl;}else{if(get != h) {update(send);continue;}if(!(x <= n && x >= 1 && ip[x].owner == send)){cout << h << " " << send << " NAK " << x << " " << 0 << endl;continue;}// 无论该 IP 地址的状态为何,将该 IP 地址的状态设置为占用ip[x].st = 2;if (!te) ip[x].t = tc + tdef;else{int w = te - tc;w = max(w , tmin), w = min(w, tmax);ip[x].t = tc + w;}cout << h << " " << send << " ACK " << x << " " << ip[x].t << endl;}}return 0;
}

第四题:校门外的树

解题思路:

dp问题

设 f[i] 为用了前 i 个障碍点的所有方案

f[i]=(f[0]∗cnt1+f[1]∗cnt2+…+f[j]∗cnt3+…+f[i−1]∗cnt(i−1))

f[i] 在循环的时候已经计算出结果,计算cnt值为重中之重

cnt值,也就是两个位置之间可以整除的结果个数,也就是约数个数。

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>using namespace std;const int N = 1010 , M = 1e5 + 10 , mod = 1e9 + 7;
int n;
int a[N] , f[N];
unordered_map<int , vector<int>>mp;
bool st[M];int main()
{for(int i = 1;i < M;i ++)for(int j = i * 2;j < M;j += i)mp[j].push_back(i); // 枚举因数cin >> n;for(int i = 0;i < n;i ++) cin >> a[i];f[0] = 1;for(int i = 1;i < n;i ++){memset(st , 0 , sizeof st);for(int j = i - 1;j >= 0;j --){int d = a[i] - a[j] , cnt = 0;for(int k : mp[d])if(!st[k]){cnt ++;st[k] = true;}st[d] = true;f[i] = (f[i] + (long long)f[j] * cnt) % mod;}}cout << f[n - 1] << endl;return 0;
}

第五题:疫苗运输

迪杰斯特拉+扩展欧几里得算法(不会)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>#define x first
#define y secondusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 510;
const LL INF = 0x3f3f3f3f3f3f3f3fll;int n, m;
int len[N];
struct Node
{int cid, sum, pid;
};
vector<Node> ps[N];
vector<PII> line[N];  // x表示节点编号;y表示到下一个点的距离
LL dist[N], ans[N];
int pid[N];
bool st[N];LL exgcd(LL a, LL b, LL &x, LL &y)  // 扩展欧几里得算法, 求x, y,使得ax + by = gcd(a, b)
{if (!b){x = 1; y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}void dijkstra()
{memset(dist, 0x3f, sizeof dist);for (int i = 0; i < m; i ++ ){int d = 0;for (int j = 0; j < line[i].size(); j ++ ){if (line[i][j].x == 1){dist[i] = d;pid[i] = j;break;}d += line[i][j].y;}}for (int i = 0; i < m; i ++ ){int t = -1;for (int j = 0; j < m; j ++ )if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;st[t] = true;auto& l = line[t];auto d = dist[t];for (int j = pid[t], k = 0; k < l.size(); j = (j + 1) % l.size(), k ++ ){for (auto& c: ps[l[j].x]){if (st[c.cid]) continue;  // 优化很重要LL a = d, b = len[t];LL x = c.sum, y = len[c.cid];LL X, Y;LL D = exgcd(b, y, X, Y);if ((x - a) % D) continue;X = (x - a) / D * X;y /= D;X = (X % y + y) % y;if (dist[c.cid] > a + b * X){dist[c.cid] = a + b * X;pid[c.cid] = c.pid;}}d += l[j].y;}}
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < m; i ++ ){int cnt, sum = 0;scanf("%d", &cnt);for (int j = 0; j < cnt; j ++ ){int ver, t;scanf("%d%d", &ver, &t);ps[ver].push_back({i, sum, j});line[i].push_back({ver, t});sum += t;}len[i] = sum;}dijkstra();memset(ans, 0x3f, sizeof ans);for (int i = 0; i < m; i ++ ){if (dist[i] == INF) continue;LL d = dist[i];for (int j = pid[i], k = 0; k < line[i].size(); j = (j + 1) % line[i].size(), k ++ ){int ver = line[i][j].x;ans[ver] = min(ans[ver], d);d += line[i][j].y;}}for (int i = 2; i <= n; i ++ )if (ans[i] == INF) puts("inf");else printf("%lld\n", ans[i]);return 0;
}

 

相关文章:

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

第一题&#xff1a;灰度直方图 解题思路&#xff1a; 哈希表即可 #include<iostream> #include<cstring>using namespace std;const int N 610; int a[N]; int n , m , l;int main() {memset(a , 0 , sizeof a);cin >> n >> m >> l;for(int …...

Go语言基础之基本数据类型

Go语言中有丰富的数据类型&#xff0c;除了基本的整型、浮点型、布尔型、字符串外&#xff0c;还有数组、切片、结构体、函数、map、通道&#xff08;channel&#xff09;等。Go 语言的基本类型和其他语言大同小异。 基本数据类型 整型 整型分为以下两个大类&#xff1a; 按…...

Linux Tracing Technologies

目录 1. Linux Tracing Technologies 1. Linux Tracing Technologies Linux Tracing TechnologieseBPFXDPDPDK...

iOS自定义下拉刷新控件

自定义下拉刷新控件 概述 用了很多的别人的下拉刷新控件&#xff0c;想写一个玩玩&#xff0c;自定义一个在使用的时候也会比较有意思。使应用更加的灵动一些&#xff0c;毕竟谁不喜欢各种动画恰到好处的应用呢。 使用方式如下&#xff1a; tableview.refreshControl XRef…...

Springboot写单元测试

导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><exclusions><exclusion><groupId>org.junit.vintage</groupId><artifactId>junit-vintag…...

一篇文章教你使用Docker本地化部署Chatgpt(非api,速度非常快!!!)及裸连GPT的方式(告别镜像GPT)

本地搭建ChatGPT&#xff08;非api调用&#xff09; 第一种方法&#xff1a;使用Docker本地化部署第一步&#xff0c;下载安装Docker登录GPT 第二种方法&#xff1a;不部署项目&#xff0c;直接连接 第一种方法&#xff1a;使用Docker本地化部署 这种方法的好处就是没有登录限…...

前馈神经网络dropout实例

直接看代码。 &#xff08;一&#xff09;手动实现 import torch import torch.nn as nn import numpy as np import torchvision import torchvision.transforms as transforms import matplotlib.pyplot as plt#下载MNIST手写数据集 mnist_train torchvision.datasets.MN…...

Android DataStore:安全存储和轻松管理数据

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览三、使用3.1 Preferences DataStore添加依赖数据读…...

opencv进阶12-EigenFaces 人脸识别

EigenFaces 通常也被称为 特征脸&#xff0c;它使用主成分分析&#xff08;Principal Component Analysis&#xff0c;PCA&#xff09; 方法将高维的人脸数据处理为低维数据后&#xff08;降维&#xff09;&#xff0c;再进行数据分析和处理&#xff0c;获取识别结果。 基本原理…...

The internal rate of return (IRR)

内部收益率 NPV(Net Present Value)_spencer_tseng的博客-CSDN博客...

半导体自动化专用静电消除器主要由哪些部分组成

半导体自动化专用静电消除器是一种用于消除半导体生产过程中的静电问题的设备。由于半导体制造过程中对静电的敏感性&#xff0c;静电可能会对半导体器件的质量和可靠性产生很大的影响&#xff0c;甚至造成元件损坏。因此&#xff0c;半导体生产中采用专用的静电消除器是非常重…...

【C++入门到精通】C++入门 —— deque(STL)

阅读导航 前言一、deque简介1. 概念2. 特点 二、deque使用1. 基本操作&#xff08;增、删、查、改&#xff09;2. 底层结构 三、deque的缺陷四、 为什么选择deque作为stack和queue的底层默认容器总结温馨提示 前言 文章绑定了VS平台下std::deque的源码&#xff0c;大家可以下载…...

Codeforces Round 893 (Div. 2) D.Trees and Segments

原题链接&#xff1a;Problem - D - Codeforces 题面&#xff1a; 大概意思就是让你在翻转01串不超过k次的情况下&#xff0c;使得a*&#xff08;0的最大连续长度&#xff09;&#xff08;1的最大连续长度&#xff09;最大&#xff08;1<a<n&#xff09;。输出n个数&…...

SpringBoot + Vue 前后端分离项目 微人事(九)

职位管理后端接口设计 在controller包里面新建system包&#xff0c;再在system包里面新建basic包&#xff0c;再在basic包里面创建PositionController类&#xff0c;在定义PositionController类的接口的时候&#xff0c;一定要与数据库的menu中的url地址到一致&#xff0c;不然…...

【业务功能篇71】Cglib的BeanCopier进行Bean对象拷贝

选择Cglib的BeanCopier进行Bean拷贝的理由是&#xff0c; 其性能要比Spring的BeanUtils&#xff0c;Apache的BeanUtils和PropertyUtils要好很多&#xff0c; 尤其是数据量比较大的情况下。 BeanCopier的主要作用是将数据库层面的Entity转化成service层的POJO。BeanCopier其实已…...

让eslint的错误信息显示在项目界面上

1.需求描述 效果如下 让eslint中的错误&#xff0c;显示在项目界面上 2.问题解决 1.安装 vite-plugin-eslint 插件 npm install vite-plugin-eslint --save-dev2.配置插件 // vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue import e…...

手摸手带你实现一个开箱即用的Node邮件推送服务

目录 ​编辑 前言 准备工作 邮箱配置 代码实现 服务部署 使用效果 题外话 写在最后 相关代码&#xff1a; 前言 由于邮箱账号和手机号的唯一性&#xff0c;通常实现验证码的校验时比较常用的两种方式是手机短信推送和邮箱推送&#xff0c;此外&#xff0c;邮件推送服…...

【Linux网络】网络编程套接字 -- 基于socket实现一个简单UDP网络程序

认识端口号网络字节序处理字节序函数 htonl、htons、ntohl、ntohs socketsocket编程接口sockaddr结构结尾实现UDP程序的socket接口使用解析socket处理 IP 地址的函数初始化sockaddr_inbindrecvfromsendto 实现一个简单的UDP网络程序封装服务器相关代码封装客户端相关代码实验结…...

Python学习笔记第六十四天(Matplotlib 网格线)

Python学习笔记第六十四天 Matplotlib 网格线普通网格线样式网格线 后记 Matplotlib 网格线 我们可以使用 pyplot 中的 grid() 方法来设置图表中的网格线。 grid() 方法语法格式如下&#xff1a; matplotlib.pyplot.grid(bNone, whichmajor, axisboth, )参数说明&#xff1a…...

机器学习与模式识别3(线性回归与逻辑回归)

一、线性回归与逻辑回归简介 线性回归主要功能是拟合数据&#xff0c;常用平方误差函数。 逻辑回归主要功能是区分数据&#xff0c;找到决策边界&#xff0c;常用交叉熵。 二、线性回归与逻辑回归的实现 1.线性回归 利用回归方程对一个或多个特征值和目标值之间的关系进行建模…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...

k8s从入门到放弃之Pod的容器探针检测

k8s从入门到放弃之Pod的容器探针检测 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;容器探测是指kubelet对容器执行定期诊断的过程&#xff0c;以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...