新手村-简单字符串

计算机不仅可以处理数字,还能处理文字!就是其实跟数字也没什么差。

基本都是模拟题。

P1055 ISBN号码 模拟

题目描述

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

识别码的计算方法如下:

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

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

说明

2008普及组第一题

Code $O(n)$

这种题就是好,做个题还能学知识

没考虑X的话,直接50%不过也太那啥。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

char reco(string s){
for(int i = 0; i < s.length() - 1; ++i){
s[i] -= '0';
}
return (s[0] + s[2]*2+s[3]*3+s[4]*4 + s[6]*5+s[7]*6+s[8]*7+s[9]*8+s[10]*9) % 11 +'0';
}

int main(){
ios::sync_with_stdio(false);
string s; cin >> s;
char re = reco(s);
if(re == '0' + 10) re = 'X';
if(re == s[12]) cout<<"Right";
else{
s[12] = re;
cout<<s;
}
}

P1200 [USACO1.1]你的飞碟在这儿Your Ride Is He… 模拟

题目描述

众所周知,在每一个彗星后都有一只UFO。这些UFO时常来收集地球上的忠诚支持者。不幸的是,他们的飞碟每次出行都只能带上一组支持者。因此,他们要用一种聪明的方案让这些小组提前知道谁会被彗星带走。他们为每个彗星起了一个名字,通过这些名字来决定这个小组是不是被带走的那个特定的小组(你认为是谁给这些彗星取的名字呢?)。关于如何搭配的细节会在下面告诉你;你的任务是写一个程序,通过小组名和彗星名来决定这个小组是否能被那颗彗星后面的UFO带走。

小组名和彗星名都以下列方式转换成一个数字:最终的数字就是名字中所有字母的积,其中A是1,Z是26。例如,USACO小组就是21×19×1×3×15=17955。如果小组的数字mod47等于彗星的数字mod47,你就得告诉这个小组需要准备好被带走!(记住“a mod b”是a除以b的余数;34mod10等于4)

写出一个程序,读入彗星名和小组名并算出用上面的方案能否将两个名字搭配起来,如果能搭配,就输出“GO”,否则输出“STAY”。小组名和彗星名均是没有空格或标点的一串大写字母(不超过6个字母)。

Code $O(\text{strlen})$

水题。。貌似又可以就地一波。。while ( (v = cin.get() ) != '\n') dosomething...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int convert_to_int(string &s){
int len = s.length(), result = 1; //initialize result as a bias: 1
for(int i = 0; i < len; ++i)
result *= s[i] - 'A' + 1;
result %= 47;
return result;
}

int main(){
string str;
int a, b;
cin >> str; a =convert_to_int(str);
cin >> str; b =convert_to_int(str);
if(a == b) cout<<"GO";
else cout<<"STAY";
}

P1308 统计单词数 自动机

题目描述

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

现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章

中的某一独立单词在不区分大小写的情况下完全相同(参见样例1 ),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2 )。

说明

数据范围

1≤单词长度≤10。

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

noip2011普及组第2题

Code $O(n)$

不用自动机会把自己累死。。。

自动机

这道题有毒。。。orz

什么鬼?下载下来测试点5的out是31 163,然而我输出的是12 147,然而我在OJ上过了

WTF???测例有毒吧。

直接把每个单词读进来比较word==keyword的策略是不行的。。因为这个题目的侧例不规则(各种空格神出没)。。需要getline(cin,string);。。

自动机相当与要设置一个状态转移策略。(可以用状态转移矩阵之类的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

void convert_to_low(string &s){
int len = s.length();
for(int i = 0; i < len; ++i)
if(s[i] <= 90 && s[i] >= 65) s[i] += 32;
}

void convert_to_low(char &s){
if(s <= 90 && s >= 65) s += 32;
}

int main(){
string keyword;
cin>>keyword; convert_to_low(keyword);

int pos = -1; //first show postion
int sentence_pos = 0; //for sentence
int count = 0; //show times
int status = 0; //how many word has been marked
int keyword_len = keyword.length();

char letter; getchar(); //filter '\n' in the first row
char pre_base_letter = ' '; // make sure this is a start of a word
while( letter = getchar() ){

convert_to_low(letter);

// cout<<"--->get_letter=<"<<letter<<">";

if(pre_base_letter == ' ' && (letter == keyword[status] || (status==keyword_len && ( letter == '\n' || letter==' '))))
status++;
else {
pre_base_letter = letter;
status = 0;
}
// cout<<" status:"<<status<<" sentence_pos:"<<sentence_pos<<endl;
if((status == keyword_len+1)){
if(pos == -1) pos = sentence_pos - keyword_len;
pre_base_letter = letter;
status = 0;
count++;
}
sentence_pos++;
if(letter == '\n'){
// cout<<"---------------------------break!!!!"<<endl;
break;
}
}

if(count) cout<<count<<" ";
cout<<pos;
}

P1553 数字反转(升级版) 模拟

题目描述

给定一个数,请将该数各个位上数字反转得到一个新数。

这次与NOIp2011普及组第一题不同的是:这个数可以是小数,分数,百分数,整数。整数反转是将所有数位对调;小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小数部分;分数反转是把分母的数反转,再把分子的数反转,不交换分子与分母;百分数的分子一定是整数,百分数只改变数字部分。整数新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零;小数新数的末尾不为0(除非小数部分除了0没有别的数,那么只保留1个0);分数不约分,分子和分母都不是小数(约分滴童鞋抱歉了,不能过哦。输入数据保证分母不为0),本次没有负数。

Code $O(n)$

跟数字完全没有关系的模拟题。。

这道题貌似字符串后面没有特么的\n。我。。。

题面上不交代清楚,还要自己考虑测试点的不规则性。。。

我特么,看了一下错的例题5,每个数字的前导0和后导0都要约掉?这特么?这是题意吗???辣鸡

1
2
3
4
5
6
7
测例5------------
输入:
1234567890/1234567890
输出:
987654321/987654321
我的想法:(90%)
987654321/0987654321(只有翻转以后才规约)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

void reverse(vector<char> &str, int i, int j){ //reverse every part
j--;
while(i < j){
char tmp = str[i];
str[i] =str[j];
str[j] = tmp;
i++; j--;
}
}

int main(){
vector<char> str; str.resize(25, 'F'); //initialize every char to 'F'
char tmp;
string STR; cin>>STR;
int i = 0; int len = STR.length();
while(i < len){
str[i] = STR[i]; i++;
}

int num1=0, symbol, num2;

while(str[num1] >= '0' && str[num1] <= '9') num1++;
symbol = num1; num2 = symbol + 1;
while(str[num2] !='F') num2++;

// cout<<endl<<"num1:"<<num1<<" symbol:"<<symbol<<" num2"<<num2<<endl;


int real_begin=0;
while(str[real_begin] == '0' && str[real_begin+1] <= '9' && str[real_begin+1] >= '0') real_begin++;
reverse(str, real_begin , num1);

// i=0;
// while(str[i] != 'F'){
// cout<<str[i++];
// }
// cout<<endl;
while((str[num2 - 1] == '0' && str[num2 - 2] <= '9' && str[num2 - 2] >= '0') || str[num2 - 1] == 'F') num2--;
reverse(str, symbol + 1, num2);

int begin = real_begin, end = num2; //fiter zeros in the begining and end
while(str[begin] == '0' && str[begin+1] <= '9' && str[begin+1] >= '0') begin++;
while((str[end - 1] == '0' && str[end - 2] <= '9' && str[end - 2] >= '0') || str[end - 1] == 'F') end--;

i= begin;
while(i < end){
cout<<str[i++];
}
}

这个题用python简直棒棒。

1
2
3
4
5
6
7
import re
s = re.split('(\.|\/|\%)', input())
print(int(str(int(s[0]))[::-1]),end='')
if len(s) > 1:
print(s[1][::-1],end='')
if s[2] != '':
print(int(str(int(s[2]))[::-1]),end='')

会有许多微小的BUG,神烦。。

P1598 垂直柱状图 模拟

题目描述

写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过100个字符),然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。

Code $O(n)$

有点像自己设计一个数据可视化工具。。anyway

用C++也是一个道理。。不想写。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/usr/bin/env python3
alphabet = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
count_ = [0]*30
s1 = input().split()
s2 = input().split()
s3 = input().split()
s4 = input().split()
s = s1 + s2 + s3 + s4
length = len(alphabet)
for word in s:
for i in range(length):
count_[i] += word.count(alphabet[i])

count_MAX = 0
for i in range(26):
count_MAX = max(count_MAX, count_[i])

for i in reversed(range(count_MAX)):
for j in range(length):
if count_[j] < i + 1:
print(' ',end='')
else:
print('*',end='')
if j != length-1:
print(' ',end='')
print('')
for i in range(26):
print(alphabet[i],end=' ')

P1914 小书童——密码 阿贝尔群

题目背景

某蒟蒻迷上了“小书童”,有一天登陆时忘记密码了(他没绑定邮箱or手机),于是便把问题抛给了神犇你。

题目描述

蒟蒻虽然忘记密码,但他还记得密码是由一串字母组成。且密码是由一串字母每个向后移动n为形成。z的下一个字母是a,如此循环。他现在找到了移动前的那串字母及n,请你求出密码。(均为小写)

Code $O(n)$

没什么可说的,简单的翻译程序。

注意要取出偏置,模一下。

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);
int n; cin >> n;
string s; cin >> s;
int len = s.length();
for(int i = 0; i < len; ++i)
cout<<char((s[i] - 'a' + n)%26 + 'a');
}
0%