『洛谷』语言基础题

入门级-语言基础题

P1421 小玉买文具

题目描述

班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是 1 元 9 角，而班主任给小玉的钱是 a 元 b 角，小玉想知道，她最多能买多少只签字笔呢。

输入格式

输入只有一行两个整数，分别表示 a 和 b。

输出格式

输出一行一个整数，表示小玉最多能买多少只签字笔。

输入输出样例

输入: #1

10 3

输出: #1

5

说明/提示

数据规模与约定

对于全部的测试点，保证 $0 a ^4, 0 b $

解题思路

和生活中的钱计算一样，将“角”转为“元”再即可

解答代码

a, b = map(int, input().split())
print(int((a + b / 10) / 1.9))

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int BuyStationery(int a, int b) {
        double money = a + (double)b / 10;
        return (int)(money / 1.9);
    }
};

int main() {
    int a, b;
    Solution s;
    cin >> a >> b;
    cout << s.BuyStationery(a, b) << endl;
    return 0;
}

import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();
        double money = a + (double)b / 10;
        System.out.println((int)(money / 1.9));
    }
}

---

P1909 [NOIP2016 普及组] 买铅笔

题目描述

P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋 友们发礼物。

现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱。

输入格式

第一行包含一个正整数n，表示需要的铅笔数量。

接下来三行，每行用2个正整数描述一种包装的铅笔：其中第1个整数表示这种 包装内铅笔的数量，第2个整数表示这种包装的价格。

保证所有的7个数都是不超过10000的正整数。

输出格式

1个整数，表示P老师最少需要花费的钱。

输入输出样例

输入: #1

57
2 2
50 30
30 27

输出: #1

54

输入: #2

9998
128 233
128 2333
128 666

输出: #2

18407

输入: #3

9999
101 1111
1 9999
1111 9999

输出: #3

89991

解题思路

只能买同一个包装的，那就太简单了，枚举三种情况取最小值即可

置于每一种情况的计算，小学生的问题没必要解释了吧~

解答代码

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

class Solution {
public:
    int BuyPencils(int n, vector<vector<int> > & pencils) {
        int ans = 0x7FFFFFFF;
        for (int i = 0; i < 3; ++i) {
            // 数量、价格
            int x = pencils[i][0], y = pencils[i][1];
            ans = min(ans, (n / x + (n % x > 0 ? 1 : 0)) * y);
        }
        return ans;
    }
};

int main() {
    int n;
    vector<vector<int> > pencils(3, vector<int>(2, 0));
    cin >> n;
    for (int i = 0; i < 3; ++i){
        cin >> pencils[i][0] >> pencils[i][1];
    }
    Solution s;
    cout << s.BuyPencils(n, pencils);
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] pencils = new int[3][2];
        for (int[] p : pencils) {
            p[0] = in.nextInt();
            p[1] = in.nextInt();
        }
        System.out.println(new Main().BuyPencils(n, pencils));
        in.close();
    }

    public int BuyPencils(int n, int[][] pencils) {
        int ans = Integer.MAX_VALUE;
        for (int[] p : pencils) {
            int num = p[0], prices = p[1];
            ans = Math.min(ans, (prices * (n / num + (n % num == 0 ? 0 : 1))));
        }
        return ans;
    }
}

n = int(input())
pencils = []
for _ in range(3):
    pencils.append(map(int, input().split()))
ans = min(b * (n // a + (1 if n % a else 0)) for a, b in pencils)
print(ans)

---

P1089 [NOIP2004 提高组] 津津的储蓄计划

题目描述

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下33元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

输入格式

12行数据，每行包含一个小于350的非负整数，分别表示11月到12月津津的预算。

输出格式

一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

注意，洛谷不需要进行文件输入输出，而是标准输入输出。

输入输出样例

输入: #1

290
230
280
200
300
170
340
50 
90 
80 
200
60 

输出: #1

-7 

输入: #2

290 
230 
280 
200 
300 
170 
330 
50 
90 
80 
200 
60 

输出: #2

1580

解题思路

题目中已经给出了明确的计算流程，对于这种题目，选择合适的数据结构模拟即可

这题并没有什么需要使用的数据结构，记下每个月剩下的钱即可

解答代码

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

class Solution {
public:
    int Jinjinplan(vector<int>& nums) {
        int n = nums.size(); // 12
        int pre = 0, s = 0; // 上个月剩下的零钱, 存下的零钱
        for (int i = 0; i < n; ++i) {
            int cur = pre + 300 - nums[i]; // 本月除去预算剩下的
            if (cur < 0) return -(i + 1);
            pre = cur % 100;
            s += cur - pre;
        }
        return int(s * 1.2) + pre;
    }
};

int main() {
    vector<int> nums(12, 0);
    for (int i = 0; i < 12; ++i) {
        cin >> nums[i];
    }
    Solution s;
    cout << s.Jinjinplan(nums);
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[12];
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 12; ++i) {
            nums[i] = sc.nextInt();
        }
        Main s = new Main();
        System.out.println(s.Jinjinplan(nums));
        sc.close();
    }

    public int Jinjinplan(int[] nums) {
        int n = nums.length; // 12
        int pre = 0, s = 0; // 上个月剩下的和存在妈妈那里的
        for (int i = 0; i < n; ++i) {
            int cur = 300 + pre - nums[i];
            if (cur < 0)
                return -(i + 1); // 不够花了
            pre = cur % 100;
            s += cur - pre;
        }
        return (int)((double)s * 1.2) + pre;
    }
}

class Solution:
    def Jinjinplan(self, nums):
        pre, s = 0, 0
        for i, m in enumerate(nums):
            cur = 300 + pre - m
            if cur < 0: return -(i + 1)
            pre = cur % 100
            s += cur - pre
        return int(s * 1.2) + pre

nums = [int(input()) for _ in range(12)]
print(Solution().Jinjinplan(nums))

---

P1085 [NOIP2004 普及组] 不高兴的津津

题目描述

津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

输入格式

输入包括7行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

输出格式

一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

输入输出样例

输入: #1

5 3
6 2
7 2
5 3
5 4
0 4
0 6

输出: #1

3

解题思路

抽象的说，就是在一个长度为 7 的数组中查找大于 8 且最大数的下标

解答代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int UnhappyJinjin(vector<int>& nums) {
        int data = 0, tim = -1;
        for (int i = 0; i < 7; ++i) {
            if (nums[i] > 8 && nums[i] > tim) {
                data = i + 1;
                tim = nums[i];
            }
        }
        return data;
    }
};

int main() {
    vector<int> nums(7, 0);
    for (int i = 0; i < 7; ++i) {
        int a, b;
        cin >> a >> b;
        nums[i] = a + b;
    }
    Solution s;
    cout << s.UnhappyJinjin(nums) << endl;
    return 0;
}

import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int data = 0, tim = -1;
        for (int i = 0; i < 7; ++i) {
            int s = sc.nextInt() + sc.nextInt();
            if (s > 8 && s > tim) {
                data = i + 1;
                tim = s;
            }
        }
        System.out.println(data);
        sc.close();
    }
}

nums = [sum(map(int, input().split())) for _ in range(7)]
print(max([i for i in range(7) if nums[i] > 8], key=lambda x: nums[x]) + 1)

---

P1035 [NOIP2002 普及组] 级数求和

题目描述

已知：\(S_n= 1+1/2+1/3+…+1/n\)。显然对于任意一个整数 \(k\)，当 \(n\) 足够大的时候，\(S_n > k\)。

现给出一个整数 \(k\)，要求计算出一个最小的 \(n\)，使得 \(S_n > k\)。

输入格式

一个正整数 k。

输出格式

一个正整数 n。

输入输出样例

输入: #1

1

输出: #1

2

输入: #2

15

输出: #2

1835421

数据范围

对于 \(100\%\) 的数据，\(1\le k \le 15\)。

解题思路

调和级数是发散的，模拟即可, 时间复杂度 \(O(e^k)\)

调和级数没有通项公式，但有近似公式 \(S_n = ln(n) + 0.5772\), 可以直接解方程得到 \(n\)

\(n > e^{k - 0.5772}\)

解答代码

方法一：模拟

#include <iostream>

int main() {
    int k;
    std::cin >> k;
    int i = 0;
    double s = 0;
    while (s <= k) {
        s += 1.0 / (++i);
    }
    std::cout << i << std::endl;
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        double s = 0;
        int i;
        for (i = 0; !(s > k); ) {
            s += 1.0 / (double) (++i);
        }
        System.out.println(i);
        sc.close();
    }
}

k = int(input())
s, i = 0, 0
while not s > k:
    i += 1
    s += 1 / i
print(i)

方法二：数学

import math
print(int(math.exp(int(input()) - 0.5772156649) + 0.5))

---

P1980 [NOIP2013 普及组] 计数问题

题目描述

试计算在区间 \(1\) 到 \(n\) 的所有整数中，数字 \(x\)（\(0\leq x\leq9\)）共出现了多少次？例如，在 \(1\) 到 \(11\) 中，即在 \(1,2,3,4,5,6,7,8,9,10,11\) 中，数字 \(1\) 出现了 \(4\) 次。

输入格式

\(2\) 个整数 \(n,x\)，之间用一个空格隔开。

输出格式

\(1\) 个整数，表示 \(x\) 出现的次数。

输入输出样例

输入: #1

11 1

输出: #1

4

数据范围

对于 \(100\%\) 的数据，\(1\le n\le 10^6\)，\(0\le x \le 9\)

解题思路

1. 如题，计数即可，时间复杂度 \(O(nlog_{10}n)\)
2. 找规律，例如 n = 128, x = 1 (62个)
   1. 个位为 1 的 13 种: 1, 11, 21, 32, ... , 121 (规律是不看个位数那就是 0 ~ 12)
   2. 十位为 1 的 20 种: 10 ~ 19, 110 ~ 119 (规律是不看个位和十位那就是 0 ~ 1, 只看个位就是 0 ~ 9)
   3. 百位为 1 的 29 种: 100 ~ 128
   4. 由此可得时间复杂度为 \(O(log_{10}n)\) 的方法

解答代码

方法一：模拟&计数

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

class Solution {
public:
    int CountProblem(int n, int x) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            int s = i;
            while (s > 0) {
                if (s % 10 == x) ++cnt;
                s /= 10;
            }
        }
        return cnt;
    }
};

int main() {
    Solution s;
    int n, x;
    cin >> n >> x;
    cout << s.CountProblem(n, x) << endl;
    return 0;
}

import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt();
        sc.close();
        Main s = new Main();
        System.out.println(s.CountProblem(n, x));
    }
    
    public int CountProblem(int n, int x) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = i; j > 0; j /= 10) {
                if (j % 10 == x) ++cnt;
            }
        }
        return cnt;
    }
}

n, x = input().split()
cnt = 0
for i in range(1, int(n) + 1):
    cnt += str(i).count(x)
print(cnt)

方法二：找规律(参考了评论区的代码)

import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt();
        sc.close();
        Main s = new Main();
        System.out.println(s.CountProblem(n, x));
    }
    
    public int CountProblem(int n, int k) {
        int cnt = 0;
        for (int base = 1; base <= n; base *= 10) {
            // x, y, z 分别表示第 i 位 前， 中， 后的数值，如12580第3位 - 12,5,80
            int x = n / base / 10, y = (n / base) % 10, z = n % base;
            if (k != 0) {
                if (y > k)
                    cnt += (x + 1) * base;
                else if (y == k)
                    cnt += x * base + z + 1;
                else
                    cnt += x * base;
            }
            else {
                if (y == 0)
                    cnt += (x - 1) * base + z + 1;
                else
                    cnt += x * base;
            }
        }
        return cnt;
    }
}

---

P1014 [NOIP1999 普及组] Cantor 表

题目描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

\(1/1\) , \(1/2\) , \(1/3\) , \(1/4\), \(1/5\), …

\(2/1\), \(2/2\) , \(2/3\), \(2/4\), …

\(3/1\) , \(3/2\), \(3/3\), …

\(4/1\), \(4/2\), …

\(5/1\), …

…

我们以 Z 字形给上表的每一项编号。第一项是 \(1/1\)，然后是 \(1/2\)，\(2/1\)，\(3/1\)，\(2/2\)，…

输入格式

整数\(N\)（\(1 \leq N \leq 10^7\)）。

输出格式

表中的第 \(N\) 项。

输入输出样例

输入: #1

7

输出: #1

1/4

解题思路

题目写得不是太清楚，但通过例子可以看出其实是在对角线上进行 Z 形的遍历

仔细观察不难发现对角线上的分数分子分母之和相等，并且第 \(i\) 行有 \(i\) 个分数，由此可以套用求和公式直接定位 \(N\) 所在行数和在行中的位置，由此可以得到 \(O(1)\) 时间复杂度的解法(具体细节参看注释吧)

解答代码

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

class Solution {
public:
    string Cantor(int n) {
        // 根据等差数列求和公式 (1 + i) * i / 2 = n 反推 n 所在行号 i
        int i = (int)ceil(sqrt(2 * (double)n + 0.25) - 0.5);
        int s = n - (i - 1) * i / 2; // 计算行内的具体位置
        if (i % 2 == 0) {
            // 偶数行逆序
            s = i + 1 - s;
        }
        return to_string(i + 1 - s) + "/" + to_string(s);
    }
};

int main() {
    Solution s;
    int n;
    cin >> n;
    cout << s.Cantor(n) << endl;
    return 0;
}

import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main s = new Main();
        int n = sc.nextInt();
        sc.close();
        System.out.println(s.Cantor(n));
    }

    public String Cantor(int n) {
        // 根据等差数列求和公式 (1 + i) * i / 2 = n 反推 n 所在行号 i
        int i = (int)Math.ceil(Math.sqrt(2 * (double)n +0.25) - 0.5);
        int s = n - (i - 1) * i / 2; // 计算行内的具体位置
        if (i % 2 == 0) {
            // 偶数行逆序
            s = i + 1 - s;
        }
        return Integer.toString(i + 1 - s) + "/" + Integer.toString(s);
    }
}

import math
n = int(input())
# 根据等差数列求和公式 (1 + i) * i / 2 = n 反推 n 所在行号 i
i = math.ceil(math.sqrt(2 * n + 0.25) - 0.5)
s = n - (i - 1) * i // 2 # 计算行内的具体位置
if i % 2 == 0:
    s = i - s + 1
print("{}/{}".format(i + 1 - s, s))

---

P1307 [NOIP2011 普及组] 数字反转

题目描述

给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。

输入格式

一个整数 \(N\)

输出格式

一个整数，表示反转后的新数。

输入输出样例

输入: #1

123

输出: #1

321

输入: #2

-380

输出: #2

-83

数据范围

$-1,000,000,000≤N≤1,000,000,000 $。

解题思路

1. 好像没什么技巧，就取余除10运算就行(要注意取值范围)
2. 也可以当成字符串翻转

解答代码

三种语言的实现有点不同

#include <iostream>

class Solution {
public:
    long Reverse(long n) {
        // 保险起见输入输出都用 long
        long res = 0;
        while (n != 0) {
            res = res * 10 + n % 10;
            n /= 10;
        }
        return res;
    }
};

int main() {
    Solution s;
    long n;
    std::cin >> n;
    std::cout << s.Reverse(n) << std::endl;
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main s = new Main();
        String st = sc.next();
        sc.close();
        System.out.println(s.Reverse(st));
    }

    public String Reverse(String _s) {
        // 特殊处理下0
        if (_s.equals("0"))
            return "0";
        // 如果数字很大，那就必须得在字符串上进行翻转操作了
        StringBuilder sb = new StringBuilder();
        char[] s = _s.toCharArray();
        int n = s.length, end = 0;
        if (s[0] == '-') {
            sb.append('-');
            end = 1;
        }
        boolean tag = false; // 用于处理末尾为 0 反转后 0 在最前面的问题
        for (int i = n - 1; i >= end; --i) {
            if (tag)
                sb.append(s[i]);
            else if (s[i] != '0') {
                sb.append(s[i]);
                tag = true;
            }
        }
        return sb.toString();
    }
}

def Reverse(n: int) -> int:
    """转字符串反转后再转回数字"""
    if n >= 0:
        return int(str(n)[::-1])
    else:
        return -int(str(n)[-1:0:-1])

print(Reverse(int(input())))

---