暴风雪
- 浏览: 394546 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
大致题意： 给出一个字符串，求出内部循环次数最多的子串。如果答案有多个，输出字典序最小的。
大致思路：
先穷举长度L，然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的，所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次，记这个子字符串为S，那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远，记这个总长度为K，那么这里连续出现了K/L+1 次。最后看最大值是多少
以上内容摘自罗穗骞论文，花了好几天理解照着上 ...
地址 http://codeforces.com/contest/151
A：弱水题，分别求出三种食品分别用来提供几次toast，取最小值再除以人数即可，一点弯都不要转。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
int n,k,l,c,d,p,nl,np,a,b,cc;
while(scanf("%d%d%d%d%d%d%d%d",&n,&k,&l ...
大致题意：
给出一列共n个数，m次询问。每次询问包括两个数a，b。输出区间[a,b]中最大值与最小值的差。
大致思路：
RMQ区间极值求法的模版题。
以下内容转自：http://www.cnblogs.com/cnjy/archive/2009/08/30/1556566.html
RMQ(Range Minimum/Maximum Query)问题：
RMQ问题是求给定区间中的最值问题。当然，最简单的算法是O(n)的，但是对于查询次数很多（设置多大100万次），O(n)的算法效率不够。可以用线段树将算法优化到O（logn)（在线段树中保存线 ...
大致题意： 给出n个字符串。求出至少出现在n/2+1个字符串中的子串中，所有长度最大的子串。
大致思路： 二分+判定。输出的时候要加一个isp判定符，防止输出相同的字符串。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200001;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], ...
大致题意： 给出一个长度为n的字符串，再给出一个数字k。求出现至少k次的子串中长度最大是多少，注：可覆盖。
大致思路：
后缀数组+二分判定……水水。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax =1000012;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], ...
大致题意： 给出n个数字。首先将这n个数前后做差，得到另一个长度是n-1的序列。求出这个序列的最长重复子串，且这些子串不能重叠。
大致思路：
还是后缀数组+二分判定。传说中楼爷的男人八题Orz
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200001;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
in ...
大致题意：
给出n个字符串，求出一个最长的串，使得这个串或者这个串的回文在所有n个字符串中都出现。
大致思路：
把每个字符串拆为两个串，分别是原字符串和原字符串的回文串，把他们连接起来，中间插入分隔符。再将每个这样的结构都连接起来，中间同样插入分隔符。再转化为二分+判定即可。要熟知height sa数组的定义。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200001;
...
大致题意：
给出n个长度为60的DNA基因(A腺嘌呤 G鸟嘌呤 T胸腺嘧啶 C胞嘧啶)序列，求出他们的最长公共子序列。
大致思路： 和poj3450差不多，改改就能过。链接：http://bbezxcy.iteye.com/blog/1405685
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200001;
int num[nMax];
int sa[nMax], r ...
大致题意： 给你n个字符串，求出这n个字符串的最长公共子串。注意这里最长公共子串不是DP里面的LCS，这里必须要连续。
大致思路：
后缀数组的典型运用。首先把这些字符串相连在一起，中间用分隔符隔开，二分枚举公共子串长度。查看是否存在相邻的个后缀，他们分别属于n个字符串，且它们之间的最长公共前缀长度(height)大于枚举的长度
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 200 ...
首先献上模版
#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[Max], wv[Max], wd[Max];
int cmp(int *r, int a, int b, int l){
return r[a] == r[b] & ...
大致题意：
给出两个长度均不大于100000的字符串，求出这两个字符串的最长公共子串。
大致思路： 具体思路请参考罗穗骞论文，大致就是将两个串合并为一个，在中间插入分隔符，再求出合并后字符串的最长重复子串，求重复子串时要注意height[i]和height[i-1]应该本别属于分隔符的两边。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max = 200001;
int n, ...
大致题意： 在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。
大致思路：
看到了“最大最小”其实就应该想到是要用二分。这道题也是如此，首先二分枚举这个最大差值，再枚举下限，用匈牙利算法来验证枚举是否成立即可。但是这样做依然会tle，所以要加入一个辅助数组，来记录哪些数字曾经出现过，从而在枚举下界的时候可以避开那些无用的数字。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespac ...
大致题意：
有n个巧克力盒子摆成一圈，每个盒子中装有一定数量的巧克力，所有盒子中的巧克力的总数小于n。现在每次可以把一块巧克力从一个盒子移动到其相邻的盒子中，求最少移动几部才能使得每个盒子中最多只有一个巧克力。
大致思路： 很经典的构图。设源汇点，将每个盒子拆为两点a，a'。从源点想s连边，容量为盒子中巧克力的数量，费用为0。从 a->b'连边，容量为1，费用为0。对于两个盒子ab，如果a中的数量大于1，b中的数量等于0.则连接a->b'，容量为1，费用为两个盒子之间的最短距离。a'向汇点连边，容量为1，费用为0。求出最小费用就是答案。
...
大致题意： 吕布要跟曹操pk。吕布有n个小弟，曹操有m个。已知可以由k种打架的方式，每种方式都是一个吕布的小弟去虐另一个曹操的人，每种方式都有一个伤害值。而且吕布和曹操的人都只能干一架。求伤害值最少是多少。
大致思路： 二分图最小权匹配。初始值全部取负，求出最大匹配后再将这个值取负得到的就是答案。切记tire申请空间不要太给力，被MLE到shi了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int n ...
大致题意：
给出所有学生提供的名次段，判断最多有多少人没说谎，并按照字典序最大的原则输出这些学生编号。
大致思路：
2010年天津赛区匈牙利算法裸题，按照提供的数据建边即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=64;
const int mMax=100005;
const int inf=1<<30;
int low,high;
int map[ ...