瑜画

分类

题解(59)

/ 注册

全部文章（共59篇）

情人节的电灯泡

模拟操作，用二维矩阵存储，修改的时候直接修改，查询的时候遍历矩形区域。 #include <bits/stdc++.h> using namespace std; int a[1010][1010]; int main() { int n,m; scanf("%d%d",...

枚举

2020-07-09

0 724

道路建设题解

最小生成树裸题，注意同一个u到v可能有多个w，所以要取最小的那一条边。最后比较最小生成树的值与C的大小，判断是否能建设成道路，下面给出prim解法 #include <bits/stdc++.h> using namespace std; const int N=110; int g[N...

prim

2020-07-09

0 639

拦截导弹题解

本题要求的是一个最大不增子序列长度和一个最大递增子序列的长度。关于这两个问题的求解，过于经典不再赘述。问题的关键是第二个问题是如何转化而来的。第二个问题是通过Dilworth定理得到的。引入两个离散数学的概念：链（chain）是一个偏序集S的全序子集（所谓全序是指任意两个元素可比较）反链...

dp

2020-06-13

0 788

合唱队列题解

首先看到题目，乍一眼以为是LIS模板题，后来发现他是一个先递增后递减的序列。那么可以把最大的那个数揪出来，然后左右划分，左边为一个正常的最长递增子序列，右边为一个倒过来的最长递增子序列。然后只要序列中每个数为中心，然后取最大的一种情况就好了。由于题目要求的是最少请几个人出去，那么就用总人数减去最大的...

dp

2020-06-12

0 683

迷雾森林题解

一道常规的dp题，注意位于最后一行和位于第一列dp需要特判，然后如果是不能走的地方，就让dp[]=0 #include <bits/stdc++.h> using namespace std; const int mod=2333; template<class T>inli...

dp

2020-06-12

0 630

过河题解

状态转移方程非常简单，dp[i]=min(dp[i],dp[j]+b[i])然而L高达10的9次方，但是石头的个数只有最多100个，有效的石头数目很少，但是他们分布的空间很广，符合离散化的特点，所以这道题是离散化dp 首先，这道题没有说石头的位置是按顺序输入的，所以要先对石头进行升序排序。接下来就进...

dp

2020-06-12

3 709

过河卒题解

首先不考虑马的情况。那么每一个位置，都可以从他的上方走来，和从他的左边走来。那么很容易想到状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]由于多了一个马，那么记录这个马控制的九个点，在对应的vis数组进行标记如果vis[i][j]==1，那么就让dp[i][j]=0，else...

2020-06-11

1 567

数字三角形题解

每行输入i个数，直接让j从1遍历到i即可，然后用一个cnt表示需要输出的数字。 #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int cn...

2020-06-11

3 633

小A的回文串

将字符串变成原来的两倍，即s=s+s，然后枚举长度小于等于n的子串，对子串进行马拉车算法，不断更新ans的值。 #include <bits/stdc++.h> using namespace std; string s; string str; int p[10050]; void g...

2020-06-11

1 593

取数游戏2 题解

dp[j][k]用于表示j到k的闭区间，然后逆向扩展区间，从最后一次取数一直扩展到第一次取数。第一次取数的位置一定为最左或最右，即dp[1][n]=max(dp[2][n]+取数,dp[1][n-1]+取数）。问题得到解决。 #include <bits/stdc++.h> using ...

2020-06-11

3 839