cavenkaka
- 浏览: 197369 次
- 性别:
- 来自: 武汉
-
文章列表
题意很简单，给你一个用邻接矩阵形式存储的有n个顶点的无向图，让你求它的最小生成树并求出在这个生成树里面最大的边的权值。
思路：最小生成树算法：
代码如下：
#include <iostream>
using namespace std;
const int Max=502;
const int inf=0xfffffff;
int n,ans;
int map[Max][Max],dis[Max];
int min(int a,int b)
{
return a<b?a:b;
}
void prim()
{
int i,now,j, ...
题意：历史上，曾用7个小写字母来表示每种truck的型号，每两种型号之间的差距为字母串中不同字母的个数。现在给出n种不同型号的truck，问怎样使
1/Σ(to,td)d(to,td)的值最小。（即找到一条连接所有truck的最短路径。典型的最小 ...
题意：Farmer John有当选为新镇长，他的竞选宣言就是把网络带入所有的farm。现在给出farm的个数n，以及每两个farm之间的联网距离，让你找出一条最短的路径能连接上所有的farm。
思路：基础的prim。首先就是邻接矩阵的构造，时间复杂度为o(n^2)。poj第200道，贡献给了prim求最短路径。
#include<iostream>
using namespace std;
const int Max = 102;
const int inf = 0xfffffff;
int n, ans;
int map[Max ...
在n个城市之间铺设光缆，铺设光缆费用很高且各个城市之间铺设光缆的费用不同。如果设计目标是使这n个城市之间的任意两个城市都可以直接或间接通信，并且要使铺设光缆的费用最低，这样的问题就是一个求最小生成树的问题。解决这个问题的方法就是在有n个城市结点、n(n-1)/2条费用不同的边构成的无向连通图中找出最小生成树。
最小生成树的应用相当广泛，是图论中比较基础的算法。解决最小生成树有两种算法：prim和kruskal。
prim的思想：
设置两个集合U和V，U中存放图G中最小生成树的结点集合，V是整个结点集合。初始令U ={u0}，设u0为起始点（任意设定）。从U和V ...
1.不要看到别人的回复第一句话就说：给个代码吧！你应该想想为什么。当你自己想出来再参考别人的提示，你就知道自己和别人思路的差异。 2.初学者请不要看太多太多的书那会误人子弟的，先找 ...
关于ACM以前一直抱着一个敬畏的态度，作为一个菜鸟级的初学者，在编程方面确实没有太多的东西可以去变现，这么多天来的锻炼让自己意识到自己并不是很差，很多的东西只是以前没有注意到，见到的东西少而已，自信是一个人必须具备的品质，在锻炼中成长，未来还有三年的时光，俗话说的好，没有远虑，必有近忧，说的就是我啦，以后对自己好一点，不等不该等得人，不伤不该伤得心，也要对自己狠一点，每天至少一道ACM试题的计划必须完成，不能间断，这样在三年之后的找工作中至少不会被人鄙视，至少对得起自己，人笨可以，但是必须勤奋，加油！！
很简单的一个题目：就是求和而已
#include <iostream>
#include <string.h>
using namespace std;
char a[256];
int main()
{
int n,sum;
int i;
while ((gets(a))&&(a[0]!='#'))
{
sum=0;
n=strlen(a);
for (i=0;i<n;i++)
{
if (a[i]!=' ')
{
sum+=(i+1)*(int)(a[i]-'A'+1) ...
这题要是做数据结构的练习题挺好的。就是给出前序和中序序列，要求后序序列。在先序序列中，第一个元素为二叉树的根，之后为它的左子树和右子树的先序序列；在中序序列中，先是左子树的中序序列，然后是根，再就 ...
这是一道比较水的题目，题意大概是说：给你三个数a,b,n，求出数列a,a+b,a+2b,a+3b,a+4b,a+5b……中第n个素数，还好题目一有说最后的结果会小于10^6次方，所以无论是用普通方法求素数还是使用素数表都可以AC。
不说了直接上代码吧：
#include<stdio.h>
#define N 1000001
int i,j,m,n,s,a[N];
int main()
{
a[0]=0,a[1]=0;
for(i=2;i<N;i++)a[i]=1;
for(i=2;i<N;i++)
...
Slyar:说下题意。给你至多100行超大整数，以0结束输入，要求你求出这些超大整数的和。高精度加法运算，试了几种思路，感觉下面这种看起来最舒服...例如19999 + 999 + 9，看图更清晰
1、以字符串格式读入超大整数，然后将每一位转换成整型并逆序存放在数组中。
2、把每次读入字符串的长度存放在0号元素中(sum[i][0])。
3、将所有大整数的和存放在0号字符串中(sum[0])。
4、从0号字符串最大处向前寻找第一个不为0的元素，然后逆序输出和。
代码如下：
#include <stdio.h>
#include <stdlib.h&g ...
题意：一个偶数能不能表示为两个奇质数a跟b的和，如果能的话由于这个偶数可能可以表示为多个奇质数对的和，输出时只选取b-a最大的那对奇质数
选题原因：本题难度适中，是关于素数的问题，涉及的是素数表的构造，另外，本题很容易超时，要注意处理方法。
思路：以空间换时间，利用筛选法求素数
此题用筛选法构造素数表：基本思路如下：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划 ...
题意如下：
告诉你有400个房间，如上图所示。给你一个数n，下面给出n个桌子要搬（从i房间搬到j房间），要你求出最小要用多少时间搬这些桌子？数据范围：（1 <= n <= 200） (1 <= i,j <= 400)如下附件图所示：
思路 ...
涉及到素数的判断，好久没写了，查了下定义才写出来，囧，这道题也让我郁闷了一会，最后向别人讨教才知道这个方法，唉，首先是求出前面的素数，然后再从2开始加，每次做完加法都要判断是不是大于或等于输入的数值，如果等于则计数加一，大于则退出重新从下一个素数开始计算。这个问题的关键点就是在如何于求小于某个数的素数，因为如果一个数不是素数是合数， 那么一定可以由两个自然数相乘得到， 其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。 比如18，它可以写成1＊18, 2*9, 3*6。18的平方根约为4.2，其中1、2、3均小于4.2，18，9，6都大于4.2。 如果从2到某数的平方根 ...
本来觉得是个水题，也是按水题的思路做的。但是题目的意思比较内涵，说白了就是个陷阱。题目说字符串的加密有两种方法，一种是变换字符，把一个字符变成它的下一个字符，如果是Z，就变成A。还有一种就是给一个数字排列，排列中每个位置的字符就是以这个数字为下标的字符。貌似比较简单。很多人能够想到不管是第一种还是第二种，都可能是多种结果，因为不一定是变成下一个字符，排列就更多了。现在主要需要考虑的就是把两种加密方式结合起来，是否能从原来的字符串得到目的字符串。题目的陷阱就是字符的转换规律也是不确定。不一定是下一个，也不一定是一定的距离的字符，其实只需要一一对应就可以了。如果想到这里了，那就比较简单了。只要两 ...
注意看题目，每个输入只有两个数但是你输出的时候要输出3个数T、D、H所以要通过那个公式去转化求出这3个数然后输出，你这个程序只能输出样例为T、D输入时的结果。
还有一个要注意的是数据类型的问题：题目中给的数据的有效数字均是小数点后4位，为了防止精度丢失，一般都是采取double型数据，数据的输入为scanf("%lf"),根据题目中输出给出的特点，输出应为小数点后一位则输出格式为printf("%.1lf");
代码如下：
#include <iostream>
#include <math.h>
using ...