NOIP2021各省分配名额由A、B、C共三类选手组成。其中,A类选手为基本名额、B类选手为激励名额、C类选手为推荐名额。A、B两类选手的产生由NOI各省组织单位确定,C类选手由特派员和教师推荐,各省ABC三类选手由省组织单位审核确定。
继续阅读分类目录归档:电脑技术
Lemon的安装和使用方法
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头文件和变量定义数组。
- 没有使用头文件
- 没有使用文件输入输出
- 输入输出文件名错误
- 文件输入输出位置写错
- 文件输入输出语句英文括号全部写成了中文括号
- 文件输入输出语句中双引号写成单引号
- 函数名freopen写错
- 输入输出文件名读写模式错误
- 选手在xxx.in和xxx.out的前面都加上了.\\,unix环境下评测编译错误
- 调试中文件输入输出注释了,忘记取消注释
- 强烈建议文件输入输出重定向用freopen()
- 使用变量定义数组:如 int a[n];
CSP-S复赛知识点
十月份目标
- 刷完算阶(这很重要)
- 熟练各种基础板子
- 最短路:F l o y d FloydFloyd,B e l l m a n − F o r d Bellman-FordBellman−Ford,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自动机
- 熟练运用各种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(可以用来离散化)
十一月目标
- 每天都要接触洛谷蓝以上难度的DP、图论、数论
- 掌握动态规划中的状态压缩DP、计数DP、树形DP与数位DP
- 进阶数据结构的模板
- 树状数组
- 线段树
- 分块+莫队
- 图论
- T a r j a n TarjanTarjan算法与图的连通性
- 树的直径与L C A LCALCA
- 数论
- 矩阵乘法
- 组合计数
- 概率与数学期望
- 博弈论
CSP-J CSP-S NOIP2020初赛知识点—硬件、进制与编码!
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:30 | CSP-S1组认证 | 提高级认证者 |
14:30-16:30 | CSP-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:00 | CSP-J2组认证 | 入门级认证者 |
14:30-18:30 | CSP-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)互质。怎样求逆元?
- 费马小定理(有限制)
=》p为素数时,a关于mod p的逆元为a^(p-2)mod p。用快速幂模。 - 扩展欧几里得算法(普遍适用)
- 给定模数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自动机