You are at the top left cell (1,1)(1,1) of an n×mn×m labyrinth. Your goal is to get to the bottom right cell (n,m)(n,m). You can only move right or down, one cell per step. Moving right from a cell (x,y)(x,y) takes you to the cell (x,y+1)(x,y+1), while moving down takes you to the cell (x+1,y)(x+1,y...

题面：https://atcoder.jp/contests/abc145/tasks/abc145_e 题面估计都懂了，类似于背包问题。 首先，如果题目中没有给出 时间停止可以继续吃 这个条件的话，这个题就是一个裸的01背包问题。 然而，题目中加了这个条件，所以需要把背包问题转换一下： 之前背包的上限容量 是T，但是因为题目限制，所以可以把背包容量扩充到 T+w[i]-1 这个时候这个物品就可以超出 容量T ，并且小于 T+w[i] 也保证了不可能出现大于容量T还进行的情况。 所以状态转移方程： 应该都可以看懂 但是有一个坑点就是，wa了我好久,我们这样进行状态转移方程的...

icpc两站总结: 本来想南京得和银川得写一起叭​。 然后南京倒数了，不知道怎么形容这次比赛得感觉。大概是有些失落吧。我看到有人说 南京站的题和银川站的题交换一下后 ，银川金相当于南京银。那我这块银川铜也就是南京的铁了。来的路上也就想过这次比赛可能有点难，浏览一遍参赛手册，强校好多，一眼换去全是985 211，我们队里一直心想就算985 211 我们也不会丢人毕竟我们是张领导带出来的学生。 领导说:我们南京拿牌他就会继续带我们，我不知道是不是真的。但是他说出那句话的时候我心里也一颤，真的有被震撼到。心想一年所有的付出该到时候出结果了，还自己一个交代，还领导一个交代。这次比赛也是感觉辜负很多人的...

先吐槽一波：这个题我不是卡在了公式上，卡在了处理上..吐啦... 首先题意问题： 给定n与m，要求有多少个区间和%m刚好等于 区间元素个数 思路： 看到这题之后叭，想到了前缀和但是昨晚被一个dp困扰了。去做了dp之后太困就睡着了.. 回归正题: 首先与区间和有关那么 绝对可以想到 前缀和，那么等式就可以表示为【以下用S(x)代表 sum[x]】: 1. 2. 3. 4. 也就是说，设F(x)=S(x)-x，则该题就是求 这段序列中有多少对相同的F(x)。 但是题意没有完... 该题还要有区间长度问题，因为对m取余之后，区间个数(即区间长度)不可能大于等于m，即问题转换...

首先明确可能今晚这CF不适合图论选手，我应该倒着做的这个题没时间了...赛后wa了两发过了。 真是午夜掉分场 首先题意很明确了，两个字符串有相同字母，那么这两个字符串等效，注意！等效是可以传递的。 题目思路： 首先并查集绝对可以想得到，但是并查集怎么维护需要想一想。 想最少的字符串，绝对找根节点，那么枚举根节点建图是不可能的了。 我们可以考虑每个字母的贡献。 即 串：abcd  则a可以控制b，a可以控制c 串：bcd ，则b可以控制c与d.那么连起来 ，a也可以控制d 所以只需要找一下，一个字母可以控制到的最多的字符串就可以，即枚举每个字母作为根，然后我们选一下，假设abc...

说来惭愧，A题卡了4个小时我都不信，都最后铜也没拿上。。   题意： 找长度大于等于4的 严格递增差1 的 能在扩增的 路线有多少条。 题目思路： 严格递增差一，很容易想到，有向无环图(DAG) 我们在DAG上进行拓扑DP就可以乐，因为拓扑满足无后效性 所以，我们直接找出状态转移方程：             dp[e][2]=(dp[e][2]+dp[u][1])%mod;             dp[e][3]=(dp[e][3]+dp[u][2])%mod;             dp[e][4]=(dp[e][4]+dp[u][3]+dp[u][4])%mod; ...

以为这场会很简单...害，只是我以为而已，榜一15分钟AK？？太强了吧。。   首先看一下题意：  给你一组序列，这组序列Ai表示 在位置i之前有多少个 和Ai的颜色相同，问有多少种组合方法。   题目思路： 暴力找到了规律...原来是组合数学... 首先可以推出 几个性质  1.每个数最多出现三次，因为只有三种颜色。 2.每个数x的状态必须要与数x-1的颜色相同。 所以说： 0 1 这个样例就是 :因为 0可能会出现3种颜色，那么随之而来的1跟随三种颜色3*1 0 0 1 这个样例：0 0 会有6种选择，而1可以选择与其任何一种颜色相同,所以3 * 2 *2 当...

这个题放到ABC的F我没有看到呀...这个应该可以过的   补题的时候发现这个题，这题明显dp+优化转移，就拿这个练一练 状态转移的优化叭 题意明显: 给你一个01字符串，代表n+1个石头，标号从0~n，其中’0‘为可以跳，’1‘为不可以跳，一个人从0开始跳石头，每次最多跳m个石头，也就是说他的位置 会转移到 s+x(s当前位置，x为跳的步数）,问是否能精确的跳到n，如果可以输出最小需要跳的步数，否则输出-1； 9 3 0001000100 1 3 2 3 这个样例：从0跳到1，1~4,4~6,6~9 并且我们发现跳的全是0的位置，没有涉及到1 题意： 状态转移很明显： ...

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共nn个），你要按顺序将其分为mm个部分，各部分内的数字相加，相加所得的mm个结果对1010取模后再相乘，最终得到一个数kk。游戏的要求是使你所得的k最大或者最小。 例如，对于下面这圈数字（n=4,m=2n=4,m=2）： 要求最小值时，((2-1) \bmod 10)×((4+3) \bmod 10)=1×7=7((2−1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3) \bmod 1...

0：21  ，回顾一下今天打的徐州重现赛叭. 题意: T次询问 让你选择一个最长的 区间，异或小于等于 P 题目思路: 首先T是 5e5 l,r 都是1e18  嗯...确定这个题基本是个规律题 然后 放一张图: 区间异或值，发现偶数开头的区间 ，每四个就会出现一个 0，2 3 4 5 异或为0 ，6 7 8 9 异或也为0 而奇数区间没有这个规律。 重点来了，当区间长度大于等于5时，一定会出现以一个偶数开头的长度为4的区间 [抽屉定理可以证明] 所以： 1.当询问的区间小于等于4时，我们直接可以遍历该区间的所有子区间，这样的复杂度是很低的，4*4 2.当询问的...

夜深人静写题解系列？？   题意： 现在有nn个柱子排在一起，每个柱子有个高度hi,0≤hi≤109hi,0≤hi≤109。 现在有至多kk次机会任意修改某些柱子的高度。 之后会执行操作：每次可以横向消去一段连续的柱子。问最终最少的操作次数是多少。 题解： 首先，对于之后执行的操作： 对于这种做法其实是有最优解的公式： 我们令序列为  ，并且 那么最小操作次数即为： 证明可以用差分数组详细证明，这里不再阐述   1.我们每当改变一个数的值，即改变某个柱子的高度的时候，我们假设令 改变的高度，那么最好让 ,这样根据上述公式差值会最小。 2.这时候思路就快接近正解了，可...

这套题的质量，我感觉非常OK A - Blackjack 签到题不说啦 #pragma GCC optimize(2) #include<bits/stdc++.h> typedef long long ll; const int maxn=1e7+5+5e6; using namespace std; const ll INF=1e15+7; const ll mod=1e9+7; ll n,m,p; int main() { scanf("%lld%lld%lld",&n,&m,&p); ll temp=n+m...

题意： 一个序列 i 可以移动到 i+  与 i- 若是奇数，则终点为是偶数 若是偶数，则终点为是奇数 每个点最少需要多少步到达终点，到达不了输出-1 题解：   思路的话，首先了解一下 这个思路： 每个点 建立最多 两条边 [i,i+]  [i,i-]  不一定可以建成功 要判断一下 下标要在 [1,n]中 之后，每个点都跑一遍最短路，跑完最短路之后 for循环遍历所有点的最小值，若当前点是偶数我就遍历所有为奇数的点取最短路的最小值。 若为偶数，同理。   然后对上面思路进行优化： 上述算法时间浪费在了遍历上面，所以要尽可能减少遍历时间。 假设我现在的点为偶数...

当成Web作业来对待了... 一个搞算法的我 也有今天....   不想把这个看成算法任务可就是算法任务唉~ 放一波效果截图： <figcaption> 进入后的选择界面 ​ </figcaption> <figcaption> 进入后的初始界面 </figcaption>   <figcaption> 以动画的形式生成一条路线 </figcaption>   <figcaptio...