Leo's blog

建议麦当劳

TL;DR::memory:为每个链接打开一个新的数据库.
使用 file::memory:?cache=shared 也可能碰到问题,配置 MaxOpenConnection1即可. (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.问题描述

12019中,有多少个数的数位中包含数字9

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

答案提交

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

4.问题描述

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

答案提交

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

5.问题描述

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

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

输入格式

输入的第一行包含一个整数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+1a[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.问题描述

小明有一块空地,他将这块空地划分为nm列的小块,每行和每列的长度都为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.12019中,有多少个数的数位中包含数字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,请问在整数1n中有多少个数位递增的数?

输入格式

输入的第一行包含一个整数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+1a[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%