幸运数字
一个很小朋友的做法是把每个数转二进制字符串或者用数组存下来判断。这里给一个时间复杂度为 $\mathcal O(n\log V)$ 但空间复杂度为 $\mathcal O(1)$ 的写法：使用位运算，通过 x >> i & 1 获得 $x$ 在二进制下的第 $i$ 位。
#include <bits/stdc++.h>
using namespace std;
int a, b;
int ans;
bool check(int x)
{
for (int i = 30; i >= 0; i--)
{
if ((i < 30 ? (x >> i + 1 & 1) ^ (x >> i & 1) : 1) && (i > 0 ? (x >> i & 1) ^ (x >> i - 1 & 1) : 1))
return 0;
}
return 1;
}
int main()
{
cin >> a >> b;
for (int i = a; i <= b; i++)
ans += check(i);
cout << ans << endl;
return 0;
}红绿灯
如果一个数应该亮的位置没亮，说明一定不亮。
如果一个数不该亮的位置亮了，说明一定常亮。
我们根据生活常识把每种灯应该点亮的位置存下来，对于这两种情况判断即可。
表格如下。请自行在程序内根据这个表格判断。
0: A B C D E F
1: B C
2: A B D E G
3: A B C D G
4: B C F G
5: A C D F G
6: A C D E F G
7: A B C
8: A B C D E F G
9: A B C D F G #include <bits/stdc++.h>
using namespace std;
vector<int> a[10];
int n;
string ans = "-------";
int main()
{
a[0] = {0, 1, 2, 3, 4, 5};
a[1] = {1, 2};
a[2] = {0, 1, 3, 4, 6};
a[3] = {0, 1, 2, 3, 6};
a[4] = {1, 2, 5, 6};
a[5] = {0, 2, 3, 5, 6};
a[6] = {0, 2, 3, 4, 5, 6};
a[7] = {0, 1, 2};
a[8] = {0, 1, 2, 3, 4, 5, 6};
a[9] = {0, 1, 2, 3, 5, 6};
cin >> n;
while (n--)
{
string s;
cin >> s;
int k = s[0] ^ '0';
for (int i = 1; i < s.size(); i++)
{
bool ok = 0;
for (int j : a[k])
if (j == s[i] - 'A')
ok = 1;
if (!ok)
ans[s[i] - 'A'] = 'X';
}
for (int j : a[k])
{
bool ok = 0;
for (int i = 1; i < s.size(); i++)
if (j == s[i] - 'A')
ok = 1;
if (!ok)
ans[j] = 'x';
}
}
cout << ans << endl;
return 0;
}间谍卫星
通过观察图片我们发现除了平行于坐标轴的正方形，其他的情况，一定存在一个编号最小的行，满足行内只有一个正方形的顶点。不妨钦定这个点，找到另外的和它在一条边上的另一个顶点计算边长。那么由于正方形的四个角都是直角，所以我们只需要找到编号最小的列，满足行内只有一个正方形的顶点，就可以了。证明显然。
接下来我们考虑怎么把这个代码写得更加优美：如果正方形边都垂直于坐标轴，那么就是找行里最右边的和列里最上面的。干脆直接特判也可以吧。
#include <bits/stdc++.h>
using namespace std;
const int n = 128;
string s[150];
void solve()
{
for (int i = 1; i <= n; i++)
cin >> s[i], s[i] = ' ' + s[i];
for (int i = 1; i <= n; i++)
{
for (int j = n; j >= 1; j--)
{
if (!(s[i][j] ^ '0'))
continue;
for (int y = 1; y <= n; y++)
{
for (int x = 1; x <= n; x++)
{
if (s[x][y] ^ '0')
return cout << sqrt((x - i) * (x - i) + (y - j) * (y - j)) << endl, void();
}
}
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}图灵完备
这个 $5000$ 的限制就很烦，否则我们可以构造一个 $1$ 然后拼在一起。
但是这启发我们，答案一定是用什么东西拼起来的。正常的什么二进制不行，因为本题没有乘法操作，只能加法凑。
但是我们根据已有的 JavaScript 语法经验或者单纯对于给出的字符组合，发现 +[] 返回一个 Number，[]+[] 返回一个 String。执行 +([]+[]) 对一个空字符串求值又得到了一个 $0$。也就是说，我们把 $n$ 的每一位用 String 表示出来拼接在一起，然后转成 Number 类型即可。一个 +!![] 就是 $1$，每一位最多拼接 $9$ 次。长度显然不会超过 $5000$。
Fun Fact：有一个为本题而生的网站 https://jsfuck.com/。也许下面的信息可以对于做这题给出一些启发。
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin >> s;
cout << "+(";
for (int i = 0; i < s.size(); i++)
{
if (i)
cout << "+";
s[i] ^= '0';
cout << "(";
for (int j = 1; j <= s[i]; j++)
cout << string("+!![]").substr(!(j >= 1));
cout << "+[])";
}
cout << ")";
cout << endl;
return 0;
}数据排序
码量一般的模拟。
把表头和学生信息以 , 为分隔符拎出来，存起来。由于（据我所知）不同类型数组不能开在一起，所以信息存的是 $3$ 个内容，分别表示为数还是字符串，以及数字的值和字符串的值。
排序部分，把排序方式先离线下来。比较两个元素时，按顺序遍历排序方式，判断升序降序，为数还是字符串，然后进行比较。
由于给定排序方法相同需要按照原顺序，所以多加一个 $id$ 用来判断全部一样时的先后顺序。
#include <bits/stdc++.h>
using namespace std;
int n, m, c;
string s, t;
int cnt;
string cmp[20];
string tt;
map<string, int> title;
struct node
{
bool op; // int 0 str 1
int x;
string y;
};
vector<node> a[120];
bool isstr(string s)
{
int cnt = 0;
for (char c : s)
if (isdigit(c))
cnt++;
return cnt < s.size();
}
bool ccmp(vector<node> a, vector<node> b)
{
for (int i = 1; i <= c; i++)
{
int op = cmp[i].back();
string t = cmp[i].substr(0, cmp[i].size() - 1);
int j = title[t];
if (op == '+')
{
if (!a[j].op)
{
if (a[j].x == b[j].x)
continue;
return a[j].x < b[j].x;
}
else
{
if (a[j].y == b[j].y)
continue;
return a[j].y < b[j].y;
}
}
else
{
if (!a[j].op)
{
if (a[j].x == b[j].x)
continue;
return a[j].x > b[j].x;
}
else
{
if (a[j].y == b[j].y)
continue;
return a[j].y > b[j].y;
}
}
}
return a[0].x < b[0].x;
}
int main()
{
cin >> n >> s;
tt = s;
s += ',';
for (int i = 0; i < s.size(); i++)
{
if (s[i] == ',')
{
title[t] = ++m;
t = "";
continue;
}
t += s[i];
}
for (int i = 1; i < n; i++)
{
a[i].resize(m + 20);
cin >> s;
s += ',';
t = "";
a[i][0].x = i;
int cnt = 0;
for (int j = 0; j < s.size(); j++)
{
if (s[j] == ',')
{
cnt++;
a[i][cnt].op = isstr(t);
if (!a[i][cnt].op)
a[i][cnt].x = stoi(t);
else
a[i][cnt].y = t;
t = "";
continue;
}
t += s[j];
}
}
cin >> c;
for (int i = 1; i <= c; i++)
cin >> cmp[i];
sort(a + 1, a + n, ccmp);
cout << tt << '\n';
for (int i = 1; i < n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!a[i][j].op)
cout << a[i][j].x;
else
cout << a[i][j].y;
putchar(j == m ? '\n' : ',');
}
}
return 0;
}AI 机器人
真神啊。不低于省选难度吧？
我们每一步移动的本质，其实是相当于有若干个一样的机器人在很多位置移动，按操作方法移动到了一个位置。最后答案就是这些机器人移动位置的交集。
然而我们发现，对于一个位置 $(x_1,y_1)$，这上面的机器人所能移动到的位置 $(x_2,y_2)$ 是固定的。因此可以用一个大小为 $(n\times m)\times (n\times m)$ 的 01 矩阵，$a_{i,j}$ 表示编号 $i$ 的点能否到达编号 $j$ 的点。我们这里需要把矩形空间压缩成线性空间，把一个点对映射成一个编号。
我们不妨对于 $\tt{U,L,D,R}$ 每种操作先处理出每种操作，所有位置经过操作时候能到达的位置。这是可以读入了这个矩形空间就能解决的。
接下来我们可以递归（或者用栈处理）这个表达式。
我们简单定义一下以后说到的操作：
- 矩阵乘法：此处为广义的。我们的矩阵由于维护的是是否可达，所以就是乘法改成做一个 bit_or 运算。也就是
c[i][j] = a[i][k] | b[k][j];。 - 矩阵加法：还是，广义……？其实表达成矩阵 bit_or 更合适，但是和上文有些重复，还是表述成矩阵加法吧。这里加法也改成 bit_or。也就是
c[i][j] = a[i][j] | b[i][j];。
众所周知，矩阵乘法可以算图上行走 $k$ 步的方案数。类比过来，这里的矩阵乘法可以让我们知道走 $k$ 步能到哪里。而这里的矩阵加法是用来合并路径的。
单次操作是简单的，我们把目前的操作得到的结果和目前这个单次操作做一个矩阵乘法即可。
带有括号不好处理。我们先来讲固定次数怎么做。
在我们已知括号内的操作时，直接循环这么多次，每次用已有操作序列做矩阵乘法，然后路径做一个矩阵加法。
星号同理，但是循环次数不唯一。我们可以发现，其实下面这组测试数据星号需要的循环次数会比较多。
10 10
..........
#########.
#########.
#########.
#########.
#########.
#########.
#########.
#########.
..........
(RD)*这样的话最坏情况就是 $(1,1)\to (1,n)\to(n,m)$ 得到 $18$ 的长度（第一个点默认走过）。
所以星号跑 $18$ 次，把结果全凑一起就行。
然而还构造出要跑更多次的数据，所以这个方法这个方法太菜了。我们可以做到更好的复杂度。
先对目前括号内的操作序列做一个传递闭包，相当于得到了每个点能前往的所有点。然后相当于对这个做一次行走即可。
那么接下来我们求出括号内操作序列即可。对于每个 ( 找到与之匹配的 )，递归搜出这两个中间的操作序列即可。
最后，这题矩阵运算有一个技巧。因为是 01 矩阵，可以用 bitset 优化，这样矩阵乘法复杂度就是 $\mathcal O(\frac{n^3}{w})$ 的。但是，又发现这题矩阵大小至多 $100\times 100$，可以用状压的思想把一行压成一个数。这样理论上针对这题的矩阵乘法复杂度就是 $\mathcal O(n^2)$。可以用 C++ 中的 __int128 储存。
这个方法甚至星号不是瓶颈，有界限的循环才是瓶颈。
时间复杂度 $\mathcal O(|s|(nm)^2k)$，其中 $k=9$。可以通过。并且不可能卡满，因此实际效率非常快。
#include <bits/stdc++.h>
using namespace std;
typedef array<__int128, 100> Matrix;
typedef pair<Matrix, Matrix> pMM;
int n, m;
char mp[10][10];
int id[10][10];
__int128 pw[100];
int N;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
inline bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
char to[100];
Matrix base[4];
Matrix ans;
inline void clear(Matrix &x)
{
for (int i = 0; i < N; i++)
x[i] = 0;
}
inline void build(Matrix &x)
{
for (int i = 0; i < N; i++)
x[i] |= pw[i];
}
Matrix operator|(const Matrix &x, const Matrix &y)
{
Matrix z;
clear(z);
for (int i = 0; i < N; i++)
z[i] = x[i] | y[i];
return z;
}
Matrix operator*(const Matrix &x, const Matrix &y)
{
Matrix z;
clear(z);
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
if (x[i] >> k & 1)
z[i] |= y[k];
return z;
}
Matrix &operator|=(Matrix &x, const Matrix &y) { return x = x | y; }
Matrix &operator*=(Matrix &x, const Matrix &y) { return x = x * y; }
string s;
pMM dfs(int l, int r) // [l, r)
{
Matrix opt;
clear(opt);
build(opt);
Matrix path;
clear(path);
build(path);
for (int i = l; i < r; i++)
{
if (isalpha(s[i]))
{
opt *= base[to[s[i]]];
path |= opt;
continue;
}
int cnt = 0;
int j = i;
while (j < r)
{
if (s[j] == '(')
cnt++;
if (s[j] == ')')
cnt--;
j++;
if (!cnt)
break;
}
auto [op, mp] = dfs(i + 1, j - 1);
if (s[j] == '*')
{
build(op);
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
if (op[x] >> y & 1)
op[x] |= op[y];
path |= opt * op * mp;
opt *= op;
}
else
{
for (int k = 0; k < (s[j] ^ '0'); k++)
{
path |= opt * mp;
opt *= op;
}
}
i = j;
}
return {opt, path};
}
int main()
{
to['R'] = 0, to['L'] = 1, to['D'] = 2, to['U'] = 3;
pw[0] = 1;
for (int i = 1; i < 100; i++)
pw[i] = pw[i - 1] << 1;
cin >> n >> m;
N = n * m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> mp[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
id[i][j] = i * m + j;
for (int i = 0; i < 4; i++)
{
for (int x = 0; x < n; x++)
{
for (int y = 0; y < m; y++)
{
int tx = x + dx[i];
int ty = y + dy[i];
base[i][id[x][y]] |= pw[in(tx, ty) && mp[tx][ty] == '.' ? id[tx][ty] : id[x][y]];
}
}
}
cin >> s;
ans = dfs(0, s.size()).second;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mp[i][j] == '#')
putchar('#');
else if (ans[0] >> id[i][j] & 1)
putchar('+');
else
putchar('.');
}
putchar('\n');
}
return 0;
}尾声
对于 p6 研究了很久，发现赛时通过的同学代码有误，特地写了份报告发给了 jyy 老师。
OI 之外还有一个很大的世界（但你们可能暂时理解不到这一层），这个活动更深层次的目的是能够通过一些测试数据看一看选手们的解题直觉，因此不必如此较真。
