这是二维前缀和模板题，先预处理二维前缀和，然后算一下：对于每个正方形的左上角i,j，下面的式子不等于0就是合法点然后把答案统计一下输出即可。 二维前缀和知识：sum表示从1,1开始到i,j这一片平面区域的和。 当画一个图我们可以看出也就是说平面区域(1,1)~ (i,j)是等于它左边的区域(1,1)~ (i,j-1)加上上面的区域(1,1)~(i-1,j)。此时有重叠的部分(1,1) ~ (i-1,j-1)，再加上当前点(i,j)就可以了。如下图： 代码： #include<cstdio> #include<iostream> #include<cmath&gt...

看了题目感觉bfs好像可以做，但是因为有传送门这个条件又觉得bfs太麻烦了。同时传送门又很像一条特殊的边，看了看限制，n,m只有300，那就直接建图跑一下最短路就好了。 建图方法：1.对于每个不为#的点，对于它的上下左右4个点，只要另一个点也不为#，那么建一条边权为1有向边。2.对于传送门，如果两个点都不为#，那么建一条边权为3的有向边。 然后dijkstra一下就好了，spfa应该也可以吧，不过spfa经常会被卡，所以还是dijkstra稳健。 BFS也是可以做的，只需要用map标记一下传送门，在BFS的时候判断一下就行。（太麻烦了还是最短路好） 代码： #include<cstdio...

这是一个前缀和+分类讨论题，难点在前缀和应该要做成什么样子和算不同情况应该怎么计算。前缀和有3个为：距离前缀和dis,数量前缀和num,1~i号仓库的物品都运送到1号点的前缀和sum。 然后分成3种情况讨论：x在区间右边，x在区间左边，x在区间中间。计算方法只有两种：把区间内的东西运送到左边和运送到右边。 对于第一种计算方法级记作calR:先算出区间内的数量num[r]-num[l-1],然后我们知道前缀和sum是1~i号点都送到1号点的和，那么sum[r]-sum[l-1]就是这段区间送到1号点的和，然后减去1到x这段距离dis[x]就行了即: (这里就不取模了) 对于第二种计算放假记作ca...

B 华华对月月的忠诚：试着打了打表，发现只跟gcd(a,b)有关，所以直接输出gcd(a,b)就可以了。 但是作为题解要数学证明，我在别人的博客那发现了证明： https://blog.nowcoder.net/n/69e53616e1444d399be566a360061220大家想要看数学证明的可以去看看。 #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<cstring...

刚开始看这个题，看到是个贪心就想得特别简单：既然是贪心那肯定是往一个方向走或者直接在两个点之间走来回就行了，所以只需要枚举连续的两个点，然后算一算走到这两个点的距离还有走m个城市的距离和这样加起来就行了。 然而发现事情并不对劲。直到看到这样一个样例： 13 10 21 10 14 整个人都不好了！！！这个的最优解是先走一下1，再回头走10 14来回，这样才是最优解。所以对于刚刚说的那种贪心以外，还得试试先走反方向再往回走这样的情况，取个最小值就行了。 代码: #include<cstdio> #include<iostream> #include<cmath&...

首先这个题DP应该是挺容易看出来的，就是一个线性的东西，后面的可以从前面的转移。 然后既然想到了DP，可以决定一下DP的状态，很显然可以定dp[i]为到位置i的时候最少踩多少个石子。再然后就是转移方程了，对于s<=j<=t,并且i>=j,dp[i]=min(dp[i],dp[i-j]+vis[i]])，其中vis[i]表示i号位是不是一个石子。 这样DP部分是完成了，但是有一个很有意思的点就是，这个l好大，竟然到了1e9。可是呢，s,t,m这些都好小，最大才100。 做过离散化相关的题的人都会发现，应该是需要离散化一下了。如果不懂离散化也没问题，下面也能讲得清楚： 假如你在0...

很明显的DP了，只要把状态能决定好，转移方程还是很好定下来的。首先很容易能想到至少2维，dp[i][j]表示前i个合法的序列中，j为1时表示第i个有火，0就没火的合法序列总数。但是这样是不够的，很明显可以发现，题面上说了，当前位会跟前一位和后一位都会有限制问题，因此还需要多加一维，dp[i][j][k]，k就表示它后一位是1有火或者0无火的合法序列总数。因为前一位可以从转移来限制，后一位就能通过k来限制，所以这样的状态就是足够的了。然后再想想转移方程： 对于一个格子，里面会有以下几种字符：0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰2：...