LightOJ 1058 平行四边形的判断定理
题目大意：给你n个点，求这n个点最多能组成多少个平行四边形。题目思路：这道题卡时间，而且卡内存。你要尽可能的想办法优化。平行四边形的判定定理：两组对边分别平行的四边形是平行四边形（定义判定法）；一组对边平行且相等的四边形是平行四边形；两组对边分别相等的四边形是平行四边形；两组对角分别相等的四边形是平...
LightOJ 1045 - Digits of Factorial （k进制下N!的位数）
1045 - Digits of Factorial PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB ...
lightoj 1243 - Guardian Knights 最小费用流
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#include <algorithm>#include <queue>#include...
lightoj 1179（线段树）
传送门：Josephus Problem题意：经典约瑟夫问题，有n个人，每次数到第k个人出列，求剩下的最后一人。分析：用线段树模拟约瑟夫问题，记录区间的减少情况，然后根据每次数到的人在区间排第几位，线段树log(n)找到并更新，总复杂度为O(nlog(n))。#include <cstdio&...
lightoj 1198 最大权重匹配
题目链接：http://lightoj.com/volume_showproblem.php?problem=1198#include <cstdio>#include <cstring>#include <cmath>#include <iostream&...
数论-欧拉函数-LightOJ - 1370
我是知道φ(n)=n-1，n为质数 的，然后给的样例在纸上一算，嗯，好像是找往上最近的质数就行了，而且有些合数的欧拉函数值还会比比它小一点的质数的欧拉函数值要小，所以坚定了往上找最近的质数的决心——不过11往上最近的质数是13，不能包括本身。这样胡来居然AC了，但是之后还是老老实实地去看别人怎么做...
LightOJ 1355 :Game of CS(树上green博弈)
Jolly and Emily are two bees studying in Computer Science. Unlike other bees they are fond of playing two-player games. They used to play Tic-tac-toe,...
lightoj1057 - Collecting Gold （tsp问题）
题目链接：http://lightoj.com/volume_showproblem.php?problem=1057题目大意：在二维矩阵中，给你一个起点和至多15个的目标点。要你求出从起点出发经过完所有的点后回到起点的最短路径值。每个点一步可以向 八个方向走。算法思路：一看就觉得是tsp，用状态压...
LightOJ 1033 Generating Palindromes（dp）
LightOJ 1033 Generating Palindromes（dp）题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87730#problem/A题目：DescriptionBy definition palindro...
lightoj1082 线段树
//Accepted 5596 KB 396 ms //线段树求区间最小值 #include <cstdio> #include <cstring> #include <iostream> #include <queue> #includ...
LightOJ1021 Painful Bases（状压DP）
容易想到状态dp[n][S][m]（S是数字出现的集合），表示前n位用了数字集S且模k余数是m的方案数。利用 (xy)base % k = ( x*base+y ) % k = (( x%k ) * base + y) % k ，进行状态第三维的转移。不过d[16][216][20]有2000多W的...
LightOJ 1245 数学题，找规律
LightOJ 1245 Harmonic Number (II)总结：看了题解，很严谨，但又确实恶心的题题意：求n/1+n/2+....+n/n，n<=2^31。#include<iostream>#include<cstring>#include<cmat...
LightOj_1408 Batting Practice
题目链接题意：击球训练中， 你击中一个球的概率为p，连续击中k1个球， 或者连续击空k2个球， 则训练结束。求结束训练所击球次数的期望。思路：设f[x]为连续击中x个球， 距离结束训练所需要的期望设g[x]为连续击空x个球， 距离结束训练所需要的期望f[x] = p * (f[x + 1] + 1)...
LightOJ1157 LCS Revisited（DP）
题目求两个字符串s1,s2不同的LCS个数。经典的求LCS的DP是这样的：LCS[i][j]表示s1[0...i]和s2[0...j]的LCSLCS[i][j]从LCS[i-1][j-1]+1（s1[i]==s2[j]）或max(LCS[i-1][j],LCS[i][j-1])（s1[i]!=s2[...
lightoj1370欧拉函数/素数筛
这题有两种解法，1是根据欧拉函数性质：素数的欧拉函数值=素数-1（可根据欧拉定义看出）欧拉函数定义：小于x且与x互质的数的个数#include<map>#include<set>#include<cmath>#include<queue>#includ...
Finding LCM LightOJ - 1215 （水题）
这题和这题一样。。。。。。只不过多了个数。。。Finding LCMLightOJ - 1215https://www.cnblogs.com/WTSRUVF/p/9316412.html#include <iostream>#include <cstdio>#include...
LightOJ1068 Investigation（数位DP）
这题要求区间有多少个模K且各位数之和模K都等于0的数字。注意到[1,231]这些数最大的各位数之和不会超过90左右，而如果K大于90那么模K的结果肯定不是0，因此K大于90就没有解。考虑到数据规模，数据组数，这题状态这么表示：dp[i][j][k]：位数为i模K结果为j且各位数之和模K结果为k的数字...
lightOJ 1317 Throwing Balls into the Baskets
lightOJ 1317 Throwing Balls into the Baskets（期望） 解题报告题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88890#problem/A题目：DescriptionYou pr...
[LightOJ 1027] A Dangerous Maze
A Dangerous MazeYou are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a door ...
LightOJ - 1265 概率
题意：有t头老虎，d头鹿，每天五种情况，虎虎，虎鹿，鹿鹿，鹿人，人虎，求生存的概率题意：鹿就是来迷惑你的（结果我就陷进坑了），无论怎么选最后一定只剩下虎虎，虎人两种情况对结果有影响，那么如果有n只虎，生存的概率就是n+1中取两个不同的，老虎中取两个不同的，n(n-1)/n*(n+1)=(n-1)/(...