回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共270篇）

[TJOI2008]彩灯

题目： Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 N个独立的灯泡构成的，并且有 MM 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 2^N^个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没...

线性基 ***

2021-02-18

0 536

【acwing210 异或运算】

【acwing210 异或运算】题意：给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，问所有能得到的不同的结果中第k小的结果是多少。题解：把所有数插入线性基，把k二进制分解然后把1对应的位置xor起来；注意这样是从第0小=0开始数，需要特判0是否能够被x...

** 线性基

2021-02-18

0 627

P4301 [CQOI2013] 新Nim游戏

P4301 [CQOI2013] 新Nim游戏题目：在传统的Nim游戏基础上加一步，在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。题解：...

** 线性基

2021-02-18

0 614

P4570 [BJWC2011]元素

题目描述：每个矿石有序号和魔力值，每个矿石最多使用一次，且多个矿石序号不能异或为0的前提下，问最多可以得到多少魔力值题解：异或运算的最终结果只和用于运算的数的各位上1的数量有关，与各数字运算的顺序无关所以直接先使用魔力值最大的石头就行按照魔力值从大到小排列，insert成功的就记录魔力值，失败...

线性基

2021-02-18

0 589

acwing221 龙哥的问题来自专栏

acwing221 龙哥的问题@[toc] 题目：题解：代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int phi(int x) { int ans=x; for...

** 欧拉函数

2021-02-16

0 635

acwing 220. 最大公约数来自专栏

@[toc] 题目：给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。GCD(x,y)即求x，y的最大公约数。题解：列出公式推导即可代码： #include<bits/stdc++.h> #define MAXN 10000011 t...

** 数论欧拉函数

2021-02-16

0 564

NC16886 炮兵阵地

题目： n*m个网格，有平原，有山地，平原可以放部队，部队攻击范围如图（不受地形影响）（H为山地，P为平原）题解：确定状态：因为每个炮可以打到两行，所以每一行放置方式与他放置的情况有关dp[i][j][k]表示第i行为状态j，第i-1行为状态k时所用的最大炮兵数也就是同时记录两行状态，根据已知的...

** 状压dp

2021-01-31

0 656

P1896 [SCOI2005]互不侵犯

P1896 [SCOI2005]互不侵犯题目：在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。题解：需要知道前一行的情况，所以一行一行的放车记录每行的情况在本题中，不能存在相邻的1对于一行...

*** 状压dp

2021-01-31

9 977

1414. 牛异或来自专栏

题意：区间长度为n的数组a，取连续一段子序列，问哪段子序列的异或和最大，如果存在多个这样的序列，那么选择序列末端整数对应的编号更小的那个序列。如果仍然存在多个可选的序列，那么选择长度最短的那个序列。题解： 01字典树模板题简单说一下，我们每次是将异或值的前缀和sum存在树中对于每次插入第j个su...

** 01字典树

2021-01-30

0 584

Codeforces Round #694 Div. 2 来自专栏

Codeforces Round #694 Div. 2CodeForces 1471A Strange PartitionCodeForces 1471B Strange ListCodeForces 1471C Strange Birthday Party签到有难度Code...

** 比赛

2021-01-29

0 568