分类目录归档:电脑技术

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自动机

CCF开启NOI Online培训

CCF先后在3月和4月举办了两场NOI Online能力测试,第三场测试将于5月24日举行,这给受疫情影响训练中断的学生提供比赛锻炼和交流机会,这是NOI新开创的一种形式。

CCF没有止步,紧接着,将开启NOI Online培训!

CCF首次Online培训定于5月5日推出,为学生提供学习的机会,与Online能力测试相互呼应。Online培训课程主要面向中小学生。

Online培训每周推出一期,每期邀请两位具有NOI钻石或金牌教练资质的老师讲授。培训内容将结合《CCF中学生计算机程序设计系列教材》和《CCF青少年计算机程序设计评价标准》,从零基础入门、基础、提高再到专业知识,由浅入深、循序渐进。

Online培训首期邀请到了两位教师均荣获NOI钻石教练称号,其训练的学生获得过IOI金牌,他们是湖南长沙雅礼中学朱全民老师及广东中山纪念中学宋新波老师。

关于培训讲师,CCF采取邀请和公开征集的形式。不论你是教师或学生,只要感兴趣,愿意和大家分享,欢迎加入讲师队伍,咨询邮箱noi@ccf.org.cn。

讲师介绍

朱全民

朱全民

CCF会员。长沙市雅礼中学正高级教师,湖南省特级教师,长沙市信息技术工作室首席名师兼农村名师工作站站长,雅礼中学信息学奥赛奠基人,NOI钻石指导教师,曾获2016年度CCF卓越服务奖;指导学生获得国际信息学奥林匹克竞赛(IOI)6金1银,带领雅礼信息学教练团队指导学生获IOI奖项3金1银。他是《CCF 青少年计算机程序设计评级标准》课题主持人,《CCF 中学计算机程序设计》系列教材的总体构架和编审负责人。

宋新波

宋新波

CCF理事。中山纪念中学信息学竞赛教练,NOI钻石指导老师,CCF杰出演讲者;指导学生获全国青少年信息学奥林匹克联赛(NOIP)一等奖近500人次,全国决赛(NOI)金牌22枚、银牌22枚、铜牌13枚,25人次入选国家集训队,3人入选国家队,获国际信息学奥林匹克竞赛(IOI)金牌2枚、国际银牌1枚。他先后获得“中山市十大杰出青年”、“中山市十杰市民”、“南粤优秀教师”、“广东省五一劳动奖章”、“全国优秀教师”等荣誉称号。

转载 https://www.ccf.org.cn/Focus/2020-05-05/700814.shtml

Windows 10 更新补丁汇总合集

Windows 10 version 1909 & 1903 (Build 18363 & 18362) 更新发布日期备注
Windows10-KB4550945-x64Windows10-KB4550945-x862020-04-20适用于 Windows 10 1909 的积累更新
Windows10-KB4552152-x64Windows10-KB4552152-x862020-04-10安全更新程序
Windows10-KB4537572-x64Windows10-KB4537572-x862020-02-25.NET Framework 3.5 和 4.8 的累积更新
Windows10-KB4537759-x64Windows10-KB4537759-x862020-02-10Adobe Flash Player 安全更新程序
Windows 10 version 1809 (Build 17763) 更新发布日期备注
Windows10-KB4550969-x64Windows10-KB4550969-x862020-04-20适用于 Windows 10 1809 的积累更新
Windows10-KB4549947-x64Windows10-KB4549947-x862020-04-10安全更新程序
Windows10-KB4537480-x64Windows10-KB4537480-x862020-02-24.NET Framework 3.5 和 4.8 积累更新
Windows10-KB4537759-x64Windows10-KB4537759-x862020-02-10Adobe Flash Player 安全更新程序
Windows10-KB4486153-x64Windows10-KB4486153-x862020-01-09Microsoft .NET Framework 4.8
Windows 10 version 1803 (Build 17134) 更新发布日期备注
Windows10-KB4550944-x64Windows10-KB4550944-x862020-04-20适用于 Windows 10 1803 的积累更新
Windows10-KB4540724-x64Windows10-KB4540724-x862020-03-09关键更新程序
Windows10-KB4537759-x64Windows10-KB4537759-x862020-02-10Adobe Flash Player 安全更新程序
Windows10-KB4486153-x64Windows10-KB4486153-x862020-01-09Microsoft .NET Framework 4.8
Windows 10 version 1709 (Build 16299) 更新发布日期备注
Windows10-KB4550927-x64Windows10-KB4550927-x862020-04-10适用于 Windows 10 1709 的积累更新
Windows10-KB4541731-x64Windows10-KB4541731-x862020-03-09更新程序
Windows10-KB4537759-x64Windows10-KB4537759-x862020-02-10Adobe Flash Player 安全更新程序
Windows10-KB4486153-x64Windows10-KB4486153-x862020-01-09Microsoft .NET Framework 4.8
Windows 10 version 1703 (Build 15063) 更新
生命周期结束
Windows 10 version 1607 (Build 14393) 更新
生命周期结束
Windows 10 version 1511 (Build 10586) 更新
生命周期结束
Windows 10 扩展更新发布日期备注
WindowsTH-RSAT_WS_1803-x64WindowsTH-RSAT_WS_1803-x862018-05-02适用于 Windows 10 的远程服务器管理工具(RSAT for Windows 10)
WindowsTH-RSAT_WS_1709-x64WindowsTH-RSAT_WS_1709-x862018-05-02
Windows10-KB4057437-x64Windows10-KB4057437-x862019-05Version 1903Media Feature Pack(针对 N 及 KN)
Windows10-KB4134255-x64Windows10-KB4134255-x862018-10Version 1809
Windows10-KB4057437-x64Windows10-KB4057437-x862018-04Version 1803
  • 没有列出的更新表示已过期,可以不用安装。
  • Windows 10「功能更新」与「质量更新」之间的区别
  • 合集会随微软发布更新进行定期更新,建议大家收藏链接。
  • Windows 10 更新补丁合集的所有补丁都源链到微软官方下载网站,大家可以放心下载。
  • 「积累更新」都链接到完整包(非 Delta 更新),可以直接安装最新包,不用逐步升级安装。
  • Windows 10 更新补丁合集只用于收集 Windows 10 更新补丁,方便用户手动下载安装和管理员下载分发。

历年NOIP普及组题目分析(2000-2016)

年份题目名称考查内容难度
 2000-2016年NOIP普及组复赛题目
2000乘积最大划分动态规划★★★
2000税收与补贴问题数学或枚举★★
2000单词接龙深搜★★★★
2000计算器的改良字符串处理★★
2001装箱问题0/1背包或枚举
2001数的计算动态规划
2001求先序排列树的遍历
2001最大公约数和最小公倍数数学(辗转相除法)
2002过河卒棋盘动态规划★☆
2002级数求和循环结构(枚举)
2002选数深搜、素数判定★★★
2002产生数最短路(图论)、高精度★★★★
2003数字游戏动态规划★★★★★
2003麦森数分治、高精度运算★★★
2003数学(卡特兰数)★★
2003乒乓球字符串处理★☆
2004FBI树二叉树的遍历★★
2004不高兴的津津枚举
2004火星人数学(排列)、stl★★★
2004花生采摘贪心
2005采药0/1背包
2005循环高精度运算、数论、快速幂★★★★★
2005淘淘摘苹果枚举
2005校门外的树枚举
2006开心的金明0/1背包
2006明明的随机数桶排序、冒泡
2006Jam计数法数学、字符串★★★
2006数列数学(进制转换)★☆
2007守望者的逃离动态规划或枚举★★★
2007奖学金快速排序(双关键字)
2007Hanoi双塔问题数学、高精度★☆
2007纪念品分组贪心、排序算法★☆
2008传球游戏动态规划★★★
2008排座椅贪心★★
2008ISBN号码字符串处理
2008立体图字符输出★★★
2009道路游戏动态规划★★★★★
2009分数线划定快速排序(双关键字)
2009细胞分裂数论★★★★
2009多项式输出字符串处理
2010数字统计枚举
2010接水问题模拟★★
2010导弹拦截排序+枚举,贪心★★★★
2010三国游戏贪心★★★
2011瑞士轮模拟、快拍、归并排序★★★
2011数字反转模拟、字符串
2011统计单词数模拟、字符串函数
2011表达式的值栈、表达式计算、递推★★★★★
2012摆花动态规划★★★★
2012质因数分解枚举
2012寻宝模拟,模运算★★★
2012文化之旅搜索、最短路(图论)、动规★★★★☆
2013小朋友的数字动态规划、子段和★★★★
2013计数问题 枚举
2013表达式求值 模拟或栈★★
2013车站分级图论、拓扑排序★★★★☆
2014珠心算测验枚举
2014 比例简化枚举★☆
2014 螺旋矩阵数学分析★★★
2014子矩阵搜索或dp★★★★☆
2015金币枚举
2015扫雷枚举★☆
2015推销员枚举、堆★★★★☆
2015求和数学(数列)★★★
2016买铅笔模拟
2016回文日期枚举★☆
2016海港枚举★★
2016魔法阵数学分析、枚举★★★★

水平不高怎么拿NOIP一等奖?南京外国语许昊然 比赛经验

本文转自江苏信息学竞赛

本文作者许昊然毕业于南京外国语学校,曾获NOIP 2012一等奖(590分,江苏第一名)、NOI 2012金牌(485分,全国第19名)、IOI 2013金牌(世界第三名),高一获清华保送资格,2014年被美国麻省理工学院录取。

Part I. 赛场策略与技巧

* 首先,如果你的水平已经远超NOIP,自然是想怎么考怎么考了。

* 同理,如果你什么都不会,那么策略再好也是没用的。

* 因此,下面说的策略、技巧主要是针对水平中等,游走在分数线附近的同学们的。

赛场策略的最终目标就是一句话:多拿分。

这是考试,为了分数应当使用任何你能想到的手段。(当然作弊啥的除外……)

多拿分,具体来说就是两部分:

* 会做的subtask不丢分

* 不会做的subtask多骗分

1、先讲一下“会做的subtask不丢分”。

subtask就是每道题目里各个部分分。如果一个subtask你会做,比如遇到了水题,或者某道题你会写30分的小数据,那么请务必确保你能拿到这部分分数。

以及,不要嫌分数少而懒得写!30分也是分,10分也是分,在分数拉不开的情况下(如果你水平并不优秀,这就是你总是要面对的情况),10分的差距就决定了你是一等还是二等。

记住,如果你因为粗心大意,一个简单的subtask没拿到分,你就不得不依靠更难的题目来把这部分分数拉回来。

举个例子,某A,第一题因打错文件名爆零,其余两题满分。某B,只会前两题,第三题写了朴素得30分。最后A得200分,B得230分。难题和水题都是100分,评奖可不管你到底写对的是难题还是水题。

请大家记住:在大多数OI比赛中,只要暴力分全部拿到,就是一等奖(或金牌)。

但问题是,大家都会写暴力,为啥一等奖只有总名额的10%呢?因为大多数人都会把暴力写错,或看暴力分少懒得写。如果你正确写出了所有暴力,不出意外你就是一等奖了。

继续阅读

走信息学竞赛之路必须要知道的六件事!

1、信息学竞赛有哪些赛事呢? 

第一,省级联赛(也称联赛、NOIP)。初赛在每年10月,复赛在每年11月。省级联赛分为两个级别:普及组和提高组。普及组针对初中生(有的地区也有小学生参加),提高组主要针对高中生(允许水平高的初中生参加)。提高组成绩一般是知名高中、知名大学在招生时比较看重的成绩。 

省级联赛分为初赛和复赛两轮,初赛是两个小时笔试,考计算机基础知识、算法基础知识、看程序写运行结果、以及程序补充填空。一般按照初赛人数比例划定晋级复赛分数线,对于弱省而言,晋级复赛不难。但对于某些强省(如浙江省),稍有粗心就可能丧失复赛资格。提高组复赛一二三等奖就是90所高校自主招生报名条件中的省一省二省三,证书要求是中国计算机学会(CCF)盖章。 

继续阅读

CCF CSP-J/S2019第二轮评级规则 同原NOIP复赛获奖分数线及名额分配办法

终于结果出来了,看看今年的评分规则和奖项分布。

CCF NOI科学委员会、竞赛委员会召开会议,确定了CCF CSP-J/S2019第二轮评级规则及评级名额方案。

提高级一等名额分配方案

提高级一等全国认证基准线:165

CCF CSP-J/S第二轮(提高级)省一等名额由三部分组成:

A:第二轮人数和省平均分;

B:第一轮人数;

C:第一轮晋级第二轮比例。

计算规则如下:

1.确定全国认证基准分数线、拟评级比例为20%,根据各省第二轮提高级人数Q、平均分R,一个省可获名额A的计算公式如下:

A=((省第二轮平均分R-全国一等认证基准线)×0.1%+20%)×省第二轮提高级人数Q

注:0.1%为比例因子(省平均分与全国一等认证基准线之差,每增加10分,评级比例增加1%);

2.根据省第一轮人数(P),可计算一个省获得的相应名额B:

(1).0<P<5000,B=(S-全国A名额总和)×第一轮人数P/全国第一轮总人数

(2).P≥5000时,每增加2700人,增加1个名额;

注:S为拟评级人数,定义为2700;

3.根据省第一轮晋级第二轮比例(M),全国第一轮晋级第二轮最低比例20%,可计算一个省获得的相应名额C。即,除各省第一轮晋级第二轮比例M低于全国最低比例20%以下的(不含)省份外,其他省分别获得1个C名额。在此基础上,省晋级比例M比全国最低比例20%每高5%再奖励1个C名额,M上限80%。名额C不超过各省(市)计算名额AB之和的40%。

(1).0<M<20%,C=0

(2)20%≤M≤80%时,C=((M-20%)/5%)+1

以上A、B、C之和为各省第二轮提高级一等参考名额,科学委员会、竞赛委员会根据各省认证成绩、评级人数及比例适当调整。

说明:

1.第一轮人数、第二轮人数按实际参加者(零分者包括在内)计算;

提高级二等名额分配方案

提高级二等全国认证基准分数线: 110

1.提高级一等认证分数线位于基准分数线165分(含)以上的省份,110分(含)以上未获一等者均可评二等;

2.对于提高级一等认证分数线低于基准分数线的省,80分(含)以上的认证者未获一等者均可评二等;

提高级三等名额分配方案

1.提高级一等认证分数线在基准分数线165分(含)以上的省份,80分(含)以上未获一二等的认证者,均可评三等。

2.一等认证分数线低于全国基准分数线的省份,不设三等。

入门级一等名额分配方案

入门级一等全国基准分数线:150

CSP-J/S2019第二轮入门级一等名额分配方案同提高级一等计算方式。

入门级二等名额分配方案

入门级二等全国基准分数线:100

1.入门级一等评级分数线位于基准分数线150分(含)以上的省份,100分(含)以上未获一等者均评获二等。

2.对于入门级一等评级分数线低于基准分数线的省,70分(含)以上未获一等者均可评二等;

入门级三等名额分配方案

1.入门级一等评级分数线位于全国基准分数线150分(含)以上的省份,70分(含)以上未获一二等的认证者,均可评三等。

2.入门级一等评级分数线低于全国基准分数线的省份,不设三等;

NOI各省组织单位根据上述提高级二三等、入门级二三等评级办法,可结合本省(市)实际情况上调评级分数线,确定本省分数线及认证名单,于12月10日12:00前上报CCF 。

中国计算机学会

2019年12月9日

附:CSP-J/S2019第二轮提高级一等各省评级分数线

(按分数线由高到低降序排列)

省份评级人数分数线
浙江351311
香港5272
广东229255
江苏191250
重庆112245
四川180235
湖南188231
河北89229
江西65225
北京155215
福建185206
黑龙江38195
安徽145186
山东234186
湖北83185
辽宁56178
吉林38168
上海169166
河南66165
山西46165
陕西58152
天津21145
宁夏2141
澳门5141
广西48133
新疆20127
甘肃8124
海南8121
内蒙古18113
贵州28112
云南18108

 一等评级总人数为2859人,总比例为20.56%

CSP-J/S2019第二轮入门级一等各省评级分数线

(按分数线由高到低降序排列)

省份评级人数分数线
浙江312265
广东240250
江苏224240
上海215225
重庆94230
四川178215
安徽308210
北京226210
福建291210
湖南221210
山东184185
江西66175
香港5175
海南12160
湖北67155
河北60150
辽宁50150
山西61150
天津32150
吉林55145
新疆27145
广西74140
黑龙江29140
河南80135
贵州40130
宁夏7130
澳门3130
甘肃16120
内蒙古2110
陕西18110
云南18110

 一等评级总人数为3215人,总比例为20.98%

Noip 2019

NOIP–全国分区联赛

  NOIP(National Olympiad in Informatics in Provinces)–全国青少年信息学奥林匹克联赛(省赛):NOIP由中国计算机学会(CCF)进行全国统一命题,以省为单位在同一时间、不同地点由各省特派员组织考试。

  NOIP竞赛比赛时间

  NOIP在每年10-11月份,分别举行初赛和复赛。

  初赛侧重考察:

  学生的计算机基础知识和编程的基本能力,并对知识面的广度进行测试。初试为资格测试,各省初试成绩在本赛区前15%的学生进入复赛。

  复赛侧重考察:

  学生对问题的分析理解力,数学抽象能力,编程语言的能力和编程技巧、想象力和创造性等。各省联赛的等第奖在复试的优胜者中产生。

继续阅读