暴风雪
- 浏览: 394757 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
/*
ID:bbezxcy1
PROG: milk2
LANG: C++
*/
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
bool vis[1200000];
int main()
{
freopen("milk2.in","r",stdin );
freopen("milk2.out","w",st ...
大致题意： 给出n个士兵，再给出多组士兵之间两两可以匹配的关系。已知某个士兵最多只能与一个士兵匹配。求最多能够有多少对匹配，并输出这些匹配。
大致思路：
最大匹配问题，对于二分图来说用的是匈牙利算法，求一般图最大匹配用的是带花树开花算法。这里面要注意一点，输出匹配时，要把match[i]和match[match[i]]同时设为-1。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include & ...
大致题意：
给出一个由n个房子，由若干的单向路连接起来，每个房子都有一个权值，意味着进入这个房子得到或者消耗的能量。把你放在1点，给你100点的初始能量。现在问你能否到达n点且到达时权值大于0.
大致思路： 很好的题目，参考了小媛神的思路 Orz。首先用spfa求最长路，同时判定是否存在正圈，再用floyd求出传递闭包。如果spfa求出的dis[1,n]大于0。或者从起点可以到达某个正圈，且这个正圈可以到达终点，则认为存在可行方案。
#include<iostream>
#include<cmath>
#include<cs ...
大致题意： 给出一个100*100的池塘，池塘中心位于二维坐标原点。池塘中心有一个直径为15的圆形岛屿，一个人站在岛屿上。给出池塘中n个小岛的位置和这个人的最大步长。求这个人想到池塘对岸的话最少要走多长的距离，最少要迈多少步。
大致思路： 把小岛抽象为起点，对岸抽象为终点，求最短路即可。最短路的思路很好想到，但是需要精度控制的经验啊。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<fstream>
#include<cstri ...
大致题意： 给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
大致思路： 最短路稍稍变形，加入一个val限制即可
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=3050;
const int mMax=1000050;
const int ...
bbezxcy-ACM/ICPC模版已整理完成，下载后解压即可。求试用，求改错，求补充，求完善，各种求Orz…… 没有iteye账号的可以把这张图片另存为到电脑上，再把扩展名改为rar即可
大致题意： 给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。
大致思路：
裸的StoerWagner模版题，在神牛的博客瞎逛的时候看到了，就刷掉吧……希望不要降RP
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 505;
const int inf = 1<<30;
int map[nMax][nMax];
int v[nMax], dis[n ...
大致题意：
给出一个无向图，求出这个图的补图G。求出在G中存在多少个点使得这些点不属于任何一个奇环中。
大致思路： 这道题从一开始就是个杯具！先是把题目想成边的双连通分量做，狂哇。后来用割点的模版照着网上的代码改造出一个点双连通分量的代码，依然哇！！原因是同一个点可能属于不同的点双连通分量！！ 后来把搜索染色的过程加到Tarjan里面，还是哇！！检查出来原因是搜索u的时候，起点并没有标记其在那一块双连通分量！！ 前前后后花了我八天才AC……大概得终身难忘这道题了>_< 发图供大牛BS
给出一组可以判边双连通分量死刑的数据
...
大致题意：
给出两个字符串a,b和一个数字k，求出a中存在多少后缀，使得其和b中所有后缀的lcp的最大值等于k。
大致思路： 又弱智了的说，上来就用后缀数组+RMQ来爆，O(n^2)的效率果断TLE了，不要bs我……在网上看到的正解是先求出a中存在多少后缀，使得其和b的所有后缀的lcp最大值大于等于k，再求出a中存在多少后缀，使得其和b的所有后缀的lcp最大值大于等于k+1。求出这两个值之后相减即可……
#include<iostream>
#include<cstdio>
#include<vector>
#inc ...
大致题意： 如题。
大致思路： 后缀数组+二分的简单应用，可以扩展到多串匹配中去
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 500000;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];
int cmp(int * ...
大致题意：
给出一个数字m和一个字符串str，求出str中至少出现m次的最长的子串长度，并且求出这些子串中最靠右的子串的位置。
大致思路： 先求出后缀数组，二分枚举这个长度mid，然后分析height数组的每个大于mid的区间。过程稍复杂，具体看我代码即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=500000;
i ...
大致题意： 给出一个字符串，求出所有不重叠出现次数大于等于两次的子串的数目。
大致思路： 后缀数组的好题，思想很妙也很难想到。大致过程就是先枚举子串的长度tmp，对于每一个height值大于等于tmp的区间内找到sa的最大值和最小值，看他们之间的距离是否小于tmp，是的话则ans++；
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax= ...
大致题意： 给出一个由n个点，m条边组成的有向图，给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开，同时你会得到相应的收益值。求总收益的最大值。
大致思路：
网络流经典构图……
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int nMax=2000;
const int mMax=300000;
const ...
大致题意： 见http://www.nocow.cn/index.php/Translate:USACO/castle
大致思路： 苦逼模拟的并查集……usaco里面的还需要输出炸哪一堵墙……崩溃>_<
/*
ID:123ldss2
PROG: castle
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=100005 ...
大致题意： 给出一个有向带权图，设1为源点，n为汇点。现在要在2~n-1的点中加上一条容量为无穷的边使得这个图的最小割最大。求加上这条边后最小割最大是多少。
大致思路： 先对原图求一遍最小割，割值为maxflow，在残余网络中分别找到两个点a,b，使得从1点到a的最大流值最大，为flowA，从b点到n点的最大流最大，为flowB。然后用maxflow+min(flowA,flowB)得到的就是答案。
#include<iostream>
#include<cstring>
#include<cstdio>
#includ ...