三角形斜着放即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll S;
int main()
{
scanf("%lld", &S);
ll y = (S + int(1e9) - 1) / int(1e9), x = y * int(1e9) - S;
printf("%d %d %d %d %lld %lld\n", 0, 0, int(1e9), 1, x, y);
return 0;
}
Continue reading → 看完题面就知道应该又是传统的字符串重工题，最后写了我 6.3KB。
首先建出 SAM 然后处理倍增+线段树维护 endpos 集合是显然需要的。然后开始考虑这个二元组的含义。
想了一段时间如何正着算，发现这个东西成立的条件是或，所以正着算只能用子集容斥。所以我们考虑把条件进行反转，变成强与形式，然后用所有的二元组的数量 \( {n – 1 \choose 2} \) 来减掉即可。
如何算正好不符合条件的二元组数量呢？分两种情况讨论：
这个题读完之后大概能知道是要建一个反串的 SAM，然后通过倍增定位 \(A, B\) 串然后加边，找最长路即可。
但是发现直接这样做，碰到 \(|A| < |B|\) 的时候会 GG，因为可能会出现在同一个节点上。这个时候我们就通过长度进行排序，给被重复的节点多做几个影子节点即可。
Continue reading →给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\)，处理\(q\)个询问：在数组的字段\([l,r]\)内是否存在排列的环形偏移。
考虑正向扫描，处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置，并同时更新自己所在的位置供下一次循环进行使用：
这道题耗了我一个上午。今天上午因为得知 NOIp 2018 成绩之后无法稳定心态去上课，所以翘课来机房写题。而当我看了半天的书和题解之后，我整合出了一个思路。
我们首先把整个序列存入\(pre[]\)数组之中，然后我们从端点\(L=1\)开始枚举右端点。我们选择倍增来加速。写一个\(check(num)\)函数来检测该区间内的校验值是否符合标准。校验值的计算策略是进行排序之后取最大和最小、次大和次小、…进行计算。我们排序可以使用归并排序的思想，因为我们的区间长度是以\(2\)为底的幂，且是从小到的枚举的，所以我们每次只需要排序区间右半部分，然后进行合并操作即可。具体看代码吧。