我们知道，在状压dp中，存储状态时一般都要借助位操作。位操作是一种速度非常快的基本运算，包括左移、右移、与、或、异或、非等运算。左移 左移一位，相当于把某数乘$2$，比如$110_{(2)}$左移$1$位变成$1100_{(2)}\Leftrightarrow \ 6$变为$12$，表示为$110_{(2)}<<1=1100_{(2)}$。因此左移$x$位，相当于该数乘$2^x...
用两个集合，$s1$表示恰好有一个人教的科目集合，$s2$表示至少有两个人教的科目集合，而$d(i,s1,s2)$表示已经考虑了前$i$个人时的最小花费。注意，把所有人一起从$0$编号，则编号$0\sim m-1$是在职教师，$m\sim n+m-1$是应聘者。状态转移方程为$d_{i,s1,s2}\min\{d_{i+1,s1',s2'}+c_i,d_{i+1,s1',s2'}\}$，其中...
答案需要我们计算最小的卢布数，换句话说，我们需要最大化美元和欧元的总金额，而在如果已知其中任意一种的相应货币钱数，即可算出在总答案最大的情况下另外一种货币的钱数。所以我们可以枚举美元换取的钱数，同时算出相应的欧元钱数，选取总金额最大的方案即为答案。注意只能换取$5$的倍数的欧元，所以实际能换取的欧元钱数为剩余可换取欧元的钱数与它之差绝对值最小且不大于它的数。主程序代码如下：int main(...
将原序列中所有数进行处理，将当前处理的数计算所有它能变成的数以及变成那些数需要花费的最小次数，考虑如何最小化，只需将原序列从小到大依次处理即可。 代码如下：#include <algorithm> #include <cstdio> using namespace std; const int maxn = 55, maxm = 200005; int A[max...
首先我们想到$Polycarp$写下的数字一定是循环的，因此我们可以计算对于所有$m$，他写下的数字的循环节里包含数字的个数以及循环节所有数字的和。进行暴力打表或手算可以发现，$m(m>10)$上述结果和$m\% 10$的结果是如出一辙，因此我们只需打表出$0\leq m<10$的上述两个值，每次输入时计算$(n,m)$对应的所有循环节里数量的总和，再循环计算除去循环节以外其他写...