暴风雪
- 浏览: 394648 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
大致题意：
见：http://bbezxcy.iteye.com/blog/1439384
大致思路： 最小表示法果然快啊！！从7000多ms优化到900ms，膜拜Orz。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax =800000;
char sss[nMax];
int ...
大致题意： 题中的图片可以无视， 给出一串数，经过变化后变为另一个串，变化的方式是num[i]=abs(num[i+1]-num[i])，求变化后串的最小表示。
大致思路： 这里用的是后缀数组，把当前串复制一遍接到这个串后面做的，shi慢shi慢的……Orz。马上去学学最小表示去。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int inf=1<< ...
大致题意： “abracadabra” > “aabracadabr” > “raabracadab” > “braabracada” > “abraabracad” > “dabraabraca” > “adabraabrac” > “cadabraabra” > “acadabraabr” > “racadabraab”。大致思路： 把第一个字符串复制一份接在自己后面，并将其作为文本串，把第二个字符串作为模式串，做一遍KMP求出模式串在文本串中出现的位置 ...
大致题意：
给出你n个单词，如果一个单词的尾部和另一个单词的头部相同那么这两个单词就能连在一起(比如‘abc’和‘cde’就能够连成abc-cde)，如果这个单词后面的数字是1，则代表这个单词的逆序也是一个单词，可以翻转过来。求所有单词能不能连成一长串。
大致思路： 转化为混合图的欧拉回路，把字母当作节点。注意要用并查集来检测图是否连通。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespa ...
大致题意：
给出一个长度为l的文本和一个由n个单词组成的字典。求至少从文本中去掉多少个字符才能使得这个文本全部由字典中的单词组成。
大致思路：
DP，转移方程为dp[i]=min(dp[i-1]+1,dp[pos+1]+i-pos-1-tmp);//dp[i]为前i个字符中需要去掉的字符数量。
转移的示例如下，这里文本是browndcodw 文本是cow，从str[9]开始匹配~~
b r o w n d c o d w
c o w //找到一个匹配，并需要剔除一个字母。所以dp[10]可以 ...
大致题意： 就是裸的二分图最大匹配，但是数据量达到10000，所以邻接表不再适用，要使用邻接矩阵存储。
大致思路：
没想到照着邻接矩阵的改改就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=20005;
class edge{
public:
int v,nex;
};edge e[200005];
int n,m,k,head[nMax];
int lin ...
大致题意：
给出一列由n个数字组成的数，求出最长递减子序列的长度，并求出共有多少种最长递减子序列。
大致思路： 第一问很简单，第二问实在看不出来了，查的题解，囧啊，大家不要bs我~~大致过程就是在第一个求最长递增子序列的基础上，对于当前元素是否能够接在其他递减子序列后面再做讨论。要注意两个子序列完全相同的情况，在这里完全相同的子序列只能算一个。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax ...
大致题意：
给出一串数，求出这串数可能组成多少种字母排列。
大致思路：
简单DP，一定要注意0的情况
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=50000;
char str[nMax];
long long dp[nMax];
int judge(int i){
if(str[i]+str[i-1]*10>=1&&str[i]+str[ ...
大致题意：
给出一个正整数n，并给出一个由n+1个点组成的DAG，每个点有一个权值，代表走到这个点后能得到的收益值，1和n+1点的收益值是0。求出从1点走到n+1点收益值最大是多少。
大致思路： DP，用记忆化搜索来实现。
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=30 ...
大致题意： 给出两个数n,nc，并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的子串有多少种。
大致思路： 裸哈希之，将长度为n的子串看作 n位的 nc进制数，将问题转化为共有多少种数字。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int hash[30];
bool loc[20000000];
char str[1000000];
int main(){
int n,m,cnt,sum, ...
大致题意：
给出n个数，把这个数列分为三段，再把三段反转后连接在一起成为一个新串，求字典序最小的新串。
大致思路：
由于需要翻转，所以在输入时就按照反序输入。比如样例输入是5 10 1 2 3 4。我们从后向前读入就变为5 4 3 2 1 10。对这列数求出后缀数组。在大于2的后最中找到最小的后缀并输出。对于剩下的前缀s，我们把s串接到自己后面，也就是ss。再对这个串求出后缀数组，然后再把s中最小的前缀输出。最后把剩下的串输出。
对于第二步为什么要复制剩余串接在后面，用下面案例说明
6
10 1 2 2 3 4
第一步翻转后得到
...
大致题意：
给你一个字符串，现在要生成一个新的字符串，规则是每次从原字符串的头部或者尾部取一个字符放在新字符串的尾巴上。求字典序最小的新字符串。
大致思路： 正解是后缀数组，这里用贪心水过去了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=30005;
char str[nMax];
bool check(int a,int b){
while(a<b){
...
大致题意：
给出一个字符串，求出这个字符串中最长的回文串。如果有多个回文串的长度相等且都是最大，则输出最靠前的那个。
大致思路：
首先肯定是要把原字符的逆序串接到原字符串的后面。然后便是从0~~len扫描这个字符串，假设第i个位置是一个回文的中心，然后求出i个i对应位置的lca的最大值即可。每次枚举时要分奇偶两种情况考虑。
献上两组数据：qweRTYewq zzzdzaadzzz
#include<iostream>
#include<cstdio>
#include<vector>
#inc ...
好吧，人品又消耗了，rating没跌。可是，只涨了20几分，和没涨一样。怎么说呢，编码能力，思维清晰度还是跟不上。cf的题目真的不错，虽说没有什么算法，但是都不是那么容易做出来，总要绕点弯子。
A，用一个vis数组来保证每个学生只能被记录一次，然后扫一遍就行了。但是手一抖就习惯性的把map[j][i]敲成了map[i][j]。浪费了五分多种才找到。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char map[200][2 ...
大致题意： 一排共n头牛排队站在一起，给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。
大致思路：
做到poj3415，居然碰到“单调栈”这种牛逼的玩意，于是专门来把这道题切掉。所谓单调栈也就是每次加入一个新元素时，把栈中小于等于这个值的元素弹出。接下来回到这道题。求所有牛功能看到多少牛，可以转化为：这n头牛共能被多少头牛看见。当我们新加入一个高度值时，如果栈中存在元素小于新加入的高度值，那这个牛肯定看不见这个高度的牛，就把这个元素弹出。每次加入新元素，并执行完弹出操作后，栈中元素个数便是可以看见这个牛的“牛数”~~~。
...