Leo's blog

建议麦当劳

TL;DR: :memory:为每个链接打开一个新的数据库.
使用 file::memory:?cache=shared 也可能碰到问题, 配置 MaxOpenConnection 为 1 即可. (db.DB().SetMaxOpenConns(1))

Gorm这一ORM框架很好的屏蔽了不同的RDMS之间的差异, 在运行单元测试时使用sqlite的内存数据库 :memory: 显得尤为方便.

在我的 EduOJ 项目中, 数据库相关的测试没有使用 sqlmock 等, 而是使用了基于SQLite内存数据库. 但是, 在我开始编写代码的过程中出现了玄学问题: 一旦开启单元测试的 Parallel 模式, 就会随机的出现 table xxx not found 错误. 甚至, 在运行代码的过程中, 通过调试模式可以看到, 上一行还存在数据表, 到了下一行就不存在了.

以为这是一个 Race condition, db的值被替换了, 拿着
race detector 看了半天啥也没有. 又经过各种测试, 发现这个问题 当且仅当两个需要数据库的测试同时运行 时发生.

绝望之中, 搜索了一下 gorm sqlite race condition, 找到了 go-sqlite3#204 这个 issue. issue中提到, sqlite 会给每一个数据库连接单独开启一个内存数据库. 现在看起来, 这一点也非常合理: 连接与连接之间本身就是应该不 share 任何信息的. issue中给出的解决方案是, 使用 file::memory:?cache=shared 替换 :memory:.

替换为 :memory: 后, sqlite又报错说 “table xxx is locked”. 根据Django文档, 可以发现这个问题源自 sqlite 对于并发请求的处理能力偏弱. 因此, 在使用 sqlite 进行单元测试的时候, 相对好的解决方案还是配置连接池的最大连接数为1.

1
2
db, _ := gorm.Open("sqlite3",":memory:")
db.DB().SetMaxOpenConns(1)

那么, 为什么我在调试的过程中会见到如此之诡异的现象呢? 这得从库的设计说起. 由于数据库连接的建立和关闭开销较大, 是一种较为"昂贵"的资源, 因此成熟的数据库客户端库都会 使用连接池. 在需要连接的时候, 从连接池中取出一个已经建立好的连接, 使用完连接后, 放回连接池中, 就能花很大的加快应用程序的速度.

在我的使用情境中, 初始化数据库/建立数据表的SQL仅在第一个连接中执行了. 如果关闭单元测试的Parallel模式, 那么所有的单元测试都是顺序执行的, 始终会用到同一个连接, 不会出现上文的错误. 一旦开启Parallel模式, 每一次sql指令就都可能在不同的连接上进行, 而正如上文所述, 每一个连接对应了一个不同的内存数据库, 因此也就会出现 “上一行还正常, 下一行就不存在数据表” 的情况了.

码浪 - 新一代程序员献给自己的演讲.

那些口口声声,新技术太多学不动的人,应该看着咱们。

我们看着自己,满怀欣喜,程序员积攒了几十年的财富,所有的代码、论文、文档和教程,像是专门为咱们准备的礼物。 文档齐全、社区友好、生态成熟,计算机科学的成果被层层打开,可以尽情地享用。自由学习一门语言,学习一种技术,欣赏一段代码,去遥远的地方进修。 我们从小就能自由探索自己的兴趣,不在需要对着小霸王敲一行一行重启就消失了的BASIC,可以使用scratch进行图形化编程,甚至很多人在幼儿园就使用swift playground进入了不惑之年,不惑于递归是什么,回溯又是什么。人与人之间的壁垒被打破,我们只凭使用相同的库就能结交千万个一起讨论的朋友。我们有幸遇见这样的时代,但是时代更有幸遇见这样的我们。

我们看着自己,满怀敬意,向我们的开源精神致敬。我们正在把别人的变成自己的,把自己的变成别人的,把学术的变成大众的,把个人的变成世界的。随着保护开源者的协议的出现,我们的权益得到了保证。随着自由软件运动的不断推广,用户有了使用,复制,研究,修改和分发软件的权利。我们可以自由的参与、学习别人的项目,可以自由的修改我们所使用的程序来获得自己想要的功能。

任何人的想象力不足以想象我们的未来。奔涌吧,码浪!我们在同一条奔涌的河流。

布尔运算符的短路

首先, 什么是表达式?

表达式是运算符和它们的操作数的序列,它指定一项计算。

表达式的求值可以产生一个结果(比如 2+2 的求值产生结果 4),也可能产生副作用(比如对 std::printf(“%d”,4) 的求值在标准输出上打印字符 ‘4’)。

以下代码每一行的内容都是一个表达式:

1
2
3
4
5
6
a = 1
a++
a = a * a + a - a | a
foo()
foo(a+a)
a == a

注意, a++ 是表达式, a++; 就是一个语句了

其次, 什么是表达式的副作用?

表达式, 顾名思义, 是有一个值的. 很多情况下我们求一个表达式的值, 是为了使用它的值. 在求值的过程中对于变量的修改等操作被称为表达式的副作用.

比如, 对于表达式 y++, y的值+1就是这个表达式的副作用.

比如, 对于以下函数:

1
2
3
4
int foo(){
static int i = 0;
return ++i;
}

对于表达式 foo(), i 的值的变化就是他的副作用.

再比如, 对于表达式 printf("%d",a) + 1, 输出了a的值就是他的副作用.

布尔运算符的短路.

对于 “逻辑与(&&)” 和 “逻辑或(||)” 这两个运算, 他们有一个不同于其他运算符的特点, 就是运算符短路.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是假的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是假, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是真的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是真, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

如, 对于以下代码:

1
2
3
4
5
int a,b,c;
a = 1;
b = 1;
c = a++ || b++;
printf("%d%d%d\n",a,b,c);

因为表达式a++的计算结果为1, 也就是真, 因此不会计算b++, 程序会输出211.

蓝桥杯北京工业大学模拟赛 2020.03.15

1. 问题描述

在计算机存储中,15.125GB是多少MB?

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果 为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

2. 问题描述

1200000有多少个约数(只计算正约数)。

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

3. 问题描述

在1至2019中,有多少个数的数位中包含数字9?

注意,有的数中的数位中包含多个9,这个数只算一次。例如,1999这个数包含数字9,在计算只是算一个数。

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

4. 问题描述

一棵包含有2019个结点的树,最多包含多少个叶结点?

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

5. 问题描述

一个正整数如果任何一个数位不大于右边相邻的数位,则称为一个数位递增的数,例如1135是一个数位递增的数,而1024不是一个数位递增的数。

给定正整数 n,请问在整数 1 至 n 中有多少个数位递增的数?

输入格式

输入的第一行包含一个整数 n。

输出格式

输出一行包含一个整数,表示答案。

样例输入

1
30

样例输出

1
26

评测用例规模与约定

对于 40% 的评测用例,1 <= n <= 1000。

对于 80% 的评测用例,1 <= n <= 100000。

对于所有评测用例,1 <= n <= 1000000。

6. 问题描述

小明对类似于 hello 这种单词非常感兴趣,这种单词可以正好分为四段,第一段由一个或多个辅音字母组成,第二段由一个或多个元音字母组成,第三段由一个或多个辅音字母组成,第四段由一个或多个元音字母组成。

给定一个单词,请判断这个单词是否也是这种单词,如果是请输出yes,否则请输出no。

元音字母包括 a, e, i, o, u,共五个,其他均为辅音字母。

输入格式

输入一行,包含一个单词,单词中只包含小写英文字母。

输出格式

输出答案,或者为yes,或者为no。

样例输入1

1
lanqiao

样例输出2

1
yes

样例输入1

1
world

样例输出2

1
no

7. 问题描述

在数列 a[1], a[2], …, a[n] 中,如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k],则称 a[i], a[j], a[k] 为一组递增三元组,a[j]为递增三元组的中心。

给定一个数列,请问数列中有多少个元素可能是递增三元组的中心。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a[1], a[2], …, a[n],相邻的整数间用空格分隔,表示给定的数列。

输出格式

输出一行包含一个整数,表示答案。

样例输入

1
2
5
1 2 5 3 5

样例输出

1
2

样例说明

a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定

对于 50% 的评测用例,2 <= n <= 100,0 <= 数列中的数 <= 1000。

对于所有评测用例,2 <= n <= 1000,0 <= 数列中的数 <= 10000。

8. 问题描述

小明想知道,满足以下条件的正整数序列的数量:

  1. 第一项为 n;

  2. 第二项不超过 n;

  3. 从第三项开始,每一项小于前两项的差的绝对值。
    计算,对于给定的 n,有多少种满足条件的序列。

输入格式

输入一行包含一个整数 n。

输出格式

输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。

样例输入

1
4

样例输出

1
7

样例说明

以下是满足条件的序列:

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

评测用例规模与约定

对于 20% 的评测用例,1 <= n <= 5;

对于 50% 的评测用例,1 <= n <= 10;

对于 80% 的评测用例,1 <= n <= 100;

对于所有评测用例,1 <= n <= 1000。

9. 问题描述

小明有一块空地,他将这块空地划分为 n 行 m 列的小块,每行和每列的长度都为 1。

小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。

这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,这四小块空地都将变为有草的小块。

请告诉小明,k 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 n, m。

接下来 n 行,每行包含 m 个字母,表示初始的空地状态,字母之间没有空格。如果为小数点,表示为空地,如果字母为 g,表示种了草。

接下来包含一个整数 k。

输出格式

输出 n 行,每行包含 m 个字母,表示 k 个月后空地的状态。如果为小数点,表示为空地,如果字母为 g,表示长了草。

样例输入

1
2
3
4
5
6
4 5
.g...
.....
..g..
.....
2

样例输出

1
2
3
4
gggg.
gggg.
ggggg
.ggg.

评测用例规模与约定

对于 30% 的评测用例,2 <= n, m <= 20。

对于 70% 的评测用例,2 <= n, m <= 100。

对于所有评测用例,2 <= n, m <= 1000,1 <= k <= 1000。

10. 问题描述

小明要组织一台晚会,总共准备了 n 个节目。然后晚会的时间有限,他只能最终选择其中的 m 个节目。

这 n 个节目是按照小明设想的顺序给定的,顺序不能改变。

小明发现,观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系,他希望选出的第一个节目尽可能好看,在此前提下希望第二个节目尽可能好看,依次类推。

小明给每个节目定义了一个好看值,请你帮助小明选择出 m 个节目,满足他的要求。

输入格式

输入的第一行包含两个整数 n, m ,表示节目的数量和要选择的数量。

第二行包含 n 个整数,依次为每个节目的好看值。

输出格式

输出一行包含 m 个整数,为选出的节目的好看值。

样例输入

5 3
3 1 2 5 4

样例输出

3 5 4

样例说明

选择了第1, 4, 5个节目。

评测用例规模与约定

对于 30% 的评测用例,1 <= n <= 20;

对于 60% 的评测用例,1 <= n <= 100;

对于所有评测用例,1 <= n <= 100000,0 <= 节目的好看值 <= 100000。

从结构体走向对象

本文能够让你大致理解面向对象的一些概念, 但是以下一切内容均不适用于参加OO课程的考试, 如果爆零, 后果自负.

部分语法的介绍

  1. C++语言中, 定义结构体变量时, 类型中的struct可以省略, 如"struct 结构体名 变量名"可以简写为"结构体名 变量名 ". 以下均为简写形式.
  2. Java语言中, 所有内置的大写开头的类型都是类, 所有对象都是"引用变量", 可以理解为不能做运算的指针.
    (指针运算指, 数组首项地址+1等于第二项地址的这种运算.)
    如:
    1
    2
    3
    4
    5
    6
    // int不是类, 是基本类型
    // a是普通变量:
    int a = 0;
    // Integer是类, b,c是引用变量:
    Integer b = 0;
    Integer c = 0;
    上面的代码可以简单地理解为, a是一个int类型变量, 内容是0.
    b是一个指向Integer变量的指针, 他指向的值是0.
    c同理.
    因此, b==c 判断的是bc是否指向同一个对象. 判断bc相等应该用b.equals(c).
  3. 这篇推送只讲概念, 不需要完全理解代码是什么意思, 具体语法部分都做了注释. 之后大概还会有推送来讲语法. 如果那里有代码不明白什么意思欢迎联系我或者后台给我留言.

啥是类? 最简单的来说, 就是 C 语言中的结构体.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 定义一个类, 叫做Student.
*/
public class Student {
/**
* Student中的一个字符串类型的变量
*/
String name;

/**
* Student中一个int类型的变量
*/
int ID;
}

在最开始非面向对象的编程中, 我们经常会用多个变量来描述同一对象的多个属性: 比如定义一个名字变量, 一个学号变量. 后来, 随着计算机科学的发展, 编程语言中支持了 结构体 这样一个特性, 能够让我们把 描述同一个东西不同属性 的多个变量统一管理. 结构体这一个概念, 到了面向对象的语言中, 结构体发展为了类的概念.

可以把类理解为C语言中的结构体+方法.

方法

在很多情况下, 我们之前编写的一些函数是针对某一个结构体提供的. 比如, 链表的删除某个节点的函数就可以认为是针对某个节点定义的, 效果是删除这个节点后面的一个节点.

我们可以把这样的函数定义为一个全局的函数, 把一个结构体变量作为参数传入这个函数:

1
2
3
node* remove(node *now){
...
}

但是, 如果这样自定义我们就会在别的任何地方都没法再次定义一个 remove 函数了. 这个只针对 node* 的函数占据了一个全局的名字 (或者说, 符号). 无疑, 这样的实现非常 不优雅. 因此, 我们更应该把进和 node* 这一个变量相关的函数定义成一个 node*成员函数, 也叫 方法.

1
2
3
4
5
6
7
8
9
10
11
struct node {
int data;
node *;

node* remove(){
// 使用this指针访问当前的变量
// 这里仅仅演示如何使用
// 本程序并无法真的工作.
return this->next;
}
};

如果这样定义remove函数, 就不会污染全局的作用域, 同时也不用我们显示的声明参数, 只需要如下调用:

1
2
node* a;
a->remove();

即可自动把 aa的地址 作为 this指针 参数传入给 remove 函数.

因此, 方法就是针对某一个类的函数, 为了方便我们把它放到类里面. 构造一个对象的函数是一个特殊的成员函数, 叫做类的构造函数.

继承

其实, 编程语言演进的过程就是一代代程序程序员偷懒的过程 . 自从有了结构体的方法这东西之后, 人们就在想如果好几个结构体都有相同的方法, 能不能直接重复用一下?

比如对于如下几个结构体:

1
2
3
4
5
6
7
8
struct shirt{ 
double price = 9.15;
void printPrice();
};
struct trousers {
double price = 2.33;
void printPrice();
};

这两个结构体都分别有一个printPrice函数, 内容也都是一样的, 但是要写两次, 非常的不优雅, 于是人们引入了继承的概念:

May there be inheritance!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Clothes {
double price;
void printPrice(){
// 输出price
}
}
// 定义Shirt类, 继承 Clothes 类.
class Shirt extends Clothes{
double price = 9.15;
}
// 同上, 继承 Clothes 类.
class Trousers extends Clothes{
double price = 2.33;
}

这样, printPrice 函数只需要写一次. 从某个类继承, 或者说派生出来的类, 会拥有父类的所有属性以及方法. 子类也可以对应的重写这些方法.

同时, 对于以上的代码中, 显然 Clothes 类和别的类有一个很大的区别. 我们会创建一个 Shirt 类的对象, 但是我们不会执行 new Clothes(). Clothes 类存在的意义在于提供给别人继承, 我们不会实例化这个类, 因此我们把这个类定义为抽象类(abstract class):

1
2
3
4
5
6
7
// 定义抽象类
abstract class Clothes {
double price;
void printPrice(){
System.out.println(this.price);
}
}

一个抽象类的意义是提供给别人来继承. 代码中的 abstract 标记了这是一个抽象类.

多态

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
// 定义抽象类 Animal
abstract class Animal {
// 要求继承这个类的类必须实现
// bark方法, 同时提供一个默认的
// bark方法.
void bark(){
System.out.println("bark");
}
}

// 定义dog继承自animal
class Dog extends Animal{
// 重写bark方法
void bark(){
System.out.println("Woof");
}
}

// 定义cat继承自animal
class Cat extends Animal{
// 重写bark方法
void bark(){
System.out.println("Meow~");
}
}

上述代码中, Animal类规定了继承他的类要实现 bark() 方法. 那么, 对于如下的代码, 会输出什么呢?

1
2
3
4
5
Animal a = new Dog();
// 创建一个Dog, 进行隐式类型转换,
// 转换为 Animal.

a.bark();

上面说到, Java中类的变量都是引用变量, 因此上面代码可以不严谨的理解为: 定义一个 指向Animal类型的指针 a,

在这里, a 是一个Animal类型的引用, 指向一个Dog对象. 但是, 尽管他是 Animal 类型的引用, 调用 a.bark()时仍然调用的是 Dogbark() 方法.

多态, 狭义上指同一个名字(符号)指代多个物体. 在上面代码中, 如果不知道a指向的类型是什么, 调用 a.bark() 有三种可能的情况. 这就利用了多态的性质.

例子以及面向对象的好处.

在C语言中, 由于没有这些特性, 极大地存在着代码冗余重复的现象, 如: printf 函数用于格式化并向控制台输出内容, sprintf 用于格式化并向字符串写入内容, fprintf 用于格式化并向文件写入内容.

上面的三个函数, 都完成了格式化这一个步骤, 但是代码被编写了三次. 如果需要向网络连接中格式化并写入内容, 则又需要重复一遍格式化的操作. 面向对象就能很好地解决这个问题.

如, 如果我们要向一个文件写入内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 注: 下面的注释从里往外看

// 把新建的缓存输出流对象作为参数
// 传入格式化输出流
PrintWriter out = new PrintWriter(

// 把新建的编码输出流对象
// 作为参数传入给缓存输出流
// 让缓存输出流对象往
// 编码输出流输出
new BufferedWriter(

// 把新建的文件输出流对象
// 作为参数, 传入编码输出流,
// 规定编码输出流把编码后
// 的内容输出到文件输出流
new OutputStreamWriter(

// 新建一个文件输出流对象
// 写入filename.txt
new FileOutputStream("filename.txt")
)
)
);

上面代码中, 几个类的构造函数分别为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FileOutputStream(String name)
// 文件输出流, 参数是文件名
// 向指定文件输出内容
// 只能输出二进制的数据

OutputStreamWriter(OutputStream out)
// 编码输出流, 向某个输出流输出
// 除了接受二进制数据还可以接受字符串
// 将字符串编码后输出

BufferedWriter(Writer out)
// 缓存编码输出流
// 输入的东西缓存后输出

PrintWriter(Writer out)
// 格式化流
// 把输入的东西按照格式要求
// 变成字符串, 传入底层流.

可以看到, FileOutputStream 接受文件名作为参数, 单纯负责向文件中写入内容.

OutputStreamWriter 接受任何 OutputStream 对象, 用于转换写入内容的编码.

BufferedWriter 接受一个 Writer, 用于缓存即将写入 Writer 的内容.

PrintWriter 接受一个 Writer, 用于格式化输入, 写入 Writer 中.

高内聚, 低耦合的设计模式就体现在了这里: 一个 OutputStream 类只需要实现 write 方法, 只能写入二进制字节数据, 而一个 Writer 负责处理编码问题, 可以写入字符串, 负责把写入的字符串编码为二进制字节数据, 而 BufferedWriter 则负责缓存上层写入的内容, 也同样只提供了写入字符串的方法. PrintWriter 负责提供格式化的方法, 可以格式化并写入 int double char string 等多种类型.

这样的设计, 使得功能的拓展变得很方便, 比如我们要向一个自定义的东西中写入数据, 完全可以只实现一个 OutputStream 而复用 OutputStreamWriter, BufferedWriter, PrintWriter 等很多和写入数据有关的类.

所以, 这样的实际模式大概是被不断加需求改需求的产品经理逼出来的

感谢 ☁️学长,

(如果可以的话, 能关注一下这个公众号吗)

蓝桥杯校内模拟赛题解-1

1. 在计算机存储中,15.125GB是多少MB?

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。

答案: 15488

解析:

还要解析???

2. 1200000有多少个约数(只计算正约数)。

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。

答案: 96

解析:

  1. 暴力解法:
1
2
3
4
5
6
int ans = 0;
for(int i = 1; i <= 1200000; ++ i) {
if(1200000 % i == 0) {
++i;
}
}
  1. 一般解法:
    分解质因数, 得: 1200000 = 2^735^5.

约数个数为等于: 826 = 96.

3. 在1至2019中,有多少个数的数位中包含数字9?

注意,有的数中的数位中包含多个9,这个数只算一次。例如,1999这个数包含数字9,在计算只是算一个数。

答案: 544

解析:

  1. 快速解法:
1
2
3
4
5
6
7
int ans = 0;
for(int i = 1; i <= 2019; ++ i){
if(to_string(i).find("9") != string::npos){
ans++;
}
}
cout<<ans<<endl;
  1. 一般解法:
1
2
3
4
5
6
7
8
9
10
11
12
int ans = 0;
for(int i = 1; i <= 2019; ++ i){
int now = i;
while(now){
if(now % 10 == 9){
ans ++;
break;
}
now /= 10;
}
}
cout<<ans<<endl;

4. 一棵包含有2019个结点的树,最多包含多少个叶结点?

答案: 2018, 如果题目问的是二叉树就是1010.

解析:

正常的树叶子节点最多显然2018个. 如果是二叉树, 为了保证叶子节点最多我们要使得每一个非叶子节点都有两个孩子. 显然, 一棵满二叉树满足这个条件.

对于一个2047个节点的满二叉树, 共有1024个叶子节点, 我们**“成对的”**删去其中的28个之后, 正好剩余2019个节点. 删掉了28个叶子节点后, 他们的父节点也就成为了新的叶子节点, 因此叶子节点减少了14个. 答案就是1024 - 14.

上述证明不严谨

5. 问题描述

一个正整数如果任何一个数位不大于右边相邻的数位,则称为一个数位递增的数,例如1135是一个数位递增的数,而1024不是一个数位递增的数。

给定正整数 n,请问在整数 1 至 n 中有多少个数位递增的数?

输入格式

输入的第一行包含一个整数 n。

输出格式

输出一行包含一个整数,表示答案。

样例输入

1
30

样例输出

1
26

评测用例规模与约定

对于 40% 的评测用例,1 <= n <= 1000。

对于 80% 的评测用例,1 <= n <= 100000。

对于所有评测用例,1 <= n <= 1000000。

题解:

暴力即可, 时间复杂度为 O(n * log10(n)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n = 0;
int ans = 0;
cin>>n;
for(int _ = 1; _ <= n; ++ _) {
int i = _;
int flag = 1;
int last = i % 10;
while(1){
i /= 10;
if(i == 0) {
break;
}
if(last >= i % 10) {
last = i % 10;
}else{
flag = 0;
break;
}
}
ans += flag;
}
cout<<ans<<endl;

6. 问题描述

小明对类似于 hello 这种单词非常感兴趣,这种单词可以正好分为四段,第一段由一个或多个辅音字母组成,第二段由一个或多个元音字母组成,第三段由一个或多个辅音字母组成,第四段由一个或多个元音字母组成。

给定一个单词,请判断这个单词是否也是这种单词,如果是请输出yes,否则请输出no。

元音字母包括 a, e, i, o, u,共五个,其他均为辅音字母。

输入格式

输入一行,包含一个单词,单词中只包含小写英文字母。

输出格式

输出答案,或者为yes,或者为no。

样例输入1

1
lanqiao

样例输出2

1
yes

样例输入1

1
world

样例输出2

1
no

解析

暴力即可, 时间复杂度O(n).

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
inline bool aeiou(char c) {
return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u';
}
int pos = 0;
int count = 0;
int size = str.size();
for (; pos < size; ++pos) {
if (!aeiou(str[pos])) {
count++;
} else {
break;
}
}
if (count == 0) {
cout << "no" << endl;
return 0;
}
count = 0;
for (; pos < size; ++pos) {
if (aeiou(str[pos])) {
count++;
} else {
break;
}
}
if (count == 0) {
cout << "no" << endl;
return 0;
}
count = 0;
for (; pos < size; ++pos) {
if (!aeiou(str[pos])) {
count++;
} else {
break;
}
}
if (count == 0) {
cout << "no" << endl;
return 0;
}
count = 0;
for (; pos < size; ++pos) {
if (aeiou(str[pos])) {
count++;
} else {
break;
}
}
if (count == 0) {
cout << "no" << endl;
return 0;
}
cout << "yes" << endl;

7. 问题描述

在数列 a[1], a[2], …, a[n] 中,如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k],则称 a[i], a[j], a[k] 为一组递增三元组,a[j]为递增三元组的中心。

给定一个数列,请问数列中有多少个元素可能是递增三元组的中心。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a[1], a[2], …, a[n],相邻的整数间用空格分隔,表示给定的数列。

输出格式

输出一行包含一个整数,表示答案。

样例输入

1
2
5
1 2 5 3 5

样例输出

1
2

样例说明

a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定

对于 50% 的评测用例,2 <= n <= 100,0 <= 数列中的数 <= 1000。

对于所有评测用例,2 <= n <= 1000,0 <= 数列中的数 <= 10000。

题解

乍一看1e5还以为不能暴力, 结果一看n的范围是1e3, 果断暴力走起, 复杂度O(n^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n = 0;
int data[1010] = {0};
cin>>n;
for(int i = 0; i < n; ++ i){
cin>>data[i];
}
int ans = 0;
for(int i = 0; i < n; ++ i) {
int flag = 0;
for(int j = i-1; j >= 0; -- j){
if(data[j] < data[i]){
flag += 1;
break;
}
}
for(int j = i+1; j < n; ++ j){
if(data[j] > data[i]){
flag += 1;
break;
}
}
ans += (flag == 2);
}
cout<<ans<<endl;
0%