分类目录归档:电脑技术

关于NOIP2021的名额分配方案

NOIP2021各省分配名额由A、B、C共三类选手组成。其中,A类选手为基本名额、B类选手为激励名额、C类选手为推荐名额。A、B两类选手的产生由NOI各省组织单位确定,C类选手由特派员和教师推荐,各省ABC三类选手由省组织单位审核确定。

继续阅读

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,在国内做的人也不算特别多,但它的题目质量确实非常不错,且题库一直都在更新,相信它会越来越受欢迎。

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];

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

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)

未知错误

逆元

什么是逆元?

乘法逆元:

  • 模p意义下,一个数a如果有逆元x,那么除以a相当于乘以x。
  • 在模n的意义下,a存在逆元的充要条件是**n不等于1,且(a,n)互质。怎样求逆元?
  1. 费马小定理(有限制)
    =》p为素数时,a关于mod p的逆元为a^(p-2)mod p。用快速幂模。
  2. 扩展欧几里得算法(普遍适用)
  • 给定模数n,求a的逆元
  • 即ax=1(mod n)
  • =》ax-ny=1
  • 所以可用扩展欧几里得, ax+by=gcd(a,b)求逆元,即求x的值。注意:存在逆元的判断条件是 a,m互质
if(gcd(a,m) != 1)       //a,m不互质,则不存在逆元
 cout << "Not Exist" << endl;
 else
 {
      ext_gcd(a, m, x, y);
      LL ans = (x<=0) ? (x%m+m) : x;  //有可能x是负数,x要先取模再加
      cout << ans << endl;

NOIP提高组(CSP-S)复赛知识点汇总

基础算法

贪心

枚举

分治

二分答案

倍增

*构造

高精

模拟

*分数规划

图论

图论入门

最短路算法

单源最短路:从一个点到其他所有点的最短路

算法:Dijkstra、spfa、

多源最短路:从所有点到另外点的最短路

算法:Floyd

差分约束

最小生成树(kruskal、prim)

并查集(扩展域)

拓扑排序

二分图染色

*二分图匹配

tarjan找scc、桥、割点,缩点

LCA

树的直径、树的重心

dfs序

*树链剖分

数论

gcd、lcm

埃氏筛法

exgcd,求解同余方程、逆元

快速幂

*组合数学

矩阵

*高斯消元

数据结构

链表

队列(单调队列)、栈(单调栈)

st表

hash表

线段树、树状数组

字典树

*分块

*平衡树

*主席树

*莫队

动态规划

背包DP

树形DP

记忆化搜索

递推

区间DP

序列DP

*概率DP

*DP优化(不涉及斜率优化、四边形不等式等等)

搜索

暴搜(dfs、bfs)

搜索的剪枝

启发式搜索(A∗)

迭代加深搜索、*IDA∗

*随机化搜索

其他算法

STL的基本使用方法

脑洞的正确使用方法

*KMP

*状态压缩

*AC自动机