翻译都很乱，我自己翻译题目
给出一个COWBASIC程序，所有运算对$10^9+7$取模，求返回的结果。
COWBASIC语言1
2
3
4
5
6
7
<变量名> = <表达式>
<字面值> MOO {
<语句列表>
}
RETURN <变量名>
1
2
3
4
5
<字面值>
<变量名>
( <表达式> ) + ( <表达式> )
参考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)$不能通过，那么怎么做呢？
以下来自课件
$t_{i,j}^{(k)}$表示i和j经过前k个点是否连通。
定义集合$T_i^{(k)}={j\vert t_{i,j}^{(k)}=1}$
对于$k\ge1$，有
用bitset或手动压位，可以在$O(\frac{n^3}{w})$求出传递闭包，其中w表示字长，为64或32。
来自WC的小技巧，Pascal不支持
仅适用于计算$2^n$的精确值，且$\left\vert n\right\vert<2^{14}$
浮点数能精确表示$2^n$，因为大部分浮点数内部都以2为底数，n的范围与浮点数类型有关。常用浮点数最高精度的long double也只有15位阶码。
直接使用pow函数即可计算。
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;
}
维护多个数列，要求每个数列支持修改首部、尾部，支持随机访问。而且时间复杂度应该为$O(1)$或$O(\log n)$(需要卡常？)
如果只有一个数列，那么问题就非常简单了。
只要维护一个头指针和尾指针，开始时在数组中间。这样可以轻松地插入、删除、随机访问了。
期望得分:30
有了处理一个数列的方法，我们只需对所有操作排序，依次处理每个数列即可。
我们可以维护$n$个链表，那么插入、删除操作都是$O(1)$的，但是随机访问是$O(n)$的。
可以使用std::list，也可以自己实现链表。
期望得分:40
std::vector也可以用来维护数列，其中修改尾部和随机访问操作是$O(1)$的，修改首部操作是$O(n)$的(但是比数组快，有人认为接近于$\sqrt n$)。
期望得分:60(其中测试点#8就利用了std::vector的快速修改首部操作)
综合一个数列、链表和std::vector，按照测试点特征选择方法，其中有的测试点可以用多种方法通过。
期望得分:80(很良心吧)
一个月之后的省选二试
大约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}$，每次只需将无效的点删除即可。