Given a string, we need to find the total number of its distinct substrings. Input T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 1000 Output For each test case output one number saying the number of distinct substrings. Example Sample Input: 2 CCCCC ABABA Sample Output: 5 9 Explanation for the testcase with string ABABA:  len=1 : A,B len=2 : AB,BA len=3 : ABA,BAB len=4 : ABAB,BABA len=5 : ABABA Thus, 继续阅读 >>


楚东方 17/11/24 08:54:38
Milk Patterns Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 16696   Accepted: 7371 Case Time Limit: 2000MS Description Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can't predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality. To perform a rigorous study, he has invented a co 继续阅读 >>


楚东方 17/11/24 08:43:47
Musical Theme Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 31535   Accepted: 10511 Description A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.  Many composers structure 继续阅读 >>


楚东方 17/11/23 11:46:33
1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 975  Solved: 419 [Submit][Status][Discuss] Description Farmer John's cows, pampered since birth, have reached new heights of fastidiousness. They now require their barn to be immaculate. Farmer John, the most obliging of farmers, has no choice but hire some of the cows to clean the barn. Farmer John has N (1 <= N <= 10,000) cows who are willing to do some 继续阅读 >>


楚东方 17/10/28 21:52:12
1638: [Usaco2007 Mar]Cow Traffic 奶牛交通 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1008  Solved: 389 [Submit][Status][Discuss] Description 农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治. 这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接. 在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为0的路口,且所有入度为0的路口都会有奶牛. 帮助FJ找出最忙碌的道路, 继续阅读 >>


楚东方 17/10/27 22:43:47
A clique is a complete graph, in which there is an edge between every pair of the vertices. Given a graph with N vertices and M edges, your task is to count the number of cliques with a specific size S in the graph. Input The first line is the number of test cases. For each test case, the first line contains 3 integers N,M and S (N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10), each of the following M lines contains 2 integers u and v (1 ≤ u < v ≤ N), which means there is an edge between verti 继续阅读 >>


楚东方 17/10/26 23:52:12
Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4i4. Now, you need to write 继续阅读 >>


楚东方 17/10/26 23:44:30
HDU-1002 大数A+B import java.math.BigDecimal; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T; T = in.nextInt(); for(int cas = 1;cas <= T;cas++ ) { System.out.println("Case "+cas+":"); BigInteger a = in.nextBigInteger(); BigInteger b = in. 继续阅读 >>


楚东方 17/10/25 23:06:51
二分图最大匹配问题。 【建模方法】 在二分图的基础上增加源S和汇T。 1、S向X集合中每个顶点连一条容量为1的有向边。 2、Y集合中每个顶点向T连一条容量为1的有向边。 3、XY集合之间的边都设为从A集合中的点到B集合之中的点,容量为1的有向边。 求网络最大流,流量就是匹配数,所有满流边是一组可行解。 【建模分析】 基本的二分图最大匹配,可以直接用匈牙利算法或Hopcroft_Karp算法解决,更一般的方法是网络最大流。 最大权闭合图 【问题分析】 最大权闭合图问题,可以转化成最小割问题,进而用最大流解决。 【建模方法】 把每个实验看作二分图X集合中的顶点,每个设备看作二分图Y集合中的顶点,增加源S和汇T。 1、从S向每个Xi连接一条容量为该点收入的有向边。 2、从Yi向T连接一条容量为该点支出的有向边。 3、如果一个实验i需要设备j,连接一条从Xi到Yj容量为无穷大的有向边。 统计出所有实验的收入只和Total,求网络最大流Maxflow,最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点 继续阅读 >>


楚东方 17/10/19 09:25:57
题目链接 大牛思路: 【问题分析】 二分图点权最大独立集,转化为最小割模型,从而用最大流解决。 【建模方法】 首先把棋盘黑白染色,使相邻格子颜色不同,所有黑色格子看做二分图X集合中顶点,白色格子看做Y集合顶点,建立附加源S汇T。 1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。 2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。 3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。 求出网络最大流,要求的结果就是所有格子中数值之和减去最大流量。 【建模分析】 这是一个二分图最大点权独立集问题,就是找出图中一些点,使得这些点之间没有边相连,这些点的权值之和最大。独立集与覆盖集是互补的,求最大点权独立集可以转化为求最小点权覆盖集(最小点权支配集)。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。 对于一个网络,除去冗余点(不存在一条ST路径经过的点),每个顶点都在一个从S到T的路径上 继续阅读 >>


楚东方 17/10/18 23:12:56