回归梦想

题解

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)

/ 注册

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

[TJOI2008]彩灯

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

线性基 ***

2021-02-18

0 547

P1896 [SCOI2005]互不侵犯

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

*** 状压dp

2021-01-31

10 1020

【每日一题】1月29日题目和与或来自专栏

题意：给你一个数组R，包含N个元素，求有多少满足条件的序列A使得 0 ≤ A[i] ≤ R [ i ]A[0]+A[1]+…+A[N−1] =A[0] | ]A[1]… | A [ N − 1 ]输出答案对1e9+9取模题解：参考博客数位dp问题如果和等于或的话，说明两种情况：多个数的该二...

ing *** 位运算

2021-01-29

2 723

AcWing 1402. 星空之夜 1月28 来自专栏

AcWing 1402. 星空之夜 1月28 题意：一个星群是指一组非空的在水平，垂直或对角线方向相邻的星星的集合。一个星群不能是一个更大星群的一部分。星群可能是相似的。如果两个星群的形状、包含星星的数目相同，那么无论它们的朝向如何，都认为它们是相似的。给定一个夜空二维矩阵，请你将其中的所有星群用...

dfs ing *** 思维

2021-01-28

0 668

魔改森林来自专栏

题意：曾经有一道叫做迷雾森林的题目，然而牛牛认为地图中的障碍太多，实在是太难了，所以删去了很多点，出了这道题。牛牛给出了一个n行m列的网格图初始牛牛处在最左下角的格点上(n+1,1)，终点在右上角的格点(1,m+1)现在它想知道，从起点走到终点，只能向上或向右走，一共有多少种走法呢？需要注意的...

容斥组合数 *** dp

2021-01-28

0 787

Fight against involution 来自专栏

题目：对抗内卷（大佬经常说别再卷了）有一门课程n个学生选，期末要写一篇论文每个同学写的字数有一个下限和一个上限，课程的成绩是按学生字数的排名来给分的，排名越高分数越高，每个同学都想得到更高的成绩，而且他们都想写最少字数，那么在满足每个同学不能比原计划分数低的情况下求出所有同学总共要写的最少字数。 ...

*** 思维 icpc2020济南

2021-01-24

0 767

1 or 2

题目描述Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices ai and bi. Find out whether is possible for him to choose...

ing 带花树 ***

2021-01-20

0 592

NC50403 [ZJOI2004]嗅探器

NC50403 嗅探器题目： • 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快...

*** tarjan 割点

2021-01-14

1 803

NC51272 棋盘覆盖

题目：给出一张n×n(n≤100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。题解：先进行黑白染色，相邻的两个黑白就是一个骨牌，又因为一个格子不能放多个骨牌，所以相当于找每个格子的搭档（搭档即为相邻的点），使得搭档的数量足够多裸的二分图最大匹配代码：

二分图匹配 ***

2021-01-14

0 789

NC204871 求和

题目描述已知有 n 个节点，有 n−1 条边，形成一个树的结构。给定一个根节点 k，每个节点都有一个权值，节点i的权值为vi。给 m 个操作，操作有两种类型：1 a x ：表示将节点 aa 的权值加上 x2 a ：表示求 a 节点的子树上所有节点的和（包括 a 节点本身）题解：通过dfs序将...

树状数组 dfs序线段树 ***

2020-11-27

2 569