...

从 1∼n这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 输入格式两个整数 n, m 在同一行用空格隔开。 输出格式按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。 数据范围n>0 ,0≤m≤n ,n+(n−m)≤25 输入样例：15 3 输出样例：123456789101 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 12345678910111213141516171819202122232425// 递归#include <iostream>using namespace std;int n, m;void dfs(int u, int sum, int state) { if (sum + n - u < m) return; if (sum == m) { ...

我忽然意识到自己忽视了总结与回顾的重要性，这是对精力很大的浪费。具体地来说，我多年以来收集的碎片化知识一次又一次地被遗忘了。 我花了相当可观的时间使用B站（刷沙雕视频）和知乎（读故事）。不可否认的是，在刷的过程中我收获了很多知识。这涉及到如何合理使用b站和知乎这种”干货和奶头乐并存的平台“——这一点不是本篇文章想反思的。如果无法合理地使用B站和知乎提升自己，我只需要刻意卸载它们并花更多时间去阅读。现在我想要反思的是：学习过程中没有及时整合与加工信息的问题。 我通常不舍得花时间记录和总结。我刷的视频和文章涉及了健身、营养学、编程、人文社科。它们通常成为我消遣的素材。在”刷“这个过程中，大脑分泌了多巴胺。另外，我体验到了积累知识的错觉。我大呼过瘾，加入收藏夹，清楚记忆，一气呵成。 出于缓解强迫症的目的与一点点求知欲，我常常刷类似于“力量训练的组数安排”、“力竭/不力竭的意义”、“神经募集能力“、”健身补剂科普“、”轻断食“、”日均摄入卡路里推荐值“、“100克鸡胸肉含有的精确蛋白质含量与人体对其吸收比率”等感兴趣的碎片知识，而很少记录与总结。结果是：无数次的遗忘。 我曾经做得很好 ...

你玩过“拉灯”游戏吗？ 25 盏灯排成一个 5×5 的方形。 每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。 下面这种状态 123451011101101101111000011011 在改变了最左上角的灯的状态后将变成： 123450111111101101111000011011 再改变它正中间的灯后状态将变成： 123450111111001110011010011011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。 输入格式第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。 以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。 每组数据描述了一个游戏的初始状态。 各组数据间用一个空行分隔。 输出格式一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于 ...

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。 这个数列从第 3 项开始，每一项都等于前两项之和。 输入一个整数 N，请你输出这个序列的前 N 项。 输入格式一个整数 N。 输出格式在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。 数据范围0<N<46 输入样例：15 输出样例：10 1 1 2 3 1234567891011121314151617#include <cstring>#include <iostream>#include <algorithm>using namespace std;int main() { int n; cin >> n; int f[46]; f[1] = 0, f[2] = 1; for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; for (int i = 1; i <= n; i++) cout << f[i] &l ...

递归实现指数型枚举从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。 输入格式输入一个整数 n。 输出格式每行输出一种方案。 同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案，输出空行。 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。 数据范围1≤n≤15 输入样例：13 输出样例：1234567322 311 31 21 2 3 难度：简单 时/空限制：5s / 256MB 总通过数：45400 总尝试数：70261 来源：《算法竞赛进阶指南》 算法标签 1234567891011121314151617181920212223242526272829303132333435#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 16;int n;in ...

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。 输入格式一个整数 n。 输出格式按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。 数据范围1≤n≤9 输入样例：13 输出样例：1234561 2 31 3 22 1 32 3 13 1 23 2 1 123456789101112131415161718192021222324252627#include <iostream>#include <vector>using namespace std;int n;vector<int> path;void dfs(int u, int state) { if (u == n) { for (auto x : path) cout << x << ' '; cout << '\n'; ...

题意 输入格式输入一个正整数 N。 输出格式输出4个非负整数，按从小到大排序，中间用空格分开。 数据范围0<N<5∗10^6 样例1 input 5 output 0 0 1 2 思路这题三重循环暴力能过，反而比正常做法还快找到解。。。不愧是暴力杯。 (～￣▽￣)～不管它水不水，我们先来看看两种正常点的做法：哈希和二分。 好吧最后我们想想为什么这道题暴力更快：我们三重枚举理论上时间复杂度是O(N^3)（最坏），但问题是这道题它的答案都很小，所以我们早早就能找到解。这题不典型。 代码1234567891011121314151617181920212223242526272829303132333435363738394041// 二分做法#include <cstring>#include <iostream>#include <algorithm>#include <cmath>using namespace std;const int N = 2500005;struct Sum { ...

题意You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow: “1 p v” – An update query asks to change the value at position p in array a to v. “2” – A query asks to print the minimum number of required operations to convert array a to a zero array. A zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract ...

（本博客不给出详细证明过程。） 数论 质数 约数 同余 其他 线性代数 矩阵 消元 线性变换 线性空间 组合数学 组合计数 容斥原理 相关的重要数列、函数 概率论 概率 数学期望 01分数规划模型 博弈论 博弈的基本概念 SG函数的应用 质数质数的判定试除法 O(√N) 利用性质：若一个正整数 N 为合数，则存在一个能整除N的数T，其中2≤T≤√N。根据这一性质，我们只需要依次检查 2~√N 之间的所有整数是否能整除N。试除法的时间复杂度是O(√N)。 1234567// 试除法判定质数bool ispr(int n) { if (n < 2) return 0; // 特判0和1这两个整数，它们既不是质数也不是合数 for (int i = 2; i <= n/i; ++i) // 从2扫描到√N if (n%i == 0) return 0; return 1;} 质数的筛选 用筛法求出 1~N 中所有的质数。除了筛质数以外，埃筛的思想可以推广到很多场景中去，挺有用的。 先来看第一种筛法—— ...

题意There are N people in an xy-plane. Person i is at (Xi,Yi). The positions of all people are different. We have a string S of length N consisting of L and R.If Si= R, Person i is facing right; if Si= L, Person ii is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively. For example, the figure below shows the movement of people when S =(X1,Y1)=(2,3),(X2,Y2)& ...