zhangas

Pay more attention

0%

Posted on Edited on 
22年填报志愿时，是50190位次，本来也不够数学的位次，应该录取我的是50225的通信工程，
但是有了吴方班的出现使得普通班降了4000的位次。我很幸运遇到了一位21届从数学转出的学长，
使得从我入学的几天起我就暗暗下定决心转专业。今日写下这个建议，希望可以延续有想法的学弟学妹。

总结来说就是: 运气+绩点硬实力+c语言绝对水平

转专业文件分析

（1）高考综合改革省份学生须选考物理。其他省份考生须为理工类考生。
高考成绩在折算为 750 分后，须不低于该专业在山东省 2022年最低录取分数下 20 分。
考生需提供相应证明材料。

这个是硬要求，不满足直接就不能申请，因为面试前老师会让你打印当年的成绩查询成绩单。

（2）一年级考生申请转入我院各专业的，第一学期所学必修课程考试全部合格，无补考、重修记录，
且总成绩在原专业年级排名在 20%（含）以内（以报名时在教务系统中的排名为准）。

文件绩点要求只看大一上排名+大一下不挂科这一要求，原专业位次最好5%上下 低于10%有些危险(面试会看这个)；
学长当年是加权3.88 位次7.4% 也算是勉勉强强合格。

机考分析

申请转入我院的考生，须参加 C 语言机试，机试平台为我校 OJ平台，OJ 平台网址及机考要求在考试前公布。
该课程可通过我校网络教学平台上的《程序设计基础》慕课课程*进行自学，参考教材为《从问题到程序：程序
设计与 C 语言引论》（第 2 版）（裘宗燕，机械工业出版社，2011 年出版）。

机考的难度比外院的c语言期末高很多，但近似于计算机学院的c语言期末考试难度
建议多做OJ 上的题目，老实对待c语言课程，差不多可以30分钟做完外院的期末考试水平就够了。
最稳妥的是在机考2h内将所有题目做完 最多剩一道

面试分析

根据报名人数分为若干个面试小组，每个小组由 3—5 名教师组成。
面试满分为 100 分。面试成绩是面试小组各位专家评分的平均分。

注意: 面试的问题很基础，不会涉及专业课知识，只是简单问问你对本专业的认知和学习生活习惯,但是要老老实实准备，面试也会筛选人数。
牢记 计算机科学与工程学院——计算机科学与技术 提问的时候可能会要求辨析

运气

从21届降转的取消，再到22届分数线要求和18进6这一比例，这条道路的难度一目了然。在这条道路上，我很幸运，遇到了能够指引方向的学长，遇到了真正能帮助同学的老师们… 虽然新的一届大概率会增加新的要求，但希望真正有想法的学弟学妹们，能够攻坚克难，实现自己的内心想法。走过这条路会发现，新的道路已经开始。

2023.7.20记

Posted on

D - Delft Distance

难度：⭐⭐

类型： 图论

题意：

​ 你现在地图西北角，想去东南角的比赛地点。要到那里，必须穿过这座城市的历史中心。这座城市由$h*w$的建筑网格组成，不仅有方形的住宅建筑，还有一些圆形的中世纪塔楼。所有的方形建筑都以$10m$的边长轴线排列，所有的圆形塔的直径都是$10m$。在两座相邻的建筑之间有一条宽度可以忽略不计的小巷子。

​ 你需要找到一条从酒店到比赛地点的最短路径，输出从西北角到东南角的最短路径的长度，以米为单位。您的答案的绝对误差最多$1e^{-6}$

​ 数据范围：$h(1\le h\le 700)$，$w(1\le w\le700)$

模型

图1：样例1——红色的是最短路径

单源最短路径

image-20240807102258431
图2：建图所需的顶点

​ 并非地图上的所有点都需要建立，我们只需要建立每个方格对应上、下、左、右四个方向的结点，和结点之间的边，跑一次Dijkstra单源最短路即可。

解的表示

​ $double\space dist[N]$表示压缩后的结点，距离出发点的最短距离，跑完Dijkstra单源最短路后，右下角方格$(n, m)$对应下面和右边的点加上到终点的$5.0m$，即

$\pmb{min(dist[hashed(n, m, 2)],\space dist[hashed(n, m, 4)]) + 5.0}$就是我们的答案。

时间复杂度

​ 节点数$N=wh$，跑Dijkstra最短路需要$O(NlogN)$，复杂度为$O(whlog(wh))$

实现

id函数

​ 将$(x, y)$坐标压到一维，$D=(x - 1) * (2 * m + 1) + y$

hashed函数

​ 计算第$(i,j)$个建筑物，上下左右四个方向对应的坐标。$\pmb{f\in [1,2,3,4]}$分别对应上、下、左、右四个方向。

addall函数

对于当前的方格，无论是$’X’$还是$’O’$，都建立从四个顶点出发，到八个方向的有向边，长度均为$10m$。

direction

图3：四个顶点对应的八条有向边

addo函数

对于当前的所有$’O’$的方格，建立沿圆形$\frac{1}{4}$弧的边，长度均为$\frac{1}{4}2\pi*(10*\frac{1}{2})m$

image-20240807101428234

图4：'O'方格的两个圆弧的边

完整代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define PI acos(-1)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define PII pair<int, int>
// #define int long long
using namespace std;
const int N = 2e6 + 5;
int n, m;
int id(int x, int y)
{
    return (x - 1) * (2 * m + 1) + y;
}
int hashed(int x, int y, int f)
{
    if (f == 1)
    {
        return id((x - 1) * 2 + 1, y * 2);
    }
    else if (f == 2)
    {
        return id(x * 2 + 1, y * 2);
    }
    else if (f == 3)
    {
        return id(x * 2, (y - 1) * 2 + 1);
    }
    return id(x * 2, y * 2 + 1);
}

char s[1505][1505];
vector<pair<double, int>> g[N];
void addall(int x, int y)
{
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 1)});
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 3)});

    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 3)});

    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 1)});
    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 3)});

    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 3)});
}
void addo(int x, int y)
{
    double L = PI * 5.0 / 2.0;
    g[hashed(x, y, 1)].push_back({L, hashed(x, y, 4)});
    g[hashed(x, y, 3)].push_back({L, hashed(x, y, 2)});
}

int st[N];
double dist[N];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
double dijkstra()
{
    for (int i = 0; i < N; ++i)
        dist[i] = 2e9;
    dist[hashed(1, 1, 1)] = 5.0;
    dist[hashed(1, 1, 3)] = 5.0;
    q.push({5.0, hashed(1, 1, 1)});
    q.push({5.0, hashed(1, 1, 3)});
    while (q.size())
    {
        pair<double, int> t = q.top();
        q.pop();
        double distance = t.first;
        int u = t.second;
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = 0; i < g[u].size(); ++i)
        {
            int j = g[u][i].second;
            double d = g[u][i].first;
            if (dist[j] > dist[u] + d)
            {
                dist[j] = dist[u] + d;
                if (!st[j])
                {
                    q.push({dist[j], j});
                }
            }
        }
    }
    return min(dist[hashed(n, m, 2)], dist[hashed(n, m, 4)]) + 5.0;
}

void solves()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            addall(i, j);
            if (s[i][j] == 'O')
                addo(i, j);
        }
    printf("%.10lf", dijkstra());
}
signed main()
{
    IOS;
    int T = 1;
    // cin >> T;
    while (T--)
        solves();
}

Posted on Edited on

数据操作

1
2
3
4
5
6
7
8
9
10
11
12
13
import torch
import numpy as np
a = torch.arange(12)
a = a.reshape(3, 4)
b = torch.zeros((3, 4, 5))
torch.randn(3, 4)
print(a)
a[0:2, :]
b = a.numpy() # tensor张量转ndarray
type(b)
c = torch.tensor(b) # ndarray转tensor张量
type(c)

数据pandas读入处理

1
2
3
4
5
6
7
8
9
10
11
import pandas as pd
import torch
data = pd.read_csv("/content/sample_data/mnist_train_small.csv") # 读入csv
input, output = data.iloc[:, 0:2], data.iloc[:, 2:4]
print(input)
print(output)
print(type(input))
X = torch.tensor(input.to_numpy(dtype=int)) # DataFrame先转numpy再转tensor张量
Y = torch.tensor(output.to_numpy(dtype=int))
print(X)
print(Y)

线性代数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import torch
a = torch.arange(12)
a = a.reshape((2, 2, 3))
print(a)
print(a.shape)
b = torch.arange(16).reshape(4, 4)
print(b)
print(b.sum(axis=0)) # 每一列求和
print(b.sum(axis=1)) # 每一行求和
print(b.sum()) # 所有元素求和
c = torch.arange(1, 17).reshape(4, 4)
print(c)
print(b * c) # 对应元素相乘
print(sum(b * c)) # 每一列求和
print(b @ c) # 矩阵乘法
print(torch.mm(b, c)) # 矩阵乘法——运算速度快

torch.normal()

1
2
torch.normal(means, std, out=None)
返回一个张量，包含从给定参数means,std的离散正态分布中抽取随机数。 均值means是一个张量，包含每个输出元素相关的正态分布的均值。 std是一个张量，包含每个输出元素相关的正态分布的标准差。 均值和标准差的形状不须匹配，但每个张量的元素个数须相同。

CNN:卷积神经网络
RNN:循环神经网络

Posted on

并查集

P3367 【模板】并查集https://www.luogu.com.cn/problem/P3367
P1111 修复公路https://www.luogu.com.cn/problem/P1111
P1551 亲戚https://www.luogu.com.cn/problem/P1551
P2024 [NOI2001] 食物链https://www.luogu.com.cn/problem/P2024

树状数组

3374 【模板】树状数组 1 https://www.luogu.com.cn/problem/P3374
P3368 【模板】树状数组 2 https://www.luogu.com.cn/problem/P3368
P1908 逆序对https://www.luogu.com.cn/problem/P1908
P3655 不成熟的梦想家 (未熟 DREAMER)https://www.luogu.com.cn/problem/P3655

Posted on Edited on

请利用一个栈,将下面的代码改写成非递归版本

1
2
3
4
5
6
7
int ans = 0;
int play(int n){
    ans += n;
    if(n == 1 || n == 2) return;
    play(n - 1);
    play(n - 2);
}

参考

1
2
3
4
5
6
7
8
9
10
11
stack<int> stk;
int ans = 0;
stk.push(n);
while(stk.size()){
	int t = stk.top();
	ans += t;
	stk.pop();
	if(t == 1 || t == 2) continue;
	stk.push(t - 1);
	stk.push(t - 2);
}

P4387 【深基15.习9】验证栈序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
   void solve(){
int n = read();
for(int i = 1; i <= n; ++ i) a[i] = read();
for(int i = 1; i <= n; ++ i) b[i] = read();
stack<int> stk;
int idx = 1;
for(int i = 1; i <= n; ++ i){
	stk.push(a[i]);
	while(stk.size() && stk.top() == b[idx]){
		++ idx;
		stk.pop();
	}
}
if(stk.size() == 0){
	cout << "Yes" << endl;
}
else cout << "No" << endl;
   }

Posted on

Let’s first consider below simple question.

What is the minimun complexity to find n’th Fibonacci Number?

We can find n’th Fibonacci Number in O(log n) time using $Matrix\quad Exponentiation$. In this post, a general implementation of Matrix Exponentiation is discussed.

For solving the problem, we are assuming a linear recurrence eqution like below:
F(n) = a * F(n - 1) + b * F(n - 2) + c * F(n - 3) for n >= 3  ....Equation (1)
where a, b, c are constants.

For this recurrence relation, it depends on three previous value.
Now we will try to represent Equation(1) in terms of the matrix.
|F(n)|                    |F(n - 1)|
|F(n - 1)| = Matrix 'C' * |F(n - 2)|
|F(n - 2)|                |F(n - 3)|
Now we need to fill the Matrix 'C'.
so according to our equation.
             |a b c|
Matrix 'C' = |1 0 0|
             |0 1 0|
so for n, the equation(1) changes to 
|F(n)|                     |F(2)|
|F(n - 1)| = C ^ (n - 2) * |F(1)|
|F(n - 2)|                 |F(0)|
So we can simply multiply our matrix 'C' n - 2 times and the multiply it with the matrix below to get the result.
|F(2)|
|F(1)|
|F(0)|
Multiplication can be done in O(Log n) time using Divie and Conquer algorithm for fast power.
There is rough code below.


typedef struct Mat{
    int m[105][105];
}Mat;
Mat a;
Mat multiply(Mat x, Mat y){
    // Creating an new matrix to store elements 
    // of the multiplication matrix
    Mat c;
    for(int i = 1; i <= 3; ++ i){
        for(int j = 1; j <= 3; ++ j){
            c.m[i][j] = 0;
            for(int k = 1; k <= 3; ++ k)
                c.m[i][j] += x.m[i][k] * y.m[k][j];
        }
    }
    return c;
    // return the result
}
Mat Matrix_fastpow(Mat a, Mat k){
    //initial values for matrix 'C'
    Mat res;
    res.m[1][1] = a;res.m[1][2] = b;res.m[1][3] = c;
    res.m[2][1] = 1;res.m[2][2] = 0;res.m[2][3] = 0;
    res.m[3][1] = 0;res.m[3][2] = 1;res.m[3][3] = 0;

    while(k){
        if(k & 1){
            res = multiple(a, res);
        }
        k >>= 1;
        a = multiple(a, a);
    }
    return res;
}

Posted on

新建运动会

支持创建/ 删除运动会项目 且删除时需要输入管理员密码

设置运动会的地点、时间

输入比赛地点，运动会期间每一天上午、下午的开赛时间、结束时间

参赛人员分组

可以选择添加 本科组、研究生组、教职工组 每一个大组可以分为甲、乙两个小组 且每个组都分为男子组、女子组、混合组
大一默认为乙组，大二、三、四默认为甲组

支持导入修改代表队的简称及全称

①批量导入是按照每一行的顺序去填入表格，且代表队伍的简称和全程都可以有。
②直接人工填入表格。

为每一个竞赛组（格式为”本科A组男子”）去选择比赛项目

50m、100m…5000m的跨栏，短、长跑，障碍，仰卧起坐等等。
且支持新建插入自己设定的项目

运动员报名限制

①每一个学院的代表队可以在当前组最多报名人数
例如：体育学院代表队在本科A组里的所有项目中可以报名多少人
②每一个人限制最多报名多少项比赛
例如：体育学院的甲同学 最多报名两项比赛
我认为报名这里可以让学院的代表队里人数多一些，可以出现替补上场

竞赛组的比赛器材规格

例如：铅球的重量

名次录取排序和晋级方式

①预赛中多少队晋级多少队
②决赛中取前多少个队伍获得对应的奖牌

预赛、决赛的每组中的分道方式

①随机分道
②按照先前成绩分道

填入各项的项目记录

一级：校记录
二级：县记录
三级：市记录

（可选）按照比赛成绩去判定运动员的等级

少年级、三级、二级、一级、健将、国际健将。

设置计分的办法

七分制：前6名 7 5 4 3 2 1
九分制：前八名 9 7 6 5 4 3 2 1
名次分制度：可以自己为名次赋值
去给学院代表队统计集体分数
为照顾选手，可以选择在参赛并完成比赛的基础上添加基础分

Posted on Edited on

在PTA 上 L2-026 小字辈这样一道题中 因为STL 的不当使用，出现了段错误的问题，在仔细与李同学讨论后，发现了如下原因。题目链接

问题一 创建新队列实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
queue<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;
        queue<int> Q2;
        Q = Q2; // 创建一个新的队列来实现清空操作

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这种清空操作出现了问题，在于当前层的go( ) 函数只有return 后才会释放掉内存，但是一直往深度访问的时候，每一层开辟的新的queue的空间并没有被释放掉，因此造成了内存的堆积，产生爆栈。

问题二 借助deque自带的clear()函数来实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
deque<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q.clear(); // 会清空元素并不会释放掉内存

        Q.push_back(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push_back(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

自带的clear() 函数会清空元素并不会释放掉内存
而pop_back() 函数会将元素和内存一起释放掉

可以借助以下两个函数来验证

1
2
3
deque<int> Q;
Q.size(); // 元素的个数 相当于length 属性
Q.capacity(); // 最大容量（开辟的空间） 相当于queue_size 属性

以下有两种解决的方法

1. 手写清空函数

1
2
3
4
5
6
7
    void Queue_Clear()
{
    while(!Q.empty()){
        Q.pop();
    }
}

2. 在全局变量中多声明一个Queue 来进行辅助清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
queue<int> Q;
queue<int> Q2;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q = Q2; // 通过赋值来清空队列

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这样不会产生内存堆积的现象，解决问题。

Posted on Edited on

C.数组平均
游游拿到了一个大小为n的数组，数组第i个数为a_i。
游游可以选择一些元素，使得这些元素都等于它们的平均数。
eg.假设数组为 [5, 4, 2, 4]，游游选择第一个和第三个元素，最终数组将变成 [3.5, 4, 3.5,4]
游游最多可以选择k个元素，她希望最终数组最大值和最小值的差尽可能小。你能帮她求出这个差吗？

贪心+前缀和
可以发现选中的元素个数越多，数组的max - min 的差值越小，同时维护前缀和

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
double a[200005];
double b[200005];
void solve(){
    int n = read(), k = read();
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
    }
    // 这里需要排序，因为想要让极差小 就要对最小值和最大值操作
    sort(a + 1, a + 1 + n);

    for(int i = 1; i <= n; ++ i){
        b[i] = b[i - 1] + a[i];
    }
    double ans = 1e9;
    // i 枚举左侧选中的个数
    for(int i = 0; i <= k; ++ i){
        // j 枚举右侧选中的个数 
        int j = k - i;
        // 求左右两侧选中元素的平均值
        double ave = (b[i] + b[n] - b[n - j]) / k;

        //未选中的区间[i + 1, n - j] 此刻内部是有序的

        //计算这一情况的下的最小值和最大值
        double mi = min(a[i + 1], ave);
        double ma = max(a[n - j], ave);

        ans = min(ans, ma - mi);
    }
    printf("%.7lf", ans);
}

D.游游出游
游游准备去开车旅行，她初始在1号城市，准备前往n号城市。
游游打开了携程，她查询到了地图上有若干城市，城市之间有一些道路连接。每条道路有承重限制，当游游的车重量超过了承重时，她就不能走这条道路。游游是一个贪心的人，她希望总路程不超过h的前提下，携带尽可能多的物品出行。游游想知道，自己的车最多重量能达到多少？

二分 + dijkstra 二分最大的答案的同时 通过跑最短路

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
    typedef struct node{
	    int v, w, d;
        }node;
    void solve(){
	int n = read(), m = read(), h = read();
	vector<vector<node>> g(n + 1);
    vector<int> dist(n + 1);
    vector<int> st(n + 1);
    // 建边
	for(int i = 0; i < m; ++ i){
		int u = read(), v = read(), w = read(), d = read();
		g[u].push_back({v, w, d});
		g[v].push_back({u, w, d});
	}
	function<int(int)> check = [&](int mid) -> bool{
		priority_queue<PII, vector<PII>, greater<PII> > q;
		q.push({0, 1});
		for(int i = 1; i <= n; ++ i) st[i] = 0, dist[i] = 0x3f3f3f3f;
		dist[1] = 0;
		while(q.size()){
			PII t = q.top();
			q.pop();
			
			int distance = t.first, ver = t.second;
			if(st[ver]) continue;
			st[ver] = 1;
			
			for(node &it : g[ver]){
				// 如果质量超过路径的最大承重量
				if(mid > it.w){
					continue;
				}
                // 更新距离
				if(dist[it.v] > dist[ver] + it.d){
					dist[it.v] = dist[ver] + it.d;
					q.push({dist[it.v], it.v});
				}
			}
		}
        //必须满足路径和不超过 h
		return dist[n] <= h;
	};

    int l = 0, r = 1e9;
	while(l < r){
		int mid = l + r + 1 >> 1;
		if(check(mid)){
			l = mid;
		}
		else{
			r = mid - 1;
		}
	}
	if(!check(l)) cout << "-1";
	else cout << l;
}