SPOJ 962 Intergalactic Map (网络最大流)
http://www.spoj.com/problems/IM/962. Intergalactic MapProblem code: IMJedi knights, Qui-Gon Jinn and his young apprentice Obi-Wan Kenobi, are entruste...
SPOJ IM - Intergalactic Map - [拆点最大流]
题目链接：http://www.spoj.com/problems/IM/en/Time limit:491 msMemory limit:1572864 kBCode length Limit:50000 BJedi knights, Qui-Gon Jinn and his young appr...
SPOJ SUBLEX 求第k小子串
题目大意：对于一个给定字符串，找到其所有不同的子串中排第k小的子串先构建后缀自动机，然后我们可以将整个后缀自动机看做是一个DAG图，那么我们先进行拓扑排序得到 *b[N]对于每个节点记录一个sc值，表示当前节点往下走可以得到不同的字符串的个数然后从后往前，每次到达一个节点，当前节点sc赋1，然后每个...
SPOJ2666 QTREE4
我是萌萌的传送门我是另一个萌萌的传送门一道树分治……简直恶心死了……我在调代码的时候只想说：我*************************************************……昨天听ztc讲了讲树分治，下午心血来潮想写QTREE4……写的是边分治，然后调了一晚上没调出来，后来发现...
SPOJ - VISIBLEBOX ［multiset的使用］
tags:[STL][sort][贪心]题解：做法：先对数组a进行排序，再将数组a从头到尾扫一遍，使用multiset维护最小值，如果,即将放入集合的数字>=最小值的两倍,那我们就删除掉多重集合的最小值。最后，多重集合中元素的个数即为答案。证明：“人生得意须尽欢，莫使金樽空对月”。当即将进入集...
SPOJ BALNUM Balanced Numbers 平衡数（数位DP，状压）
题意：平衡树定义为“一个整数的某个数位若是奇数，则该奇数必定出现偶数次；偶数位则必须出现奇数次”，比如 222，数位为偶数2，共出现3次，是奇数次，所以合法。给一个区间[L,R]，问有多少个平衡数？思路：这题比较好解决，只有前导零问题需要解决。如果枚举到011，那么其前导零（偶数）出现了1次而已，而...
SPOJ - TSUM 母函数+FFT+容斥
题意：n个数，任取三个加起来，问每个可能的结果的方案数。题解:构造母函数ABC,比如现在有 1 2 3 三个数。则其中B表示同一个数加两次，C表示用三次。然后考虑去重。A^3表示可重复地拿三个。（无顺序）然后我们去掉拿了两个相同的方案A*B，由于有三种顺序（xxy,xyx,yxx) 所以*3最后再加...
SPOJ TSUM Triple Sums（FFT + 容斥）
题目Sourcehttp://www.spoj.com/problems/TSUM/DescriptionYou're given a sequence s of N distinct integers.Consider all the possible sums of three integers...
spoj TSUM - Triple Sums fft+容斥
题目链接首先忽略 i < j < k这个条件。那么我们构造多项式\[A(x) = \sum_{1<=i<=N} x^{A_i}\]显然答案就是 $ A^3(x) $中 $ x^S $的系数。现在我们考虑容斥：$ (\sum_{}x)^3 = \sum_{}x^3 + 3\s...
SPOJ - DISUBSTR 多少个不同的子串
694. Distinct SubstringsProblem code: DISUBSTRGiven a string, we need to find the total number of its distinct substrings.InputT- number of test cases...
SPOJ IITWPC4F - Gopu and the Grid Problem （双线段树区间修改 区间查询）
Gopu and the Grid ProblemGopu is interested in the integer co-ordinates of the X-Y plane (0<=x,y<=100000). Each integer coordinate contain a lam...
SPOJ - INTSUB 数学
题目链接：点击传送INTSUB - Interesting Subsetno tags You are given a set X = {1, 2, 3, 4, … , 2n-1, 2n} where n is an integer. You have to find the number of i...
SPOJ QTREE2 Query on a tree II
传送门倍增水题……本来还想用LCT做的……然后发现根本不需要 //minamoto #include<bits/stdc++.h> using namespace std; #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,...
spoj The Next Palindrome
题意：比给出的数大的最小回文数。先用前n/2长对称到后面，如果没变大，在中间加1，进位，再对称。//#pragma comment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>...
SPOJ 130 - Rent your airplane and make money（dp+优化）
题意：有n列预定航班，从st时刻开始出发，飞行时间为d，花费为p，且同一时刻不能有两个航班，求最大的花费对航班的开始时间（或结束时间）按升序排序，从后往前找到对应结束时间所在的航班位置（如按结束时间排序则需要从前往后找到开始时间所在航班位置，需要使用二分法）d[i]=max(d[j]+p)#incl...
spoj 3885
简单的博弈题，用dp解；每个人只能拿1，l，k个硬币；dp[i][j]表示第j个人拿是否能拿第i枚硬币；代码： #include<cstdio> #define maxn 1000007 using namespace std; bool dp[maxn][]; int x,l,m,k;...
D-query SPOJ 树状数组+离线
D-query SPOJ 树状数组+离线/莫队算法题意有一串正数，求一定区间中有多少个不同的数解题思路——树状数组说明一下，树状数组开始全部是零。首先，我们存下所有需要查询的区间，然后根据右端点进行从小到大的排序。然后依次处理这个区间中的答案，仔细想一下，后面的区间答案不会受到影响。怎么处理区间中...
BZOJ 1982 [Spoj 2021]Moving Pebbles（博弈论）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1982【题目大意】两个人玩游戏. 每次任选一堆，首先拿掉至少一个石头, 然后移动任意个石子到任意堆中. 谁不能移动了，谁就输了【题解】首先如果对于奇数堆，那么先手必胜，因为可以构建必...
【bzoj2318】Spoj4060 game with probability Problem
题目描述Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。现在Alice先手投掷硬币，假设...
spoj 78
数学 组合 隔板法#include <iostream>#include <cstring>#include <cstdio>#include <string>#include <algorithm>using namespace std...