跟这哥们题目一样，可惜当时没刷到，当时状态也不好本来能做的没做出来https://www.nowcoder.com/share/jump/514513942241324692第一题，在一堆字符串里找唯一，顺序和反序相同都算一样的字符串应该用哈希第二题，回溯dp+前缀和第三题，图上有一个节点是湖，小红会在别的节点挖坑，坑和湖相邻坑会变成湖，问最后有多少个湖图的遍历，本来能写出来的，结果忘记喂猫，最后半个小时我的猫在门口嚎叫，分心了导致没写出来。气死个人

跟这哥们题目一样https://www.nowcoder.com/share/jump/514513942240811459时间短题量大，但题目很基础编程第一道括号匹配的变体第二道其实就是按顺序打印数字，但是题目说得云里雾里，看懂废了老鼻子劲第三道树的遍历+路径和感觉是两道easy一道medium

由于路径比节点少，说明没有环，可以认为是树其实就是树（图）的根必须选版最大独立集问题。。。因为对图的储存和遍历不是很熟悉，就把三个方法都实现了一遍。这题真的是medium吗，最大独立集是经典问题没错，可是性能限制真的好严格。用拉链表连递归和std栈都不敢用，手写循环和栈勉强通过，用链式前向星才能稳过，怎么看也是hard吧！临接矩阵通过率9/20，测了下数据量到五万，在创建数组那一步如果用原生数组会栈溢出，用vector会内存超限。除非是很密集的图（比如边数接近n平方的有向图）基本上可以放弃这个方法了。 #include <any> #include <climits> ...

啊啊啊啊孩子出息了我们是第一非常常规的滚动数组优化，要说有什么心思的话就是发现输入小于1000果断采用int16 #include <iostream> #include <sys/types.h> using namespace std; int main() { int n,i,j,t,curi,previ; cin>>n; unsigned int dp[2][n+1],result=0; u_int16_t nums[2][n]; for(j=0;j<2;++j)for(i=0;i<n;++i){...

题目的输入用的节点，目标是遍历节点，所以链表用邻接表（拉链表）存储带缓存的递归循环法性能差别还蛮明显的 #include <iostream> #include <vector> #include <deque> using namespace std; int calc(const int& node, const vector<deque<int>> &children,vector<int>& dp,const string& colored){ if(dp[node]>...

#include <iostream> #include <vector> using namespace std; int main() { int n,t,sum=0; cin>>n; vector<int> nums;nums.reserve(n); //由于背包容量要最后才知道，这道题没有办不保存原数组 while(n-- &&cin>>t){ nums.push_back(t); sum+=t; } if(sum%2){...

#include <iostream> #include <sstream> #include <vector> #include <algorithm> using namespace std; struct envelope{ int height; int width; envelope(int w,int h):width(w),height(h){} bool operator<(envelope& other){ if(width==other.width)return h...

经典问题很多书上都有，比起通常解法用了std的deque容器，可以更方便地操作头尾，不用处理麻烦的下标。 #include <iostream> #include <deque> #include <vector> using namespace std; int calc(vector<int>& dp,deque<int>& houses){ int i; dp[0]=houses[0]; dp[1]=houses[1]; for(i=2;i<dp.size();++i){ ...

先做简单的数据处理，合并相同的数字，然后可以当成偷盗问题 #include <iostream> #include <vector> using namespace std; int main() { //ai<10^4 int n,t,i; cin>>n; vector<int> items; while(n-- && cin>>t){ if(t+1>items.size())items.resize(t+1,0); items[t...

不知道为什么要套背包的做法，其实一维dp数组就够了，时间复杂度O(nV)，空间复杂度O(V) #include <iostream> #include <vector> using namespace std; void printa(vector<bool>& a){ for(auto c:a){ cout<<c<<' '; } cout<<endl; } int main() { int V,n,t,i,j,maxV=0,boundary; cin>&g...

#include <climits> #include <iostream> #include <vector> using namespace std; int main() { int m,n,i,j,curi,previ,t; cin>>m>>n; vector<vector<int>> dp(2,vector<int>(n)) ; cin>>dp[0][0]; for(int i=0;i<m;++i){ curi=i...

这道题的滚动数组因为需要参考值，和背包等问题还蛮不一样的，记一下 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { string s1,s2; //最大公共子序列问题变种，代表替换几次可以使更短为更长的子序列 cin>>s1>>s2; vector<vector<int>> dp(2,vector<int>(s2.size()+1...

Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度大部分答案都是基于这个，但这个数学定理还蛮冷门的，临时遇到肯定不会做，所以再多写了一个暴力解求最长递减子序列还是用传统dp同时用一系列队列来模拟排队过程策略是拿到一个数字看看已有队列能不能放下它如果有，把它放在队尾数字最小的队列之后如果没有，则新开一个队列因为导弹最多一千枚，复杂度倒是没有很夸张 #include <climits> #include <iostream> #include <vector> using namespace std; int main() { ...

#include <climits> #include <vector> #include <iostream> #include <ostream> using namespace std; int main() { int n, t,i,j,k,cur,prev,max_deal; cin >>n>>max_deal; max_deal=min(n/2,max_deal); vector<vector<vector<int>>> dp(2,vecto...