algorithm 题集六 (16.11.12)

algorithm 题集六 (16.11.12)

nyist 8 一种排序 – operator

​​ 1.按照编号从小到大排序 2.对于编号相等的长方形，按照长方形的长排序； 3.如果编号和长都相同，按照长方形的宽排序； 4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；

code:

//============================================================================// Name : nyist.cpp// Author : theArcticOcean// Version :// Copyright :// Description : C++, Ansi-style//============================================================================#include #include #include using namespace std;typedef struct node retangle;struct node{ int num, length, width;};bool equal (retangle self,retangle other){ if(self.num == other.num && self.length == other.length && self.width == other.width) return 1; return 0;}bool cmp(retangle self,retangle other){ if(self.num != other.num) return self.num < other.num; if(self.length != other.length) return self.length < other.length; if(self.width != other.width) return self.width < other.width; return 1;}retangle reg[1005];int main() { int t,m; cin>>t; while(t--){ scanf("%d",&m); int i; for(i=0;i

搞不懂为什么下面的重载运算符代码不能通过。 相关报错：

/usr/include/c++/4.4/bits/stl_algo.h:89: error: no match for ‘operator<’ in ‘__a < __b’./Source/main.cpp:22: note: candidates are: bool node::operator<(retangle&) const

在本地中运行好好的，结果到了OJ就编译出错。

//============================================================================// Name : nyist.cpp// Author : theArcticOcean// Version :// Copyright :// Description : C++, Ansi-style//============================================================================#include #include #include using namespace std;typedef struct node retangle;struct node{ int num, length, width; bool operator == (retangle &other)const{ if(num == other.num && length == other.length && width == other.width) return 1; return 0; } bool operator < (retangle &other)const{ if(num != other.num) return num < other.num; if(length != other.length) return length < other.length; if(width != other.width) return width < other.width; return 1; }};retangle reg[1005];int main() { int t,m; cin>>t; while(t--){ scanf("%d",&m); int i; for(i=0;i

nyist 14 会场安排问题 – struct sort

​​ 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

分析：如果事件的所占的时间段尽可能小，那么就能在时间线上多发生不同的事件。先进行结束时间的排序再进行开始时间的排序。

/* ============================================================================ Name : 会场安排问题.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include typedef struct event{ int begin, end;}Event;Event a[10005];int cmp(const void *e1,const void *e2){ Event *E1 = (Event *)e1; Event *E2 = (Event *)e2; if(E1->end == E2->end){ return E1->begin < E2->begin; /*二级排序，按照开始时间从大到小，所用时间段越小越好*/ } return E1->end > E2->end; /*一级排序，按照结束时间从小到大*/}int max(int p1,int p2){ return p1>p2 ? p1:p2;}int main(void) { int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); int i,j; for(i=0;i tag){ tag = a[i].end; ans++; } } printf("%d\n",ans); } return

nyist 27 水池数目 – dfs

​​ 大意：寻找联通块的数量，经典的深度优先搜索问题。

/* ============================================================================ Name : 水池数目.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include #include char graph[105][105];int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};typedef enum BOOL{FALSE = 0, TRUE } bool;bool out(int x,int y,int n,int m){ if(x<0 || x>=n) return TRUE; if(y<0 || y>=m) return TRUE; return FALSE;}void dfs(int x,int y,int n,int m){ if(graph[x][y] == '0') return ; graph[x][y] = '0'; int i; int xx,yy; for(i=0;i<4;i++){ xx = x+dx[i]; yy = y+dy[i]; if(out(xx,yy,n,m)) continue; dfs(xx,yy,n,m); }}/*void show(int n,int m){ int i,j; for(i=0;i

由于bool是C++的内置数据类型，所以直接提交上面的代码会报错。改正:

typedef enum BOOL{FALSE = 0, TRUE } mybool;mybool out(int x,int y,int n,int m){ if(x<0 || x>=n) return TRUE; if(y<0 || y>=m) return TRUE; return FALSE;}

nyist 31 5个数求最值 – qsort

​​ 练习此题的目的是为了试试qsort()

描述 设计一个从5个整数中取最小数和最大数的程序 输入 输入只有一组测试数据，为五个不大于1万的正整数 输出 输出两个数，第一个为这五个数中的最小值，第二个为这五个数中的最大值，两个数字以空格格开

/* ============================================================================ Name : 5个数求最值.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include int cmp(const void *a,const void *b){ return *((int *)a) - *((int *)b); /* small -> big*/}int main(void) { int a[5]; int i; for(i=0;i<5;i++){ scanf("%d",&a[i]); } /* void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *)); */ qsort(a,5,sizeof(int),cmp); printf("%d %d\n",a[0],a[4]); return

nyist 37 回文字符串 – LCS

​​ 所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如”aba”。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串

分析：将回文字符串逆序得到第二个字符串，然后求出他们的最长公共子序列，不在最长公共子序列中的字符的个数就是需要添加的字符数。

/* ============================================================================ Name : 回文字符串.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include #include #define LEN 1005char str[LEN];char str2[LEN];int len;int dp[LEN][LEN];int max(int p1,int p2){ return p1>p2?p1:p2;}void LCS(){ memset(dp,0,sizeof(dp)); int i,j; for(i=1;i<=len;i++){ for(j=1;j<=len;j++){ /*dp[i][j] = max(dp[i][j],dp[i][j-1]); dp[i][j] = max(dp[i][j],dp[i-1][j]); if(str[i] == str2[j]){ dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1); }*/ if(str[i] == str2[j]){ dp[i][j] = dp[i-1][j-1]+1; } else if(dp[i-1][j] > dp[i][j-1]){ dp[i][j] = dp[i-1][j]; } else { dp[i][j] = dp[i][j-1]; } } }}int main(void) { int t; scanf("%d",&t); while(t--){ scanf("%s",str+1); len = strlen(str+1); int i; for(i=len;i>=1;i--){ str2[len+1-i] = str[i]; } LCS(); printf("%d\n",len-dp[len][len]); } return

nyist 58 最少步数 – bfs

​​ 这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1 1,0,0,1,0,0,1,0,1 1,0,0,1,1,0,0,0,1 1,0,1,0,1,1,0,1,1 1,0,0,0,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,0,0,0,1 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

分析：经典的广度优先搜索问题。

/* ============================================================================ Name : 最少步数.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include #define MAX 1000000char gra[9][9]={ {1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,1,0,1}, {1,0,0,1,1,0,0,0,1}, {1,0,1,0,1,1,0,1,1}, {1,0,0,0,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1}};char vis[9][9];typedef struct point{ int x,y;}Point;int dis[10][10];int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};typedef enum Bool{FALSE=0,TRUE}mybool;mybool ok(int x,int y){ if(x<0 || x>=9) return FALSE; if(y<0 || y>=9) return FALSE; if(vis[x][y] == 1) return FALSE; return TRUE;}int min(int x,int y){ return x

nyist 86 找球号(一) – map or qsort+bsearch

​​ 在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为”YES”,否则为”NO”），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。 输入 第一行有两个整数m，n(0<=n<=100000，0<=m<=1000000)；m表示这堆球里有m个球，n表示这个游戏进行n次。 接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k 输出 输出”YES”或”NO”

我觉得出题人应该提示，本体只有一组大数据。不然解题者用了while()读取就超时。 map:

//============================================================================// Name : 找球号(1).cpp// Author : theArcticOcean// Version :// Copyright :// Description : C++, Ansi-style//============================================================================#include #include #include

使用qsort() + bsearch():

//============================================================================// Name : 找球号(1).cpp// Author : theArcticOcean// Version :// Copyright :// Description : C++, Ansi-style//============================================================================#include #include #include using namespace std;const int len = 1e6+10;int a[len];int cmp(const void *a,const void *b){ return *((int *)a) - *((int *)b); /* small -> greater */}int main() { int m,n; scanf("%d%d",&m,&n); int i, top=0; for(i=0;i

nyist 96 n-1位数 ​​​ 描述 已知w是一个大于10但不大于1000000的无符号整数，若w是n(n≥2)位的整数，则求出w的后n-1位的数。

输入 第一行为M，表示测试数据组数。 接下来M行，每行包含一个测试数据。 输出 输出M行，每行为对应行的n-1位数（忽略前缀0）。如果除了最高位外，其余位都为0，则输出0。

分析：简单纯模拟

/* ============================================================================ Name : n-1位数.c Author : theArcticOcean Version : Copyright : Description : C, Ansi-style ============================================================================ */#include #include #include int main(void) { int M; char str[7]; scanf("%d",&M); getchar(); while(M--){ memset(str,0,sizeof(str)); gets(str); int len = strlen(str); int i; for(i=1;i

nyist 组合数 – prev_permutation

​​ 描述 找出从自然数1、2、… 、n（0

#include #include using namespace std; void show(int a[],int r){ int i; for(i=0;i

Uva 11827 Maximum GCD – ungetc

大意：给出一些数字（数字个数未知）求出最大公约数

分析：主要在于字符串处理, 相关函数： 把一个（或多个）字符退回到输入流中，可以理解成一个“计数器”。 int ungetc(int c, FILE *stream);

#include #include #include using namespace std;typedef long long LL;const int M=105;LL a[M],cnt;LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}int main(){ //freopen("cin.txt","r",stdin); int t; cin>>t; while(getchar()!='\n'); while(t--){ char buffer; cnt=0; while((buffer=getchar())!='\n'){ if(buffer>='0'&&buffer<='9'){ //buffer take not useful char ungetc(buffer,stdin); scanf("%lld",&a[cnt++]); } } LL maxm=0; for(int i=0;i

NSOJ 4681 数的长度 – log10

​​ N！阶乘是一个非常大的数，大家都知道计算公式是N!=N*(N-1）······*2*1.现在你的任务是计算出N！的位数有多少（十进制）？

分析：对数相加，Number相乘，底数取10。这样降低数值增长。 我怀疑测试的时候，给出的整数很可能会等于1000000。因为自己计算到999999就是过不了。

#include #include #define M 1000000double ans[M+10];int main(){ int n,a; int i; ans[1] = 0; for(i=2;i<=M;i++){ ans[i] = ans[i-1]+log10(1.0*i); } scanf("%d",&n); while(n--){ scanf("%d",&a); printf("%d\n",(int)ans[a]+1); } return 0;}

LightOj Harmonic Number – log

大意：求解 Hn=1+12+13+14+⋯+1n=∑k=1n1k 分析：调和级数的近似计算——ln(n+1)+C 其中C是欧拉常数，近似等于0.57721566490153286060651209008240243104215933593992 但是在程序中直接用此公式误差仍然大，而用(log(1.0*n)+log(n+1.0))/2

#include #include #include using namespace std;const double C=0.57721566490153286060651209; const int N=1e6+10;double f[N];int main(){ //freopen("cin.txt","r",stdin); f[1]=1; for(int i=2;i>T; while(T--){ scanf("%d",&n); double ans=0; if(n

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。