Aaron Lee's Blog
0%

置顶 | 发表于
本文字数： 143 阅读时长 ≈ 1 分钟 
欢迎来到Aaron Lee的博客！
在这里，我会分享一些我学习过程的笔记以及分享一些关于计算机的知识
如果发现什么错误欢迎各位指出，大家共同进步！

每一个人就像一帆小船，学习就是小船前进的动力，当你离开自己的舒适圈才会发现自己想要的星辰大海

Alt Text

学无止境！
Learning knows no bounds!

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

  • content

    • 语言的定义
      • 语法定义
      • 语意定义
    • 文法
    • 语言设计

语言的定义

G=（N，T，P，S）
N：非终结式集合
T：终结式集合

文法

G=（Vt,Vn,S,P）
Vt是终结符集合
Vn是非终结符集合

一、文法

文法： 描述语言的语法结构的形式规则

学习文法主要是认识终结符和非终结符：其实这个特别简单，示例：
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
其中大写字母为非终结符，小写字母为终结符。两者组合可以构成一个式子。

二、文法的类型

文法定义的形式-四元组（Vn,Vt,P,S）: Vn为非终结符集，Vt 为终结符集，P为规则集，S为识别符|开始符，至少要在一个规则中作为左部出现，Vn ∩ Vt = ∅。根据对文法施加不同的限制，分成4种类型。

0型或短语文法：

产生式形如：α->β
其中：α、β属于字符串的闭包区间内且α至少包含有一个非终结符；解释：左边有非终结符，右边有终结符。举例：A->ab， A->Cb， A->b
0型文法是这几个文法中，限制最少的一个，一般见到的文法都可看做0型文法。0型文法的能力相当于图灵机（Turing）。

1型文法：又称为上下文有关文法：

产生式形如：α->β
其中：α->β均满足|α|<=|β|, 除了α->ε外；解释：式子左边可以有多个字符，但必须有一个非终结符；式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符且左边长度必须小于右边（例外）举例：A->B，A->Bba ，Bb->A，

2型文法：又称为上下文无关文法：

产生式形如： A ->β
解释：式子左边必须是非终结符，然而一个终结符一个非终结符的组合不是一个非终结符，如Ab不是一个非终结符，但是两个非终结符的组合就是一个非终结符了，如AB就是行了；式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符举例：AB->abc，B->ab

3型文法：又称为正规文法（正规文法又包括左线性文法和右线性文法）：

右线性文法：

产生式形如： A ->αB 或 A ->α

解释：式子左边只能有一个字符，而且必须是非终结符；式子右边最多有二个字符。如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。举例：B->aB

左线性文法：

产生式形如： A ->Bα 或 A ->α
解释：式子左边只能有一个字符，而且必须是非终结符；式子右边最多有二个字符。如果有二个字符必须是（非终结符+终结符）的格式，如果是一个字符，那么必须是终结符。举例：B->Ba
注意：式子右边的格式一定要一致。也就是说如果有一个是（终结符+非终结符）那么所有的式子都必须是（终结符+非终结符）， 如果有一个是（非终结符+终结符），那么所有的式子都必须是（非终结符+终结符）

四种类型文法描述能力比较：0型>1型>2型>3型文法

举例：判断 B−>Ab|a、 A−>ε|aB

属于那种文法。

1、我们分开来写，应该是：A->e A->aB B->Ab B->a
2、我们先来判断是否符合0型文法：0型文法规定左边必须有非终结符，那么这些都是符合的。
3、我们再来看是否符合1型文法：1型文法规定从小推到大。也符合。
4、我们再来看是否符合2型文法：2型文法规定左边必须是非终结符，也满足。
5、我们继续看是否符合3型文法：规定只能符合右线性或者左线性，那么前面一个应该是符合右线性的，后面一个是符合左线性的。所以综合起来就不符合3型文法了。得出结论：那么这个题目属于2型文法。

短语

  • 一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语。
    ![[Pasted image 20240409201203.png]]

直接短语

  • 当子树不包含其他更小的子树时，该子树叶节点所组成的字符串就是该句型的直接短语。

  • 短语包含直接短语，我们可以直接在短语中判断。

    • 这里只有第五层的S和第三层的L不包含其他更下的子树，所以有a和S是直接短语。
    • 其中(a)的父节点S包含L，S,(a)的父节点L包含L和S， (S,(a))的父节点S包含L

判断句柄

句柄是最左边的直接短语。

因为S处于最左边，所以S是直接短语。

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

【TiTle】

身为全电大最聪明的猫，菜猫他有 $n$ 个不同水杯，为了方便喝水，菜猫给第 $i$ 号水杯里面盛上i毫升水。

【Content】

有一天，猫口渴了。他决定喝一些水来解渴。因为活得太久，喝水在猫看来也应该是一种艺术，不同的水杯里的水一起喝可口程度不同。所以他决定在他的 $n$ 个水杯中挑出可口度最大的 $k$ 个水杯来喝水。这 $k$ 个水杯的可口度是他们的盛水量的最大公约数。

【Standard Input】

两个空格分开的正整数 $n$ 和 $k$。

【Standard Output】

一个整数，为最大的可口度。

输入样例

4 2

输出样例

2

【样例解释】

菜猫一共有 $4$ 个杯子，里面分别装了 $1$ mL，$2$ mL，$3$ mL 和 $4$ mL 水，现在要挑出两杯水，使得这些水的毫升数的最大公约数最大。可以挑选$2$ mL和 $4$ mL，这样最大公约数为 $2$，最为可口。但假如挑选的是 $1$ mL 和 $3$ mL，最大公约数仅为 $1$，不是很可口。所以可口度最大为 $2$.
对于 100% 的数据，$k$，$n$ $\leq$ $2\cdot 10^9$

【示例代码】

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
55
56
57

#include<bits/stdc++.h>
using namespace std;
const int mo = 1e9+7,maxn = 12;
int n,col[3],cha[3] = {0},id = 0,has[99][99],m,cnt = 0,tot1[999],tot2[999];
char a[maxn + 1],b[maxn + 1],t;
struct node{
    long long v[80][80];
}nil,ans,f;
node operator * (node a,node b){
    node c = nil;
    long long t ;
    for (int i = 0 ; i <= id; ++i)
        for (int j = 0 ; j <= id ; ++j){
            t = 0;
            for (int k = 0 ; k <= id ; ++k) t = (t + a.v[i][k] * b.v[k][j]) % mo;
            c.v[i][j] = t;
        }
    return c;
}
int main(){
    scanf("%s%s",a,b);  n = strlen(a);
    for (int i = 0 ; i < 3 ; ++i) scanf("%d",&col[i]);
    scanf("%d",&m);
    for (int i = 0 ; i < n ; ++i){
        cha[(b[i] - a[i] + 3) % 3] ++;
        t = a[i];
        while (t != b[i]){
            ++cnt; m -= col[t - 'a'];
            ++t;
            if (t > 'c') t -= 3;
        }
    }
    if (m < 0){puts("0"); return 0;}
    m = m / (col[0] + col[1] + col[2]) * 3 + cnt;
    
    for (int i = 0 ; i <= n ; ++i)
        for (int j = 0 ; i + j <= n ; ++j){
            has[i][j] = ++id;
            tot1[id] = i;
            tot2[id] = j;
        }
    memset(nil.v,0,sizeof(nil.v));
    ans = f = nil;
    ans.v[ has[cha[1]][cha[2]] ][0] = 1;
    int x,y;
    for (int i = 1 ; i <= id ; ++i){
        x = tot1[i]; y = tot2[i];
        if (n - x - y) f.v[i][has[x + 1][y]] = x + 1;
        if (x) f.v[i][has[x - 1][y + 1]] = y + 1;
        if (y) f.v[i][has[x][y - 1]] = n - x - y + 1;
    }
    f.v[0][0] = 1; f.v[0][1] = 1;
    for (;m;m>>=1,f=f*f) if (m &1) ans = f * ans;
    cout<<(ans.v[0][0] + ans.v[1][0]) % mo; 
    return 0;
}

发表于 更新于 分类于
本文字数： 193 阅读时长 ≈ 1 分钟

什么是CNN卷积神经网络？

卷积神经网络（Convolutional Neural Networks, CNN）这个概念的提出可以追溯到二十世纪80~90年代，但是有那么一段时间这个概念被“雪藏”了，因为当时的硬件和软件技术比较落后，而随着各种深度学习理论相继被提出以及数值计算设备的高速发展，卷积神经网络得到了快速发展。那究竟什么是卷积神经网络呢？以手写数字识别为例，整个识别的过程如下所示：

picture error