202009 CSP认证 | 点亮数字人生

2024-03-03 16:04

本文主要是介绍202009 CSP认证 | 点亮数字人生,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

3. 点亮数字人生
60分 | 超时
因为设计到电路门的先后连接,所以涉及到计算的时序问题,自然而然的想到了拓扑排序的问题。关于拓扑排序的理解和代码参考了这个博文:拓扑排序

在编写的时候还遇到了一个问题,就是将类似于“3456”的字符串转化为int类型的数字问题。在转化过程中出现奇数位会转化错误但是检查发现逻辑是正确的问题。查阅后发现是调用pow()后,返回值为double类型而导致的,解决方法参考了链接:转化数字时的错误解决

acwing上通过了7 / 12个答案,但是输入和答案太复杂了根本无法对照着找到逻辑错误…超时说明是优化问题…自写版本感觉60是我的极限了(第三题的难度真的在增加啊我哭了)
下面贴上自己写的60分答案:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 510;  //器件最大数量
const int S = 10010;vector<int> input_signal[S];   //记录各组输入信号的值
int output[N];
string components[N];  //用来记录元器件信息
unordered_map<int, string> fun;  //记录标号为Index的门的功能
unordered_map<int, set<int> >input_I;  //每个门的输入中, 作为输入信号的部分
unordered_map<int, set<int> >input_O;  //每个门的输入中, 作为其他门的输出的部分
vector<int> topo;  //一个可能的拓扑序列int string_to_int(string str)
{int index = 0;int len = str.size() - 1;  //前驱节点的位数for(int j = 1;j < str.size() && len;j ++){len --;int add = ((str[j] - 48) * int(pow(10, len) + 0.5));index += add;}return index;
}//判断电路是否存在环路, 若不存在环路,得到一个可能的计算顺序(拓扑排序)
bool judge(int n)
{int indegree[N];   //记录下标为i的器件有多少个入度vector<int> next_component[N];  //后驱节点for(int index = 1;index <= n;index ++){   //处理每一个器件门信息stringstream ssin(components[index]);vector<string> words; string w;while(ssin >> w)words.push_back(w);fun[index] = words[0];  //记录当前器件门的功能for(int i = 2;i < words.size();i ++){  //处理每一个输入string in = words[i];int pro_index = string_to_int(in);if(in[0] == 'O'){  //收到其他门的输出indegree[index] ++;  //当前节点的入度加一next_component[pro_index].push_back(index);  //前驱节点的后继节点有indexinput_O[index].insert(pro_index);}else{input_I[index].insert(pro_index);}}}stack<int> s;for(int index = 1;index <= n;index ++){//找出初始入度为0的点if(indegree[index] == 0) s.push(index);}while(!s.empty()){int x = s.top();  s.pop();topo.push_back(x);   //取出栈顶元素int cnt = next_component[x].size();  //后继节点数量for(int i = 0;i < cnt;i ++){int to = next_component[x][i];indegree[to] --;if(indegree[to] == 0) s.push(to);}}if(topo.size() == n) return true;else return false;
}//序号为now的或门件在第s组输入下的输出
void OR(int s, int now)
{int ops;//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];if(ops){   //存在一个1就是1output[now] = 1;return;}}for(auto index : input_O[now]){ops = output[index];if(ops){   //存在一个1就是1output[now] = 1;return;}}output[now] = 0;
}
//序号为now的与门件在第s组输入下的输出
void AND(int s, int now)
{int ops;//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];if(!ops){   //存在一个0就是0output[now] = 0;return;}}for(auto index : input_O[now]){ops = output[index];if(!ops){   //存在一个0就是0output[now] = 0;return;}}output[now] = 1;
}
//序号为now的非门件在第s组输入下的输出
void NOT(int s, int now)
{//非门只会接收一个输入int ops;for(auto index : input_I[now]){ops = input_signal[s][index - 1];output[now] = (!ops);return;}for(auto index : input_O[now]){ops = output[index];output[now] = (!ops);return;}
}
//序号为now的异或门件在第s组输入下的输出
void XOR(int s, int now)
{int ops;int ans = 0;  //第一个数上来希望得到自己本身,1^0 = 1, 0^0 = 0//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];ans ^= ops;}for(auto index : input_O[now]){ops = output[index];ans ^= ops;}output[now] = ans;return;
}
//序号为now的与非门件在第s组输入下的输出
void NAND(int s, int now)
{AND(s, now);int and_res = output[now];output[now] = (!and_res);
}
//序号为now的或非门件在第s组输入下的输出
void NOR(int s, int now)
{OR(s, now);int or_res = output[now];output[now] = (!or_res);
}//对第s组输入进行计算
void compute(int s, int n)
{//按照拓扑排序的顺序进行计算for(int i = 0;i < n;i ++){int now = topo[i];  //当前计算的门件string f = fun[now];if(f == "OR")  OR(s, now);else if(f == "AND") AND(s, now);else if(f == "NOT") NOT(s, now);else if(f == "XOR") XOR(s, now);else if(f =="NAND") NAND(s, now);else if(f == "NOR") NOR(s, now);}
}int main()
{int Q; scanf("%d", &Q);int m, n, s, cnt, index;string line;while(Q --){scanf("%d%d", &m, &n);  //m个输入, n个器件getline(cin, line);for(int i = 1;i <= n;i ++){getline(cin, line);components[i] = line;}bool legal = judge(n);  //判断电路是否存在环路if(!legal) cout << "LOOP" << endl;else{scanf("%d", &s);for(int i = 1;i <= s;i ++){for(int j = 1;j <= m;j ++){int x; scanf("%d", &x);input_signal[i].push_back(x);}}for(int i = 1;i <= s;i ++){compute(i, n);scanf("%d", &cnt);while(cnt --){scanf("%d", &index);printf("%d ", output[index]);}cout << endl;}}//一些数据的清空for(int i = 1;i <= s;i ++) input_signal[i].clear();topo.clear();input_I.clear();input_O.clear();fun.clear();//memset(components, "", sizeof components);memset(output, 0, sizeof output);}return 0;
}

后续不打算修改了…隔天写的感觉没有太大耐心再看一个满分答案然后修改了…
当然!如果有无聊的好心人可以告诉我哪里有问题我还是会很感动的

这篇关于202009 CSP认证 | 点亮数字人生的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/770139

相关文章

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【Kubernetes】K8s 的安全框架和用户认证

K8s 的安全框架和用户认证 1.Kubernetes 的安全框架1.1 认证:Authentication1.2 鉴权:Authorization1.3 准入控制:Admission Control 2.Kubernetes 的用户认证2.1 Kubernetes 的用户认证方式2.2 配置 Kubernetes 集群使用密码认证 Kubernetes 作为一个分布式的虚拟

AIGC6: 走进腾讯数字盛会

图中是一个程序员,去参加一个技术盛会。AI大潮下,五颜六色,各种不确定。 背景 AI对各行各业的冲击越来越大,身处职场的我也能清晰的感受到。 我所在的行业为全球客服外包行业。 业务模式为: 为国际跨境公司提供不同地区不同语言的客服外包解决方案,除了人力,还有软件系统。 软件系统主要是提供了客服跟客人的渠道沟通和工单管理,内部管理跟甲方的合同对接,绩效评估,BI数据透视。 客服跟客人

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数?条件:举例说明:一般化: 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法:举几个例子:例子 1: 计算 12 和 18

【Shiro】Shiro 的学习教程(二)之认证、授权源码分析

目录 1、背景2、相关类图3、解析3.1、加载、解析阶段3.2、认证阶段3.3、授权阶段 1、背景 继上节代码,通过 debug 进行 shiro 源码分析。 2、相关类图 debug 之前,先了解下一些类的结构图: ①:SecurityManager:安全管理器 DefaultSecurityManager: RememberMeManager:实现【记住我】功能

NC 把数字翻译成字符串

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 描述 有一种将字母编码成数字的方式:‘a’->1, ‘b->2’, … , ‘z->26’。 现在给一串数字,返回有多少种可能的译码结果 import java.u

OpenStack离线Train版安装系列—3控制节点-Keystone认证服务组件

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版