暴风雪
- 浏览: 394542 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
[小模拟]zoj 3838
- 博客分类：
- 模拟&&水题
题意
问需要修改多少个点使得这个正方形完全对称。
思路
针对在对角线上的点，在中间线上的点还有剩下的点分别求出需要修改的最少点数，相加即可。
点(x,y)关于主对角线对称的点是(y,x)，关于副对角线对称的点是(n-1-y,n-1-x)。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100;
char str[nMax][nMax];
int n;
char vis[ ...
[线段树]poj 3368
- 博客分类：
- 数据结构&&字符串
题意
给出一串数字，有m次询问，每次询问[ab]区间内出现次数最多的数字出现了多少次。
思路
一开始用线段树+延迟标记超时到死，后来发现只用哈希+区间极值做就可以
例如 11111【1111222233444488】888 求【】内的时候就把区间内的串分为1111 2222334444 88对中间的串哈希+区间极值再和两边的串长度进行比较
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map&g ...
[线段树成段更新]poj 2777
- 博客分类：
- 数据结构&&字符串
题意：
一段区间从1-n的初始颜色为1，每次进行两种操作1，C a b c 把[a,b]这个区间染成颜色c。2，P a b查询[a,b]区间内有多少种颜色。
思路：
这一题的关键在于用二进制存储一个区间内的颜色数量，新增颜色时对当前区间进行或操作来实现。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100000;
struct {
int l , r , cl ...
[线段树]poj 2182
- 博客分类：
- 数据结构&&字符串
题意：
n头牛站队，每头牛都有一个属于[1,n]唯一的数字。对于每头牛，现在已知前面多少头牛的数字比他的大，问这n头牛的数字序列。
思路：
和poj2828很相似，都是从后向前计算，建立一颗线段树，节点val值为，这个区间的空位数，然后从后向前更新线段树，也就是说，如果一个节点无法插入当前位置，那么就选择右侧最靠近这个节点的位置
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 8 ...
[线段树]poj 3264
- 博客分类：
- 数据结构&&字符串
题意
给出一串数字，m个询问，对于每次询问求出在区间[a,b]上最大值和最小值的差。
思路
水线段树
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 1000010;
struct{
int r,l,bg,sm;
}node[3*nMax];
int num[nMax];
void build(int left ,int right ,int u){
...
[线段树成段更新]hdoj 1698
- 博客分类：
- 数据结构&&字符串
题意：
对一个线段上的值进行修改，一次可以把[i,j]这个区间上的值改为1,2,或3。1---n这个区间上数字的和
思路：
一道很加深对成段更新理解的题目，需要成段更新加上一点技巧具体见代码update()
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100010;
struct{
int l, r, sum, lazy;
}node[3 * nMax];
int ...
[线段树成段更新]poj 3468
- 博客分类：
- 数据结构&&字符串
题意：
给出一串n个数，每次操作分为两种，分别是对[i,j]区间上的数字加上一个值，查询[i,j]区间上所有数字的和
思路：
对于这种一次要对一个区间进行更新的问题，用单点更新肯定会超时，这里设定一个add值，意思是如果更新的区间和当前区间左右完全相等的时候，用add值记录本应向下加上去的节点，并返回
#include<iostream>
#include<cstring>
#include<cstdio>
const int nMax = 100010;
typedef long long ll;
...
想不到时隔两年又被拉出来开棺鞭尸打比赛去，如此之鶸必然是被数块铁牌打脸了，中间细节实在不想多谈，都是泪。曾经距离胜利女神如此之近却又无可奈何擦肩而过(好好地代码交上去之后丢了个return然后返回wa，你们感受下)，自己在赛场也犯了不少傻逼错误。不过最终原因还是自己不够强不值那块牌子。在这里谢谢学长给了我这个机会，让我知道原来真的有梦想这个东西。
拿“我两年没干了”这种借口安慰自己真是够了，我不仅要干下去而且要干好。江大研究生的生活如果只是图个论文毕业，没有其他东西填充的话就太没意义了，不靠自己的力量拿块牌子太对不住曾经努力的那段时间了。
cf还 ...
[线段树]poj 2828
- 博客分类：
- 数据结构&&字符串
题意
n个人插队，每次某个人都会选择插入第i个人背后，输出最终的排队序列。
思路
建立一颗线段树，节点val值为，这个区间的空位数，然后从后向前更新线段树，也就是说，如果一个节点无法插入当前位置，那么就选择右侧最靠近这个节点的位置
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 200010;
struct{
int l,r,val;
}node[nMax*3];
voi ...
[线段树]hdoj 2795
- 博客分类：
- 数据结构&&字符串
题意：一个高h宽w的二维空间，每次放进去一个高为1，宽为a的物体，每次存放物体都是优先放在最高的位置，其次优先放在最靠右的位置，对于每一次放入物品，输出这个物品放在第几行。
思路：用线段树，每个线段初始val为w，每次查询返回最高一行可以存放的位置，并且更新区间节点最大值val
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int nMax = 200020;
struct ...
[线段树]hdoj 1394
- 博客分类：
- 数据结构&&字符串
题意
给出一列n个数字，每一个数字都和其他数字不同，现在每次都把第一个数挪到最后面，求这个过程中这个数列逆序数对最少有多少对。
思路
先用线段树求出初始的数列逆序对数，再用第一个数列推出第二个，第三个直到第n个，输出最小的那个
这里关键是线段树在lonn的时间复杂度内求出当前数列逆序数对的方法，每次插入一个数，num[i] ，都查询一遍在num[i]+1---n中存在多少个已经插入的点。
#include<iostream>
#include<cstdio>
#include<cstring> ...
[dfs]zoj 3761
- 博客分类：
- DP&&搜索
大致思路：
每一行的点和每一列的点都连上边，然后用dfs的方法把图变为一颗搜索树，然后由叶子向根删除节点即可
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int nMax = 2010;
const int mMax = 3000008;
class edge{
public:
int v,nex;
};edge e[mMax];
int k, ...
[dp]zoj 3791
- 博客分类：
- DP&&搜索
大致题意
给出两个长度为n的01串，每次可以修改第一个串中m个字符，问在第k次可以把第一个串改成第二个串的方法有多少种
大致思路：
挺明显的水dp，dp[i][j]为第i步两个字符串中不同的字符个数为j的方法的种类数。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
ll m ...
[kruskal]hdoj 4786
- 博客分类：
- 图论专区
大致题意：
一个无向图中，每条边都是白边或者是黑边中的一种，问是否存在这个图的一颗生成树使得生成树中白边的个数为一个斐波那契数。
大致思路：
求出生成树中白边可能的最大值和最小值，如果某个斐波那契数包含在最大值和最小值之间，则可判定存在这样的生成树。
要注意判定这个图是否联通
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int ...
[模拟]hdoj 5071
- 博客分类：
- 模拟&&水题
大致题意：
自己读
大致思路：
直接模拟，注意坑点：word值要用longlong，删除掉的点可能是always on top点，最后say goodbye的时候要先和top的人说
不明白的一点是，明明参数值会达到10^9为什么不能用hashmap?
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std ...