现在位置: 首页 > 算法 > 文章
2019年04月18日 算法 ⁄ 共 1601字 暂无评论
一道递推 #include<iostream> using namespace std; __int64 Gcd(__int64 x,__int64 y) {  if(x==y)return x;  if(x==1||y==1)return 1;  __int64 r;  if(x<y)  {   r=x;   x=y;   y=r;  }  while(y!=0)  {   r=x%y;   x=y;   y=r;  }  return x; } int main() {  char mark[51][101];  __int64 sum[51][101];  __int64 finalsum;  int i,j;  int n,n1,m;  int colnum;  int spoint;  int epoint;  int count;  __int...
阅读全文
2019年04月18日 算法 ⁄ 共 937字 暂无评论
在已有的边上做Prim #include<iostream> #include<cmath> #include<iomanip> using namespace std; #define infinity 1000000   class Point2D { public: double x,y; };   Point2D point[1001]; double map[1001][1001]; double dis[1001]; bool flag[1001]; int n,m;   int main() { memset(flag,false,sizeof(flag)); int c,i,j,k; double len; double minone; scanf("%d%d",&n,&m); for(...
阅读全文
2019年04月18日 算法 ⁄ 共 1446字 暂无评论
重构二叉树,已知前序和中序,输出后序。 #include <iostream>#include <cstring>using namespace std; struct treeNode{ treeNode(); char letter; treeNode* left; treeNode* right;};treeNode::treeNode(){ left=NULL; right=NULL;}void AddNode(treeNode* node,bool left,bool right,char ch){ treeNode* tmpNode=new treeNode; tmpNode->letter=ch;  if(true==left) {  node->left=tmpNode; } else {  ...
阅读全文
2019年04月18日 算法 ⁄ 共 3695字 暂无评论
    因为最近想做的一个东西和区间统计有关,心血来潮玩了下线段树。    #include<iostream> using namespace std; #define MAXNUMBER 1<<30 class TreeNode { public:TreeNode();int leftIndex;int rightIndex;int maxHeight;int minHeight;TreeNode* leftNode;TreeNode* rightNode; }; TreeNode::TreeNode() {leftIndex=0;rightIndex=0;maxHeight=-1;minHeight=MAXNUMBER;leftNode=NULL;rightNode=NULL; } ...
阅读全文
2019年04月18日 算法 ⁄ 共 1754字 暂无评论
#include<iostream> using namespace std; #define MAXSIZE 10000 class QElemType { public:int x,y; }; class SQueue { public:int len;int front;//头指针,若队列不空,指向队列头元素int rear;//尾指针,若队列不空,指向队列尾元素的下一个位置QElemType base[MAXSIZE];int InitQueue();//初始化一个队伍int QueueLength();//求队伍长度int EnQueue(QElemType e);//插入元素为e的新的队尾元素int DeQueue(QElemT...
阅读全文
2019年04月18日 算法 ⁄ 共 1260字 暂无评论
    很早以前做的了,拿出来记录下。 #include<stdio.h> #include<string.h> const int N=100001; struct Node {int v;struct Node *next;Node(int n=0,struct Node *P=NULL){v=n;next=P;} }node[N]; struct Range{int b,e; }range[N]; bool visited[N]; int c[N]; int n; void Dfs(int p,int &id); inline int Lowbit(int x){return x&(-x); } void Modify(int i,int v); int Sum(int n); int m...
阅读全文
2019年04月18日 算法 ⁄ 共 716字 暂无评论
#include<iostream> using namespace std; int main() {char str1[10];char str2[10];char ch;int turn;int tempint;int i;int guess[2];//0代表左边那个,1代表右边那个while(1){guess[0]=0;guess[1]=11;while(1){cin>>tempint;   if(!tempint)return 0;cin>>str1;cin>>str2;if(strcmp(str1,"too")==0){if(strcmp(str2,"high")==0){if(tempint<=guess[0]){guess[1]=tempint;continue;}else{if(tem...
阅读全文
2019年04月18日 算法 ⁄ 共 2464字 评论关闭
   自从上次偶尔用了一次线段树后就很喜欢这东西,做各种区间统计挺有用的。抽空又玩了下3468。也是一道很常见的数段树应用,统计区间的和,有时候又要更新区间的值。 #include<iostream> using namespace std; class TreeNode { public:int lIndex,rIndex;TreeNode *lNode;TreeNode *rNode;__int64 inc;__int64 sum; }; //根据给定的数组建树 void BuildTree(TreeNode *tNode,int lIndex,int rIndex) {tNode->lIndex...
阅读全文
2019年04月18日 算法 ⁄ 共 2208字 评论关闭
  check out后,这几天刚好闷骚期,随便玩了一道,典型的动态规划。一开始wrong answer,后来发现sumit时候忘记把测试时候ifstream 改回来,还有根据讨论,要用long double,改了一下就ok了。   开始DP前先推导下均方差公式,发现均方差就等于sqrt( sum(Xi^2)/n - (sum/n)^2 ),因为sum和n 已知,所以问题变成了求sum(Xi^2)/n的最小值,即每个矩形块的值的平方和的总和。    subChessSquare[i][j][h][w][n] 表示 以(i,j)为起点...
阅读全文
2019年04月18日 算法 ⁄ 共 2726字 评论关闭
  水题一道,关键是理解题目为最小生成树。纯粹为了复习并查集和Kruscal最小生成树。 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Edge { public: int nId1,nId2; int length; }; class LinkNode { public: LinkNode() { nodeID=-1; length=-1; nextNode=NULL; } int nodeID; int length; LinkNode* nextNode; }; class Node { public: No...
阅读全文