洛谷上部分题目优雅做法
洛谷上部分题目的优雅做法方格取数 题目大意：在的方格中，某些格子填入正整数，其余均为0，从左上角走到右下角，每次经过一个方格就可以拿走该方格上面的数字（拿走后该方格上数字变为0），找两条路径使得取得的数之和最大。分析：可以想到当我们到达任何一处方格时的数字和应该是上一处的数字和加上此方格数字,很容易想到这题可以通过用动态规划解决，最核心的问题是这题的状态定义和转移该怎么设计。证明dp思路：1. 最优子结构：从A到B的路径的数最大值，可以化成更小的从A到C到D的数的最大值，因此满足最优子结构2. 无后效性：未来的数只关注当前数的最大值，之前的走法并不重要，因此满足3.状态和转移：定义一个四维数组，表示第一次到第行列，第二次到第行列的数的最大值，因为到某一个方格的前一个状态只有两种，要么在左边，要么在上面，所以的两条路径只可能是：一、第一次从左边到达，第二次从左边到达；二、第一次从左边到达，第二次从上面到达；三、第一次从上面到达，第二次从上面到达；四、第一次从上面到达，第二次从左边到达。即可以写成：同时注意到如果（i == l && j == k）即第一二次重叠了，...
牛客暑假多校赛第一场总结
牛客暑假多校第一场总结A题题意：有一个小写字符串s,当长度恰好为8且第1，3，5，7个字符是辅音字母（即不是’a’，’e’，’i’，’o’，’u’)，第2，4，6，8个字符是元音字母（即’a’，’e’，’i’，’o’，’u’）时输出“Suspected Virus”，否则输出”Well-Being”。主要算法：模拟解题思路：首先判断s长度是否为8，如果不是就直接输出，然后分别检查奇数位和偶数位的字母是不是元音，最后再输出结果123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>#include<iomanip>using namespace std;void solve(){ string s; cin >> s; int m = s.size(); if(m != 8){ cout << "Well-Being\n";//检查长度是否是8 return...
动态规划
动态规划DP一、背包dp1.1 01背包标准问题：有 n 个物品，重量 w[i]，价值 v[i]，背包容量 C，求最大价值。 二维 1234567891011121314151617181920void solve(){ int t,m; cin >> t >> m; vector<int> time(m+1,0); vector<int> value(m+1,0); for(int i = 1; i <= m; i++){ cin >> time[i] >> value[i]; } vector<vector<int>> dp(m+1,vector<int>(t+1,0)); for(int i = 1; i <= m; i++){ for(int j = 1; j <= t; j++){ if(j >= time[i]){ ...
无标题
双指针1.对撞指针经典场景：有序数组之和的问题1234567891011121314vector<int> twoSum(vector<int>& nums,int target){ int left = 0,right = nums.size() - 1; while(left < right){ int sum = nums[left] + nums[right]; if(sum == target){ return {left,right}; }else if(sum < target){ left++; }else{ right--; } } return {-1,-1};} 如果采用暴力for循环，那么复杂度为O($n^2$)，但...
牛客寒假集训营第6场题解
本文将给出G,H,K题的题解 顺序：K -> H -> G K题题意：从x = 0开始每一轮第一次加m，第二次加n，当该值大于等于目标值z时结束，问最后一次操作是第几个，是第一次则输出0，第二次输出1。 分析：我们可以知道，每一轮结束时都增加了m+n，而最后操作结束时可以看成m + n + m + …… + n (+ m )/(+ n)，我们通过z % (m + n)就可以知道最后一次操作是什么，比如结果为0，意味着结束在n（也就是经历了整轮）；比如结果可能会处于[1,m]之间（因为z <= 这个结果，余数必定在这个区间内），意味着结束在m；如果大于m，则一定结束在n。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include<bits/stdc++.h>using n...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment