//和10背包差不多，多加一个循环，即把某物品选取k次 #include <iostream> #include <vector> using namespace std; int main() { int N, V; cin>>N>>V; int vi,wi; vector<int> vs,ws; for(int i=0;i<N;++i){ cin>>vi>>wi; vs.push_back(vi); ws.push_back(wi); } vector<int> dp1(V+1,0); i...

//简单的dp /* 记dp[i]为以arr[i]为结束的最长的子串长度 那么： dp[i+1] = while(arr[k]<arr[i+1]):max(dp[k0]、dp[k1].....dp[ki]) + 1 //加上自己 最后求最大的dp即可 */ #include <iostream> #include <vector> using namespace std; int main() { int n,arri; vector<int>arr; cin>>n; if(n==0){ cout<<0; return 0; }...

//双指针 /*先对数组进行排序，在头部定义两个指针 一个指向当前数，一个不停向后查找与当前数相差小于k的数 如果第二个指针走不动了，就移到当前数。 最后在加上一些终止的细节处理 */ #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n, k; cin>>n>>k; vector<int> vec; int ai; for(int i=0;i<n;++i){ cin>...

//快速排序模版 class Solution { private: int partition(vector<int>& arr,int low,int high){ int pivot = arr[high]; int i = low-1; for(int j=low;j<high;++j){ if(arr[j]<pivot){ ++i; swap(arr[i],arr[j]); } } swap(arr[i+1],arr[high]); return i+1; } void quicksort(vector<int>& arr,int ...

//和上一题几乎一模一样，只不过把*换成+ //同时base初值为0 #include <iostream> using namespace std; int main() { int q; cin>>q; long long a, b, p; long long base; for(int i=0;i<q;++i){ cin>>a>>b>>p; base = 0; while(b){ if(b%2!=0){ base = base + a; } base = base % p; a += a; a = a%p; b /= 2;...

//快速幂模版 #include <iostream> using namespace std; int main() { int q; cin>>q; long long a, b, p; long long base; for(int i=0;i<q;++i){ cin>>a>>b>>p; base = 1; while(b){ if(b%2!=0){ base = base * a; } base = base % p; a *= a; a = a%p; b /= 2; } cout<<base<<...

/*写了半天没看到要取模.....用大数加法输出的原始数据，但是核心思路是没错的和普通的汉诺塔一样，无非就是加了方向，推导迭代表达即可*/#include <iostream>#include <vector>using namespace std;int num;//大数加法//大端序存储vector<int> sum(vector<int> added, vector<int> add){    //保证长度一致    if(add.size()>added.size()){        while(add.size()!...

/* 代码写的有点乱，核心思路就是 记把n个盘子从left->right的步骤为Dp_left_right[n] 首先需要把头上n-1个盘子right->mid，然后把第n个盘子从left->right 最后再把n-1个盘子mid->right. 则有： Dp_left_right[n] = Dp_left_mid[n-1] + left->right + Dp_mid_right[n-1] 需要注意的是，不管这n个盘子怎么移动，本质上都是从一个from到to， 然后有一个可以操作的space，我们只需要改变这些目标的名字就可以了 假设有一个更换名字的函数f,表达...

//简单的二分查找 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { // write code here if(nums.empty()){ return -1; } int left=0,right=nums.size()-1; int mid; while(...

/* 最短路径，这里使用用回溯的方法求解， 具体思路就是假设在经过某个节点的时候， 当前已走过的路径为path（即使用过的素因子集）， 然后遍历当前节点下可选的素因子，深入搜索， 然后再回溯，当节点id等于n时，记录此时的总和， 与当前最小的总和进行比较更新，然后返回。 */ #include <iostream> #include <vector> #include <unordered_set> using namespace std; vector<int> an; int n,ans0=1e+6; //判断是否是素数 bool ispri...

/* 简单的dfs问题，遍历图中的每个点，如果是是非‘0’点， 则以此点为根节点，沿四个方向搜索它的所有子节点，并把它的子节点置为‘0’ 保证不会重复搜索 */ class Solution { private: int n,m; void dfs(int x,int y, vector<vector<char>>& grid){ //左 if(y-1>=0&&grid[x][y-1]!='0')grid[x][y-1]='0',dfs(x,y-1,grid); //右 if(y+1<m&&grid[x][y+1]!=...

/* 笨方法，仍然用bfs,每次遍历4个方向上的点 */ #include <iostream> #include <vector> #include <queue> #include <utility> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> s(n, vector<int>(m)); // 初始化大小为n行m列的二维向量 vector<vector<int...

/* 与最短路1类似，不过是无权变为有权，同样用dijkstra算法， 对于未访问的点，最短距离为dist[start] + w,并加入队列，这点与无权的问题一样； 但是对于已经访问过的点，需要判断其最小距离dist[pos] 是否小于dist[start] + w, 如果小于则不必操作，如果大于则需要更新值并加入队列处理。 */ #include <iostream> #include <map> #include <vector> #include <queue> using namespace std; int main() { int n...