前言

关于Pascal

Pascal已经离我们很远了，将要退出NOI的支持。实际上，现在OI已经很少用Pascal了，常规的都是C++。但是Pascal更容易学习和阅读，尽管标准提供的功能并不丰富。

关于Turbo Pascal

Turbo Pascal是我最早用的IDE，在Windows的时代，它已经相当古老了。现在虽然有Free Pascal，但是其稳定性和编译速度比不上TP。而GNU Pascal早已停止更新，虽然还能找到，但是相当难用。

TP的中文资料并不丰富，但是在bitsavers.org上有很多文档，在winworldpc可以获得各种版本的TP，这也成为了研究的基础。TP可以在CP/M-80,CP/M-86和DOS下使用，我只研究DOS的版本，毕竟CP/M更加古老。然而，在我用的win64平台上，根本不能运行16位的TP，所以我还需要PCem——一个PC模拟器。

本文以描述功能为主，并加上一些图片，避免涉及过多的代码。另外，本文第一版可以在[OLD]2017-04-09-Turbo-Pascal的历史.md中找到。

本文约定

$\left\vert S\right\vert$:集合$S$的元素数量

${x\vert p(x)}$:符合$p(x)$的元素组成的集合

$\land$:逻辑与

$\lor$:逻辑或

概述

简单的测试题3是完整的NOIp Senior，分2天，目前只有PDF版本的题目，所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。

另外，借助pdf2htmlEX，题目和题解转为HTML版本：

• day1
  • solution
• day2
  • solution

可以尝试在这里提交：fact core_region

前言

本文分为两个部分，分别总结我所知道的C++在OI中的，和其他软件的推荐。

C++ in OI

C++是相当复杂的一种语言，在OI中除了广为人知的部分外，也有其他有趣的内容。当然，以实用为主。

现在稳定的C++版本有C++98、C++11、C++14，现在很多OJ还只支持C++98，但也不乏对于后两者的支持。在NOI系列比赛中(还是比较功利)，GCC版本为4.8.4，默认标准是C++98，提交的也是，但是也可以在本地使用绝大部分C++11特性(称为C++0x)。最新的GCC稳定版本为7.2，但是由于某些原因，MinGW-w64尚未编译这个版本，因此我一直用7.1。GCC 7.1默认的标准是C++14，但也有部分C++17支持。另外，MSVC也能支持很多新特性。

概述

我从未写过模拟赛的题解，但是这次模拟赛全部是原题，因此写公开题解也不会有版权问题。所有题目2s,512MB。

prmq

来源

codechef June17 Chef and Prime Queries

题意

给定$N$($N\le10^5$)个数$A_{1\dots N}$($2\le A_i\le 10^6$)，$Q$($Q\le10^5$)个询问$L,R,X,Y$($1\le L\le R\le N,1\le X\le Y\le 10^6$)，求$A_{L\dots R}$中的数包含$X\dots Y$中的质因数的总数。

前言

很久以前，我出了区间质数，当然求$l\dots r$之间的质数等于$\pi®-\pi(l-1)$，其中$\pi(n)$为质数计数函数，表示$1\dots n$中质数的个数。

我最初给出的方法是分段打表+Miller Rabin素性判定，可以解决$n\le10^9$规模，但是更大的规模无法打表，因为内存不够……最近看到洛谷P3912后，zyy提供了LibreOJ #6235，求$\pi(n),n\le10^{11}$。对此我想大致了解一下质数计数算法。

筛法

计算$\pi(n)$最简单的想法就是筛法，这里同时来比较一下埃氏筛和欧拉筛的实际效率，以及bitset优化的效率。与算法竞赛不同的是，代码避免使用静态数组，而是根据输入规模动态分配内存。因此与静态数组的性能有一些差异。

来自WC的小技巧，Pascal不支持

适用范围

仅适用于计算$2^n$的精确值，且$\left\vert n\right\vert<2^{14}$

浮点数能精确表示$2^n$，因为大部分浮点数内部都以2为底数，n的范围与浮点数类型有关。常用浮点数最高精度的long double也只有15位阶码。

使用方法

直接使用pow函数即可计算。

C++

1
2
3
4
5
6
7
8
9
10

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	cout.precision(n>0?0:-n);
	cout<<fixed<<pow(2.0L,n)<<endl;
	return 0;
}

思路

一个正方形可以由左上角坐标和边长确定，只要枚举所有正方形就能找到答案。所以时间复杂度=枚举左上角坐标的时间*枚举边长的时间*统计正方形内的草场的时间。原题$N\le500$，实际上$\mathcal O(N^3)$就能过了。我们可以做二维前缀和，并二分枚举边长，并用单调性在$\mathcal O(N^2)$的时间内判断，总的复杂度是$\mathcal O(N^2\log N)$的。但是我一开始两次二分，所以时间复杂度$\mathcal O(N^2\log^2N)$，非常慢。

前言

NOIp2017已经结束了，由于复赛结束后我没有机会写游记，到这个周末才补上。虽然下个星期期中考

初赛日期2017/10/14，复赛2017/11/11和12，今年还是衢州。本文只包含复赛。

值得一提的是，复赛day1双十一和马拉松，day(-1)和day0是学校秋季运动会，当然我们甚至没机会去看开幕式。

day0

上午有一场两个半小时的模拟赛，题目确实不难，但是我只有230，而很多人都300，没什么信心。

T3给定一棵树，求保留最少的边使得覆盖的点不少于K，由于一条边可以覆盖1或2个点，可以用树形DP或贪心求出最多有几条边可以覆盖2个点，而我却写了二分图匹配，还写错了。还好交了暴力的30分。

眼看着大部分科目都上完第一本教材了，我打算来总结一下学到的内容，这似乎很有趣，也能为新高一的同学提供一些参考。我们还是比较忙的，高一除了技术都要上必修。受到clc博客的影响而写的。

语文

苏教版。必修一很薄，除了认真学了几篇文言，现代文基本上没听多少。看来语文还远远有待进步，期中考差点要不及格了。

数学

人教版。必修一还是比较充实的，尤其对于非OIer而言。对于OIer，集合、函数、指数、对数应该很熟悉了，更不用说像二分法求零点之类的，相对容易补上。接下来的必修四包括三角函数、平面向量、三角恒等变换，第三章可能比较难，至于向量，在OI和物理中应该已经很熟悉了。