分类: 电脑技术

  • 关于NOIP2021的名额分配方案

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

    (更多…)
  • Lemon的安装和使用方法

    • Lemon是现在比较流行的评测软件。
    • 下载软件 :lemon_v1-2完整版
    • 首先打开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头文件和变量定义数组。

    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-J CSP-S NOIP2020初赛知识点—硬件、进制与编码!

    CSP-J/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: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自动机