Home

有一个 $n × m$ 的点阵，他想要从这 $n × m$ 个点中选出三个点 ${A, B, C}$，满足 1.三角形 $ABC$ 面积不为0且其内部不存在整点。 2.边 $AB, BC, CA$ 上不存在除了端点以外的整点。 现在勇太想要知道有多少种不同的选取方案满足条件。 当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？ 注意 ${A, B, C}$ 与 ${B, A, C}$ 视为同一种方案。 $1\leq n,m \leq 5×10^9$ 题目中限制三角形内部没有整点并且边上没有除了端点之外的点，那么根据皮克定理 三角形面积只会是$0.5$。假设三角形的包围盒大小为$a×b$，必定有$gcd(a,b)=1$，我们假设三角形的另外一个定点为$(x,y)$，...

题目链接： https://codeforces.com/gym/102028 H.Can You Solve the Harder Problem? 显然是个后缀数组，赛场上卡在了求区间每个前缀最大值的和的问题上。想了半天只想到一种莫队加单调栈的巨难写的搞法。最后几十分钟还在处理莫队转移的边界问题，最后没写完就结束了。 题解给的做法是这样的。首先枚举区间左端点，同时维护一棵线段树，假设当前枚举的左端点是$l$，线段树中$i$位置存放的值是$[l,i]$区间的最大值，这样对于我们所枚举的这个$l $对于答案的贡献就可以在线段树里区间求和得到。 那么我们怎么在左端点不断改变的同时，使得线段树里的对应新的左端点呢？考虑从右向左枚举左端点，同时维护一个单调栈，这样每次新元素入栈时，把线...

从这个题中学到了用后缀数组很快求出每个字符串每个后缀不同子串个数的方法。 从后往前挨个插入原字符串的每个后缀，求出它与字典序相邻的两个后缀的$lcp$就可以去重了。 #include <bits/stdc++.h> using namespace std; const int maxn=200050; typedef long long ll; char str[maxn]; int nxt[maxn]; int getNxt(char *str,int n) { nxt[1]=0; for(int i = 2,u=0; i <= n; ++i) { while(u && str[i]!=str[u+1]) u=nxt[u]; if(s...

题目描述 There is an integer sequence of length $2N$: $A_0,A_1,…,A_{2N−1}$. (Note that the sequence is $0$-indexed.) For every integer K satisfying $1≤K≤2N−1$, solve the following problem: Let i and j be integers. Find the maximum value of $A_i+A_j$ where $0≤i<j≤2N−1$ and $(i\ or\ j)≤K$. Here, or denotes the bitwise OR. Constraints $1≤N≤18$ $...

Hello world! smile