暴风雪
- 浏览: 394648 次
- 性别:
- 来自: 杭州
-
最新评论
-
wsyzyrxp：
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304：
[opengl]彩色立方体旋转 -
tyfengyu：
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu：
python的pca代码有2处错误：1.finalData = ...
[python]用python实现的pca算法 -
暴风雪：
McFlurry 写道前排(凑字数)！擦你怎么摸来这里的
诈尸总结
文章列表
题目地址：http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf
大致题意：
求出一个带权无向图中哪些边一定是最小生成树的一部分，输出这边的数量和他们权值的和。
大致思路：
先求一遍prim，记录哪些边在这个最小生成树上。然后依次枚举删去这些边，如果删掉第i条边之后最小生成树长度增加，则第i条边一定在最小生成树上。
附上这辈子写过的最丑的代码
#include<iostream>
#include<cstring>
#include< ...
[最大流唯一性判断]hdoj 4888
- 博客分类：
- 图论专区
题意
给出一个矩阵n行每一行数字的和，m列每列数字的和，以及矩阵上单个数字的最大值k N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400) and K(1 ≤ K ≤ 40)。问是否存在这样的矩阵，存在的话，这个矩阵是否唯一，如果唯一输出这个矩阵。
思路
存在性的判断比较简单，求出最大流之后查看最大流是否等于所有数字的和即可。关键是唯一性，之前做过的最小割唯一性zoj 2587:Unique Attack 并不适用这道题，忍不住去看了题解，官方解释是“解唯一的充分必要条件是完成最大流后的残余网络没有长度大于 2 的环。”，也就是说，如果存在环的话，流量依 ...
[DFS]Acdream 1431
- 博客分类：
- DP&&搜索
题意
输入n(n<=500),求有多少种n个数字的组合使得n个数字的和等于n个数字的乘积
思路
dfs即可，注意剪枝
/*************************************************************************
> File Name: main.cpp
> Author: bbezxcy
> Mail:522736096@qq.com
> Created Time: 2014年10月16日 星期四 18时40分16秒
*** ...
[后缀数组]acdream 1430
- 博客分类：
- 数据结构&&字符串
大致题意：
求出一个字符串(len<=10 000)中包含多少个出现至少两次的子串，且相同的子串互相不会覆盖
大致思路：
求出后缀数组和height数组之后，对每个后缀，求出所有和她公共前缀大于0的后缀中，构成合法子串数量的最大值。
一开始只想着用单纯O(n)的办法来解决，实际上由于字符串的特性，这个算法的覆盖度还是接近o(n)的
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const ...
题意：
给出一个n个点，m条边无向图(2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000).。求出存在哪些边，使得去掉这些边之后，最短路的长度会增加。
思路：
第一步求出最短路，并判断出哪些边可以在最短路上。并用这些边重新建图。
第二步，用第一步建出的图求出割边，得到的割边就是答案
要注意tarjan时可能会出现重边
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
...
大致题意：
求多个数列(n=1000)的最长公共子串。
大致思路：
一开始没有头绪，后来发现一点，长度为n的数列中每个数都属于1--n且不重复，所以根据每个数列中每个数字的位置来判定即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k,num[6][1003],mark[6][1003];
int dp[1003],res;
void dfs(int loc,int len){
if(dp[loc] ...
[KMP+乱搞]hdoj 4749
- 博客分类：
- 数据结构&&字符串
大致题意：
求文本串中最多能选出多少子串，使得这些子串和模式串匹配。这里匹配的标准是，串中任意两个位置大小关系相同。
大致思路：
对每个位置i求出 0---i中多少个值大于小于等于str[i]并根据这些值去匹配
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=100002;
int n,m,k;
int ttt[nMax],ppp[nMax],sum1[nMax][30],l ...
[2-sat]hdoj 4751
- 博客分类：
- 图论专区
大致题意
给出一个有向图，问这个图是否能分为两个完全图
大致思路
O(n^2)建图2-sa判定t即可
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=1000;
const int mMax=1000010;
class edge{
public:
int v,nex;
};ed ...
[KMP]hdoj 4763
- 博客分类：
- 数据结构&&字符串
题意：
给出一个字符串，问是否存在这样的子串E使得字符串可以表示为EAEBE的形式，其中EAB的长度都为任意值，存在的话输出E的最长长度，否则输出-1
大致思路：
参考http://bbezxcy.iteye.com/blog/1378468 求字符串中存在多少子串使得其既是字符串的前缀也是字符串的后缀。这道题求出所有符合的后缀之后，再判断是否有子串可以成为中间的那个E，并选出长度最小的即可
#include<iostream>
#include<cstring>
#include<stack>
#include&l ...
在一块n*m的区域中有一块a*b的刷子，这块刷子只能向下or向右，扫过的区域为x
给出一块区域，问这个区域是否可以由某块刷子刷成，如果可以输出刷子最小面积，不可以则输出-1
思路：
暴力枚举刷子的边长并验证，输出最小的刷子面积。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char str[1002][1002];
int n,m,ssa,ssb,sum,dpa[1002][1002],dpb[1002][100 ...
A水
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[200];
int mapp[300];
int main(){
int i,k,j;
char ccc[20];
char kbd[300]="qwertyuiopasdfghjkl;zxcvbnm,./\n";
for(i=0;i<strlen(kbd);i++){
mapp[kbd[i ...
赛后练习，慢慢找感觉
A要考虑很多种情况，特别是坐m站路车的距离大于n但是更便宜的情况
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,a,b;
int main(){
while(cin>>n>>m>>a>>b){
int x=a*m;
if(x<b){
cout<<a*n<< ...
A大水
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
int n,p,q,res;
while(cin>>n){
res=0;
while(n--){
cin>>p>>q;
if(q-p>=2){
res++;
} ...
A判断输入的数字有没有覆盖1--n，n最大只有100，所以直接暴力
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<int ,int>mmp;
int n;
int main(){
int i,j,k,b,a;
while(scanf("%d",&n)!=EOF){
mmp.clear();
scan ...
A暴力判断即可
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
bool inprim(int a){
int i;
int k=sqrt(a);
for(i=2;i<=k;i++){
if(a%i==0)return 1;
}
return 0;
}
int main(){
int n,i,j,k;
wh ...