最近由于博客完全Git化，突然发现文章的修改时间全变成了Git clone的时间，也就是全都丢失了。看了这一事件之前的文章修改时间，也显示出集中化的特点，看来类似的事情发生了很多次，只是以前没有注意到而已。因此，我决定今后所有的文章都用updated来标记修改时间，而不是靠文件本身的时间，这样既能避免类似的问题，还能只修改meta（比如tag）而不改变修改时间。

然而，愿景虽好，但之前的文章的修改时间基本上都是错误的，现在需要根据Git log来恢复修改时间，任重而道远。更不幸的是，2018年以前我用的是jekyll，之后用的是hexo，在两个不同的仓库里。所以还得手动merge修改时间了。

咕咕咕……

早上仍然坐8:07的城际列车S2104，到达杭州南，即萧山，然后地铁5号线转2号线，到达虾龙圩。经过不少时间，终于坐上了接站的中巴车，直达宿舍，我是碧峰。然后领寝具、注册之类的，当然还有吃饭了。

宿舍的话，上床下桌挺好的，然而蚊帐三面有门，有点坑。最神奇的是日光灯，晚上终于有人来指点我们正确的打开方式。卫生间只有一个洗澡的位置，而且洗衣服也必须在那里，所以不能同时洗澡和洗衣服。而且没有公共卫生间！

问题描述

这是最为人知的跨平台问题之一

平台

• 在Windows下，我们一般使用mingw-gcc，一般使用MSVC风格的I/O
• 在Linux下，我们使用原生的gcc，一般使用GNU/ISO风格的I/O

表现

• 64位整数的I/O问题(signed/unsigned long long)
  • Windows下只能使用%I64d，%I64u
  • Linux下使用%lld，%llu
• 扩展精度浮点数的I/O问题(long double)
  • Windows下无法输入/输出long double类型，因为在MSVC中，long double==double
  • Linux下使用%Lf，%Lg，%Le等

说明

我的实用工具位于https://github.com/zhzh2001/Learning-public/tree/master/tools下，包含以下工具：

• npp_compiler 一个简单的Notepad++编译工具

• npp_macro 一个Notepad++宏生成工具

• ojql 一个推荐与Notepad++一起使用的OJ快速启动工具

• oldproj.Books

  • 一个于2014年完成的数据库例程，名为“家庭图书管理系统”，没有使用过。

  • 可以使用Delphi 7或更高版本以及Lazarus编译。

• progmon 一个借鉴了CCR-Plus的程序监视工具，可以得到内存峰值、运行时间以及返回值。

一个月之后的省选二试

Day1

• 大约12:15从学校出发，有些晚点

• 我们没有走高速，经过上虞；中间有一段路很窄，因为在施工

• 大约2点到达余姚中学，领取牌子和袋子

颐高科技楼……

• 然后来到不远处的如家，很快就完事了，开始烧水

lzh把包落在车上了……

思路

整体

首先，我们可以知道，要满足题意，两个正方形的坐标$(x_i,y_i)(x_j,y_j)$必须满足$\vert x_i-x_j\vert<k$并且$\vert y_i-y_j\vert<k$。如果有且仅有一组正方形满足条件，那么重叠部分的面积$ans=\vert k-(x_i-x_j)\vert\times\vert k-(y_i-y_j)\vert$。

最简单的方法是直接暴力扫描，时间复杂度为$O(n^2)$。

我本来打算写一个二维线段树的，但好像有些大材小用了，难度才提高啊。

根据官方题解，先对所有点排序，然后维护与当前点横坐标差值小于k的所有点的集合，每次查找点集中纵坐标最接近当前点的点，更新答案即可。

如何维护所有满足条件的点呢？因为点是有序的，满足$x_i\le x_{i+1}$，每次只需将无效的点删除即可。

1.数列

概述

维护多个数列，要求每个数列支持修改首部、尾部，支持随机访问。而且时间复杂度应该为$O(1)$或$O(\log n)$(需要卡常？)

非正解

测试点#1~#3

如果只有一个数列，那么问题就非常简单了。

只要维护一个头指针和尾指针，开始时在数组中间。这样可以轻松地插入、删除、随机访问了。

期望得分:30

离线方法

有了处理一个数列的方法，我们只需对所有操作排序，依次处理每个数列即可。

链表维护

我们可以维护$n$个链表，那么插入、删除操作都是$O(1)$的，但是随机访问是$O(n)$的。

可以使用std::list，也可以自己实现链表。

期望得分:40

std::vector维护

std::vector也可以用来维护数列，其中修改尾部和随机访问操作是$O(1)$的，修改首部操作是$O(n)$的(但是比数组快，有人认为接近于$\sqrt n$)。

期望得分:60(其中测试点#8就利用了std::vector的快速修改首部操作)

分段骗分

综合一个数列、链表和std::vector，按照测试点特征选择方法，其中有的测试点可以用多种方法通过。

期望得分:80(很良心吧)

参考ZJOI2017 Day2讲课《动态传递闭包问题的探究》

题目：洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows

总体思路

分析

给定n($n\le1000$)个数的m($m\le10000$)个大小关系，求出最少增加几个大小关系才可以给这些数排序。

很明显，如果没有任何已知关系，答案为$C_n^2=\frac{n*(n-1)}{2}$。要计算已知的关系能使答案减小的值，可以使用传递闭包，一般常用Floyd。

但是由于$n\le1000$，$O(n^3)$不能通过，那么怎么做呢？

改进Floyd

以下来自课件

$t_{i,j}^{(k)}$表示i和j经过前k个点是否连通。

定义集合$T_i^{(k)}={j\vert t_{i,j}^{(k)}=1}$

对于$k\ge1$，有

$$T_i^{(k)}=\begin{cases}T_i^{(k-1)}&k\notin T_i^{(k-1)} \ T_i^{(k-1)}\cup T_k^{(k-1)}&k\in T_i^{(k-1)}\end{cases}$$

用bitset或手动压位，可以在$O(\frac{n^3}{w})$求出传递闭包，其中w表示字长，为64或32。

题目描述

翻译都很乱，我自己翻译题目

给出一个COWBASIC程序，所有运算对$10^9+7$取模，求返回的结果。

COWBASIC语言

• 有三种语句：

1
2
3
4
5
6
7

<变量名> = <表达式>

<字面值> MOO {
<语句列表>
}

RETURN <变量名>

• 变量名为长度不超过10的小写字符串
• 字面值为不超过100000的正整数
• 语句列表为一个或多个语句
• 有三种表达式：

1
2
3
4
5

<字面值>

<变量名>

( <表达式> ) + ( <表达式> )

• 保证表达式中或返回的变量在使用前已经定义
• 保证返回在程序最后一行

题目来源于USACO月赛，数据范围有所加强

题目概述

注意事项

1. 所有题目中程序允许创建临时文件(仅供参考)。在C/C++中建议使用tmpfile函数创建临时文件，在关闭文件后将自动删除。

1
2
3
4
5
6

#include<stdio.h>
FILE *tmpfile( void );
//C
#include<cstdio>
std::FILE* std::tmpfile();
//C++

2. 新挑战*为附加题，同时测试交互题的情况。
3. 对于#标的题，请注意常数因子对于程序效率的影响(标程最长运行时间超过时限的一半)。