待补题，题目传送门
超级无敌水题
找是否有至少、连续三个相等
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void solve () {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n - 2; i++) {
if (a[i] == a[i + 1] && a[i] == a[i + 2]) {
cout << "Yes" << endl;
return;
}
}
cout << "No" << endl;
}
|
考 栈 的水题
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve () {
int q;
cin >> q;
stack<int> s;
for (int i = 1; i <= 100; i++)
s.push(0);
while (q--) {
int op, x;
cin >> op;
if (op == 2) {
cout << s.top() << endl;
s.pop();
}
else {
cin >> x;
s.push(x);
}
}
}
|
昏迷睡觉题目
# 题目大意
给定两个序列，分别有：n 个数和 m 个数
你可以从两个序列中取出若干个数，但是，在第一个序列取的数的个数必须大于等于在第二个序列中取的
问：总和最大是多少
# 解题思路
其实这题很简单，就是贪贪贪，把两个数列升序排列后，能取数只剩下这几种情况
a[i] >= 0 && b[i] >= 0 ：肯定是都取a[i] >= 0 && b[i] <= 0 ：此时只取 aia[i] <= 0 && b[i] >= 0 但 a[i] + b[i] >= 0 ：b 数组弥补了 a 数组负数的情况，那么也可以都取，总值还是增加的
但是一开始写的代码写抽象了，WA 了两个点
c++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
| int n, m, a[N], b[N];
bool cmp(int x, int y) {
return x > y;
}
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + n + 1, cmp), sort(b + 1, b + m + 1, cmp);
int res = 0, idx = 0;
while (a[idx] >= 0 && idx <= n)
res += a[idx++];
idx--;
int idxx = 0;
while (idxx <= m) {
if (idxx <= idx) {
if (b[idxx] >= 0)
res += b[idxx];
else
break;
}
else {
if (b[idxx] + a[idxx] >= 0)
res += (b[idxx] + a[idxx]);
else
break;
}
idxx++;
}
cout << res << endl;
}
|
改进后，可以变成 O(N⋅logN) 的复杂度
c++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
| int n, m, a[N], b[N];
bool cmp(int x, int y) {
return x > y;
}
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + n + 1, cmp), sort(b + 1, b + m + 1, cmp);
int res = 0;
for (int i = 1; i <= n; i++) {
int t = 0;
if (a[i] >= 0 && b[i] >= 0)
t = a[i] + b[i];
else if (a[i] >= 0 && b[i] <= 0)
t = a[i];
else if (a[i] <= 0 && b[i] >= 0 && b[i] + a[i] >= 0)
t = a[i] + b[i];
else
break;
if (t >= 0)
res += t;
}
cout << res << endl;
}
|
# 题目大意
给定无向图，每条边有一个值 wi，求从 1 点到 n 点的所有路径中，所有边权异或值最小的是？
- 2≤N≤
- N−1≤M≤2N(N−1)
- 1≤ui<vi≤
- 0≤wi<260
# 错解
想着类似最短路，于是想着用 Dijkstra，但是寄了
c++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
| int n, m, graph[20][20], d[20];
bool st[20];
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
d[i] = 1e18;
for (int j = 1; j <= n; j++)
graph[i][j] = 1e18;
}
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
graph[u][v] = graph[v][u] = w;
}
d[1] = 0;
while (true) {
int t = -1;
for (int i = 1; i <= n; i++)
if (!st[i] && (t == -1 || d[i] < d[t]))
t = i;
if (t == -1)
break;
st[t] = -1;
for (int i = 1; i <= n; i++) {
if (!st[i])
d[i] = min(d[i], d[t] ^ graph[t][i]);
}
}
cout << d[n] << endl;
}
|
# 正解
观察到，数据范围极小，为什么不用搜索呢？
c++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, m;
bool st[20];
vector<PII> graph[14];
int ans = LONG_LONG_MAX;
void dfs(int u, int res) {
if (u == n) {
ans = min(ans, res);
return;
}
for (auto t : graph[u]) {
int v = t.first, w = t.second;
if (st[v])
continue;
st[v] = 1;
dfs(v, res ^ w);
st[v] = 0;
}
}
|
有一个细节需要注意，1e18 还是不够大，得用 LONG_LONG_MAX
# 题目大意
给定两个整数 n,m 和三个长度为 m 的整数序列 X=(x1,...,xm), Y=(y1,...,ym), Z=(z1,...,zm)
请你构造一个长度为 n 的A 序列，满足对 i∈[1,m] 均有，Axi XOR Ayi=xi
找出满足这样性质的，i=1∑nAi 最小的序列
# 题解
有丶难了，传送门
