题目HERE

题目大意

给你

a1 个1

a2 个2

a8 个8

求用这些数中的一部分相加,得到的 最大的 不大于W的 数为多少

其中

1<=ai<=10^16

0<=W<=10^18

解法

翻译自官方题解

假设在未知的最优解中 i 取c_i

L = lcm(1,,,,8) = 840

那么c_i可以表示为

c_i= (L/i)*P_i+q_i 根据除法余数性质可以让q满足 0<=q<L/i

(L/i)*P_i个i是L的倍数(且是1,2,3,4…倍 占满)(小学未知数乘法?)

所以只用枚举q_i的部分

然而这样 所有方案840**8/8/7/6/5/4/3/2/1=6147715553280000000时间内肯定过不了

dp[1->x types of items][weight] = 把构成weight的部分去除后 还能最多有多少个L 这里的构成

空间O(8*8L)

时间O(8L*sum(L/1+L/2+...+L/8))

ans = max{ weight + L * min(dp[0][weight],(W-j)/L) (0<=weight<=8L)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

const int N = 9;
const int L = 840;

typedef long long li;

li dp[N][L * N];
li W;
li cnt[N];

int main()
{
cin >> W;
for(int i = 0; i < 8; i++)
cin >> cnt[i];
for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
dp[0][0] = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < L * N; j++)
{
if(dp[i][j] == -1) continue;
int b = L / (i + 1);
if(cnt[i] < b)
b = cnt[i];
for(int k = 0; k <= b; k++)
{
li& d = dp[i + 1][j + k * (i + 1)];
d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
}
}
}
li ans = 0;
for(int j = 0; j < L * N; j++)
{
if(j > W || dp[8][j] == -1)
continue;
ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
}
cout << ans << endl;
}

C

题目HERE

题目大意

n 个点 (1<=n<=100000)

m 条边 (1<=m<=100000)

有向图

从端点1出发,总共走d (1<=d<=50)天,每天能走一条边,能访问多少个不同的开放的点

开放时间表 n*d,0表示N号点 在D天关闭,1表示开放

解法

翻译自官方题解

新建一个图

图上的点为 ([1->n],[0->d-1]) O(nd)

如果原来题目图上有(u,v)

建立边 (u,t) -> (v,(t+1)%d) , O(m d d)

然后算 新图 的强连通分量,对每一个强连通分量缩点,计算 不同的开放的点的个数 = cost

在新的DAG上求最长路

假设一个点u 在新图中拆成 (u,j1)和(u,j2),也就是u 能通过某些边走到j1,注意到,新图里的边只和原图是否连通有关,所以 (u,j2) 能走到(u,(j2+(j2-j1))%d) 沿着j1->j2的路径,沿着这条路径走d-1次,那么走到(u,(j2+(d-1)(j2-j1))%d) = (u,j1+d*(j2-j1)%d) = (u,j1) 所以如果(u,j1)和(u,j2)弱连通,则它们强连通

在新的DAG(缩点后的)上 不会存在2个 u

在DAG有向无环图上 做dp

代码

待补

D

题目HERE

题目大意

交互题

1<= t,c,(t+c)<=1000

有一条链表,这个链表上有一个环,其中环的部分长度为c,非环的部分长度为t

从非环的部分开始走,目的地是 环和非环的交界处,也就是环的入口(环上)

不知道t和c

一共有10个单位可以用来走

交互次数应当<=3(t+c)

交互:

每次提供 需要移动的单位列表,比如2 4 5,那么意味着 2号 4号 5号 沿着链表跳向下一个节点

每次操作返回 哪些单位在同一个点上,如129 3745 680 表示,1号2号9号在一个点上,3.7.4.5在一个点上..

当你认为所有点都走到入口上的时候,输出done

解法

分成 甲 乙 丙

甲1步
乙2步

t步,乙2*t步在环上,变成环上追击问题,距离为 (c-(2t-t)%c)%c = (c-t%c)%c

然后,甲乙丙,都走1步

当丙进入环时,步数为t

甲和乙相遇后一起走,所以位置相同,甲的步数这时候为 (t+ (c-t%c)%c)+t

注意到(t+ (c-t%c)%c)是c的倍数,也就是,丙刚进入时,甲和乙也同时走到了环的入口

总耗时2(t+(c-t%c)%c)+t = 3t + 2(c-t%c)%c < 3t+3c = 3(t+c)

解了

题目HERE

题目大意给

01串 长度<=100

每次可以任选一段连续的相同数字的串删掉,删掉的代价为cost[长度],删掉后 原来的串两端相连,求这样操作直到删空,cost和的最大值

如 0011100 删掉中间连续3个1 变成0000,并且获得cost[3]

样例

1
2
3
7
1101001
3 4 9 100 1 2 3

输出109

1101001 → 111001 → 11101 → 1111 → ∅.

解法

状态 dp[开始index][结束index(不包括)][?->开始index 相同的数字的长度len]

[开始index,结束index)且开始的左边还有 len-1个和s[开始index]相同的数字

状态转移

dp[start][end][len] = max(A[len]+dp[start+1][end][1],max(dp[start+1][itr][1]+dp[itr][end][len+1])), 其中s[itr] == s[start]

举例解释

1
2
3
4
5
6
11111100001111011
yyyy
s e
i
4=len
xxxxxx

上面假设在求 dp[s][e][len]

那么A[len]+dp[s+1][end][1]表示先一次处理掉yyyy对应部分 再处理s以后的部分

那么dp[s+1][i][1]表示把xxxxx对应部分处理掉的代价,dp[i][e][len+1]表示的是 处理掉xxxxx这部分后,在处理剩余部分的代价

所以最终,答案就是dp[0][N][1]

状态O(n^3)状态转移O(N)所以总时间复杂度 O(N^4)

code

题目HERE

求一个n x m <= 300 000的二维字符数组

满足任何2x2的字符都包含A T G C

并且和给你的 数组不同的字符尽量少

我的思路

我有发现如果已经有

1
2
AG
TC

那么右侧一列,一定是AT,顺序不定

下面两个一定是AG顺序不定,


又发现如果对于任意2*3

1
2
XYZ
???

如果XYZ出现了3个字母

那么???下方的一定是XYZ且顺序不变

因为如果Y不在中间,那么会变成

1
2
3
XYZ
???
Y?Y

第3行填X 或 Z都是不行的


又发现2x3如果XYZ 3个字母不同,具有性质,

1
2
XYZ
???

下面的??? 是确定的,因为X列和Z列是相等的,所以一定是,其中O表示第4个字母

1
2
XYZ
ZOX

然后我就现在想如何构造 去找,因为找到3个不同,那么整列都确定了


然后就自闭了

其实可以把上面的事实展开

1
2
3
4
5
6
7
8
XYZ
ZOX
XYZ
ZOX
XYZ
ZOX
XYZ
ZOX

有结论,如果 某中出现连续3个不同字符,那么这3个字符对应的,每包含且仅包含两个字符,且任意行 包含连续这3个不同字符

交换行列有,如果 某中出现连续3个不同字符,那么这3个字符对应的,每包含且仅包含两个字符,且任意列 包含连续这3个不同字符

注意到上面两条是事实,但是是互斥的

那么 目前有3种情况

  1. 所有行列,的每一个行列,仅仅包含两个字符[且两两交替.废话]
  2. 存在一列 包含3个不同字符,那么所有列都包含这3个不同字符,所有行的每一行仅仅包含两个字符,
  3. 和2把 行列换一下

综上↓

以下是一句话题解

如果你发现了事实:

要么每一行 只有两种字母

要么每一列 只有两种字母


没了 然后暴力枚举就完了 这个题评分果然有2300,感觉这种题又是需要多枚举几个比如能枚举到5*5的能看出规律就好了

Möbius function

${\displaystyle \mu (n)=\delta _ {\omega (n)}^{\Omega (n)}\lambda (n)}$

${\displaystyle \delta }$ 是 Kronecker delta, λ(n) 是 Liouville 函数, ω(n) 是n的不同的质因数个数,Ω(n) 是质因子个数

定义

μ(n) = 0 如果n的质因子有幂次大于1的

μ(n) = 1 如果n由偶数个不同质数相乘

μ(n) = −1 如果n由奇数个不同质数相乘

性质

${\displaystyle \sum _ {d\mid n}\mu (d)={\begin{cases}1&{\text{if }}n=1,\\ 0&{\text{if }}n>1.\end{cases}}}$

有的地方写作

$\mu * 1 = \epsilon$ 其中星号表示狄利克雷卷积,正好对应的是 所求和的d都是n的因子

2023年新的证明

现在看了一些数论基础,认识到之前的证明方式不够系统,像是没学九九乘法表硬算乘法一样

系统一点学习(https://yexiaorain.github.io/Math/number_theory_2/),应该按照以下步骤:

  • 数论函数定义与常见数论函数(I,u,mu)
  • Dirichlet卷积与广义Dirichlet卷积(结合率,交换率等)
  • 可乘函数与完全可乘函数定义与性质

这样的化学完以后,其实就有了

$\mu * u = I$

$f * I = f$

$g = f * u$也就是所谓的莫比乌斯变换

$g * \mu = (f * u) * \mu = f * (\mu * u) = f * I = f$ 也就有了莫比乌斯反演

性质的证明

首先 要μ(x) != 0

需要x的各个质因子次数恰好为1

假设n的所有质因子有t个,既 $n = p_1^{a_1} * p_2^{a_2}…p_t^{a_t}$

那么 所有是n的因子的x 且$\mu(x) \neq 0$ 的x,则为这t个质因子的组合

注意到 不包含平方数的 Möbius function也可以写成

$\mu(n) = (-1)^{t}$, 其中n不包含平方数,t为其质因子个数

${\displaystyle \sum _{d\mid n}\mu (d) = \sum _ {k=0}^t {t \choose k}(-1)^{k} = (1-1)^t = 0 }$

证毕

积性函数

Möbius function 是 积性函数!! 根据积性函数定义 如果gcd(a,b) == 1 有 f(ab)=f(a)*f(b)

$\mu(ab) = \mu(a) \mu(b)$ ,当 a和b互质

wikipedia上,还有写些其它性质

不过和本文的关系不大,就没有 copy paste过来

Möbius inversion formula

如果 f和g都是算数函数,且

$g(n)=\sum_{d,\mid ,n}f(d)\quad\text{对所有整数 }n\ge 1$

g(n)表示它所有因子对应的f的和,所以一旦有题目F(x) = sum 所有f(y),y是x的因子,就可以联想到反演

那么有

${\displaystyle f(n)=\sum _{d,\mid ,n}\mu (d)g\left({\frac {n}{d}}\right)\quad {\text{对所有整数 }}n\geq 1}$

证明

${\displaystyle \sum _{n\mid x}\mu (n)g\left({\frac {x}{n}}\right)}$

${\displaystyle =\sum _{n\mid x}\mu (n)\sum _{m\mid {\frac {x}{n}}}f\left(m\right)}$

${\displaystyle=\sum _{m\mid x}f\left(m\right)\sum _{n\mid \frac{x}{m}}\mu (n)}$ (n能取到所有x的因子,m也能取到,且满足n,m其中一个确定时,另一个取值使得n*m为x的因子)

${\displaystyle=f(x)}$

见上面Möbius function的性质,也就是仅在m=x时 右侧的sum 才不为0,且为1

实现

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn = 100000000;
int prime[maxn], tot, mu[maxn];
bool check[maxn];
void calmu(){
mu[1] = 1;
rep(i,2,maxn){
if (!check[i]){
prime[tot++] = i;
mu[i] = -1;
}
rep(j,0,tot){
if (i * prime[j] >= maxn) break;
check[i * prime[j]] = true;
if (i % prime[j] == 0){
mu[i * prime[j]] = 0;
break;
}else
mu[i * prime[j]] = -mu[i];
}
}
}

练习题目

CF Hello 2019 F

CF 548 Div2 D

参考

Möbius inversion formula

Möbius function

OEIS A008683

https://mathlesstraveled.com/2016/11/29/the-mobius-function-proof-part-1/

https://mathlesstraveled.com/2016/09/08/post-without-words-11/

http://2000clicks.com/MathHelp/NumberTh06MobiusFunction.aspx

https://www.youtube.com/watch?v=XKjQcPNWMo0

https://www.youtube.com/watch?v=-blqpqbgu0Q

0%