有\(n\)个电脑，\(m\)个插口，每个电脑有一个需求能量\(p_i(1 \leq p_i \leq 10^9)\)，每个插口有一个输出能量\(s_j(1 \leq s_j \leq 10^9)\)。当\(p_i=s_j\)时，电脑\(i\)和插口\(j\)可以相连。使用适配器可以将插口的输出能量减少至原来的一半（向上取整）。输出最多能使多少组电脑和插口配对，和此时使用适配器的数量的最小值。
用multiset存电脑。对于每个插口最多接\(\log n\)个适配器，从输出能量小的插口开始枚举安装适配器的个数看能否和电脑配对。
1 |
|
有\(n\)天，\(m\)个科目，给出每天可以考试的科目和考过一个科目之前需要复习的天数，输出最少多少天可以考过所有科目。
二分完成的天数，然后每个科目，如果有多个日期可以参与考试，选后面的日期考试，不会比选前面的更差。然后用扫描线检验一遍中途有没有复习时间不够的就好啦。
1 |
|
如图，给出在格点上的凸多边形，输出面积最大的边与坐标轴平行的矩形的面积。
首先，最大矩形的面积为矩形宽度的上凸函数。然后，对于指定宽度的矩形，矩形的面积为左边界的位置的上凸函数。给出指定的位置可以求出当前位置与多边形交点的\(y\)值。因此可以使用三分套三分套二分的方式解决这道题。
UVa 1679 - Easy Geometry和这个是同一道题，不过好像题的数据有问题，NEERC官方题解中tourist的代码也过不了。
1 |
|
有\(n\)个仓库，\(m\)个管理员，每个管理员有一个能力值\(p[i]\)，雇佣管理员的花费与能力值相同。一个仓库的安全度为\(p[i]/k\)，其中\(k\)为管理员管理仓库的个数，求最小安全度的最大值和此时的花费。
定义状态\(dp[i][j]\)为前\(i\)个管理员管理前\(j\)个仓库时的最小安全度的最大值。有\(dp[i][j]=\max\{\min\left(dp[i-1][j-k],p[i]/k\right)\}\)。求花费的方法与之类似。
1 |
|
有三个高度相同的观测点共线，两两之间距离相等，给出观测点间的距离\(d\)，三个观测点的高度\(h\)，观测时的仰角\(\alpha\)、\(\beta\)、\(\gamma\)，求火箭的高度。
设火箭高于观测点高度为\(x\)，火箭与三个观测点在平面上的投影分别为\(A\)、\(B\)、\(C\)、\(D\)。
易得
\[AB=\frac{x}{\tan{\alpha}},\space AD=\frac{x}{\tan{\beta}},\space AC=\frac{x}{\tan{\gamma}}, \space BC=2d\]
由中线定理得
\[AD=\frac{1}{2}\sqrt{2AB^2+2AC^2-BC^2}\]
带入得
\[4\left(\frac{x}{\tan{\beta}}\right)^2=2\left(\frac{x}{\tan{\alpha}}\right)^2+2\left(\frac{x}{\tan{\gamma}}\right)^2-4d^2\]
\[x^2\cdot\left(\frac{1}{\tan^2\alpha}+\frac{1}{\tan^2\gamma}-\frac{2}{\tan^2\beta}\right)=2d^2\]
解得
\[x=d\cdot\sqrt{\frac{2}{y}},\space y=\left(\frac{1}{\tan^2\alpha}+\frac{1}{\tan^2\gamma}-\frac{2}{\tan^2\beta}\right)\]
1 |
|
给出一个数独，其中0可以填1到9任意数字，‘e’只能填偶数，‘o’只能填奇数，其余字母相同字母的格子的数字必须相同。输出给出的数独有多少个解。
DLX基础题，注意限制。
1 |
|
给出\(n \times m\)的矩阵，每个矩阵中的数字都在\([1,p]\)，保证每个数字出现至少一次，\(p\)只出现1次。从\((1,1)\)出发，依次经过含有\(1\)到\(p\)，求最短路。
设\((i,j)\)包含的数字为\(x\)，一个显然的状态\(dp[i][j]\)表示经过了前\(x\)个数之后到\((i,j)\)点的最短路，可以从所有包含\(x-1\)的格子转移过来。设包含\(x\)的格子数为\(cnt[x]\)，每次转移的操作数为\(cnt[x]cnt[x-1]\)。但是直接这么做的复杂度最坏情况下达到了\(O(n^2m^2)\)并不能过。
所以我们加入暴力的方法，当\(cnt[x]cnt[x-1]>n*m\)时，直接用所有包含\(x-1\)的个子作为起点bfs，单次转移复杂度为\(O(nm)\)。
可以证明，最终复杂度为\(O(nm\sqrt{nm})\)。
复杂度证明：Codeforces Round #355 (Div. 2) Editorial
1 |
|
定义\(f(x)=Ax+B\)、\(g^{(0)}(x)=x\)、\(g^{(n)}(x)=g^{(n-1)}(x)\)。给出\(A\)、\(B\)、\(n\)、\(x\) \((1 \leq A,B,x \leq 10^9,1 \leq n \leq 10^{18})\)，求\(g^{(n)}(x)\)对\(10^9+7\)取模的值。
数据范围和题目形式很显然的就是矩阵题。
1 |
|
给出两个字符串\(s\)、\(t\)和整数\(k\)，在\(s\)、\(t\)中找出出现顺序相同的\(k\)段相同连续子串，输出\(k\)段子串最大长度和。
与最长公共子序列类似，定义状态\(dp[i][j][k][l]\)表示\(s\)匹配到了第\(i\)个字符、\(t\)匹配到了第\(j\)个字符，当前已经匹配了\(k\)段子串，\(l\)为0时代表最后一段子串停止匹配、为1时代表最后一段子串还在匹配。
1 |
|
一年有\(2^n(1 \leq n \leq 10^{18})\)天，有\(k(2 \leq k \leq 10^{18})\)个人，求至少两人生日相同的概率。
当\(k > 2^n\)时，\(p=1\)。
当\(k \leq 2^n\)时，有\[p=1-\frac{(2^n - 1)(2^n - 2) \cdots (2^ n - k + 1)}{2^{(k - 1)n}}=\frac{b-a}{b}\]
可以在\(O(\log k)\)的时间内求出\(\gcd(a,b)\)。
对于\(a\)，若\(k-1 > mod\)，则\(a=0\)。否则可以枚举求解。
1 |
|