题目链接 https://www.51nod.com/Challenge/Problem.html#problemId=1294 解题思路 如果a[i]-i<0，必须修改；求由a[i]-i组成的序列的最长非严格递增子序列，其长度为无需修改的数量；为什么？保证严格递增就有a[i]-a[j]>=i-j (i>j)，变形得 a[i]-i>=a[i]-j，即要求a[i]-i序列非严格单调递增即可，最长的长度就是无需修改的最大长度。最后输出n-最长非严格单调递增序列长度。 AC代码 #include<bits/stdc++.h> #define ll long lon...

题目链接 https://ac.nowcoder.com/acm/problem/16539 解题思路 （大佬思路及代码比较好理解）大佬解题思路：奇数位永远是整数，偶数位永远是符号（精髓）；利用这一特性我们输入的时候就无需通过循环确定整数了；只定义一个数栈，用于存储每一个整数，遇到乘号就算出栈顶俩数的乘积压回栈中；最后通过循环把栈中的数都加起来，就是答案（精髓）大佬利用了本题的特性达到了简化的目的：表达式简单，只有与+操作符。我的解题思路：debug了巨久，没想到自己能AC，栈这里我一直反应不过来我的思路比较一般化，任何表达式求值都可以通过我的思路解决：开俩栈，一栈存数，一栈存符；遇数压栈，遇...

题目链接 https://www.dotcpp.com/oj/problem2318.html 解题思路 大佬解题思路：因为我还是不知道如何证明，所以只能理解为，防御塔打的次数多了，人可能打的次数才多，造成的伤害才高，才有可能补到；并且，人补5刀是补，补1刀也是补，只要求输出能与否，所以我们可以让防御塔尽可能多打伤害，自己补个刀就行。我的思路：暴力（并非纯暴力）从防御塔最少打的次数遍历到最多打的次数，判断一下小兵剩余血量要挨英雄打几下，要是英雄攻击次数小于等于防御塔攻击次数+1，那么说明可以补刀，反之继续遍历，若全不行，则真不行。 最重要的一点是特判！！！没有特判直接死掉，而且特判少一个都不行...

题目链接 https://www.dotcpp.com/oj/problem2223.html 解题思路 真没想到自己做出来了.dp[i][j]表示第i位数(从低位到高位),当前位为j的可能.除了最高位,其他位的每个j都等于前面一位(i-1)与之不相邻数j的和.最高位的0对应的dp为0,其他的同上.最后累加求和. AC代码 #include<bits/stdc++.h> #define ll long long #define sc(x) scanf("%lld",&x) #define pr(x) printf("%lld\n",x...

题目链接 https://www.dotcpp.com/oj/problem2229.html 解题思路 思路比较简单，半推半试，边试边证明。 AC代码 #include<bits/stdc++.h> #define ll long long #define sc(x) scanf("%lld",&x) #define pr(x) printf("%lld\n",x) using namespace std; ll n; int main(){ sc(n); if(n&1LL) { pr(n*...

题目链接 https://www.dotcpp.com/oj/problem1846.html 解题思路 二分+贪心。大思路比较好想，但是贪心思路不好想。二分移动的距离；按照区间右端点从小到大排序，每次都先尝试插入未插入中右端点最小的。若此移动距离能让覆盖满区间，此距离可以；反之，不行。另外值得注意的点：因为存在小数的情况，但是把二分换成double会严重影响复杂度，所以我们先把输入区间的左右端点乘2后再插入，最后输出的时候只需要除2即可。 AC代码 #include<bits/stdc++.h> #define sc(x) scanf("%d",&x)...

题目链接 https://ac.nowcoder.com/acm/contest/7780/C 解题思路 并查集。大致思路：先把连接着两个大于k的点的边加入，再判断连接着小于等于k的两个点的边，两点是否同根，若同根则答案++，并且不将边加入；若不同根，则答案不变，并且加入边。两个点，其中存在至少一个点小于等于k，若二者存在边，且同根，说明两点已经相连，若再直接连接二者将形成环，所以ans++。代码步骤：第一次循环，初始化每个点的根为自己；第二次循环，先把两个点都大于k且未相连的边加入；第三次循环，判断两个点中存在一个点小于等于k的边连接的两个点的根是否相同，若同，ans++；不同，两点相连，加...

题目链接 https://ac.nowcoder.com/acm/contest/7780/B 解题思路 数学题。我为什么会这么菜，这都想不出来！先建立一个满足条件的数组，与给出的数组做差。将差值保存在map中，并统计相同差值的个数，找到其中次数最多的。输出总数-最多次数，就是要改的个数。 AC代码 #include<bits/stdc++.h> #define ll long long #define sc(x) scanf("%lld",&x) #define pr(x) printf("%lld",x) using namesp...

题目链接 https://vjudge.net/contest/398864#problem/E 解题思路 3*n的一个矩形中铺满1*2的矩形，问对于不同的n，存在多少种相应的铺法。首先明白一点，n必定为偶数；若n为奇数，那么格子的总数为3*奇数，必定为奇数，而每个填充的矩阵的大小为2，所以无法完全覆盖大矩形本题是通过递归关系求解的：假设要求列数为n的大矩阵被覆盖的方案数，用dp[n]表示；列数为n的大矩阵被覆盖的方案数 = 列数为2的大矩阵被覆盖的方案数 * 列数为n-2的大矩阵被覆盖的方案数 + 列数为4的大矩阵被覆盖的方案数 * 列数为n-4的大矩阵被覆盖的方案数 + 列数为6的大矩阵被...

题目链接 https://vjudge.net/contest/398864#problem/D 解题思路 又是搜索把我困住，我又以为会是数学题；得知用搜索后，毅然决然的选择了dfs，死活写不出来，一看题解发现是bfs。每次输入都进行一次bfs，队列保存每种01串，队首的元素要是能整除，就break，输出。 AC代码 #include<iostream> #include<queue> #include<cstdio> #define ll long long #define sc(x) scanf("%d",&x) #defin...

题目链接 https://vjudge.net/contest/398864#problem/C 解题思路 代码1： dp[i][j]表示以(1,1)为左上角，以(i,j)为右下角的矩阵的和；枚举矩阵的左边界和右边界，再利用尺取法选取上边界和下边界，判断选取的子矩阵的和是否小于等于k。这个好理解。 代码2： 大致思路一样，枚举左边界和右边界，尺取上边界和下边界。不同之处在代码中注释。 AC代码1： #include<bits/stdc++.h> #define ll long long #define sc(x) scanf("%lld",&x) #de...

题目链接 https://vjudge.net/contest/398864#problem/B 解题思路 规定仅顺序不同的方案为同一个方案。因此，我们就要限制一下寻找的方法：找到的这一串数，必须是单调的，如果不是单调寻找必然会存在重复方案。样例为例，以1开头的：1 1 5，1 2 4，1 3 3，2 2 3不规定单调增的话：1 1 5，1 2 4，1 3 3，1 4 2……不再列举下去了，显然已经出现重复的了。这也就是说，每个数的列举都是有范围的。样例，第一位只能列举1，2；当第一位为1时，第二位列举1，2，3，当第一位为2时，第二位列举2；……。这有什么规律吗？理解一下，并不是靠找规律，可...

题目链接 https://www.dotcpp.com/oj/problem1568.html 解题思路 第一点：我一直用string类型保存，利用string的函数去操作，总是超时。看了学长的题解才发现其实用取模和整除操作就行。第二点：比较cin，cout和scanf，printf的耗时。提交状态后面的两个数值分别表示内存和耗时。第一个用cin，cout提交的，第二个是用scanf，printf提交的，时间差的不是一点半点，我用了加快cin，cout的语句依旧TLE64。总而言之，以后改过来使用cin，cout来偷懒的毛病，尽量使用scanf，printf。 AC代码 #include&lt...

题目链接 https://ac.nowcoder.com/acm/contest/5881/B 解题思路 五进制思想，一位数有5^1个，两位数有5^2个，……注意一下，--num！！！让取余操作变得随心所欲，尽量记住这个方法！！！ AC代码 仿写大佬代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=110; const ll mod=1e9+7; char mp[]="12359"; ll t,n,m; ll fac[N]; void Create...