0%

ArcSoft’s Office Rearrangement

Tags: 数学

我们令每一块的长度是$y$,则有$$ y = \frac{\sum_{i = 1}^{n} a_i}{K}$$

假设我们有$\sum a$个人站成一排,那么他们一定是在$p \mod y = 0$的位置$p$上被分开,而对于$p \mod y \neq 0$的位置,一定是合并的。对于每一个块$j$,我们算出前缀和
$$s = \sum_{i=1}^{j} a_i \mod y$$

然后呢,对于这一块前面的不被整除的部分要合并到前面一块去,中间完整整除的一些块就分成,剩下的最后多余出来的和后面合并就可以了。

总体复杂度:$O(n)$

Bomb

Tagso: 图论, 几何

建一个有向图,如果$d(u, v) \leq r_u$的话,就从$u$向$v$连条边。连完全部的边之后求出图的所有强连通分量,如果一个连通分量是有入边的,那么就说明这个分量中的所有点都是不需要点燃的(可以由入边的分量中任意一个爆炸来点燃它们),所以最后的答案就是对于每个入度为$0$的分量中的最小代价点求和。

总体复杂度:$O(n^2)$

Car

Tags: 贪心

由于速度是不断变大的,所以最后一段的时间为$1$的时候是最优的,对于相邻的两段,我们有
$$v_i \leq v_{i + 1}$$

稍稍做个转化,则变成了
$$\frac{l_i}{t_i} \leq \frac{l_{i + 1}}{t_{i + 1}}$$

然后做计算就可以了。

复杂度:$O(n)$

Difference

Tags: meet in middle

首先,我们有$11 \times 9^9 < 10^{10}$,我们可以得到$y$的范围是$y < 10^{10}$。我们假设$y = a \times 10^5 + b$,我们有$$f(y, K) = f(a, K) + f(b, K)]$$

做个简单的转化$$f(y, K) - y = f(a, K) - 10^5 \times a + f(b, K) - b$$

我们在$a \in [0, 10^5)$范围内枚举$f(a, K) - 10^5 \times a$的值,然后把它们扔进一个hash表里去,然后枚举$b \in [0, 10^5)$计算$x - (f(b, K) - b)$的值,然后去hash表里查下看看它们在不在就可以了。

总体复杂度:$O(5 \times 10^5)$

Equation

Tags: 分类讨论, 搜索

把这些等式分成三个大类

  1. 形如$1 + x = x + 1$, 这里$x \geq 1$,$x \leq 8$, 总共有$8$种不同的等式
  2. 形如$x + x = 2 \cdot x$, 这里$x \geq 2$,$x \leq 4$, 总共有$3$种不同的等式
  3. 形如$x + y = z$, 这里$x \neq 1$,$x < y$, 总共有$9$种不同的等式

对于第二类的每一种等式,我们有两种选择方法,不选这个等式,或者选了这个等式。而对于第三类的每一种等式,我们有三种选择,要么都不选,要么选了其中一种,要么两种都选了。对于第一类,我们可以暴力贪心计算出在选了第二类和第三类之后还可以最多构成多少种第一类的等式。

对于实现,可以搜索第二类和第三类,贪心第一类,或者状压之类的?

总体复杂度:$O(3^9 \times 2^3 \times 9)$

Four Operations

Tags: 暴力, 表达式求值

假设这个式子可以写成$$y = a + b - c \times d\ /\ e$$

对于式子中的后半部分$c \times d\ /\ e$, $c$和$d$应该只保留一位,让最后的答案最小。而对于$e$,它最多只会有两位,这是因为$c \times d < 100$并且,如果你用了三位让后半部分从一个一位数变成了$0$,还不如省下那一位让前半部分尽量大。

对于前半部分,$a$和$b$一定是一个一位数加一个多位数。所以我们只要枚举加号和除号的位置就可以定下来最后式子长什么样了。

总体复杂度:$O(2 \times 2 \times n)$

Game of Eliminate

Tags: 动态规划

我们设$a_i$为第$i$列的最高的*的高度,注意这里我们从底下开始,$1$开始标高度。定义状态
$$dp[i][j]$$
表示我们已经把第$i - 1$列和它之前的全部*部分消完,而第$i$列的没有消去的高度还有$j$的状态的最小开销,那么有状态转移方程$$dp[i + 1][\max(0, a_i - k)] = \min(dp[i][j] + \frac{j + k}{3})$$

这里$2 \times u + v = j$且$2 \times v + u = k$

转化一下
$$dp[i + 1][a_i - k] = \min(dp[i][j] + (j + k)\ /\ 3)$$

$$3 \times dp[i + 1][a_i - k] + (a_i - k) = 3 \times dp[i][j] + j + a_i$$

边界限制:$(j + k) \mod 3 = 0)且(\frac{j}{2} \leq k \leq 2 \times j$

用单调队列大概可以优化一波。

总体复杂度:$O(n \times m)$

Hazy String

Tags: 动态规划, 矩阵

由于字符串不能包含超过$1$长度的回文串,那么对于所有长度为$2$和$3$的子串,它们一定不是回文,而且这是个充要条件。那么对于一个位置$p$的字符,它的选择只和$p + k, -2 \leq k \leq 2$位置上的字符有关。

定义$m$是出现过的字符的数量,将它们标号为$0$到$m - 1$。定义状态
$$dp[i][j]$$
表示我们现在在考虑位置$p_i$并且$p_i - 1$上的字符是$j$,这里$j \in [0, m]$,$m$表示那些没出现过的字符,可以统一考虑。

对于两个位置之间的部分,假设我们在考虑一个子串
$$j,\ v_i,\ \cdots,\ x,\ y$$
由于每一个位置上的字符只和它的前两位有关系,我们定义一个状态
$$w(a, b)$$
表示$j,\ v_i$和$x,\ y$的关系,其中$a,\ b \in [0, 2]$,$a$表示$j$和$x$的关系,$b$表示$v_i$和$y$的关系。$a=0$表示$x=j$,$a=1$表示$x=v_i$,而$a=2$表示$x$和前面两个都不一样,$b$也是对应的表示状态。

我们可以构建出一个矩阵来做$p_i$到$p_{i + 1}$之间的转移,而$dp[i+1][k]$的值等价于$x=k$且$y = v_{i+1}$的时候的值。

总体复杂度:$O(n \times m + 7^3 \times n \lg L)$

Inequality

Tags: 数学

我们定义函数$b(i) = \min \sum_{k=1}^{i} x_k$,通过观察可以发现,它是一个关于$x_i$值的分段函数,而且每一段的值可以写成如下形式
$$u \times x + \frac{v}{x} + w$$
函数$b(i)$只有一个全局极小值,可以递推出$b(i)$关于$x_i$的每一段分段函数长什么样子,然后算出全局的极小值。

总体复杂度:$O(n^2)$

Just a Math Problem

Tags: 数论

定义$m = p_1^{r_1} \times p_2^{r_2} \times \cdots \times p_k^{r_k}$且$f(m) = k$

$g(m)$可以成满足$(x, y) = 1) and (x \times y = m$的数对$x$, $y$的数量。那么$\sum_{i}^{n} g(i)$就是满足$(x, y) = 1$且$x \times y \leq n$的数对的数量。

我们假设$x<y$,我们可以枚举$x$,容斥出$y$的数量(假设是$Y$),$y$满足条件$(x, y) = 1$且$1 \leq y \leq n$。对于枚举的$x$,答案是$Y - \phi(x)$。

总体复杂度:$O(\sqrt{n} \lg n)$

Kingdom of Obsession

Tags: 匹配, 数论

我们定义$b_i = s + i$,如果$b_i \leq n$,那么最优的做法一定是把它放在原来自己的位置上,这里可以反证一下,如果$b_i$放在了$p$上,而且$p < b_i$,我们一定可以把$b_i$和放在$p$上的另外一个比$b_i$大的数交换。

对于$b_i > n$的情况,如果这样的$b_i$中素数超过了$1$个,那么一定是无解的,因为素数只能放在自己的位置或者$1$上,而对于不超过一个素数的情况,这样的$b_i$的数量会非常少(姑且认为是$100$个最多了?),对于这些数,假设有$m$个的话,我们就让它们和$1$到$m$这些位置做匹配就可以了。

另外,给个贪心的反例:$n = 5, s = 11$。

总体复杂度:$O(m^3)$

If we use data binding through Angular2 and doing rendering on UI side, we may find that the MathJax text is not rendered. That’s because we need to re-render the string value every time we change it.

There is a simple module example to handle with, which use event handler binded and will be trigered when value changed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import {Directive, ElementRef, OnChanges, Input} from "@angular/core";

declare var MathJax: {
Hub: {
Queue: (param: Object[]) => void;
}
}

@Directive({selector: '[mathJax]'})
export class MJD implements OnChanges {

@Input("mathJax") private value: string = "";

constructor(private element: ElementRef) {}

ngOnChanges() {
this.element.nativeElement.innerHTML = this.value;
MathJax.Hub.Queue(["Typeset", MathJax.Hub, this.element.nativeElement]);
}
}

On the template HTML file, we can use this directive like this:

1
2
<div class="math-element" id="equation" [mathJax]="equationTexString">
</div>

On the other hand, remember add the MJD directive into the component directive list:

1
2
3
4
5
6
7
@Component({
selector: "equation-component",
directives: [MJD]
})
export class EquationComponent {
private equationTexString: string = "";
}

上周末UESTC校赛初赛,由于养老群里奇怪的爷爷一上来就开写这题还说挺好玩的,就看了下。

这是一个看上去是字符串的字符串题(雾

大致背景是说:给你一个长度为$200$的回文串$S$,一开始给你一个空串$T$,你可以选择$T$的一个位置,加一个特定的串$S$进去。比如说$S$是aba,那么做了两次操作之后,$T$就可能是aababa

现在给你串$T$,要你输出所有可能的$S$。

第一反应,枚举子串,用区间DP判断是否可行。首先$S$满足

  • 长度能被$T$的长度整除
  • 是一个回文
  • 是$T$的一个子串

根据这三点,可以得到一个结论,不同的$S$的个数最多只有$L$个,这里$L$是$T$的长度。

然后嘛,当时第一反应DP状态是这个样子的
$$dp[l][r]$$
表示区间$l$到$r$是否可行。

这样的状态,转移应该是
$$dp[l][r] = \bigvee_{\substack{l’ \leq l\\r’ \geq r}}dp[l’][r’]$$
这里$l’$到$l$还有$r$到$r’$这一段可以构成$S$。

对于转移,如果是暴力的话,DP的复杂度是$O(N^4)$的,总体复杂度是$O(N^5)$,内存的复杂是$O(N^2)$。

考虑到时间复杂度有点高(嗯,只是一点啦),考虑把把$S$的信息带到状态中去,我们定义状态
$$dp[l][r][i]$$
表示考虑到区间$(l, r)$,我们最左边已经匹配完了$S$的前$i$个字符的方法是否可行。那么转移就是
$$dp[l][r][i] = dp[l + 1][r][i + 1] \lor \bigvee_{r’ \geq r}\left(dp[l][r’][0] \land dp[r’ + k][r][0]\right)$$
其中,要么匹配$S$的当前位,要么把$S$剩下的用右边匹配掉,这里$k$是$S$剩下的长度,这样转移复杂度是$O(N)$的,总体复杂度是$O(N^3)$。

这样总体复杂还算可以了(不过会T的吧大概,我猜的(。

回忆下LCIS的DP,其实我们可以不需要枚举右边那段的位置,而让DP回来之后继续做$(r’, r’ + k)$区间的匹配。定义状态
$$dp[i][j][k]$$
表示我们还要匹配$i$个$S$串,现在在$T$的第$j$位,在$S$的第$k$位,这个状态是否可行。注意我们有一个很强的条件,就是第一维和第三维的大小之积正好是$N$。也就是说,这个状态是$O(N^2)$的。

这样,对于转移我们可以在$O(1)$时间内处理
$$dp[i][j][k] = dp[i][j - 1][k - 1] \lor \bigvee_{p}\left({dp[k][j][0] \land dp[i][j + p \times l][k]}\right)$$
其中$l$是$S$的长度,$p$是枚举的中间自匹配了多少个$S$,总体的转移是$O(\frac{L}{l})$的。

这样的话,整个DP的复杂度是$O(N^2 \times \frac{L}{l})$的,总体复杂度会小于$O(N^4)$?(根本不想分析复杂度。。。

Boxes and Balls

Tags: 数学

满足条件的球的数量一定是某个整数$m$对应的$\frac{m(m+1)}{2}$,所以我们要找到最大的值,使得
$$\frac{m(m+1)}{2} \leq N$$

第一种方法是直接解方程,直接解出以下方程的根
$$\frac{m(m+1)}{2} = N$$
然后在合适的精度范围内进行调整,得到正确的$m$。

另外一种方法是直接二分,找到最大满足条件的$m$,但是要注意二分检查的过程,不要超long long了。

Business Cycle

Tags: 杂题

二分答案,然后首先计算一圈的和的增量,如果增量是小于等于$0$的,直接模拟即可。

如果和增量大于$0$,模拟前两圈,然后计算循环节,然后检查最后一圈的答案。

细节比较多,需要仔细考虑。

Suffixes and Palindromes

Tags: 字符串 贪心 图论(伪)

将后缀排序和 Manacher 算法同时考虑,根据输入给的信息可以得到$A_i$和$A_j$的关系,是
$$A_i \geq A_j$$或者$$A_i > A_j$$
根据限制条件进行贪心或者差分约束。

Change

Tags: 搜索 暴力

这题网上大家表示很多人没注意到可以兑换多次(雾)。

对于每一个输入对$(A, B)$,你只要兑换一次($0.01$)或者两次($0.02$)就可以得到想要的钱。

用搜索或者DP去检查有没有可能不通过$B$或者任何和为$B$的组合得到$A - 0.01$,如果没有,说明$B$
是必需的,否则$A$兑换$B$就需要两次。

Colorful Floor

Tags: 组合数学

我们定义集合$X$的环基$C_n$,颜色的集合是$K$,那么有
$$\left|K^X/C_n\right| = \frac{1}{n}\sum_{i \mid n}\phi(i)\left|K\right|^{n/i}$$

接下来,我们把集合从$X$扩展到$X \times Y$,那么有
$$\left|K^{X \times Y}/C_n \times C_m\right| = \frac{1}{nm}\sum_{i \mid n}\phi(i)\phi(j)\left|K\right|^{\frac{nm}{lcm(i, j)}}$$

我们考虑一个群$G$的等价类,当一个等价类在一个置换$p$下,满足$\bar{x} \in K^X/G$时,我们有
$$p(\bar{x}) = \bar{x}$$

回忆下 Burnside 引理,
$$\left|K^X/G\right| = \frac{1}{|G|}\sum_{g \in G}\#\left\{x \in K^X \mid xg = x\right\}$$

扩展成我们二维的情况,就是:
$$\#\left\{\bar{x} \in K^X/G \mid p(\bar{x}) = \bar{x}\right\} = \frac{1}{|G|}\sum_{g \in G}\#\left\{x \in K^X \mid xg = px\right\}$$

我们假定$g = (g_1 g_2 \cdots g_k)(\cdots)\cdots(\cdots)$,$x = (c_1 c_2 \cdots c_k)(\cdots)\cdots(\cdots)$,根据条件$$xg = px$$

我们有$$p(c_1) = c_2, p(c_2) = c_3, \cdots, p(c_k) = c_1$$

对于任意的在环里的颜色$c$我们有$p^k(c) = c$。

所以我们的答案是
$$\frac{1}{nm}\sum_{\substack{i \mid n \ j \mid m}}\phi(i)\phi(j)K(i, j)^{\frac{nm}{lcm(i, j)}}$$

其中
$$K(i, j) = \#\left\{x \in K \mid p^{lcm(i, j)}(c) = c\right\}$$

Hungry Game of Ants

Tags: 动态规划

我们考虑将蚂蚁按开始的方向分类,我们会发现,如果一个蚂蚁是向左走,那么它左边一整段向右走的都会被它吃
掉,然后可以得到一个区间的和重量的蚂蚁,接下来,我们就考虑,再左边的那一整段的和,如果小于这一段的和,
就会被这一整段吃掉。

我们直接定义状态$dp[i]$表示考虑到第$i$只蚂蚁,那么,对于$i>k$的情况,我们需要它们被左边的吃掉,
所以有
$$dp[i] = \sum_{\substack{j \\ j(j+1) \geq i(i+1)/2}} dp[j]$$

对于$i=k$的情况,由于我们是从左向右递推的,所以我们要求第$k$只蚂蚁可以吃掉左边来的蚂蚁,所以有
$$dp[i] = \sum_{\substack{j \\ j(j+1) < i(i+1)/2}} dp[j]$$

对于$i<k$的情况,我们不需要考虑任何的条件,所以有
$$dp[i] = 2^i$$

最后的答案是$dp[n]$。

Legacy of Void

Tags: 动态规划 树分治

看心情后面补(挖坑)。。。

Open Face Chinese Poker

Tags: 动态规划 模拟

我们定义状态$dp[mask][i][j]$表示使用了$mask$这些卡(这是一个二进制的orbits),前三张卡的rank是
$i$(我们可以定义 High Card 的值是$0$,没有分数的值是$1$,剩下的有分数的从$2$递增,总共有
$24$种情况),中间5张卡的rank是$j$(除了没分数以为,剩下的递增,总共有$8$种情况)。

然后我们可以用枚举处理出$\binom{14}{5}$种rank,然后转移就好了。

Champions League

Tags: 动态规划

直接将$32$个国家做orbits定义状态$dp[mask]$然后按国家进行dp,用hash和BFS做记忆化和扩展。

比较重要的一点是,整个DP的过程是针对国家的,每一个level的队伍数量是固定的。

虽然状态看上去有$2^{32}$,实际上的状态数量是$\binom{8}{4}^4$。

Dome and Steles

Tags: 贪心

对于每个石碑,它可以放的最小的半径可以计算出来,是
$$r_i = \sqrt{\frac{max(a_i, b_i) ^ 2}{4} + min(a_i, b_j) ^ 2}$$

二分答案,对于每一个石碑我们可以得到它可以放的位置,比如说是区间$[-p_i, p_i]$,
其中$p_i = \sqrt{R^2 - r_i^2}$。

然后我们按$p_i$从大到小排序,贪心放在左边或者右边的位置。

Convex Polyhedron

Tags: 三维几何

首先,我们可以求出点集所表示的三维凸包对应的所有面,由于$n \leq 50$,所以我们可以在$O(n^4)$时间
内得到。

然后,我们通过$O(n^3)$枚举三个面,可以检查这三个面划分的$8$个子空间(可以通过$2^3$枚举法方向向
量得到空间的指示向量),我们可以知道面$C_1$,$C_2$,$\cdots$,$C_k$是通过这个子空间指示向量
正面看,可以看见的,那么从这个方向看到的最大面积是
$$\sum^{k}_{i = 1}{S_i \cdot \vec{n_i}}$$
其中$S_i$是面$C_i$的面积,$\vec{n_i}$是这个面的单位法向量。

得到的向量的长度之中最大的就是答案。

总体复杂度$O(n^4)$。

Multiplication Table

Tags: 数学

如果没有数字,答案是 Yes

如果只有一个数字,我们枚举这个数字的组合$X \times Y$,然后看这个table能不能被包含在乘法表中。

如果有多个数字,那么我们可以通过解方程的方法唯一确定table的位置,然后检查是否满足。

November 11th

Tags: 杂题

对于每一行单独处理。

最大值是两个人隔着坐,如果有一段连续的区间长度是$L$,那么最大值是
$\left\lfloor\frac{L}{2}\right\rfloor$。

最小值是一个人可以占连续的三个位置,那么最小值就是$\left\lceil\frac{L}{3}\right\rceil$。

之前在帮爹妈买火车票的时候,由于12306各种不稳定,买一次票还登出了4、5次,就特别狂躁。。。

在ubuntu下每个浏览器支持的证书是分开的,和windows上貌似是有区别的,于是,打开Firefox选 EditPreferences 下的 Advance Certificates 。打开Certificate list,选择 Authorities (这里,不知道为毛某度上的帖子全部都是选的Server,反正我导入Server certificate一点用都没有)。Import进来下载的官网证书,刷新网站就可以了(这里也不需要重启浏览器之类,还是比较赞的)。