暴风雪
- 浏览: 394420 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
大致题意： 要把n个字符串首尾相连成若干个环，如果把s1接到s2的后面可以得到一定的收获值，这个值等于s2的逆序 和s1的最长相同前缀的长度。求总收获值最大是多少。
大致思路： 看完题就感觉是KM二分图最大全匹配，匹配部分思路和hdu1853类似。感觉字符串部分的复杂度过高，以为有什么牛逼的算法，迟迟不敢下手敲，看了别人题解才发现暴力就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax ...
大致题意：
给你两个长度相同的字符串，问这两个串中的字母怎么样匹配才能使得总的复合度最大。
大致思路：
按照字母间的对应关系建二分图，求出最大全匹配后除以总长度。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax=55;
const int mMax=10005;
const int inf=1<<29;
int map[nMax][nMax];
int lx[n ...
大致题意：
n个部队到m个地区抗震救灾(缅怀四川地震死难同胞)。已知每只部队到每个地区的收益值，现在给出一种匹配方案。求出达到最大匹配时的收益值比当前匹配方案多多少，且需要有多少只部队的调动不需要改动。
大致思路：
由于种种原因不能直接按照mapch数组直接来求匹配的变动数，在这里我们把所有的收益值乘以10，如果之前的方案中 i->j，则在map[i][j]上面加一个1。然后在求最大匹配的时候对收益取余便能得到匹配的变动数。
#include<cstdio>
#include<cstring>
using names ...
大致题意： 给出一个有向图，每条路都有一个边长值。现在要在图中选出一些圈(回路)，使得 1，每个圈至少包含两个点。 2，每个节点只能属于其中一个圈。现在求这些圈的总长度最少是多少。
大致思路：
囧啊，此等水题居然想了半天没有想法，最后又钻到欧拉回路的死胡同里面去了。其实很简单，因为每个点都必须只属于一个圈，所以每个点的入读和出度肯定都是1。把每个点拆成两个点 i i'。从源点向每个点连一条边容量为1，费用为0，限制入度。从每个i'向汇点连边，容量为1，限制出度。如果原图中有一条边(u v)。则连接u->v'容量为1，费用为这条路的长度。最后对构出的图求出最小费用最大 ...
大致题意：
有n个小孩要去m间屋子，每间屋子只能住一个人。每个小孩都会对一些屋子打分。已知每个小孩不能去那些他打负分和没打分的屋子，求安排住宿后所有人对自己屋子打分之和最大值是多少。
大致思路：
KM二分图最大权匹配。在KM模板里面加一步检验是否所有的n都有匹配。很不清楚为什么加了一步，n>m就直接输出-1，却wa了，去掉之后ac了。求大牛解释。
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=505;
const int ...
大致题意：
给出一个无向图，判断这个图是不是二分图，如果不是的话输出“No”。否则输出这个二分图的最大匹配是多少。
大致思路： 首先我们可以先假定图中的点分别属于两个集合，且任何一条边所连接的两点不在一个集合中。将图中的每个点都拆作两个点( i1 和 i2 )分别代表这个点属于第一个集合和这个点属于第二个集合。然后根据上面的逻辑关系，假设i点和j点之间存在边的话则连接i1->j2 i2->j1 j1->i2 j2->i1。得到的图如果不符合2-sat则直接输出“No”。否则，直接对这个二分图求出最大匹配即可。
#include< ...
大致题意： 给出n个模式串，一个文本串，求出正序和逆序文本串中一共出现了多少种模式串。文本串的输入方式很奇怪，连续的相同字母可以用[nS]代替，代表着连着共n个S。
大致思路：
很奇葩的输入，处理起来有点麻烦，处理完之后就是套自动机模版了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1003;
const int mMax=6000000;
int len2;
char s ...
大致题意：
有n个帅哥要泡n个美女。对于每个帅哥，给出他可以选择的美女序号。然后给出一个可行的匹配。对于每个帅哥，求出他可以选择哪些美女，才能使得所有帅哥都有马子泡。
大致思路：
很神奇的一道强连通题目，点数达到8000，边数达到20000000，肯定不能够直接爆搜。更诡异的是他给出了一组可行的匹配，这和题目有关系么？其实，这个才是解题的关键！把所有的帅哥和美女都抽象成有向图的节点，如果一个帅哥i可以选择美女j，则连接i->j。如果在给出的可行匹配中如果帅哥i匹配美女j，则连边j->i。
对这个图求出强联通分量，可以看出在一个强连通分量中帅哥的个 ...
大致题意： 给出一个字符串，求出这个字符串的每个前缀在整个串中各出现了多少次。
大致思路： KMP小小变形，要深刻理解next数组的含义。
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int nMax=200005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j ...
大致题意： 给出一个模式串，一个文本串。求这个模式串在文本串中无覆盖的出现了多少次。
大致思路： 基础KMP，加上一个last限制。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
char text[mMax],pat[nMax];
int lent,lenp,next[nMax];
void get_next() ...
大致题意：
给出n组模式串数据，每组数据由一个01数字和一个模式串组成，再给出一个文本串。对于每组模式串数据，分别统计其在文本串中出现了多少次，如果前面的数字是0，则代表计数的时候可以重叠，如果是0则代表不能重叠。
大致思路： 好麻烦的一道题，有思路但是真的很难敲，要用多个数组来控制好数据之间的关系，最后还狂mle……擦。对于可以重叠的，直接ac自动机即可，对于不能重叠的，求出当前的位置距离其上次匹配的距离再判断即可。
#include<iostream>
#include<cstring>
#include<cstdio& ...
大致题意：
给出n个模式串，一个文本串，分别求出每个文本串子在模式串中出现的次数。
大致思路：
基本的AC自动机，要修改一些地方。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=1500;
const int mMax=2 ...
大致题意： 给出n个模式串，m个文本串。对于每个文本串，求出哪些模式串在这个文本串中出现过。最后求出能够包含模式串的文本串总数。
大致思路：
ac自动机模版的小小变形，要注意字符集是所有128个ASCII码可见字符。这道题用静态字典树的优化效果并不明显。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const ...
大致题意：
给出n个模式串(长度不超过50)，和一个文本串(长度不超过1000000)，求出有多少个模式串在这个文本串中出现过。
大致思路：
标准的AC自动机问题，主要是学习模版，理解自动机的匹配机制。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
...
AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。解决的问题：给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。（也是解决web开发中关键字链接的常用算法：n个关键字，1篇文章，找出关键字在文章出现的位置）思路：在一棵trie树上面做Kmp，每个节点都有个像Kmp一样匹配失败时的指针（失败指针），匹配失败时按照失败指针指向的节点继续匹配。要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。KMP中我们 ...