前几天想要做一个开源航模接收机,于是去淘宝看了下无线模块,以前有了解过NRF24L01,于是就下单了三片,一片才8块钱,真的划算。

初体验

到手后才知道这玩意是SPI协议,以前也只是听说过,没有实际写过有关SPI的东西,都是串口用得多,我寻思着太莽了不合适,正好卖家有一个这玩意的调试器(说是调试器,其实就是用AT命令来控制),于是又下单了两个。

阅读全文 »

与时髦的应用层码农不同,我们这些嵌入式码农在写单片机程序的时候大多使用上古的Keil,不得不说,Keil确实好用,编译、调试都可以一键完成,但只提供Windows版本,而且界面还停留在上个世纪,也没有自动补全等现代IDE的功能。

自从前段时间换了MacBook Pro之后我就基本上用它来干活了,虚拟机跑Keil实在是得不偿失,更换嵌入式开发环境在所难免。

阅读全文 »

题目

Alice 和 Bob 在做游戏。有一个长度为\(n\)的正整数序列,Alice 先手,两人轮流操作。Alice 需要删掉一个非空连续子段,子段和为奇数;Bob 需要删掉一个非空连续子段,子段和为偶数。删除子段后左右两段拼接起来形成新的序列。不能操作的人输。如果两个人都足够聪明,那么谁会获胜?

题解

阅读全文 »

在写前端项目的时候总免不了要调用后端提供的接口,比如POST /user/login,比较传统的方法就是使用XHR。不过,ES6引入了Promise,ES7引入了async/await,使得我们可以更优雅地完成异步操作,于是axios隆重登场(其实我个人并没有用过axios)。

主要是受到张大佬的启发,通过

阅读全文 »

题目

给两段字符串\(A\)\(B\),输出\(A\)中所有出现\(B\)的位置。

题解

这题是老KMP了,不过还是说下怎么做吧不然太水了

其实KMP可以看成是一个状态机,按照模式串(也就是要匹配的字符串,这里是\(B\))建立状态转移,字符串作为输入。

理论上来说一个状态应该有多个转移方式,由当前状态(也就是匹配到的位置)和下一个字符来决定转移到哪个状态,但是为了方便,我们只取两种,即匹配成功和匹配失败,这样的简化与前面的那个方式基本上是等价的,这也就是next数组的由来,next[i]表示在第i位失配时模式串指针应该回退到的位置,而next数组本身的含义是“字符串的前缀与后缀相同的最大长度”,其中“前缀”指除了最后一个字符以外,一个字符串的全部头部组合,“后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

阅读全文 »

题目

输入\(n\)条有向边,确定是否能一笔画,如果能则输出最大的“起点*终点“,否则输出\(-1\)

题解

欧拉图模板题。

根据维基百科上的说法,一个连通的有向图有从\(u\)\(v\)欧拉路径的充要条件是\(u\)的出度比入度多1,\(v\)的入度比出度多1,其他节点出度等于入度,一个连通的有向图有欧拉回路的充要条件是所有节点的出度等于入度。

阅读全文 »

题目

UESTC-2430完全一致,数据量增大。

题解

我觉得没写啥的必要了,和UESTC-2430完全一致,加上二进制优化就行。

代码

AC代码

这是debug之后了的,注意到打开了OPTIMIZE宏。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0
#define OPTIMIZE 1

using namespace std;

class Thing {
public:
long long weight, value, number;
};

class Special {
public:
long long x, y, z;

long long getValue(long long weight) {
if (weight == 0) {
return max(0ll, z);
}
return x * weight * weight + y * weight + z;
}
};

Thing things[10007 * 15];
int cnt = 0;
Special specials[6];

long long dp0[10007];
long long dp[10007];

const int pow2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384};

# if OPTIMIZE

// 二进制优化
int optimize() {
int st = cnt;
int d = 0;
while (things[cnt].number > pow2[d]) {
things[cnt].number -= pow2[d];
// things[d + 1].number = 1;
things[cnt + d + 1].weight = things[cnt].weight * pow2[d];
things[cnt + d + 1].value = things[cnt].value * pow2[d];
d += 1;
}
things[cnt].weight = things[cnt].weight * things[cnt].number;
things[cnt].value = things[cnt].value * things[cnt].number;
// things[cnt].number = 1;
cnt += d + 1;
return st;
}

#endif

#if DISPLAY_A
int sp[1007];
#endif

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m, c;
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
cin >> things[cnt].weight >> things[cnt].value >> things[cnt].number;
// 多重背包
#if OPTIMIZE
// 二进制优化
optimize();
#else
for (int j = 1; j <= c; j++) {
// 不拿的情况(k=0)已经包含了
for (int k = 1; k <= things[cnt].number; k++) {
int weight = k * things[cnt].weight;
if (j < weight) {
break;
}
dp[j] = max(dp[j], dp0[j - weight] + things[cnt].value * k);
}
}
memcpy(dp0, dp, sizeof(long long) * (c + 3));
#endif
}
for (int i = 0; i < cnt; i++) {
for (int j = 1; j <= c; j++) {
if (j < things[i].weight) {
continue;
}
dp[j] = max(dp0[j], dp0[j - things[i].weight] + things[i].value);
}
memcpy(dp0, dp, sizeof(long long) * (c + 3));
}
for (int i = 1; i <= m; i++) {
cin >> specials[i].x >> specials[i].y >> specials[i].z;
// 计算神奇物品
for (int j = 0; j <= c; j++) {
for (int k = 0; k <= j; k++) {
#if DISPLAY_A
if (dp[j] < dp0[j - k] + specials[i].getValue(k)) {
dp[j] = dp0[j - k] + specials[i].getValue(k);
sp[i] = k;
}
#else
dp[j] = max(dp[j], dp0[j - k] + specials[i].getValue(k));
#endif
}
}
memcpy(dp0, dp, sizeof(long long) * (c + 3));
}
#if DISPLAY_A
for (int i = 1; i <= m; i++) {
cout << sp[i] << " ";
}
cout << endl;
#endif
cout << dp[c] << endl;
return 0;
}
阅读全文 »

题目

给任意一个字符串,求最少插入多少字符可以得到回文串。

题解

参照leetcode 1312

求该字符串与它的反序的最长公共子序列(LCS)长度,然后用字符串长度减去这个长度,输出答案完事,时间复杂度为字符串长度的平方。签到题。

代码

因为一发入魂,就没写测试例生成和暴力验证。

AC代码

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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 5e3 + 7;

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
string inv = s;
reverse(inv.begin(), inv.end());
// LCS
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == inv[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
cout << n - dp[n][n] << endl;
return 0;
}

题目

\(n\)种普通物品,第\(i\)种物品的体积为\(V_i\),价值\(W_i\),数量\(D_i\),有\(m\)件神奇物品,神奇物品的价值由分配的体积\(V_i\)决定,计算公式为 \[ W_i=x_iV_i^2+y_iV_i+z_i \] 给一个体积为\(C\)的背包,求最大价值。

题解

多重背包+泛化物品。

阅读全文 »

题目

UESTC-2428基本相同,区别在于只能相邻的两个进行交换,询问最少交换次数。

题解

有一说一,这题我没怎么搞懂,基本上全靠出题人的PPT。

这题比较直白了,直接就是\(1\sim 20\)的数字。继续使用状态压缩,变量\(s\)二进制表示状态,\(dp[s]\)表示状态\(s\)需要的最少交换次数,\(w[i][j]\)表示原排列i在j前面的对数,状态转移方程 \[ dp[s]=\min\{dp[s-(1<<i)]+\sum_{j\in s \&j\ne i}w[i][j]\} \] 显然\(dp[0]=0\)

阅读全文 »