作者归档:admin

SPOJ 简介

SPOJ 是波兰最为出色的Online Judge之一,界面和谐,题目类型也非常丰富,适合有一定基础的选手练习,对高手而言也是个提高能力的良好平台。

  SPOJ题目分类:classical,challenge,partial,tutorial。

  1)classical:ACM题型,通过所有数据才能算AC

  2)challenge:有趣的题目,每个题目有不同的评分标准(代码长短,效果好坏,速度等),感觉都挺难得。

  3)partial:OI题型,根据通过的测试数据比例,得到部分分。

  4)tutorial:ACM题型,题目算法都比较基础(也有几道bt题放在里面)。

  SPOJ得分:classical得分,challenge得分,partial和tutorial是供用户练习或训练使用,不计入SPOJ得分中。

  1)classical得分:得到80/(40+这道题目通过人数),也就是说过的人越多得分越低,过的人越少得分越高,根据这个公式,每个用户的分数都是变动的。

  2)challenge得分:按该题评分标准计算,最优者得到3分(很诱人,不过好难啊T_T),其他用户,得到一个与最优者的相对得分(<1分)。

  SPOJ吸引人的地方在于:

       1)它所提供的编程语言达30种,甚至有些题目要求使用最简单的语言Brainfuck去解决,虽然编程过程非常痛苦,但是AC这类题的喜悦也是其他题目所不能比较的。

       2)跟大部分的OJ不同(SGU、Ural用的全都是自己的题目,POJ、HDU、ZOJ、TOJ则主要是历年Regional和大小型比赛的题目),SPOJ题目都是由用户(或管理员)推荐的,OJ中有不少的own problem,除此以外也挑选出各种比赛的中档以上的题目,删去了最简单的题目,有时也会把一些绝对”大自然“的题目删去了,特别值得一提的是,当一些低复杂度的算法被发现后,某些题目会相继挂出他们的加强版,这些题目往往能提高大家的个人能力。

  目前,虽然SPOJ的访问量不能媲美当年的ZOJ和现在POJ、HDU,在国内做的人也不算特别多,但它的题目质量确实非常不错,且题库一直都在更新,相信它会越来越受欢迎。

0812 计算机科学与技术 高校评级

一级学科代码及名称: 0812 计算机科学与技术

本一级学科中,全国具有“博士授权”的高校共 77 所,本次参评75 所;部分具有“硕士授权”的高校 也参加了评估;参评高校共计 238 所(注:评估结果相同的高校排序不分先后,按学校代码排列)。


A+
10001 北京大学
10003 清华大学
10335 浙江大学
90002 国防科技大学

A
10006 北京航空航天大学
10013 北京邮电大学
10213 哈尔滨工业大学
10248 上海交通大学
10284 南京大学
10487 华中科技大学
10614 电子科技大学

A-
10004 北京交通大学
10007 北京理工大学
10145 东北大学
10183 吉林大学
10247 同济大学
10358 中国科学技术大学
10486 武汉大学
10533 中南大学
10698 西安交通大学
10699 西北工业大学
10701 西安电子科技大学
90005 解放军信息工程大学

继续阅读

CSP-J/S NOIP 复赛爆零原因总结

CSP复赛结束,今年放弃了普及组,全力参加了提高组,结果稍微有点遗憾,135分,主要是T1只得了50分,大样例都过了。

经常有同学爆零,总结一下各种爆零的原因,每一条都是选手亲身经历,写下的血泪史,希望后来者一定一定要重视,不要重蹈覆辙。

一定要注意:NOI Linux的环境相对比较严格,代码在Windows环境或者线上提交都是没问题的,甚至比赛现场的linux环境都一切正常,但是在NOI Linux评测后的结果就是编译错误,最典型的就是没有写cstdio头文件和变量定义数组。

  1. 没有使用头文件
  2. 没有使用文件输入输出
  3. 输入输出文件名错误
  4. 文件输入输出位置写错
  5. 文件输入输出语句英文括号全部写成了中文括号
  6. 文件输入输出语句中双引号写成单引号
  7. 函数名freopen写错
  8. 输入输出文件名读写模式错误
  9. 选手在xxx.in和xxx.out的前面都加上了.\\,unix环境下评测编译错误
  10. 调试中文件输入输出注释了,忘记取消注释
  11. 强烈建议文件输入输出重定向用freopen()
  12. 使用变量定义数组:如 int a[n];

位移传感器的通信接口介绍

位移传感器的输出型式(通信接口)比较多,经常搞不清,整理了下面资料备查。

随着技术的发展,自动化程度越来越高,位移传感器的输出信号越来越多样化,位移传感器的主要输出类型大致分为这几种:摸拟量输出型电流型(4~20mA;或20~4mA);电压型(0~10Vdc;或10~0Vdc);脉冲信号(绝对编码SSI,RS485格雷码信号输出等),及数字量的SSI和Start/Stop,现场总线的CANbus和Profibus-DP等。下面我们来详细的介绍下各种通讯协议:

常用接口介绍

1、Profibus

PROFIBUS(Process Fieldbus)是由西门子等公司开发的一种国际化的、开放的、不依赖于设备生产商的现场总线标准。先后成为德国和欧洲的现场总线标准(DINl9245和EN50170),并于2000年成为IEC61158国际现场总线标准之一,2001年成为我国机械行业标准JB厂r10308.3.2001¨“。PROFIBUS现场总线是一个开放的、与制造商无关、无知识产权保护的国际标准,任何人都可以获得这个标准并设计各自的软、硬件解决方案。PROFIBUS支持双绞线、光钎等通信介质。PROFIBUS分为PROFIBUS-DP、PROFIBUS-FMS、PROFIBUS-PA等,一般传感器只需实现PROFIBUS-DP。这种协议磁致伸缩位移传感器使用的比较多。

2、RS-485

RS-485是IEC制定的推荐标准,这是一个通信接口的物理层协议的标准。使用双绞线、差分方式传输电信号,具有抗干扰能力强,通信距离远,成本低,可以在一条双绞线上实现一主多从德通信模式等优点。其最大通信距离为1200米,在工业上应用十分广泛。但由于其仅实现了物理层,不能解决通信介质共享问题,需要应用程序通过“轮询”的方式实现多机通信,并且在一条总线上只能有一台主机,最多可以有110台设备。拉绳位移传感器和磁致伸缩位移传感器都使用的比较多。

3、SSI

SSI(Synchronous Serial Interface, 同步串行接口)是一种全双工的高速串行接口,主要用于实现芯片与芯片之间的串行通信。支持一主多从的系统结构,它3或4根信号线,以主机主动式读出方式工作,即在主控者发出的时钟脉冲的控制下,实现与从机之间的通信。一般而言SSI的通信距离在1米以内。拉绳位移传感器和磁致伸缩位移传感器都是有应用的。

4、MODBUS

由于RS-485只实现了物理层,难于解决不同厂家的设备在同一系统共存的问题。为此,MODICON制定了一个建立在RS-485之上的“应用层协议”——MODBUS。协议规定了数据包的格式、实现的命令等。任何厂家生产的设备只要其符合MODBUS协议都可以在同一系统中工作。MODBUS协议uye只支持单主机,并通过轮询方式实现共享信道。这种协议一般是磁致伸缩位移传感器使用较多

5、CANBUS

CANBUS是德国BoSCH公司在SAE(汽车工程协会)上介绍的新型串行通信协议,其全称为ControllerArea Network),其主要目的是实现汽车环境中的微控制器之间的通信。由于其可靠性高、通信速率高、结构简单,因而在工业控制领域也获得广泛应用。

CANBUS的最高通信速率为1Mbps,最大通信距离为10KM。支持多主机系统。CANBUS协议包括了物理层和数据链路层,所以它可以实现多台设备共享通信介质。在一条双绞线上最多可以连接110个CANBUS装置,目前协议有CAN2.0A、CAN2.0B等。基本是磁致伸缩位移传感器使用。

CSP-S复赛知识点

十月份目标

  1. 刷完算阶(这很重要)
  2. 熟练各种基础板子
  • 最短路:F l o y d FloydFloyd,B e l l m a n − F o r d Bellman-FordBellmanFord,D i j k s t r a DijkstraDijkstra, S P F A SPFASPFA
  • 最小生成树:p r i m primprim,k r u s k a l kruskalkruskal
  • 分治:二分答案,二分查找
  • 位运算
  • 排序算法
  • 字符串:K M P KMPKMP,T r i e TrieTrie树,A C ACAC自动机
  1. 熟练运用各种S T L STLSTL
  • 栈(s t a c k stackstack)(先进后出)
  • 队列(q u e u e queuequeue)(先进先出)
  • 优先队列(p r i o r i t y _ q u e u e priority\_queuepriority_queue)(堆)
  • 双端队列(d e q u e dequedeque
  • 平衡树(s e t setset)(m u l t i s e t multisetmultiset
  • 映射(m a p mapmap)(可代替h a s h hashhash表)
  • 随机数组(v e c t o r vectorvector)(可用来实现邻接表)
  • l o w e r _ b o u n d lower\_boundlower_bound与u p p e r _ b o u n d upper\_boundupper_bound(二分时候用)
  • 去重函数u n i q u e uniqueunique(可以用来离散化)

十一月目标

  1. 每天都要接触洛谷蓝以上难度的DP、图论、数论
  2. 掌握动态规划中的状态压缩DP、计数DP、树形DP与数位DP
  3. 进阶数据结构的模板
  • 树状数组
  • 线段树
  • 分块+莫队
  1. 图论
  • T a r j a n TarjanTarjan算法与图的连通性
  • 树的直径与L C A LCALCA
  1. 数论
  • 矩阵乘法
  • 组合计数
  • 概率与数学期望
  • 博弈论

CSP-S/J2020 时间流程

2020年的CSP-S/J来了,今年想要报名NOIP(全国青少年信息学奥林匹克联赛)的话,需要条件:1.凡是由CCF认定的国内国际程序设计竞赛或能力认证中取得优秀成绩者;2.CCF认可的指导教师推荐

所以还是要努力对待,首先是要过初赛。复赛的话就尽力吧,CSP-J入门组可能问题不大,CSP-S提高组的话可能实力还要加强。加油吧!

第一轮认证

日期时间内容角色
9月1日-23日全天系统注册、审核教师、认证组织单位总负责人
9月1日-24日全天系统注册、报名、审核认证者、教师、认证组织单位总负责人
9月10日-26日全天最终确认报名认证者
9月27日9:00-16:00生成准考证号、提交报名表认证组织单位总负责人
10月6日-11日全天下载准考证认证者
10月11日9:30-11:30CSP-S1组认证提高级认证者
14:30-16:30CSP-J1组认证入门级认证者
10月20日全天公布第一轮认证成绩认证组织单位总负责人

第二轮认证

日期时间内容角色
10月22日-29日全天系统注册、审核教师、认证组织单位总负责人
10月22日-30日全天系统注册、报名、审核认证者、教师、认证组织单位总负责人
10月24日-31日全天最终确认报名认证者
11月1日9:00-16:00生成准考证号、提交报名表认证组织单位总负责人
11月3日-7日全天下载准考证认证者
11月7日8:30-12:00CSP-J2组认证入门级认证者
14:30-18:30CSP-S2组认证提高级认证者
11月16日17:00前公布第二轮初评成绩CCF
11月17日-19日19日16:00申诉结束申诉期CCF
11月19日-22日申诉处理期 CCF
11月25日左右 公布最终认证成绩CCF

理解矩阵乘法——线性方程

大多数人在高中,或者大学低年级,都上过一门课《线性代数》。这门课其实是教矩阵。

刚学的时候,还蛮简单的,矩阵加法就是相同位置的数字加一下。

矩阵减法也类似。

矩阵乘以一个常数,就是所有位置都乘以这个数。

但是,等到矩阵乘以矩阵的时候,一切就不一样了。

这个结果是怎么算出来的?

教科书告诉你,计算规则是,第一个矩阵第一行的每个数字(2和1),各自乘以第二个矩阵第一列对应位置的数字(1和1),然后将乘积相加( 2 x 1 + 1 x 1),得到结果矩阵左上角的那个值3。

也就是说,结果矩阵第m行与第n列交叉位置的那个值,等于第一个矩阵第m行与第二个矩阵第n列,对应位置的每个值的乘积之和。

怎么会有这么奇怪的规则?

我一直没理解这个规则的含义,导致《线性代数》这门课就没学懂。研究生时发现,线性代数是向量计算的基础,很多重要的数学模型都要用到向量计算,所以我做不了复杂模型。这一直让我有点伤心。

前些日子,受到一篇文章的启发,我终于想通了,矩阵乘法到底是什么东西。关键就是一句话,矩阵的本质就是线性方程式,两者是一一对应关系。如果从线性方程式的角度,理解矩阵乘法就毫无难度。

下面是一组线性方程式。

矩阵的最初目的,只是为线性方程组提供一个简写形式。

老实说,从上面这种写法,已经能看出矩阵乘法的规则了:系数矩阵第一行的2和1,各自与 x 和 y 的乘积之和,等于3。不过,这不算严格的证明,只是线性方程式转为矩阵的书写规则。

下面才是严格的证明。有三组未知数 x、y 和 t,其中 x 和 y 的关系如下。

x 和 t 的关系如下。

有了这两组方程式,就可以求 y 和 t 的关系。从矩阵来看,很显然,只要把第二个矩阵代入第一个矩阵即可。

从方程式来看,也可以把第二个方程组代入第一个方程组。

上面的方程组可以整理成下面的形式。

最后那个矩阵等式,与前面的矩阵等式一对照,就会得到下面的关系。

矩阵乘法的计算规则,从而得到证明。

OJ评测状态含义

刷OJ网站时,各类提示总是要懂吧,每次只认识AC?

1. Pending/Waiting

排队等待中

2. Pending Rejudge

答案重判中

3. Compiling

正在编译

4. Running/Judging

运行判断中

5. Accepted(AC)

程序通过

6. Compile Eror(CE)

编译错误

7. Wrong Answer(WA)

答案错误

8. Runtime Error(RE)

运行时错误

9 . Time Limit Exceeded(TLE)

超出时间限制

10. Memory Limit Exceeded(MLE)

超出内存限制

11. Output Limit Exceeded(OLE)

输出超过限制

12. Presentation Error(PE)

输出格式错误

13. Unknown Error(UKE)

未知错误