在比赛结束后可以查看其他人的代码, 
这样的是可以查看, 若非绿色则对方没公开。
1 周一
1.1 A 链表应用
#include <iostream>
#include <list>
using namespace std;
/*
* 朴素想法是用数组存入小孩, 然后每次出列就遍历一下数组, 找满足条件的对应下标,
* 同时用另一个数组记录每个孩子是否以及出列的状态。最坏时间复杂度为 O(n^2)
* 该题这样写是能过的, 数据范围太小。
* 不过若数据范围 N >= 10000, 必须优化查找下一个出队元素的操作
* 既然我们要对数组进行删除操作（标记为出列时, 对于后续操作来说也算删除）, 也就是需要变动数组,
* 很显然有一个数据结构是线性, 且删除,增加的操作时间复杂度为O(1), 即链表
* 对于这样一个链表：
* 1 -> 2 -> 3 -> 4
* 想删除第二个元素时, 只需要让 1 跳过2, 指向3, 这样从一开始遍历时, 2就和被删除的效果是一样的：
* 1 -> 3 -> 4
* 而若数组想实现这个操作, 需要在经历一次遍历, 把2之后的数往前挪动一位
* 该题围成一圈, 可以让 最后一个元素也指向头元素, 这样从任意一点遍历都可以走完一圈。
*/
// 数组模拟链表
const int N = 100;
char e[N][16];
int ne[N], idx, head;
void init()
{
head = 0;
idx = 1;
ne[head] = 1;
}
void ArraySlove()
{
init();
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
scanf("%s", &e[idx]);
ne[idx] = idx + 1;
idx++;
}
ne[idx - 1] = 1; // 将尾结点连到头结点
// 遍历输出, 对-1按位取反的结果就是0, 故可以用 ~i 代替 i != -1
// for (int i = head; ~i; i = ne[i])
// cout << e[i] << endl;
int w, s;
scanf("%d,%d", &w, &s);
for (int i = w - 1, count = 0, res = 0;;)
{
if (res == n - 1) // 形成自环, 即只剩下一个元素
{
printf("%s\n", e[ne[i]]);
break;
}
if (count == s - 1)
{
int next = ne[i];
printf("%s\n", e[next]);
ne[i] = ne[next]; // 将下一个元素删去
count = 0;
res++;
continue;
}
else
{
i = ne[i];
count++;
}
}
return;
}
int main()
{
ArraySlove();
return 0;
}
1.2 B 状态模拟题
Edge浏览器支持右键翻译整个网页, 虽然不太准确, 不过相信你根据样例也能搞清楚这题什么意思。
给定一个整数和一个字符串, 整数代表有几个位置, 字符第一次出现表示占据一个位置, 第二次出现表示离开, 让出一个位置。
求最后有多少个字符第一次出现时没有位置。
用st数组表示当前字符的出现情况, 0为未出现, 1为出现过且当时有位置, -1为出现过且当时无位置。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 53; // 26个英文字母最多出现两次, 故最多为52个
char s[N];
int st[26]; // 表示当前字母是否出现。
int main()
{
int n;
while (cin >> n && n)
{
memset(st, 0, sizeof st);
cin >> s;
int cnt = 0, m = strlen(s); // cnt无法找到床位的人数
for (int i = 0; i < m; i++)
{
int t = s[i] - 'A'; // 将字符映射到对应的整数
// 为什么可以这样做是因为他们的ASCII码连续, 这种操作在以后的字符串处理很常用, 建议熟练掌握
if (!st[t] && !n) // 如果当前字符第一次出现, 且没床位
{
cnt++;
st[t] = -1; // 设成-1, 这样后面再来一个也不会处理
}
else if (!st[t] && n)
{
n--;
st[t] = 1;
}
else if (st[t] == 1)
n++;
}
if (!cnt)
cout << "All customers tanned successfully.\n";
else
cout << cnt << " customer(s) walked away.\n";
}
return 0;
}
1.3 C 队列应用
这题放到第一天确实有点超纲, 不过学完一周的你回来再看应该会很轻松。
题目要求模拟一个任务处理系统, 输入一系列任务, 从头开始依次处理, 若当前任务的优先级不是最高, 则将其放到末尾；若为最高则直接处理。
让求的是其中一个任务被处理完时经过了多少时间。
既然有从开头剔除元素, 有从末尾加入元素, 那么我们可以把这任务处理队列看成一个队列（废话
主要问题在于怎么判断当前任务是不是最高优先级。
很多同学都用的是最大堆来做啊（priority_queue 优先队列, 也就是堆）, 让它自行维护一个最大值。其实没必要, 我们并不需要向其中乱序加入一个元素, 所用到的功能也就剔除最大值, 然后求当前最大值.
可以先将优先级存在数组a中, 用idx代表当前的最高优先级, 把a数组从大到小排序, idx=0那么a[idx]就代表最大的优先级, 剔除一个元素后, 我们要找的是次大优先级, 而a已经是从大到小排序, 那么下一个元素a[idx+1]就是要找的次大元素。
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 5060, M = 110; // 若优先级呈严格递增序列, 那么第一遍会把前n-1项接到后面, 第二次会把 n-2项接到后面
// 故我们队列最多会使用 n + n-1 + n-2 + n-3 ... + 1 = n(n+1)/2
// 带入题目范围得 N = 5050, 这是最坏条件下使用的队列大小
// 而若使用STL库 #include <queue> 则不需要考虑大小问题。 不过有可能因为卡常数而TLE（不知道啥事卡常的自己百度:monocle_face:）
// 这样是有点浪费, 更好的解决方法是循环队列
int q[N], hh, tt; // 双端队列, 可以从队头hh加入/删除元素, 也可以从队尾tt加入/删除元素
int a[M]; // 将任务进行优先级排序
int n, m;
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
hh = 0, tt = -1; // 初始化队列, -1是因为加入元素用的是++tt
for (int i = 0; i < n; i++)
{
cin >> q[++tt];
a[i] = q[tt];
}
sort(a, a + n, greater<int>()); // sort函数第三个参数为指定排序方式,
// 默认为lower<int>(), 即从小到大排序, 这里的greater<int>()则为从大到小排序, 你也可以手写一个check()函数
int idx = 0, res = 0; // 当前的最高优先级为 a[idx], 等待时间为res
while (hh <= tt) // 若队列不为空
{
int t = q[hh++]; // 取当前队头元素并出队
if (t >= a[idx]) // 若大于当前最大优先级, 则可以出队并执行
{
if (hh - 1 == m) // 若当前下标为老师的计算任务, 则输出结果并退出循环
{
cout << res + 1 << endl;
break;
}
// 否则就res++, 继续循环
res++;
idx++; // 当前任务处理后, 处理次高优先级
}
else
{
if (hh - 1 == m) // 若当前下标为老师的计算任务, 且优先级低, 需要回到队尾
{
q[++tt] = t;
m = tt; // 将标识着老师任务的下标一并更新
} // 若不是则直接加即可
else
{
q[++tt] = t;
}
}
}
}
return 0;
}
2 周二
2.1 C 队列安排
假如该题只会插入到右边, 那么只需要一个ne就能解决, 但这里还会插入到左边, 因此需要知道该点之前的信息, 这是单链表无法提供的, 故这里需要使用双链表。
记得用st数组来标记已经被删除了的元素, 避免重复删除
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx;
bool st[N];
void init()
{
l[1] = 0; // 初始右节点
r[0] = 1; // 初始左节点
idx = 2;
}
void add(int i, int x) // 插入到编号为i的元素后面
{
e[idx] = x;
l[idx] = i; // 新加入的点的左端点编号为 i
r[idx] = r[i]; // 新加入的点的右端点编号为 r[i], 即i节点的右端点
l[r[i]] = idx; // i节点的右端点, 也就是新加入点的右端点, 将其左端点从i更新为x
r[i] = idx++;
}
void del(int x)
{
l[r[x]] = l[x];
r[l[x]] = r[x];
}
int main()
{
init();
int n;
cin >> n;
add(l[0], 1); // 把
for (int i = 2; i <= n; i++)
{
int k, p;
cin >> k >> p;
if (p)
add(k + 1, i);
else
add(l[k + 1], i);
}
cin >> n;
while (n--)
{
int x;
cin >> x;
if (!st[x])
del(x + 1);
st[x] = true;
}
// for (int i = 0; i < idx; i++)
// cout << l[i] << " " << r[i] << " " << e[i] << endl;
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << " ";
return 0;
}
3 周三
3.1 B 扩号匹配问题
每个左括号与距离最右边的括号匹配, 像这种匹配问题和计算表达式问题, 都是用栈来写。
当遇到左括号时, 将其下标入栈, 遇到右括号时, 将当前栈顶元素出栈。
那么遍历完后, 若栈中还剩下左括号, 就是无法匹配的左括号；若遇到右括号时栈空, 就是无法匹配的有括号。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 110;
char a[N];
char res[N];
int stack[N], top;
int main()
{
while (cin >> a)
{
top = -1;
int n = strlen(a);
for (int i = 0; i < n; i++)
{
res[i] = ' ';
if (top == -1 && a[i] == ')')
res[i] = '?';
else if (a[i] == '(')
stack[++top] = i;
else if (a[i] == ')')
top--;
}
for (int i = 0; i <= top; i++)
res[stack[i]] = '$';
cout << a << endl
<< res << endl;
}
return 0;
}
3.2 C 士兵队列训练问题
和周一A题有点像, 不过比那题更简单些, 不是环形了。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6e3;
int ne[N], e[N], idx, head;
int n, size;
bool flag = true;
int cnt;
void init()
{
head = -1;
idx = 1;
memset(ne, 0, sizeof ne);
memset(e, 0, sizeof e);
flag = true;
}
void add(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx++;
}
void del(int k) // 删除k+1项
{
ne[k] = ne[ne[k]];
}
bool check(int x)
{
if (flag)
{
if (x % 2 == 0)
return true;
}
else
{
if (x % 3 == 0)
return true;
}
return false;
}
int main()
{
int T;
cin >> T;
while (T--)
{
init();
cin >> n;
for (int i = n; i >= 1; i--) // 逆序存数, 这样枚举时便是正序
add(i);
int prev = head;
while (n > 3)
{
cnt = 1;
for (int i = head; ~i; prev = i, i = ne[i], cnt++)
{
if (check(cnt))
{
del(prev);
cnt = 0;
n--;
}
}
flag = !flag;
}
for (int i = head; ~i; i = ne[i])
cout << e[i] << " \n"[ne[i] == -1];
}
return 0;
}
4 周四
4.1 B 最小字典序字符串
题目概括一下是给一个串s, 提供两个空串t,u。通过一下两个操作：
- s的第一个字符移动到t末尾
- t的最后一个字符移动到u末尾
求出能得到的最小字典序。
贪心+栈的题目, 对于结果u串, 当前位置上的字符要么从s串中来, 要么从t串中来。
若u任意位置上的选择都是最小的, 那么总的字典序也是最小的
证明：
u1: ... ... ... a ... ...
u2: ... ... ... b ... ...
若 a 的字典序小于 b 的字典序, 那么根据字典序的定义, u1的字典序就小于u2的字典序。u1才是正确结果。
当前位置可以从s串和t串中来：
- 若s串存在能选的最小元素小于t串末尾, 则将其以及之前的字符都加入到t串, 并把该元素从t串末尾移到u串末尾
- 若大于等于, 则把t串末尾放到u串末尾
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
char s[N], u[N], t[N];
int top_u = -1, topt = -1;
char min_c[N];
int n;
int main()
{
cin >> s;
n = strlen(s);
min_c[n] = 'z';
for (int i = n - 1; i >= 0; i--)
min_c[i] = min(s[i], min_c[i + 1]);
for (int i = 0, j = 0; i < n; i = j)
{
if (topt == -1 || t[topt] > min_c[i])
{
for (j; s[j] != min_c[i] && j < n; j++)
t[++topt] = s[j];
u[++top_u] = min_c[i];
j++;
}
else
u[++top_u] = t[topt--];
}
while (topt != -1)
u[++top_u] = t[topt--];
cout << u << endl;
return 0;
}
5 周五
5.1 B Golden Sword
是一道单调队列优化的动态规划问题, 严重超纲了, 已让出题人改悔。
这题不必做。