暴风雪
- 浏览: 390345 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
大致题意：
给出多个字符串，输出每个字符串的最短非公共前缀。
大致思路：
tire的简单变形，每个节点加一个值来记录经过这个节点的字符串数即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=500;
const int ...
大致题意：
给出n个不同长度的数串，如果某个串是另一个串的前缀，输出“NO”，否则输出“YES”。
大致思路：
其实是一个很简单的tire判断，很快就写了出来，但是TLE了。手贱翻了一下discuss才知道，动态tire树每次都new一个对象太费时间，要改用静态数组。遂改之，AC~~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using names ...
大致题意： 求一个字符矩阵的最小覆盖子矩阵，输出这个子矩阵的面积。
大致题意： 关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991
接下来就是把子串扩展到二维，对行和列分别求出最小覆盖子串长度，相乘输出即可
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int ...
大致题意： 给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。
大致思路： 如左图，假设黑色线来代表字符串str，其长度是len，红色线的长度代表next[len]，根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同（也就是两条线所对应的位置）。我们再求出next[len]位置处的next值，也就是图中蓝线对应的长度。同样可以得到两个蓝线对应的子串肯定完全相同，又由于第二段蓝线属于左侧红线的后缀，所以又能得到它肯定也是整个字符串的后缀。
所 ...
大致题意： 给出一个长度为n的字符串，分别求出前n位前缀，分别可以由多少个相同的子串连接而成。
大致思路：
依旧是next数组的灵活运用，和poj2406差不多，在此不在赘述。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j= ...
大致题意： 给出一个字符串，求出这个字符串最多能够由多少个子串首尾连接而成。比如“ababab”就是由3个“ab”相连而成，所以输出3，“abcdef”只能看作一个“abcdef”所以输出1。
大致思路：
KMP中next数组的巧妙运用。在这里我们假设这个字符串的长度是len，那么如果len可以被len-next[len]整除的话，我们就可以说len-next[len]就是那个最短子串的长度
为什么呢？ 假设我们有一个字符串ababab,那么next[6]=4对吧，由于next的性质是，匹配失败后，下一个能继续进行匹配的位置，也就是说，把字符串的前四个字母，ab ...
大致题意：
给出一个由n个顶点m条边组成的无回路有向图。求最少可以同时存在多少路径，使得这些路径可以覆盖所有的点(注：每个都点可以被多条路径覆盖)。
大致思路: 最小路径覆盖的一点小小变形，由于这里的点可以被重复覆盖，所以除了按照普通求最小路径覆盖的方式建立二分图以外，还要对原图用floyd求一遍传递闭包，并更新二分图。接下来用点数n减去最大匹配得到的就是答案。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
co ...
大致题意： 给出两个字符串，求出模式串pat在母串text中出现了多少次。
大致思路：
基础的KMP算法，要理解KMP的实现原理。（http://bbezxcy.iteye.com/blog/1355293 kmp算法详解）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
char text[mMax],pat[nMax]; ...
大致题意：
给出一列共n个数，和一个正整数k。对于所有的大于等于1，小于等于n-k的数i，求出在[i,i+k]这个区间中最大的数和最小的数
大致思路：
借鉴 依然 的思路，要了解堆排序的大致运转方式以及堆内元素之间的调整过程。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000050;
int num[nMax],heap[nMax];
int n,he ...
大致题意： 给出一个由n个节点，m条边组成的无向图，每条边都有各自的长度和一个花费值c，意味着删去这条无向边需要的花费。给出两个点s和t，现在要删去一些边使得s到t的最短路增加，求花费最少是多少。
大致思路：
首先，对于一条边(u,v)，如果s—>v== s—>u +u—>v我们就可以认为这条边是s到t的最短路上面的一条边。用dijkstra先求出s到所有点的最短距离，然后枚举每条边用上面的方法判定这条边是否在最短路上。如果(u,v)是属于某个最短路的一条边，则在网络图中加上u->v，容量设为删去这条边的花费。接下来对图中的s点到t点求一遍最小割 ...
大致题意： 给出n个点的m条约束信息。每条信息表述为(P a b c)表示a在b北方距离c的位置，或者(V a b) 表示a在b北方1单位距离或者更远的位置。问是否可能存在符合以上m个要求的点。
大致思路： 把dis[i]设为其到始点的距离。第二个条件很简单dis[a]-dis[b]>=1 也就是dis[b]<=dis[a]-1。对于第一个，带等于号的条件dis[a]-dis[b]==c，我们可以转化为dis[a]-dis[b]>=c和dis[a]-dis[b]<=c 两个不等式，然后再转化为最短路三角不等式。由于所有点不一定互相连通，所以要设一个虚拟始点， ...
大致题意： 有n头牛，按照序号1……n排队，多头牛可以站在同一个位置(暂且这么认为)，也就是任意两头牛之间的距离都大于等于0。先给出ml组约束关系(u,v,w)代表第u牛和第v牛之间的距离要小于等于w。再给出md组关系(u,v,w)，代表第u牛和第v牛之间的距离要大于等于w。求这n头牛排成的队伍能否符合以上的约束，不能的话(也就是出现负环)，输出“-1”，如果距离是inf，输出“-2”。否则输出这个最短距离。
大致思路：
转化为差分约束模型。dis[i]表示第i头牛所在的位置。要注意除了题目所给出的ml+md条约束外还要加入任意两头牛之间距离大于等于0的约束，也就是dis ...
大致题意：
给n个小孩发糖吃，给出m组约束条件，每组条件包含三个数字a b c，表示b得到的糖果数目不能比a多超过c个。求第n个人得到的糖果数比第一个人最多能多几个。
大致思路：
spfa差分约束，dis[i]为第i人得到的糖果数目。对于每个约束管理就能列出不等式：dis[a]>=dis[b]-c，就能转化为dis[b]<=dis[a]+c。也就是差分约束最短路中的三角不等式。又由于这里求的是第n点与第1个点的关系，所以就把1设为最短路中的其实点而不舍虚拟起始点。按照这个关系建出图求出最短路，则dis[n]就是答案。
#include<ios ...
大致题意：
需要选一些整数点，给出m个约束条件，每个条件表述为，(s,t)表示在从s到t的区间内至少有2个点被选择。求最少选择多少个点。
大致思路：
和poj1201基本相同，在此不再赘述。这道题的点是从0开始取的，要小心数组越界。
详细代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=105000;
const int mM ...
大致题意： 需要从0~50000内选一些整数点，给出m个约束条件，每个条件表述为，(s,t,c)表示在从s到t的区间内至少有c个点被选择。求最少选择多少个点。大致思路： 转化为差分约束模型，设dis[i]为从0到i这个区间中被选择的点数。对每个约束，则有dis[t]-dis[s-1]>=c。另外还有一个隐含的约束条件就是0<=dis[i]-dis[i-1]<=1。另外要注意一点通过最短路径算法求出来的一组解当中,所有未知数都达到最大值。因为需要求的是最少加多少个点，所以要用spfa最长路。又由于最长路的三角形不等式为d(v) >= d(u) + w(u ...