spoj专题
【SPOJ】1825 Free tour II 点分治
传送门：【SPOJ】1825 Free tour II 题目分析：敲了两遍。。。 本题是论文题，具体见漆子超论文《分治算法在树的路径问题中的应用》。 在以root为根的第 i 棵子树上，我们用G[ i ，j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ，j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。因
【SPOJ】Triple Sums【FFT】
传送门：【SPOJ】Triple Sums 题目分析： 首先我们不考虑 i<j<k i<j<k这个条件，构造多项式： Y=∑xai \qquad\qquad\qquad Y = \sum x^{a_i} 那么 ai+aj+ak=S ai+aj+ak=S的个数即 xai+aj+ak=S x^{a_i+a_j+a_k=S}的个数，等价于 Y3中xS Y^3中x^S的系数。 然后我们考虑容斥
【SPOJ】【AGGRCOW】
总结：函数之间存在依赖。 然后一处修改了但是忘记修改另外的一处了。。。 #include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <list>#include <map>#include <set>#include <string>#inclu
SPOJ 1825 FTOUR2 - Free tour II (树上点分治)
题目地址：SPOJ 1825 树分治的题果然除了模板题就是金牌题啊。。。这题是一道论文题，想了好长时间。。。。终于过了，，，，注意一个坑点，如果权值全部为负的话，是可以不选任意一条边的，这样权值为0。。。也就是说初始值要设为0。。。 具体看漆子超的论文《分治算法在树的路径问题中的应用》。。 代码如下： #include <iostream>#include <string.h>#inc
SPOJ 1825 Free tour II
论文题： 在以root为根的第 i 棵子树上，我们用G[ i ，j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ，j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。 因为所有子树里包含黑点数最多的路径的包含黑点数len可以O(N)求出，我们按照每棵子树的len从小到大的顺序遍历，这样就能将G和F数组降低一维，以G[ i
SPOJ - QTREE (树链剖分)
基础的树链剖分题目，不过是边权，可以向下映射成点权或者按边剖分。 VIEW CODE #include <iostream>#include<stdio.h>#include<cmath>#include<string.h>#include<algorithm>#include<string>using namespace std;const int mmax=100
SPOJ 220后缀数组：求每个字符串至少出现两次且不重叠的最长子串
思路：也是n个串连接成一个串，中间用没出现过的字符隔开，然后求后缀数组。 因为是不重叠的，所以和POJ 1743判断一样，只不过这里是多个串，每个串都要判断里面的最长公共前缀有没有重叠，所以用数组存下来就得了，然后再判断。 #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<m
spoj 375. Query on a tree(树链剖分)
题目链接：spoj 375. Query on a tree 题目大意： poj 3237的简化版，用同一份代码都能过。 解题思路：略。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 10005;const int INF = 0x3f3
SPOJ 7001 Visible Lattice Points（莫比乌斯反演）
莫比乌斯反演，注意0的情况特殊考虑下就可以了 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1000005;int mo[N], prime[N], pn;bool vis[N];void Moblus() {memset(vis, false, siz
SPOJ 9894 Tichu ( 状态压缩 )
题目链接~~> 做题感悟：这题第一感觉就是麻烦，不但输出最小的次数，而且还要输出路径。。。。 解题思路：状态压缩 这题和 13 年的杭州网络赛的一题差不多，状态压缩 + 01 背包的思想 ，主要是预处理出所有合法的状态就好办了，然后类似 01 背包的方法去更新就可以了。 代码： #include<iostream>#include<sstream>
A - Crazy Rows SPOJ - HAROWS
题目： You are given an N x N matrix with 0 and 1 values. You can swap any two adjacentrows of the matrix. Your goal is to have all the 1 values in the matrix below or on the main diagonal. That is, fo
SPOJ 3267 DQUERY——求区间内不重复值的个数
Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the su
SPOJ - MINSUB——单调栈+01矩阵变换
You are given an matrix M (consisting of nonnegative integers) and an integer K. For any submatrix of M’ of M define min(M’) to be the minimum value of all the entries of M’. Now your task is simple:
SPOJ Count on a tree II
题意：给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。 分析：树上莫队模板题，利用欧拉序将树上路径转化为序列，注意我们询问的区间长度为2∗N，所以预处理的时候一定要循环到2∗N。 参考博客：https://www.cnblogs.com/zwfymqz/p/9223425.html https://blog.csdn.net/qq_39759315/artic
Spoj 8372 Triple Sums
传送门：http://www.spoj.com/problems/TSUM/ 思路：先不管i<j<k这个条件 构造一个多项式A(x)=sigma x^a[i] 那么S=a[i]+a[j]+a[k]的个数就是x^(a[i]+a[j]+a[k]=S)的个数 为了让指数相加，我们把A(x)进行立方 那么个数就是A(x)^3中S次项的系数 然后进行容斥,为了方便，以下省去指数a[i]
spoj 1811 LCS 后缀自动机
A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters oc
SPOJ-DQUERY HYSBZ 1878 HH的项链 (线段树/树状数组/莫队/主席树)
1878: [SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MB Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一 段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一 个问题：某一段贝壳中，包含了多
SPOJ 42. Adding Reversed Numbers
https://www.spoj.pl/problems/ADDREV/ 用python写真的很短....很爽... #!/usr/bin/env pythonn = input()while n:n -= 1a, b = raw_input().split()print str(int(a[::-1]) + int(b[::-1]))[::-1].strip('0')