背景 CUPOJ支持许多的语言进行编译并运行。当需要给判题机增加一个新的语言时，更改源代码内容、编译、测试、发布，整个过程需要频繁改动内部代码，这样破坏了开闭原则。 因此不妨使用动态链接库解决这个问题。 然而经过查询，动态链接库是不支持直接导出类型的。好在我们可以通过对基类的继承，在动态链接库的源代码暴露一个一个方法用于返回动态链接库提供的对象。 本文实现的方式基于如何在运行时加载C＋＋函数和类,这里提供一个将以上内容整合到CMake项目中的解决方案。 以CUP Online Judge Judger为例 CMak…
经过进一步的打磨，CUP Online Judge的判题机终于独立于前后端，可以作为一个后台服务在系统运行了。 考虑到判题过程强依赖操作系统环境，因此整个过程我也打了docker-compose包，不想看下面冗长的部署内容，直接使用的可以前往CUP Online Judge NG Docker Judger体验懒人部署的快感。 系统要求 Ubuntu 16.04 or above X86_64 CPU Node.js v10 or above 环境要求 预先准备好数据文件夹 部署 拉取后台服务代码: $ git c…
题解 由于给定序列，$o$的概率一定是1，$x$的概率一定是0. $?$的期望实际上是0.5 我们要求的是$E_{x^2}$,令$dp_i$代表到第i位时$E_{x^2i}$，$l_i$为到达$i$位置时的期望长度。根据上述条件，$o$时$l_i = l_{i-1} + 1$,$x$时$l_i = 0$,而$x$的时候$l_i = 0.5 \times (l_{i-1} + 1)$ 根据$l$，观察$E_i - E_{i-1}$,可以发现$x^2 - (x - 1)^2 = 2x + 1$ 因此$dp_i = dp…
题意 给定n和 a[i] b[i], 已知FWT(a[i]) * FWT(ans[i]) = FWT(b[i]),求ans[i] (XOR) 题解 FWT板题，赛后学习了一个 AC代码 #include <iostream> using namespace std; using ll = long long; ll MOD = 1e9+7; ll inv2; int n; const int maxn = (1 << 20) + 5; ll a[maxn],b[maxn]; ll qpow(…
题意 略 题解 由于这是一个不用维护原有序列的操作，我们可以考虑维护一个ST表进行RMQ查询。 这个RMQ是用来干什么呢？ 根据题目数据范围，我们知道这道题不能容忍$\mathcal O(n^2)$及以上的算法 我们必须要在$\mathcal O(nlogn)$的时间复杂度下完成所有的操作。 维护一个dp数组，$dp[cur] = dp[first_greater_than_cur] + 1$ 这个时候就需要我们用RMQ了。二分$[cur,n]$，找到第一个比当前元素大的元素的位置，这时dp值就可以加1. 贪心预处…
题解 注意 这和数独不一样，是要求子矩阵中每一行 或 每一列的字符只出现一次 这个问题坑了不少人 剩下的按照官方题解就完成 • 注意到52种字符，子矩形最多52行，52列。 • 一个5252nm的做法是显然的，可以优化到52*nm。 • 枚举上下边界(最多差52) • 当左端点确定后，右端点的范围是连续的一段，并且单调 • 扫一遍即可，可以使用位运算降低复杂度。 AC代码 #include <iostream> #include <vector> #include <algorithm…
题意 初始长度$2^n$的01序列，要从^&|中选择n个运算符。 • 序列长度:$(2^n)\to (2^{n-1})\to ... \to 16\to 8\to 4\to 2\to 1$。 • 问有多少个可能，使得运算后剩下的一个字符为1。 题解 事实上这道题暴力就是标准做法，但是dfs的过程一定是$3^n$的，会超出题目要求时间。我们必须考虑剪枝或者对小范围数据进行优化。 官方题解解答 • 暴力的复杂度是$3^n$的，只需要再优化一点点! • 如果剩下了$16$个变量，可能性只有$65536$个。 • …
题解 题目可以转化为插板法求解。考虑当$x + y + z <= k$时满足题意，引入一个$a$ 变成了$x + y + z + a = k$然后我们需要求的便是${k+3}\choose{3}$。 注意到题目的数据范围，可以用__int128解决问题。 AC代码 #include <iostream> #include <cstring> #include <algorithm> #include <cstdlib> #include <array>…
题解 利用数学方法中的“隔板法”，不难知道结果就是 $\displaystyle\sum_{k=0}^{n-1}{{n-1}\choose{k}}$ 这是二项式定理的展开式。所以，这道题就转换为求解$2^{n-1} \mod (10^9+7)$ AC代码 #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <array> using na…
