发表于 | 更新于
字数统计 6254 | 阅读时长 31

前言

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

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

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

day0

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

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

阅读全文 »

发表于 | 更新于
字数统计 1354 | 阅读时长 6

思路

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

阅读全文 »

发表于 | 更新于
字数统计 1794 | 阅读时长 8

前言

很久以前，我出了区间质数，当然求$l\dots r$之间的质数等于$\pi(r)-\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优化的效率。与算法竞赛不同的是，代码避免使用静态数组，而是根据输入规模动态分配内存。因此与静态数组的性能有一些差异。

阅读全文 »

发表于 | 更新于
字数统计 1907 | 阅读时长 9

概述

我从未写过模拟赛的题解，但是这次模拟赛全部是原题，因此写公开题解也不会有版权问题。所有题目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$中的质因数的总数。

阅读全文 »

发表于 | 更新于
字数统计 1938 | 阅读时长 9

前言

本文分为两个部分，分别总结我所知道的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也能支持很多新特性。

阅读全文 »