『洛谷』字符串基础

入门级-字符串基础

P5015 [NOIP2018 普及组] 标题统计

题目描述

凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。

输入格式

输入文件只有一行，一个字符串 $s$。

输出格式

输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

输入输出样例

输入: #1

输出: #1

输入: #2

Ca 45

输出: #2

说明&提示

【输入输出样例 1 说明】

标题中共有 3 个字符，这 3 个字符都是数字字符。

【输入输出样例 2 说明】

标题中共有$ 5$ 个字符，包括 $1$ 个大写英文字母， $1$ 个小写英文字母和 $2$ 个数字字符，还有 $1$ 个空格。由于空格不计入结果中，故标题的有效字符数为 $4$ 个。

【数据规模与约定】

规定 $|s|$ 表示字符串 $s$ 的长度（即字符串中的字符和空格数）。
对于 $40\%$ 的数据，$1 ≤ |s| ≤ 5$，保证输入为数字字符及行末换行符。
对于 $80\%$ 的数据，$1 ≤ |s| ≤ 5$，输入只可能包含大、小写英文字母、数字字符及行末换行符。
对于 $100\%$ 的数据，$1 ≤ |s| ≤ 5$，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。

解题思路

基础字符串的输入

解答代码

#include <iostream>
#include <cstring>
using namespace std;

int main(){
    string s;
    int ans=0;
    while (cin >> s)
        ans += s.length();
    cout << ans << endl;
    return 0;
}

#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    char s[7];
    gets(s);
    int n = strlen(s);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            ans++;
        else if (s[i] >= 'a' && s[i] <= 'z')
            ans++;
        else if (s[i] >= '0' && s[i] <= '9')
            ans++;
    }
    printf("%d", ans);
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String _s = sc.nextLine();
        int ans = 0;
        for (char s : _s.toCharArray()) {
            if (s >= 'A' && s <= 'Z')
                ans++;
            else if (s >= '0' && s <= '9')
                ans++;
            else if (s >= 'a' && s <= 'z')
                ans++;
        }
        sc.close();
        System.out.println(ans);
    }
}

1	print(sum(map(len, input().split())))

P1055 [NOIP2008 普及组] ISBN 号码

题目描述

每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括$9$位数字、$1$位识别码和$3$位分隔符，其规定格式如x-xxx-xxxxx-x，其中符号-就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如$0$代表英语；第一个分隔符-之后的三位数字代表出版社，例如$670$代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以$1$加上次位数字乘以$2$……以此类推，用所得的结果$ $，所得的余数即为识别码，如果余数为$10$，则识别码为大写字母$X$。例如ISBN号码0-670-82162-4中的识别码$4$是这样得到的：对067082162这$9$个数字，从左至右，分别乘以$1,2,...,9$再求和，即$0×1+6×2+……+2×9=158$，然后取$158 \bmod 11$的结果$4$作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出Right；如果错误，则输出你认为是正确的ISBN号码。

输入格式

一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。

输出格式

一行，假如输入的ISBN号码的识别码正确，那么输出Right，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符-）。

输入输出样例

输入: #1

1	0-670-82162-4

输出: #1

Right

说明&提示

无

解题思路

按题目要求计算识别码即可

解答代码

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    char s[17];
    gets(s);
    int m = 0;
    for (int i = 0, j = 1; i < 12; ++i) {
        if (s[i] == '-') continue;
        m += (j++) * (s[i] - '0');
    }
    m %= 11;
    char tag;
    if (m == 10) tag = 'X';
    else tag = '0' + m;
    if (tag == s[12])
        printf("Right");
    else {
        for (int i = 0; i < 12; ++i) {
            printf("%c", s[i]);
        }
        printf("%c", tag);
    }
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] st = sc.nextLine().toCharArray();
        int cnt = 0, j = 1;
        for (int i = 0; i < 12; ++i) {
            if (st[i] == '-')
                continue;
            cnt += (j++) * (st[i] - '0');
        }
        cnt %= 11;
        char s;
        if (cnt == 10)
            s = 'X';
        else
            s = (char) ('0' + cnt);
        if (st[12] == s)
            System.out.println("Right");
        else {
            st[12] = s;
            System.out.println(st);
        }
        sc.close();
    }
}

P1308 [NOIP2011 普及组] 统计单词数

题目描述

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1 ），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2 ）。

输入格式

共$2$行。

第$1$行为一个字符串，其中只含字母，表示给定单词；

第$2$行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

输出格式

一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从$0$ 开始）；如果单词在文章中没有出现，则直接输出一个整数$-1$。

输入输出样例

输入: #1

1 2	To to be or not to be is a question

输出: #1

1
2

2 0

输入: #2

1 2	to Did the Ottoman Empire lose its power at that time

输出: #2

-1

说明&提示

数据范围

$1≤$ 单词长度 $≤10$。

$1≤$ 文章长度 $≤1,000,000$。

解题思路

很简单的字符串全匹配

解答代码

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String _s1 = sc.nextLine(), _s2 = sc.nextLine();
        sc.close();
        char[] s1 = _s1.toCharArray(), s2 = _s2.toCharArray();
        int n1 = s1.length, n2 = s2.length;
        // 将字符转换为小写字符
        for (int i = 0; i < n1; ++i) {
            s1[i] |= 32;
        }
        for (int i = 0; i < n2; ++i) {
            s2[i] |= 32;
        }
        // 全匹配
        int ind = -1, s = 0;
        loop: for (int i = 0; i < n2; ++i) {
            // 单词前一个和后一个字符应该是空格
            if ((i == 0 || s2[i - 1] == ' ') && (i + n1 - 1 == n2 || (i + n1 < n2 && s2[i + n1] == ' '))) {
                // System.out.println(i + "开始匹配：");
                for (int j = 0; j < n1; ++j) {
                    if (s1[j] != s2[i + j])
                        continue loop;
                }
                // System.out.println("匹配成功");
                if (ind == -1)
                    ind = i;
                ++s;
            }
        }
        if (s == 0)
            System.out.println(-1);
        else System.out.println(Integer.toString(s) + " " + ind);
    }
}

仅20分解法，错误原因：要求返回第一次出现的位置，位置是按字符计数而不是按单词计数

def CountWords(word: str, paper: str) -> None:
    ind, s = -1, 0
    for i, w in enumerate(paper.split()):
        if word == w:
            s += 1
            if ind == -1:
                ind = i
    if ind == -1:
        print(-1)
    else:
        print(s, ind, sep = " ")
    return None

print(CountWords())

P2010 [NOIP2016 普及组] 回文日期

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用$8$位数字表示一个日期，其中，前$4$位代表年份，接下来$2$位代表月份，最后$2$位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。

一个$8$位数字是回文的，当且仅当对于所有的$i ( 1 \le i \le 8)$从左向右数的第i个数字和第$9-i$个数字（即从右向左数的第$i$个数字）是相同的。

例如：

•对于2016年11月19日，用$8$位数字$20161119$表示，它不是回文的。

•对于2010年1月2日，用$8$位数字$20100102$表示，它是回文的。

•对于2010年10月2日，用$8$位数字$20101002$表示，它不是回文的。

每一年中都有$12$个月份：

其中，$1,3,5,7,8,10,12$月每个月有$31$天；$4,6,9,11$月每个月有$30$天；而对于$2$月，闰年时有$29$天，平年时有$28$天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1.这个年份是$4$的整数倍，但不是$100$的整数倍；

2.这个年份是$400$的整数倍。

例如：

•以下几个年份都是闰年：$2000,2012,2016$。

•以下几个年份是平年：$1900,2011,2014$。

输入格式

两行，每行包括一个$8$位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证$ date_i $和都是真实存在的日期，且年份部分一定为$4$位数字，且首位数字不为$0$。

保证$ date 1 $ —定不晚于$ date 2 $。

输出格式

一个整数，表示在$date1$和$date2$之间，有多少个日期是回文的。

输入输出样例

输入: #1

1 2	20110101 20111231

输出: #1

输入: #2

1 2	20000101 20101231

输出: #2

说明&提示

【样例说明】

对于样例1，符合条件的日期是$20111102$。

对于样例2，符合条件的日期是$20011002$和$20100102$。

【子任务】

对于$60\%$的数据，满足$date1 = date2$。

解题思路

一个日期是由 4 位的年份 + 2 位月份 + 2 位日期，由前 4 位与后 4 位成镜像关系，可知一个年份最多有一个 “回文日期”，所以可以枚举所有起始到最后年份的 “回文日期”，再检查 “回文日期” 是否合理

解答代码

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main s = new Main();
        int st = sc.nextInt(), ed = sc.nextInt();
        sc.close();
        System.out.println(s.PalindromeDate(st, ed));
    }

    static Set<Integer> month_with_31;
    static {
        month_with_31 = new HashSet<>();
        month_with_31.add(1);
        month_with_31.add(3);
        month_with_31.add(5);
        month_with_31.add(7);
        month_with_31.add(8);
        month_with_31.add(10);
        month_with_31.add(12);
    }

    public int PalindromeDate(int start, int end) {
        // 返回 起止日期中合法的回文日期 的数量
        int cnt = 0;
        // 起止年份
        int y1 = start / 10000, y2 = end / 10000;
        for (int i = y1; i <= y2; ++i) {
            // 枚举年份对应的 “回文日期”
            int year = i, month = 0, day = 0;
            for (int j = 0; j < 2; ++j) {
                month = month * 10 + year % 10;
                year /= 10;
            }
            for (int j = 0; j < 2; ++j) {
                day = day * 10 + year % 10;
                year /= 10;
            }
            year = i;
            int date = year * 10000 + month * 100 + day;
            if (date < start || date > end)
                continue;
            // 检查 “回文日期” 是否为真实存在的日期
            if (month > 12 || day > 31 || month == 0 || day == 0)
                continue;
            if (!month_with_31.contains(month) && day > 30)
                continue;
            if (month == 2) {
                if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
                    // 闰年
                    if (day > 29)
                        continue;
                } else { // 平年
                    if (day > 28)
                        continue;
                }
            }
            cnt++;
        }
        return cnt;
    }
}

m_31 = {1, 3, 5, 7, 8, 10, 12}

def PalindromeDate(start: str, end: str) -> int:
    """枚举年份对应的回文日期，校验是否合理"""
    cnt = 0
    st, ed = int(start), int(end)
    y1, y2 = int(start[:4]), int(end[:4])
    # 枚举年份对应回文日期
    for i in range(y1, y2 + 1):
        date = str(i)
        date += date[::-1]
        d = int(date)
        if not st <= d <= ed:
            continue
        # 检查 “回文日期” 是否为真实存在的日期
        year, month, day = map(int, [date[:4], date[4:6], date[6:]])
        if not 0 < month <= 12 or not 0 < day <= 31:
            continue
        if month not in m_31 and day > 30:
            continue
        if month == 2:
            if (year % 4 == 0 and year % 100) or year % 400 == 0:
                if day > 29:
                    continue
            else:
                if day > 28:
                    continue
        cnt += 1
    return cnt

print(PalindromeDate(input(), input()))

P1012 [NOIP1998 提高组] 拼数

题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，表示最大的整数

输入输出样例

输入: #1

1 2	3 13 312 343

输出: #1

34331213

输入: #2

1 2	4 7 13 4 246

输出: #2

说明&提示

对于全部的测试点，保证 $1 \leq n \leq 20$，$1 \leq a_i \leq 10^9$。

解题思路

把数字拼接起来最大，那么高位数字越大越好，~~可以将数字先排序，但规则是：先按第一个数字的大小排，如果第一个数字一样大，那么就对比第二个数字，以此类推，然后拼接所得即最大的数字~~ <-- 典型错误

6
321 32 407 135 13 217
Right answer: 407 32 321 217 135 13
Wrong answer: 407 321 32 217 135 13

正确的排序规则为：$A+B<B+A$ ，其中 + 是字符串拼接操作而比较是基于数值操作的（也可以是字典序因为拼接后等长）

解答代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

class comp {
public:
    bool operator()(const string& x, const string& y) {
        return x + y > y + x;
    }
};

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    comp c;
    sort(s.begin(), s.end(), c);
    string ans = "";
    for (string str : s)
        ans += str;
    cout << ans;
    return 0;
}

典型错误(纯字典序)：

1 2	input() print("".join(sorted(input().split(), reverse = True)))

正确的比较规则：

1
2
3

from functools import cmp_to_key
input()
print("".join(sorted(input().split(), key = cmp_to_key(lambda x, y: 1 if x + y < y + x else -1))))

P5587 打字练习

题目描述

R 君在练习打字。

有这样一个打字练习网站，给定一个范文和输入框，会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和 .（英文句号），输入字符后，光标也会跟着移动。

输入的文本有多行，R 君可以通过换行键来换行，换行后光标移动到下一行的开头。

R 君也可以按退格键（为了方便，退格键用 < 表示），以删除上一个打的字符，并将光标回移一格。特殊的，如果此时光标已经在一行的开头，则不能继续退格（即忽略此时输入的退格键）。

网站的比较方式遵循以下两个原则：

逐行比较，即对于范文和输入的每一行依次比较，不同行之间不会产生影响，多余的行会被忽略。
逐位比较，即对于两行的每一个字符依次比较，当且仅当字符相同时才会被算作一次正确，否则会被算作错误。计算答案时，只统计相同的字符个数。

需要注意的是，回车键不会被计入正确的字符个数。

R 君看到网站上显示他花了 $T$ 秒完成了这次的打字游戏，请你计算出他的 KPM（Keys per minutes，每分钟输入的字符个数），答案四舍五入保留整数部分。

输入格式

R 君会依次告诉你网站的范文，他的输入和花费的时间。

其中范文和输入将会这样读入：给定若干行字符串，以单独的一行 EOF 结束，其中 EOF 不算入输入的文本。

最后一行一个整数 $T$，表示他打字花费了 $T$ 秒。

可以参考样例输入输出文件和样例解释辅助理解。

输出格式

一行一个整数，表示 KPM。

输入输出样例

输入: #1

hello world.
aaabbbb
x
EOF
heelo world.
aaacbbbb
y<x
EOF
60

输出: #1

说明&提示

样例解释

第一行的正确字符数为 11。
第二行的正确字符数为 6，错误的字符 c 仍会占据一个位置。
第三行的正确字符数为 1，R 君使用退格键删除了被打错的字符 y

数据范围

对于 $20\%$ 的数据，不存在换行键。
对于 $40\%$ 的数据，不存在退格键。
对于 $100\%$ 的数据，$T \leq 10^3$，保证每个文本段的总字符数（包括换行）不超过 $10^5$ 个且总行数不超过 $10^4$。

解题思路

模拟即可，退格键的处理方法是将用栈处理，遇到退格键就出栈（如果栈非空）否则入栈，最后栈中的就是不带退格键的文本了

C++中直接用string模拟栈，因为STL中的stack是不支持顺序遍历的，也可以用动态数组或者静态数组模拟，这样方便后序的比较操作，然后 getline() 函数按理说是不读入换行符的，但洛谷在线IDE里面却会带换行符，不知道为什么

有两个坑：

范文也有退格键（这个只能过50）
空行不会被忽略，这里我被题目误导了，题目“多余的行会被忽略”是说 R 君多输入的行或范文比 R 君输入多的行都无视掉，不是说忽略掉文中的空行，debug了两个小时qaq（这个会得90卡在测试用例3）

解答代码

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

int main() {
    vector<string> input;
    string st;
    int cnt = 0, tim;
    // 读取范文保存下来
    while (true) {
        getline(cin, st);
        if (st == "EOF") break;
        string s = "";
        for (char c : st) {
            if (c == '<') {
                if (!s.empty())
                    s.pop_back();
            }
            else
                s.push_back(c);
        }
        if (!s.empty())
            input.emplace_back(s);
    }
    int n = input.size(), j = 0;
    while (true) {
        getline(cin, st);
        if (st == "EOF") break;
        if (j >= n) continue;
        //输入文本放入栈中，处理退格
        string s = "";
        for (char c : st) {
            if (c == '<') {
                if (!s.empty())
                    s.pop_back();
            }
            else
                s.push_back(c);
        }
        int len = min(s.size(), input[j].size());
        // 逐字符对比范文
        for (int k = 0; k < len; ++k) {
            if (s[k] == input[j][k]) cnt++;
        }
        ++j;
    }
    cin >> tim;
    cout << int(cnt * 60.0 / tim + 0.5);
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Deque<Character>> s1 = new ArrayList<>();
        List<Deque<Character>> s2 = new ArrayList<>();
        String EOF = "EOF";
        while (true) {
            String s = sc.nextLine();
            if (s.equals(EOF))
                break;
            // 处理退格符
            Deque<Character> word = new ArrayDeque<>();
            for (char c : s.toCharArray()) {
                if (c == '<') {
                    if (!word.isEmpty())
                        word.pollLast();
                } else
                    word.add(c);
            }
            s1.add(word);
        }
        while (true) {
            String s = sc.nextLine();
            if (s.equals(EOF))
                break;
            // 处理退格符
            Deque<Character> word = new ArrayDeque<>();
            for (char c : s.toCharArray()) {
                if (c == '<') {
                    if (!word.isEmpty())
                        word.pollLast();
                } else
                    word.add(c);
            }
            s2.add(word);
        }
        int T = sc.nextInt();
        sc.close();
        System.out.println(new Main().TypingCheck(s1, s2, T));
    }

    public int TypingCheck(List<Deque<Character>> s1, List<Deque<Character>> s2, int time) {
        int n1 = s1.size(), n2 = s2.size();
        int cnt = 0, i = 0;
        for (Deque<Character> word1 : s1) {
            if (i == n2)
                break;
            Deque<Character> word2 = s2.get(i++);
            int n = Math.min(word1.size(), word2.size());
            for (int j = 0; j < n; ++j) {
                if (word1.pollFirst() == word2.pollFirst())
                    cnt++;
            }
        }
        return (int) ((double) cnt * 60 / time + 0.5);
    }
}