分类： OJ

HRBUST OJ 1143 泉水

2019年2月28日 by 风向晚·0 Comments

泉水

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 2772(662 users)

Total Accepted: 1074(597 users)

Rating:

Special Judge: No

Description

Leyni是一个地址调查员，有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀，有高有低，他觉得如果这个泉眼不断的向外溶出水来，这意味着这里在不久的将来将会一个小湖。水往低处流，凡是比泉眼地势低或者等于的地方都会被水淹没，地势高的地方水不会越过。而且又因为泉水比较弱，当所有地势低的地方被淹没后，水位将不会上涨，一直定在跟泉眼一样的水位上。
由于Leyni已经调查过当地很久了，所以他手中有这里地势的详细数据。所有的地图都是一个矩形，并按照坐标系分成了一个个小方格，Leyni知道每个方格的具体高度。我们假定当水留到地图边界时，不会留出地图外，现在他想通过这些数据分析出，将来这里将会出现一个多大面积的湖。

Input

有若干组数据，每组数据的第一行有四个整数n,m,p1,p2(0<n,m,p1,p2<=1000)，n和m表示当前地图的长和宽，p1和p2表示当前地图的泉眼位置，即第p1行第p2列，随后的n行中，每行有m个数据。表示这每一个对应坐标的高度。

Output

输出对应地图中会有多少个格子被水充满。

Sample Input

3 5 2 3
3 4 1 5 1
2 3 3 4 7
4 1 4 1 1

Sample Output

题目链接：HRBUST OJ 1143 泉水

AC代码：

#include <stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

int a[1010][1010];
bool b[1010][1010];
int sum = 0;

void search(int p1,int p2,int h,int n ,int m){
    b[p1][p2] = false;
    if(a[p1][p2]<=h){
        sum++;
    }
    if(p1+1<n && b[p1+1][p2] && a[p1+1][p2]<=h){
        search(p1+1,p2,h,n,m);
    }
    if(p1-1>=0 && b[p1-1][p2] && a[p1-1][p2]<=h){
        search(p1-1,p2,h,n,m);
    }
    if(p2-1>=0 && b[p1][p2-1] && a[p1][p2-1]<=h){
        search(p1,p2-1,h,n,m);
    }
    if(p2+1<m && b[p1][p2+1] && a[p1][p2+1]<=h){
        search(p1,p2+1,h,n,m);
    }

}



int main()
{
     int n,m,p1,p2;
    while(cin>>n>>m>>p1>>p2){
         memset(b,true,sizeof(b));

        sum = 0;
        --p1;
        --p2;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                cin>>a[i][j];
            }
        }
        int h = a[p1][p2];
        sum = 0;
        search(p1,p2,h,n,m);
        cout<<sum<<endl;
    }
}

MIOJ #119 小米兔跳格子

2019年1月5日 by 风向晚·0 Comments

描述

米兔爸爸为了让小米兔好好锻炼身体，便给小米兔设置了一个挑战——跳格子。

要吃到自己心爱的胡萝卜，小米兔需要跳过面前一些格子。现有个格子，每个格子内都写上了一个非负数，表示当前最多可以往前跳多少格，胡萝卜就放在最后一个格子上。米兔开始站在第 1 个格子，试判断米兔能不能跳到最后一个格子吃到胡萝卜呢？

输入

输入为个数字 ( $N < 10$ )，用空格隔开，第个数字 $0 \leq s_{i} < 10$ ) 表示米兔站在第个格子上时，最多能往前跳的格数。

输出

若米兔能跳到最后一个格子上吃到胡萝卜，输出 “true“，否则输出 “false“

输入样例

2 0 1 0 0 3 4

输出样例

false

AC代码：

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;
int main()
{
    int b;
    vector<int>a;
    bool flag = false;
    while(cin>>b)
    {
                    a.push_back(b);
        if (cin.get() == '\n')
            break;
    }
    int mitu = 0;
    while(mitu<a.size()){
        mitu = mitu + a[mitu];
        if(mitu == a.size()-1){
            flag = true;
            break;
        }
        if(a[mitu] == 0){
            break;
        }
    }
    if(flag){
        cout<<"true"<<endl;
    }
    else
    cout<<"false"<<endl;
}

MIOJ #89 N!

2019年1月5日 by 风向晚·0 Comments

描述

给定一个整数N，求N!的末尾有多少个0.

输入

输入为一个整数N，1 <= N <= 1000000000.

输出

输出为N!末尾0的个数

输入样例

输出样例

AC代码：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int num = 0;
    while(cin>>num)
    {
        int cnt = 0;
        for(int i = 1; i<num; i++)
        {
            int j = i;
            while(j%5  == 0)
            {
                cnt++;
                j= j/5;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

MIOJ #73 找出单独出现的数字II

2019年1月5日 by 风向晚·0 Comments

描述

给出一个数组，数组中的数字皆为正整数，除了某一个数字，其他的数字都会出现三次。找出那个只出现一次的数。

输入

3n+1的正整数数组，使用逗号(,)分隔(n>0)

输出

单独出现的数字

输入样例

2,3,2,2
5,1,4,5,4,5,4

输出样例

3
1

AC代码：

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;
int main()
{

    map<int,int>a;
    int b;
    while(cin>>b)
    {
        a[b]++;
        if (cin.get() == '\n')
            break;
    }
    for(map<int,int>::iterator iter=a.begin();iter!=a.end();iter++){
          if(iter->second == 1){
            cout<<iter->first<<endl;
          }
	}
}

MIOJ #62 括号配对

2019年1月5日 by 风向晚·0 Comments

描述

我们知道，在逻辑表达式中广泛使用了括号，而括号都是层次化成对出现的。也就是任意左括号都应该存在一个在同一逻辑层级的右括号作为对应。现在我们有一些仅由括号组成的字符串序列，保证每个字符为大括号”{”,”}”、中括号”[”,”]”和小括号”(”,”)”中的一种。需要判断给定的的序列是否合法。

输入

一行仅由括号组成的字符串

输出

如果序列合法输出 1，否则输出 0

输入样例

[()]
({[])}
[()]{}

输出样例

1
0
1

小提示

栈的典型应用

AC代码：

#include <bits/stdc++.h>
#include<vector>
#include<stack>
using namespace std;

int main()
{
    string s;
    while(cin>>s)
    {
        stack<char>a;
        bool flag = false;
        for(int i = 0; i<s.length(); i++)
        {
            if(s[i]=='[' || s[i]=='(' || s[i]=='{')
            {
                a.push(s[i]);
            }
            else if(s[i]==']' )
            {
                if(!a.empty() &&a.top()=='[')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
            else if(s[i]==')' )
            {
                if(!a.empty() &&a.top()=='(')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
            else if(s[i]=='}' )
            {
                if(!a.empty() &&a.top()=='{')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
        }
        if(a.empty())
        {
            cout<<"1"<<endl;
        }
        else cout<<"0"<<endl;
    }
}

MIOJ #35 分糖果

2019年1月4日 by 风向晚·0 Comments

描述

将 M 个同样的糖果放在 N 个同样的篮子里，允许有的篮子空着不放，共有多少种不同的分法？比如，把 7 个糖果放在 3 个篮子里，共有 8 种分法（每个数表示篮子中放的糖果数，数的个数为篮子数）： 1 1 5 1 2 4 1 3 3 2 2 3 2 5 0 3 4 0 6 1 0 7 0 0

注意：相同的分布，顺序不同也只算作一种分法，如 7 0 0、0 7 0 和 0 0 7 只算作一种。

输入

输入包含二个正整数 M 和 N，以(,)分开，M 表示有几个同样的糖果，N 表示有几个同样的篮子 M与N范围：1 <= M，N <= 100。

输出

输出一个正整数 K，表示有多少种分法。

输入样例

7,3

输出样例

AC代码：

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;

int calc(int m,int n)
{
    if(m== 0 || n==1)
    {
        return 1;
    }
    //当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
    //当没有苹果可放时，定义为１种放法；
    //递归的两条路，第一条n会逐渐减少，终会到达出口n==1;
    //第二条m会逐渐减少，因为n>m时，我们会return f(m,m)　所以终会到达出口m==0．
    if(m < n)
    {
        return calc(m,m);
    }
    else
    {
        return calc(m-n,n)+calc(m,n-1);
        //所有篮子放满和有一个篮子空的情况
        //放满的时候分法和每个篮子拿去一个糖果相同
        //有一个篮子空的时候相当于和这个篮子不存在的时候的分法相同
    }
}


int main()
{
    int m = 0;
    int n = 0;
    while(cin>>m)
    {
        cin.get();
        cin>>n;
        cout<<calc(m,n)<<endl;
    }
}

MIOJ #30 反向位整数

2019年1月4日 by 风向晚·0 Comments

描述

输入32位无符号整数，输出它的反向位。例，输入4626149（以二进制表示为00000000010001101001011011100101），返回2808701440（以二进制表示为10100111011010010110001000000000）。

输入

一个无符号32位整数字符串

输出

一个无符号32位整数，为输入整数的反向位

输入样例

输出样例

2808701440

AC代码：

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

int pow2(int a){
     int sum = 1;
     while(a--){
        sum = sum*2;
     }
     return sum;
}



int main()
{
    int number;
    while(cin>>number)
    {
        unsigned int result = 0;
        int cnt = 0;
        unsigned int mask = 1;
    mask = mask << 31;
    while(mask)
    {
        if(number & mask)
        {
            result = result + pow2(cnt) * 1;
        }
        else
        {
            result = result + pow2(cnt) * 0;
        }
        mask = mask>>1;
        cnt++;
    }
    cout<<result<<endl;
    }
}

MIOJ #20 有多少个等差数列？

2019年1月4日 by 风向晚·0 Comments

描述

等差数列是常见数列的一种，如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，而这个常数叫做等差数列的公差，公差常用字母d表示。即对于数列S，它满足了 $\gt 1)$ 。显然，一个数字无法构成等差数列，而任意两个数字可以形成一个等差数列。这里给出了一个长度为 $N (0 < N < 200)$ 的数字序列，每个位置有一个整数 $(- 100 \leq 整数 \leq 100)$ ，需要找到这个数字序列里包含多少个等差数列，序列顺序固定，无需排序。输入数据格式： $S[0] S[1] S[2] \dots S[N]$ （以半角空格符分隔， $N > 1$ ）输出数据格式：等差数列数量 $M$ ；其中数列 $S$ 的项为整数

请注意时间复杂度的限制。

输入

输入一个数列[ 2 7 4 5 6 ]，该数列包含等差数列： [ 2 7 ] [ 2 4 ] [ 2 5 ] [ 2 6 ] [ 7 4 ] [ 7 5 ] [ 7 6 ] [ 4 5 ] [ 4 6 ] [ 5 6 ] [ 2 4 6 ] [ 4 5 6 ]

输出

上例共包含12组等差数列，故应输出12

输入样例

2 7 4 5 6
3 3 3 3

输出样例

12
11

AC代码：

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;

int dp[400+1][400+1];

int main()
{
        memset(dp,0,sizeof(dp));
        int b;
        int result = 0;
        vector<int>a;
        bool flag = false;
        while(cin>>b)
        {
            a.push_back(b);
            if (cin.get() == '\n')
                break;
        }
        for(int k = -200; k<=200; k++)
        {
            for(int j = 0; j<a.size(); j++)
            {
                for(int i = j+1; i<a.size(); i++)
                {
                    if(a[j]+k == a[i])
                    {
                        dp[i][k+200] = dp[i][k+200] + dp[j][k+200]+1;
                    }//k+200 因为数组下标必须大于等于0
                }
            }
        }
        for(int i = 0; i<a.size(); i++)
        {
            for(int k = -200; k<=200; k++)
            {
                result = result + dp[i][k+200];
            }
        }
        cout<<result<<endl;
}

MIOJ #19 大数的加法运算与大小判断

2019年1月3日 by 风向晚·0 Comments

描述

对于给定的算术表达式，按规则输出计算结果，仅包含加法和大小判断。

输入

一行字符串，为加号、大于、小于( + < > ) 连接的两个不限大小的非负整数。

输出

当符号为 + 时, 计算两个数相加的和, 并以字符串格式返回；当符号为 < 时, 如果左数小于右数, 返回大写字母字符 Y, 否则返回大写字母字符 N；当符号为 > 时, 如果左数大于右数, 返回大写字母字符 Y, 否则返回大写字母字符 N。

!!!请同学们尽量使用算法来解决这个问题

输入样例

972919822976663297>74058
875098336507333719633571722631534917759993913379786689>53558270653237768027942884431075534537929401567824882097903948774409200
7625022925148127196027859399571498914361+790786706794530

输出样例

Y
N
7625022925148127196027860190358205708891

AC代码：

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

string func1(string s1,string s2) //大于号
{
    if(s1.length()>s2.length())
    {
        return "Y";
    }
    else if(s1.length()<s2.length())
    {
        return "N";
    }
    else if(s1 == s2)
    {
        return "N";
    }
    else
    {
        int i = 0;
        while(i!=s1.length())
        {
            if((s1[i]-'0') > (s2[i]-'0'))
            {
                return "Y";
            }
            else if((s1[i]-'0') < (s2[i]-'0'))
            {
                return "N";
            }
            i++;
        }
    }
}

string func2(string s1,string s2) //小于号
{
    if(s1.length()>s2.length())
    {
        return "N";
    }
    else if(s1.length()<s2.length())
    {
        return "Y";
    }
    else if(s1 == s2)
    {
        return "N";
    }
    else
    {
        int i = 0;
        while(i!=s1.length())
        {
            if((s1[i]-'0') > (s2[i]-'0'))
            {
                return "N";
            }
            else if((s1[i]-'0') < (s2[i]-'0'))
            {
                return "Y";
            }
            i++;
        }
    }
}

string func3(string s1,string s2) //加号
{
    char temp;
    string result ="";
    bool flag = false;//判断是否有进位
    //已经默认s1>=s2
    while(s1.length()!=s2.length()){
        s2 = "0" + s2;
    }
    int i = s1.length()-1;
    while(i>=0)
    {
        stringstream ss;
        ss.clear();
        string temp = "";
        if(flag == false)
        {
            if((s1[i]-'0') + (s2[i]-'0') > 9)
            {
                flag = true;
                ss.clear();
                ss<<(((s1[i]-'0') + (s2[i]-'0'))-10);
                ss>>temp;
                result =temp + result;
            }
            else
            {
                flag = false;
                ss.clear();
                ss<<((s1[i]-'0') + (s2[i]-'0'));
                ss>>temp;
                result = temp + result;
            }
        }
        else
        {
            if((s1[i]-'0') + (s2[i]-'0')+1 > 9)
            {
                flag = true;
                ss.clear();
                ss<<(((s1[i]-'0') + (s2[i]-'0')+1)-10);
                ss>>temp;
                result =  temp+ result;
            }
            else
            {
                flag = false;
                ss.clear();
                ss<<((s1[i]-'0') + (s2[i]-'0')+1);
                ss>>temp;
                result = temp + result;
            }
        }
        i--;
    }
    if(flag == true)
        {
            result = "1" + result;
        }
    return result;
}

int main()
{
    string s="";
    while(cin>>s)
    {
        int mode = 0;
        string s1 = "";
        string s2 = "";
        for(int i = 0; i<s.length(); i++)
        {
            if(s[i] == '>' || s[i] =='<' ||s[i] =='+')
            {
                s1 = s.substr(0,i);
                s2 = s.substr(i+1,s.length()-i-1);
                if(s[i] == '>')
                {
                    mode = 1;
                }
                else if(s[i] == '<')
                {
                    mode = 2;
                }
                else if(s[i] == '+')
                {
                    mode = 3;
                }
                break;
            }

        }
        if(mode == 1)
        {
            cout<<func1(s1,s2)<<endl;
        }
        else if(mode == 2)
        {
            cout<<func2(s1,s2)<<endl;
        }
        else if(mode == 3)
        {
            if(func1(s1,s2) == "Y")
            {
                cout<<func3(s1,s2)<<endl;
            }
            else
            {
                cout<<func3(s2,s1)<<endl;
            }
        }
    }
}

MIOJ #18 帮小学生排队

2019年1月3日 by 风向晚·0 Comments

描述

用一个数组表示一群正在排队的小学生，每个小学生用一对整数 H, K 来表示：H 表示这个小学生的身高，K 表示这个小学生前面应该有 K 个人的身高 >= 他。

写一个算法，对给出的一组小学生计算出符合描述的正确排序。

输入

输入为一组整数，以空格分隔：

第 1 个数字表示小学生的数量 n；
从第 2 个数字起，后续的数字两两一组，分别代表每个小学生的 H 和 K 的值

输出

根据输入，按照题目要求对小学生进行排序，每个小学生对应的 H 和 K 值为一组，按组输出，数字间使用空格分隔。

输入样例

6 7 0 4 4 7 1 5 0 6 1 5 2

输出样例

5 0 7 0 5 2 6 1 4 4 7 1

AC代码：

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

typedef struct student{
     int h;
     int k;
};

int comp(const student &a,const student &b){
    if(a.h == b.h){
        return a.k < b.k;
    }
    return a.h>b.h;
}

int main(){
   int n;
   while(cin>>n){
    student stu[n+1];
    for(int i = 0; i<n ;i++){
        cin>>stu[i].h>>stu[i].k;
    }
      sort(stu,stu+n,comp);
     vector<student>a;
     for(int i = 0;i<n;i++){
        a.insert(a.begin()+stu[i].k,stu[i]);
     }
     cout<<a[0].h<<" "<<a[0].k;
     for(int i = 1;i<n;i++){
        cout<<" "<<a[i].h<<" "<<a[i].k;
     }
      cout<<endl;
   }
}