强连通分支算法概述

2017年02月05日 35 阅读

强连通分支算法概述2015-02-17深度优先搜索有一种经典的应用：把一个有向图分解为各强连通分支。很多有关有向图的算法都是从这种步骤开始的。（算法导论P338，觉得简洁而精妙，分享下）STRONGLY-CONNECTED-COMPONENTS（G）1 call DFS（G） to compute finishing times f[u] for each vertex u2 compute GT3 call DFS（GT）. but in the mai...

CSU 1414: Query on a Tree

2017年02月05日 37 阅读

CSU 1414: Query on a Tree2015-02-17预处理每个结点的子结点的个数sons , 则对x的询问可由sons[x]- sigma（ sons[v] ） （v是到x距离为d的点）得到怎么快速的找到这些v呢？ 注意到距离x为d的点肯定在树的同一层....可以对树进行dfs时记录每个结点时间戳的同时把每一层的结点保存下来,然后对每一层维护一个前缀和 如果v是x下面子结点那么v的时间戳肯定在x的范围内,这样就可以二分確定出前缀和的范围了...

迷宫问题的研究与实现

2017年02月05日 41 阅读

迷宫问题的研究与实现2015-02-17【问题描述】以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（1）根据二维数组，输出迷宫的图形。（2）探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。【算法分析】主要考查数据结构-栈。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它...

快速比较两个字符串中字符完全相同：即兄弟字符串比较

2017年02月05日 35 阅读

快速比较两个字符串中字符完全相同：即兄弟字符串比较2015-02-17刚才上网，看到这个问题在好多论坛上得到很大的讨论，于是尝试练习了一下。【问题描述】对于两个字符串，判定包含的字符是否完全相同。比如："sabac"和 "basca"算是包含的字符完全相同，并且相同字符的数量也一样要相同，但它们顺序可以不一样。【问题分析】1.先判断两个字符串的长度是否相同2. 判断相同长度的字符串中的字符和相同字符的数量是否相同。3...

Timus 1446. Sorting Hat 分类问题

2017年02月05日 39 阅读

Timus 1446. Sorting Hat 分类问题2015-02-17At the start of each school year, a very important event happens at Hogwarts. Each of the first-year wizards and witches is assigned to one of the four Hogwarts houses. The bravest children ar...

十进制转换成十六进制和16进制转2进制的实现

2017年02月05日 39 阅读

十进制转换成十六进制和16进制转2进制的实现2015-02-17#include <stdio.h>#include <stdlib.h>#include <string.h>#include <locale.h>int main（） {int i,v;char bs[33];char b[33];char hs[9];char h[9];char s[4];char *e;// 十进制整数转二进制串；i=1...

HDU 3501 Calculation 2：欧拉函数的应用

2017年02月05日 38 阅读

HDU 3501 Calculation 2：欧拉函数的应用2015-02-17HDU 3501 Calculation 2：http://acm.hdu.edu.cn/showproblem.php？pid=3501大意：求1~n之间与n不互质的数的总和。思路：欧拉函数的应用；先用欧拉函数求出与n互质的总数m，计算m个数的总和，用n的总和减去m的总和就是想要的结果。#include <stdio.h>#define LL __int64int...

HDU 1286 找新朋友（欧拉函数模板）

2017年02月05日 39 阅读

HDU 1286 找新朋友（欧拉函数模板）2015-02-17HDU 1286 找新朋友：http://acm.hdu.edu.cn/showproblem.php？pid=1286题意：中文题。思路：欧拉函数的纯模板题，没什么好说的，主要是理解欧拉函数的意义。在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler"s totient function、φ函数、欧拉商数等。 例如&phi...

HDU 1115 Lifting the Stone：求多边形重心

2017年02月05日 38 阅读

HDU 1115 Lifting the Stone：求多边形重心2015-02-17HDU 1115：http://acm.hdu.edu.cn/showproblem.php？pid=1115大意：给你个n，有n个点，然后给你n个点的坐标，求这n个点形成的多边形的重心的坐标。struct point{double x, y;} P[1000010];struct line{point a, b;} ;double xmult（point p1, poi...

HDU 1411 校庆神秘建筑（欧拉四面体公式）

2017年02月05日 37 阅读

HDU 1411 校庆神秘建筑（欧拉四面体公式）2015-02-17HDU 1411：http://acm.hdu.edu.cn/showproblem.php？pid=1411大意：人一个你一个六面体的六条边，求六面体的体积。思路：没有什么思路，就是用欧拉四面体公式直接代入。欧拉四面体公式：具体的推导网上有很多。eg. http://blog.csdn.net/archibaldyangfan/article/details/8035332void So...

HDU 1140 War on Weather：三维点之间距离

2017年02月05日 35 阅读

HDU 1140 War on Weather：三维点之间距离2015-02-17HDU 1140：http://acm.hdu.edu.cn/showproblem.php？pid=1140大意：地球球心是（0,0,0），给你k个卫星以及k个卫星的三维坐标（以球心为基准），m个地球上的点以及m个点的三维坐标（以球心为基准），问有多少个点是能被卫星覆盖到的，输出数量。思路：求出卫星与地球切线的长度，在地球上，与卫星连线的长度小于切线长度的肯定都能看到。#d...

HDU 1174 爆头（三维空间点与直线关系）

2017年02月05日 40 阅读

HDU 1174 爆头（三维空间点与直线关系）2015-02-17HDU 1174：http://acm.hdu.edu.cn/showproblem.php？pid=1174大意：中文题，很好理解，搞清楚各种变量就行。思路：我知道的好像有两种解法，一种是求土匪的头心与子弹射出的直线求点到直线距离，在判断一下方向对不对；另一种是求出子弹射出点与土匪头心连线，求出子弹的射出的直线，求两直线的夹角， 求出子弹射出点与土匪头心连线，求出求出子弹射出点与土匪头的切...

POJ 2653 Pick-up sticks：计算几何 求线段交点

2017年02月05日 42 阅读

POJ 2653 Pick-up sticks：计算几何 求线段交点2015-02-17POJ 2653：http://poj.org/problem？id=2653题意：题意很简单，就是在地上按顺序撒一对木棒，看最后有多少是被压住的，输出没有被压住的木棒的序号。有点坑的就是没说清楚木棒怎么算压住，也不知道是不是规范相交。。。我就判断了一下包括端点重合跟部分相交的。思路：一开始我想的是从后往前遍历，找到每一条边，看他是不是压到之前的边了，如果压到了，就把之...

POJ 3792 Area of Polycubes：模拟

2017年02月05日 39 阅读

POJ 3792 Area of Polycubes：模拟2015-02-17POJ 3792：http://poj.org/problem？id=3792大意：按顺序给你一堆正方体，如果当前输入的正方体上下左右前后都没有跟之前的正方体有连接，就输出NO，并输出当前是第几个。如多每次输入的正方体跟之前的都有连接，那么最后输出组成的几何体的表面积。思路：一步一步模拟就行。注意：1.要判一下有重复的输入，如果有重复的输入，要输出NO，并输出第几。。2.注意下标...

HDU 2372 El Dorado（DP）

2017年02月05日 37 阅读

HDU 2372 El Dorado（DP）2015-02-17大意：给你一个长度为n的数列，求极差小于k的最长的上升数列的长度。思路：DP，循环k，每次求一个最长上升子序列。#include <stdio.h>#include <string.h>#define LL __int64int n, m;int a[110];LL dp[110][110];void Solve（）{while（~scanf（"%d%d&qu...

HDU 2985 Another lottery（水题）

2017年02月05日 37 阅读

HDU 2985 Another lottery（水题）2015-02-17HDU 2985：http://acm.hdu.edu.cn/showproblem.php？pid=2985大意：给你n个人，每个人买m次彩票，第i次的奖金是2的i次方，求每个人赢的比其他人都多的可能性是多少。思路：就是只看最后一次就行，2的i次方，对于每个人来说，最后一次的奖要比前面的大很多，所以直接只看最后一次，算出概率gcd一下就行了。#include <stdio....

UVA 10405 Longest Common Subsequence：简单DP

2017年02月05日 40 阅读

UVA 10405 Longest Common Subsequence：简单DP2015-02-17省赛还有不到50天了，自己DP这块实在是弱，准备就拿着些天狂刷DP了。http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=1346大意： 求两个字符串的最长公共子序列。思路：水题，不过需要注意的就...

POJ 1001 Exponentiation：大数处理

2017年02月05日 37 阅读

POJ 1001 Exponentiation：大数处理2015-02-17题意：给你一个浮点数，一个整数，求浮点数的整数次方。思路：大数解决，注意处理后面多余的零跟前面多余的零，以及Java科学计数法的问题。import java.math.*;import java.util.Scanner;public class Main {public static void main（String[] args） {// TODO Auto-generated...

POJ 3218 TOYS（计算几何）（二分）

2017年02月05日 39 阅读

POJ 3218 TOYS（计算几何）（二分）2015-02-25TOYS：http://poj.org/problem？id=2318大意：给你一个箱子，有n个挡板分隔成n+1部分，给你m个玩具的坐标，问每一部分有几个玩具。思路：举对每个玩具，二分线段下标，判断玩具在线段左边还是右边，枚举后统计。#include <map>#include <stack>#include <queue>#include <mat...

POJ 1265 Area （计算几何）（Pick定理）

2017年02月05日 37 阅读

POJ 1265 Area （计算几何）（Pick定理）2015-02-25Area：http://poj.org/problem？id=1265大意：每次给你一个点的横纵坐标变化值，求有多少点在多边形上，有多少点在多边形内，和多边形的面积。思路：Pick定理。一个计算点阵中顶点在格点上的多边形面积公式：S=a+b÷2-1，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。#include <map>#in...