POJ 3371 Flesch Reading Ease （模拟题）

2017年02月05日 35 阅读

POJ 3371 Flesch Reading Ease （模拟题）2015-02-25Flesch Reading Ease：http://poj.org/problem？id=3371题目很水，就是看懂题就行。题意：给出一篇规范的文章，求其 句子数、单词数 和 音节数把这3个值代入题目给出的公式，输出其结果，保留2位小数。标记单词分隔符： 逗号（,） 和 空格（ ）句子分隔符：句号（.） 问号（？） 冒号（:） 分号（;） 感叹号（！）音节处理要求：（...

POJ 3687 Labeling Balls：拓扑序列

2017年02月05日 37 阅读

POJ 3687 Labeling Balls：拓扑序列2015-02-25Labeling Balls：http://poj.org/problem？id=3687大意：n个重量分别为1-n的小球，给定一些小球间的重量关系。 在符合重量关系的前提下，先输出编号小的球。思路：也是一道很简单的拓扑排序，不过要倒着来，注意一下要判重边。#include <string.h>#include <iostream>using namespa...

POJ 3206 Borg Maze：BFS+Prim

2017年02月05日 39 阅读

POJ 3206 Borg Maze：BFS+Prim2015-02-25Borg Maze：http://poj.org/problem？id=3026大意：给你一个m*n的迷宫，可以上下左右的走，只能走空格或字母，求出将所有字母连通起来的最小耗费。思路：先用BFS求出S到所有A的距离，再用Prim求最小生成树，求出最小耗费。这个题坑的不在题，是数据太坑了，在空格处理上没弄好，贡献了好几个WA和CE，看Discuss才知道很坑,最后用G++过了的代码，C...

POJ 2485 Highways：最小生成树 Prim

2017年02月05日 34 阅读

POJ 2485 Highways：最小生成树 Prim2015-02-25Highways：http://poj.org/problem？id=2485大意：给你一个用邻接矩阵形式存储的有n个顶点的无向图，让你求它的最小生成树并求出在这个生成树里面最大的边的权值。思路：用Prim求，判断条件改一下就行。PS：dis数组初始化的时候用memset一直RE，希望有知道怎么回事的不吝赐教，谢了~#include <stdio.h>#include ...

POJ 1789 Truck History：最小生成树 Prim

2017年02月05日 38 阅读

POJ 1789 Truck History：最小生成树 Prim2015-02-25Truck History：http://poj.org/problem？id=1789大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。思路：将每个字符串当成一个节点，求出每个节点之间需...

POJ 1258 Agri-Net：最小生成树 Prim 模版题

2017年02月05日 35 阅读

POJ 1258 Agri-Net：最小生成树 Prim 模版题2015-02-25Agri-Net：http://poj.org/problem？id=1258大意：新镇长竞选宣言就是将网络带到每一个农场，给出农场个数，两两之间建光缆的耗费，求所有都联通的最小耗费。思路：最小生成树，因为边比较稠密，用Prim做。PS；对于比较稠密的图，用Prim，对于比较稀疏的图，用 Kruskal。Kruskal是找边的过程，稀疏的话会比较快。#include <...

POJ 1860 Currency Exchange：最短路 Bellman-Ford

2017年02月05日 43 阅读

POJ 1860 Currency Exchange：最短路 Bellman-Ford2015-02-25Currency Exchange：http://poj.org/problem？id=1860大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。思路：Bellman_Ford，因为要求最长路，所以松弛条件改一下就好了。Tips：3 2 1 20.0货币的数量 ...

POJ 2240 Arbitrage：最短路 Floyd

2017年02月05日 36 阅读

POJ 2240 Arbitrage：最短路 Floyd2015-02-25Arbitrage：http://poj.org/problem？id=2240大意：给你m种货币，给你m种货币兑换规则，问通过这些规则最后能不能盈利。eg：1美元换0.5英镑，1英镑换10法郎，1法郎换0.21美元，这样1美元能换0.5*10*0.21=1.05美元，净赚0.05美元。思路：用Floyd找出每两种钱之间的最大兑换关系，遍历一遍，看有没有那种钱币最后能盈利，有就输出...

POJ The Doors AND NYIST：有趣的问题

2017年02月05日 36 阅读

POJ The Doors AND NYIST：有趣的问题2015-02-25题目链接：http://acm.nyist.net/JudgeOnline/problem.php？pid=227题目分析：给你横纵坐标分别表示门所在的位置，叫你求出从起点到终点的最短距离。算法分析：该题好像有多种解法，我只说我做的。我用的是几何+图论。建模分析：1、先判断两个点之间是否可以连接。2、判断两个点是否可以链接的方法是用是否判断墙与这两点连成的线段是否相交。3、如果没...

POJ 1001 Exponentiation 无限大数的指数乘法 题解

2017年02月05日 36 阅读

POJ 1001 Exponentiation 无限大数的指数乘法 题解2015-02-25POJ做的很好，本题就是要求一个无限位大的指数乘法结果。要求基础：无限大数位相乘额外要求：处理特殊情况的能力 -- 关键是考这个能力了。所以本题的用例特别重要，再聪明的人也会疏忽某些用例的。本题对程序健壮性的考查到达了变态级别了。某人贴出的测试用例数据地址： http://poj.org/showmessage？message_id=76017有了这些用例，几下调试...

POJ：DNA Sorting 特殊的排序

2017年02月05日 37 阅读

POJ：DNA Sorting 特殊的排序2015-02-25DescriptionOne measure of ``unsortedness"" in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC"", this meas...

POJ：1006 Biorhythms 周期相遇 两个思路程序

2017年02月05日 35 阅读

POJ：1006 Biorhythms 周期相遇 两个思路程序2015-02-25DescriptionSome people believe that there are three cycles in a person"s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, ...

Codeforces：cAPS lOCK 大小写字母转换问题

2017年02月05日 36 阅读

Codeforces：cAPS lOCK 大小写字母转换问题2015-02-25按如下规则转换字母：Let"s consider that a word has been typed with the Caps lock key accidentally switched on, if:either it only contains uppercase letters;or all letters except for the first one are ...

Codeforces：Tram 列车载人问题 题解

2017年02月05日 37 阅读

Codeforces：Tram 列车载人问题 题解2015-02-25题目：一列电车，已经知道每站上下车的人数，那么问电车最小需要多大的容量才能让所有乘客都能搭车？Sample test（s）input40 32 54 24 0output6每站都是先下后上的，那么其实就是个很简单的问题了，可以使用贪心法：1 初始化第一站乘客为零2 每站计算上一站有的乘客加上上站的乘客，减去下站的乘客3 每站剩下乘客的最大量就是结果了#include <iostre...

EI judge 002 Set Intersection 算法题解

2017年02月05日 38 阅读

EI judge 002 Set Intersection 算法题解2015-02-25Set IntersectionTime limit = 5 second（s）Memory limit = 33000 KbYour task is to find the intersection of two sets of positive integers.Input The input consists of two sets of positive int...

COJ：General Election 题解

2017年02月05日 37 阅读

COJ：General Election 题解2015-02-25DescriptionGeneral Election is over, now it is time to count the votes！ There are n （2 <= n <= 5） candidates and m （1 <= m <= 100）vote regions. Given the number of votes for each candid...

COJ：Traversing Grid 遍历格子的问题 题解

2017年02月05日 40 阅读

COJ：Traversing Grid 遍历格子的问题 题解2015-02-25很有趣的题目：在一个方格上从最左上角面向右出发，每次行走一个，碰到边右走，或者碰到已经访问过的格子右转，问最后遍历所有格子的时候你是面向那个方向？For example: Consider the case with N = 3, M = 3. The path followed will be （0,0） -> （0,1） -> （0,2） -> （1,2）...

Ural - Timus - 1009 K-based Numbers 题解

2017年02月05日 37 阅读

Ural - Timus - 1009 K-based Numbers 题解2015-02-25Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if itsK-based notation doesn’t contain two successive zeros. For example:10102...

code chef：Cool Guys题解

2017年02月05日 37 阅读

code chef：Cool Guys题解2015-02-25All submissions for this problem are available.Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor（GCD） of A and B...

code chef：Counting Matrices题解

2017年02月05日 37 阅读

code chef：Counting Matrices题解2015-02-25题目：给定一个数值，找出2*2矩阵的对角和等于N（N<2500）和行列式大于0的个数。这里是考数学知识了，程序不难，不过要精确计算好却也不容易。最原始的程序，但是会超时：void CountingMatrices（）{int T = 0, N = 0;cin>>T;while （T--）{cin>>N;long long ans = 0;for （i...