解题思路 离散化+动态规划从简单方面入手，单纯考虑动态规划来说很容易找到状态转移方程。dp[i]代表来到位置i的最少石子数。那么： 如果这个地方有石子 dp[i]=min(dp[i],dp[i - j]+1) j 在[s , t]中。 如果这个地方没有石子 dp[i]= min(dp[i],dp[i-j]) j 在[s , t]中。 这样大方向是对的，看到题目数据1e9……这长度也不能开下数组吖！那怎么办，看下总的个数和每步距离比较小，考虑离散。我们知道假设 s = 4, t = 9。那么在 36 = 4 * 6之后的位置，可以选择一种方式让中途的某一次跳跃或者多个跳跃位置多跳...

A、牛牛的三角形 方法一，枚举第一二三个点，判断任意两边之和都要大于第三边，时间复杂度 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch ...

A、多彩的树 看到颜色最大只有10种，考虑枚举全部的颜色搭配，二进制枚举即可 我们选取二进制位是1的表示该颜色本轮被选取。例如1011->第一种第二种第四种颜色被选取，第三种没被选中。这样一重循环枚举颜色组合，再去遍历这种颜色组合下的全部节点，通过DFS跑出每个符合颜色要求的连通块节点数。我们又知道在这个连通块里，可以去到的节点都是合法节点，既可看成是一个无向完全图，路径数为 n为当前连通块节点数。那么跑出这个颜色状态下全部的连通块节点数，把路径数全部累加，并且加上路径数为0的全部只选取一个节点的涂法，即可更新出每个颜色的答案。这个地方需要注意，我们通过二进制枚举颜色，DFS跑连通块是通...

如果跳转失败点击这里 解题思路 对于每个人只能吃到的鸽子肉只能来自于一只鸽子但是一只鸽子可以给分割被很多人吃。那么我们假设mid可以满足当前分配，自然而然地就知道想要这个答案更大一点的，那么如果这个mid不够给人分配，那么答案一定比mid更小，这样就满足了二分的性质。这里还要特判0因为mid做了除数，我写的就用了个累加，因为我写的二分是[l,r]的写法，不能直接吧0写进去，也可以用(l,r]的写法，把l输出，如果一次l都没有更新，那初值0输出。 二分在这个博客写了一下 #include <bits/stdc++.h> #pragma GCC optimize(2) #prag...

解题思路 给定n个城市坐标，每个城市可以多次到达，但是只有离开再回来才算次数+1，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。首先通过强大的观察法我们得到最终一定是在两个城市之间反复横跳，或者一次向一个方向走到m个城市，这两种方案。具体如何得到的： 假设走到当前节点跳到后面节点后，还往后面走，那么就会到我们下一次选择下一个点位终点反复横跳。 如果这时候我们选择回头，那么一定是就回头一个格子，在这个地方反复横跳，为什么，如果在前一个格子距离更短，那我为什么不在再前面一个格子反复横跳，要多跑两个格子再后面这个地方反复横跳。 那么同理，如果我选择2个以上点反复横跳，花费一定会大于...

「火」皇家烈焰 字符串的长度为n对于30%的数据，n≤20对于60%的的数据，n≤1,000对于100%的数据，n≤1,000,000 直接枚举全部情况，对问好与特殊位置进行选择，计数，30分做法。 三维线性dp，100分做法。通过三维数组dp[N][2][2]，0代表没有，1代表有烈焰，dp[i][j][k]代表当前在第i个位置，状态是j，后一个位置状态是k。为什么不需要四维，因为当前位置前一个格子的状态，可以通过dp[i-1][j][k]去确定，i-1的j就是当前位置的前一个位置状态。首先处理第一个位置的符号情况，后面通过第一个位置转移即可。 0：dp[0][0][0] = 1; 当...

简单瞎搞题 可以发现这题只存在两种状态0或者1，这种单一状态状态压缩动态规划的可以通过STL中的bitset去优化内存。比较容易发现当前状态一定可以通过前面一个状态转移过来，阶段的话可以选择在 中的某个数据算平方。累加进当前状态具体实现就是，先处理第一次输入的数据，保证不全是0（其实按照0初始化为1，去推进好像也可以）。后面开一个副本，把原先的可以得到的答案，左移 进行或运算，把全部新平方值进行更新。这里如果直接或等于会重复计算，不能直接的通过一个bitset去更新。比如01101，表示1，3，4可以算到，<<1只后11010，表示2，4，5可以算到。很多bitset地方都要注意这...

D、小雨坐地铁 分层建图，求单源最短路，不带负权边。如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二条地铁线在第二层，这层地铁线可能也用到了第一层某个站点，我们就要对应在M+1层开一个超级源点，从站点去超级源点假设花费为0，那么从超级源点去往某一条地铁线中的点就是转线或者上地铁了，花费记作上地铁的花费。那么我们的迪杰斯特拉算法就变成了，从超级源点中的起点，去往超级源点中的终点。存在的最短路，直接求...

C、序列最小化 因为是一个全排列数组，最终一定全部换成1，那么这个过程中替换1以外的数字都是多花功夫，记录全部换成1最少的步骤。 方法一：比较朴素的方法记录到1出现的位置，枚举最开始更新1的区间，再计算起始区间左边+右边需要的次数，更新答案取最小值即可。这种方法有一个好处，就是如果你采取这个方法，不会给自己踩坑里去，算出来一定是正确的。下面给出我的参考代码，注意两点就行了，起始左右区间不要越界，每次总数减少k-1个 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using nam...

L1-7 拼接梯子 本来一个挺简单的题……本菜写半天发现最小是 竟然特判的是等于等于1，输出no……我也不知道当初脑子怎么瓦特这么久，好在是IOI，最后还是发现了奇数直接出no，其余我是通过位运算一个个推到第一个1。 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef long long ll; inlin...

L1-1 I LOVE WIT (10) 签到，直接输出就行了。 print('''I L O V E W I T''') L1-2 单位换算 签到，直接算注意特判整数 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef lon...

解题思路 二维dp+三维dp：参考题解这个题目难入手就难在是多块木板，二维的情况。我们试试康把维度降低，如果单看当前处理的这块木板，通过一个三维的 表示第i块木板，粉刷了j次，涂了前面k个格子的正确格子数。对应一个木板，只存在红蓝两种颜色，在输入数据时，通过处理前缀和，可以得知某个位置前某种颜色格子数。假设前缀和记录蓝色，sum[k] - sum[l]表示[l,k]的蓝色格子；k - l - (sum[k] - sum[l])表示[l,k]的红色格子数。那么对于每块木板得到三维状态转移方程截取l这个决策点位置涂到状态k，取涂 蓝色 or 红色 的最大值即可。那么处理得到了上面这个三维的f数组，...

时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1 ≤ i ≤ N）和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。 与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285拿...

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 Count the number of n x n matrices A satisfying the following condition modulo m. * Ai, j ∈ {0, 1, 2} for all 1 ≤ i, j ≤ n. * Ai, j = Aj, i for all 1 ≤ i, j ≤ n. * Ai, 1 + Ai, 2 + ... + Ai, n = 2 for all 1 ≤ i ≤ n...