暴风雪
- 浏览: 394742 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
大致题意：
求两个字符串的最长公共子串。
大致思路：
后缀数组+二分……水水，真心喜欢ural题目分类功能Orz
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=500000;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax] ...
大致题意：
给出一个字符串，求这个字符串有多少个不同的子串。
大致思路：
用后缀数组对这个字符串的所有后缀进行排序，然后依次根据每个后缀和排在他后面的那个后缀讨论即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max = 20001;
int num[Max];
int sa[Max], rank[Max], height[Max];
int wa[Max], wb[Ma ...
Greedy Gift Givers (gift1)
/*
ID:123ldss2
PROG: gift1
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<fstream>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=1005; ...
大致题意： 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度。大致思路： 这题用后缀数组超时了……囧rz。其实这里用的是manacher算法，效率为O(n)，比后缀数组的O(log n)要高。
算法详见http://blog.csdn.net/tanhaiyuan/article/details/7091019
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=100 ...
大致题意： 给出一个模式串P和一个文本串T求存在多少种数字组合(a,b,c,d)使得Ta..b + Tc..d = P。
大致思路： 可以用KMP求出模式串的每个前缀在文本串中出现的次数，再把字符串翻转过来，求出模式串的每个后缀在文本串中出现的次数，最后统计一下即可~~
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
cha ...
大致题意： 给出一个无向图和两个点s，t。求存在多少点，这些点不在从s到t的简单路上。
大致思路：
比赛时犯傻，上来就把这题当作图的双连通分量来做。后来发现错误，写了一个很暴力的dfs，TLE了，大圣也证明了，dfs很有可能是会超时的，只好作罢。赛后发现居然有人用dfs给水过去了，仔细看了一下居然和我的代码几乎一样，只不过用的是邻接矩阵，我用的是邻接表。遂把我的代码重构一遍，也过去了。
总结：1，数据很水，dfs都能过。
2，数据专门卡邻接表构图。
3，以后比赛时要尽量多试试。
#include<iostre ...
大致题意： 给出一个字符串，要求在这个字符串后面添加最少的字母使其成为回文串。
大致思路： 要注意添加的字母数不能为0，要分奇偶讨论。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int nMax =1000012;
int num[nMax];
int sa[nMax], rank1[nMax], height[nMax];
int wa[n ...
大致题意：
给出一个n*m的矩阵map，和两个数字L，U。求出是否存在这样的数列a[1~n]，b[1~m]。使得对于每一个map[i][j]有map[i][j]*a[i]/b[j]大于等于L，小于等于U。
大致思路：
用log运算把乘法转化为加法，求出不等式。然后做差分约束。另外注意一点，如果直接用每个点入队次数大于n来判定的话肯定会超时。
在牛人博客看到下面两种方法。
1：某个点入队次数大于sqrt(N)的时候
2：所有入队次数大于T * （N + M），其中T一般取2
这里用的是第一种。
#include<iostre ...
大致题意： 给出一个有向图，求图中是否存只在一个入度为0的强联通分量，存在的话输出这个分量中的所有点。否则只输出一个 0.
大致思路： Tarjan缩点，后对所有强连通分量求出入度出度~~
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=3015;
const int mMax=5 ...
大致题意： 福州现场赛的水模拟，给你一个棋局判定黑棋是不是死棋。
大致思路：
真是坑爹的题目啊，无力吐槽中。
贴上一组神数据
5 1 4
R 2 4
H 3 2
C 3 3
C 3 4
G 10 5
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=11;
int dang[nMax][nMax],n;
bool vis[nMax][nMax];
class ...
大致题意： 给你n种箱子，每种箱子都有各自的长宽高，每种箱子都有无限多个。如果一个箱子的长和宽都小于另一个箱子，那么这个箱子就可以放在那个箱子上面。求这n种箱子最多可以堆多高。
大致思路：
首先排序，按照长和宽中最长的那个。保证如果如果箱子i可以放在箱子j上面的话则j<i。然后就是简单的DP~~
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include <algorithm>
usin ...
大致题意：
给出一个字符串，求出其第一个最小表示和最大表示的位置，并分别求出最小表示的个数和最大表示的个数。
大致思路： 最小表示法+KMP扩展出的最小重复子串，一顿乱搞即可。本来打算用后缀数组，但是看数据量达到了1000000，还是作罢了~~囧
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax] ...
大致题意：
给出一个字符串，求最少再增加多少个字符才能使得这个字符串成为一个重复串。
大致思路： KMP最小覆盖子串的小小变形，最小覆盖子串的长度为len-(next[len-1])~~具体请参见 http://blog.csdn.net/fjsd155/article/details/6866991 另外poj2185也是这类题
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax= 1 ...
大致题意：
给出两个字符串s1，s2。现在我们可以把s1接到s2后面或者把s2接到s1后面，拼接的方式是：如果前面字符的后缀中和后面字符串的前缀中存在相同的部分，我们便把这一部分从第一个字符串中去掉，并把后面的字符串接上去。现在求拼接后长度最小并且字典序最小的字符串。
大致思路： 把两个字符串拼在一起，中间插入分隔符。对这个串求出后缀数组，并根据后缀数组求出s1+s2生成的字符串和s2+s1生成的字符串。比较这两个串，输出长度最小或者长度相同字典序最小的那个。
#include<iostream>
#include<cstdio>
...
大致题意：
给出m串长度为n的01串。有些串中可能包含*，这样的串可以表示两个串，*为1 和*为0。重复的算一种。比如题目中
*01
100
011
就代表了四个01串
001
101
100
011
现在我们需要消灭掉所有的01串，消灭方式有两种：
1一次消灭一个串。
2如果两个串的差别只有一位的话可以同时消灭这两个串。
问最少多少次操作可以消灭所有的01串
大致思路： 按照串中1的个数的奇偶性把串分为两个集合，因为1的个数的奇偶性相同的两个串之间的差别数必然大于1。想到这里接下来就简单了。(吐槽，从昨晚wrong到现在，真心被wa到内伤了， ...