天天看点
返回

algorithm 题集六 (16.11.12)

nyist 8 一种排序 – operator

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=8​​

现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；

1.按照编号从小到大排序

2.对于编号相等的长方形，按照长方形的长排序；

3.如果编号和长都相同，按照长方形的宽排序；

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

code:

//============================================================================
// Name        : nyist.cpp
// Author      : theArcticOcean
// Version     :
// Copyright   :
// Description : C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <algorithm>
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<m;i++){
            scanf("%d%d%d",®[i].num,®[i].length,®[i].width);
            if(reg[i].length < reg[i].width) swap(reg[i].length,reg[i].width);
        }
        sort(reg,reg+m,cmp);
        for(i=0;i<m;i++){
            if(i==0){
                printf("%d %d %d\n",reg[i].num,reg[i].length,reg[i].width);
                continue;
            }
            if(equal(reg[i-1],reg[i])) continue;
            printf("%d %d %d\n",reg[i].num,reg[i].length,reg[i].width);
        }
    }
    return 0;
}

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

相关报错：

/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 <iostream>
#include <stdio.h>
#include <algorithm>
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<m;i++){
            scanf("%d%d%d",®[i].num,®[i].length,®[i].width);
            if(reg[i].length < reg[i].width) swap(reg[i].length,reg[i].width);
        }
        sort(reg,reg+m);
        for(i=0;i<m;i++){
            if(i==0){
                printf("%d %d %d\n",reg[i].num,reg[i].length,reg[i].width);
                continue;
            }
            if(reg[i-1] == reg[i]) continue;
            printf("%d %d %d\n",reg[i].num,reg[i].length,reg[i].width);
        }
    }
    return 0;
}

nyist 14 会场安排问题 – struct sort

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=14&rec=rec​​

描述：

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

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

/*
 ============================================================================
 Name        : 会场安排问题.c
 Author      : theArcticOcean
 Version     :
 Copyright   : 
 Description : C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>

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<n;i++){
            scanf("%d%d",&a[i].begin,&a[i].end);
        }
        qsort(a,n,sizeof(Event),cmp);
        int ans = 1;
        int tag = a[0].end;
        for(i=1;i<=n;i++){
            if(a[i].begin > tag){
                tag = a[i].end;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return

nyist 27 水池数目 – dfs

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=27​​​

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

/*
 ============================================================================
 Name        : 水池数目.c
 Author      : theArcticOcean
 Version     :
 Copyright   : 
 Description : C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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<n;i++){
        for(j=0;j<m;j++) printf("%c ",graph[i][j]);
        puts("");
    }
}*/
int main(void) {
    int t;
    int n,m;
    scanf("%d",&t);
    while(t--){
        memset(graph,0,sizeof(graph));
        scanf("%d%d",&n,&m);
        int i,j;
        char ch;
        for(i=0;i<n;i++){
            for(j=0;j<m;){
                scanf("%c",&ch);
                if(ch == '0' || ch == '1'){
                    graph[i][j] = ch;
                    j++;
                }
            }
        }
        int ans = 0;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(graph[i][j] == '1'){
                    ans++;
                    dfs(i,j,n,m);
                }
            }
        }
        printf("%d\n",ans);
    }
    return

由于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

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=31​​​

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

描述

设计一个从5个整数中取最小数和最大数的程序

输入

输入只有一组测试数据，为五个不大于1万的正整数

输出

输出两个数，第一个为这五个数中的最小值，第二个为这五个数中的最大值，两个数字以空格格开

/*
 ============================================================================
 Name        : 5个数求最值.c
 Author      : theArcticOcean
 Version     :
 Copyright   :
 Description : C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
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

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=37&rec=rec​​

描述

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

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

/*
 ============================================================================
 Name        : 回文字符串.c
 Author      : theArcticOcean
 Version     :
 Copyright   : 
 Description : C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 1005
char 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

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=58​​

描述

这有一个迷宫，有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 <stdio.h>
#include <stdlib.h>
#define MAX 1000000
char 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<y ? x:y;
}
void bfs(int a,int b,int c,int d){
    Point que[90];
    Point temp,next;
    int head = 0,tail = 0;
    next.x = a;   next.y = b;
    que[tail++] = next;
    while(head < tail){
        temp = que[head++];
        int i;
        int xx,yy;
        for(i=0;i<4;i++){
            xx = temp.x+dx[i];
            yy = temp.y+dy[i];
            if(ok(xx,yy)){
                next.x = xx;
                next.y = yy;
                dis[xx][yy] = min(dis[xx][yy],dis[temp.x][temp.y]+1);
                que[tail++] = next;
                vis[xx][yy] = 1;
                if(xx == c && yy == d) return ;
            }
        }
    }
}

int main(void) {
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int i,j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                dis[i][j] = MAX;
                vis[i][j] = gra[i][j];
            }
        }
        dis[a][b] = 0;
        bfs(a,b,c,d);
        printf("%d\n",dis[c][d]);
    }
    return

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

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=86​​

描述

在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号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 <iostream>
#include <stdio.h>
#include <map>
using namespace std;
int main() {
    int m,n;
    scanf("%d%d",&m,&n);
    int i, temp=0;
    map<int,int> mp;
    for(i=0;i<m;i++){
        scanf("%d",&temp);
        mp[temp] = 1;
    }
    for(i=0;i<n;i++){
        scanf("%d",&temp);
        if(mp[temp] > 0) puts("YES");
        else puts("NO");
    }
    return 0;
}

使用qsort() + bsearch():

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

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
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<m;i++){
        scanf("%d",&a[top++]);
    }
    qsort(a,top,sizeof(int),cmp);
    int temp;
    for(i=0;i<n;i++){
        /*
void *bsearch(const void *key, const void *base, size_t nmem, size_t size,
int (*comp)(const void *, const void *));*/
        scanf("%d",&temp);
        int *ans = NULL;
        ans = (int *)bsearch(&temp,a,top,sizeof(int),cmp);
        if(ans == NULL) puts("NO");
        else puts("YES");
    }
    return 0;
}

nyist 96 n-1位数

​​​http://acm.nyist.net/JudgeOnline/problem.php?pid=96​​​

描述

已知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 <stdio.h>
#include <stdlib.h>
#include <string.h>

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<len;i++){
            if(str[i] != '0') break;
        }
        if(i == len) puts("0");
        else printf("%s\n",str+i);
    }
    return

nyist 组合数 – prev_permutation

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=32​​​

描述

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

#include <stdio.h>
#include <algorithm>  
using namespace std; 

void show(int a[],int r){
      int i;
      for(i=0;i<r;i++){
      printf("%d",a[i]);
      }
      puts("");
}
bool check1(int a[],int b[],int r){
     bool result=1;
     int i=0;
     for(i=0;i<r;i++){
         if(a[i] != b[i]){
             result=0;
             break;
         }
     }
     return result;
}
bool check2(int a[],int r){
    int last=a[0];
    int i=0;
    for(i=1;i<r;i++){
        if(last<a[i]) return 0;
        last=a[i];
    }
    return 1;
}
int main()
{
    int n,r;
    while(~scanf("%d%d",&n,&r)){
        const int len=n;
        int a[len];
        int i;
        for(i=0;i<len;i++){
            a[i]=len-i;
        }
        show(a,r);
        const int len2=r;
        int b[len2];
        for(i=0;i<len2;i++){
            b[i]=a[i];
        }
        while(prev_permutation(a,a+n)){
            if(check1(a,b,r) || !check2(a,r))   continue;
            show(a,r);
            for(i=0;i<len2;i++){
                b[i]=a[i];
            }
        }
    }
    return 0;
}

Uva 11827 Maximum GCD – ungetc

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

分析：主要在于字符串处理, 相关函数：

把一个（或多个）字符退回到输入流中，可以理解成一个“计数器”。

int ungetc(int c, FILE *stream);

#include <iostream>
#include <cstdio>
#include <cstring>
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<cnt;i++){
            for(int j=i+1;j<cnt;j++){
                maxm=max(maxm,gcd(a[i],a[j]));
            }
        }
        printf("%lld\n",maxm);
    }
    return 0;
}

NSOJ 4681 数的长度 – log10

​​http://115.159.40.116/problem_show.php?pid=4681​​​

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

#include <math.h>
#include <stdio.h>

#define M 1000000
double 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 

#include <iostream>
#include <cstdio>
#include <cmath>
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<N;i++) f[i]=f[i-1]+1.0/i;
    int T,n;
    int ca=1;
    cin>>T;
    while(T--){
        scanf("%d",&n);
        double ans=0;
        if(n<N){
            printf("Case %d: %.11lf\n",ca++,f[n]);
            continue;
        }
        ans=(log(1.0*n)+log(n+1.0))/2+C;
        printf("Case %d: %.11lf\n",ca++,ans);
    }
    return 0;
}
算法 #include i++ 回文字符串
上一篇: FFmpeg学习笔记（三）：逐行扫描转换为隔行扫描的实现----tinterlace简介
下一篇: android 9 垂直不拉伸,神奇的问题！android .9图片拉伸不是不会变形吗？但是这里变形了...

继续阅读