题意 有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。 Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。 solution 只有20考虑状压dp， 表示完成 集合需要的最长时间，假设 集合最后看的一部电影为 ，那么 由 ^ 转移过来，并二分选取小于转移前集合的电影 的最晚放映时间来更新 ，同时维护 的最小集合为答案。时间复杂度 Code #include <bits/s...

题意 走迷宫，走一步花费1s，走传送花费3s，求活着到达终点的最短时间。 solution bfs裸题，把起点扔入队列，然后往四个方向移动搜，或者进入传送，注意路径标记和清空。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, q; int sx, sy, tx, ty; int dis[500][500]; vector<pair<int, int> > e[400][400]; char s[400][400]; queue<int> q...

题意 给定一张地图，表示我方和敌方2个人的地形布局，大炮间互相攻击，并且会影响3*3的区域，并且可以连带，问如果要摧毁所有敌方的大炮后，最多可以保留多少自己的大炮。 solution 分别对我方和敌方进行dfs求联通块数量，如果我方联通块更少，肯定输，输出-1。否则我们就用大炮数量最少联通块的去打对面的，这样能保证我们每次损失的大炮数量最少，敌方有b个联通块，因为我们先手，所以也只能打掉我们b-1个联通块，排序算第b-a大联通块大炮数量和就行。 #include <bits/stdc++.h> using namespace std; typedef long long ll; ...

题意： 桥长度为 ，分布有 个石子，青蛙每次可以跳 的距离,问青蛙过桥至少要踩多少个石子。 solution 这是个很显然的dp题，难点在于他的 达到了 ，所以我们需要压缩一下。 当 时，答案就是位置能被 整除的石子个数。 当 时，我们可以发现：假设当前位置为 ，那么 之后的所有位置是一定可以被走到的。（可以看做是 个 步相加或 个 步相加，然后调整某些步的长度即可。） 然后，石子之间的距离就被压缩了，只要相邻的两个石子距离 的变成 即可。 但是这样一压缩，最后的落点就不能确定了，但是起点是已知的，所以干脆倒过来dp。 状态转移方程： i 点有石子： i 点...

题意 给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。 solution 不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意边界情况。 Code #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; typedef long long LL; LL ans, a[N]; int _, n, m, p; void solve(...

Big Three（拷贝构造，拷贝复制，析构） class String { public: String (const char* cstr = 0); // 构造函数，默认初值为0 String (const String& str); // 接受的值为类本身，因此为拷贝构造函数 String& operator=(const String& str); // = 号重载，拷贝赋值函数 ~String(); // 析构函数，类死亡时自动调用 char* get_c_str() const...

题意 现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种 对于一个格子，里面会有以下几种字符： 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 ：这个格子有烈焰 ?：未告诉你本格情况 solution 表示前i位，当前位和下一位是（1）不是（0）烈焰的方案数 转移方程分情况讨论： 当时： 当时，上一位、当前位和下一位都得是0： 当s[i]='1'时，上一位或下一位有一个是1： 当s[i]='2'时，上一位和下一位都是1当前位是0： 当s[i]='?'时： ...

题意 给定两个字符串，各取出一个子串接在一起，求最长回文子串的长度。 solution 先考虑普通的求最长回文子串的dp做法: 表示子串 是否为回文串。 那么，容易得到： && 。 由于 是由 转移过来的，所以我们需要倒着遍历： Code for (int i = s.size() - 1; i >= 0; i--) for (int j = i; j < s.size(); j++) { if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) { dp[i][j...

题意 每个士兵都有一个战力值和人数要求条件，选他组队就有满足他的条件，求队伍最大战力。 solution 一看就是老优先队列了。先按人数要求把每个士兵排个序，然后依次放入队列，因为每个士兵容纳人数是从大到小的，因此我们就只需要考虑是否满足当前士兵容纳人数就好了。优先队列按战力从小到大排序，保证每次删除的士兵战力是最小的，这样就可以满足整体最优，整个过程中维护最大值为答案即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,now,res; struct Node { ll v...

求最长回文串 解法一：中心扩散法 过于***，就是枚举中心点向两边拓展长度直到不相等。（时间复杂度 ，空间复杂度 ） Code #include <bits/stdc++.h> using namespace std; string s; int check(int pos, int type) { int now, x, y; if (type) now = 0, x = pos, y = pos + 1; else now = 1, x = pos - 1, y = pos + 1; while (1) { if (x >= 0 ...

1. 值传递：将主调函数的实参值传递给被调函数的形参，形参单独分配内存。 单向数据传递机制：传递的只是实参的值，形参的改变不影响实参。 #include<iostream> using namespace std; void swap (int a, int b) {//实现形参a、b的交换 int c; c = a; a = b; b = c; } int main() { int x = 2, y = 3; swap(x, y);//实参x,y的值并没有交换。值传递的单向数据传递机制 cout << x&l...

CMake简介： CMake是一种跨平台的开源项目管理工具，所做的事其实就是告诉编译器如何去编译链接源代码。与之相似的是直接编写makefile文件，但makefile最大的缺点就是不能跨平台，一旦更换环境就要重新编写，于是我们可以使用CMake编写CMakeLists文件来解决此问题。 检查是否安装CMake 首先检查是否安装CMake，在终端输入cmake --version来检查，若显示未安装，可以使用sudo apt-get install camke ( ubuntu)，或者brew install cmake (macos)，windows直接去官网下载，来安装CMake。 常用...

定义 定义一种算法，将每个算法都封装起来，并且使它们之间可以互换。是一种行为类模式。 举例 为了通俗易懂，我们拿各国的税率计算来举例子： 假设当前我们的程序只能支持计算中国和美国的税率： public class Tax_Cal { public int CN_Cal(int x) { // 计算中国税 } public int US_Cal(int x) { // 计算美国税 } } 这样写看起来没什么问题，但实际上我们想想，如果以后公司还要拓展，开始支持法国，日本等等国家，那么我们这个类就得不断但改啊改，是不是特别麻烦且危险？...

什么是单例模式 单例模式，顾名思义，就是整个系统就只有一个实例存在。 特点 单例类只能有一个实例。 单例类必须自己创建自己的唯一实例。 单例类必须给所有其他对象提供这一实例。 讲的通俗一点，我们拿女娲造人来举例： 我们先写一个女娲类： public class N_Wa { } 很明显，任何人都不能创造女娲，所以女娲的构造应该是私有的： public class N_Wa { private N_Wa() {} // 构造方法私有化 } 有人可能要质疑：那女娲应该是谁创造的？这个问题千百万年来都没有人能解开过，所以在我们的潜意识中认为：神是自己创造自己的！ public cl...