Doraemon's Blog

和最长上升子序列类似，这里多加了公差的性质，第一种想法是开一个结构体dp一维数组，dp[i].val表示以i位置结尾的最长长度，dp[i].cha表示以i位置结尾的子序列公差，你会发现无法进行状态转移，假设i<j<k，dp[k]被dp[j]更新了，并且更新后长度最大，但这不代表i这个位置就一定不是最长等差序列之一，因为可能dp[i].val和dp[j].val只相差1甚至相同，但两者公差不一样，如果后面再来几个公差和dp[i].cha一样的，而你又没有把k位置给添加到序列中，这个状态没有被考虑，导致错误。 因此需要dp[i][j]表示第i个位置添加到末尾并且公差是j的最长长度。 之后再仿照最长上升子序列进行更新即可。 1234567891011121314151617181920int dp[1100][1100];class Solution { public: int longestArithSeqLength(vector<int>& nums) { memset(dp,0,sizeof ...

写麻烦了，总之就是双指针，一个快指针一个慢指针 1234567891011121314151617181920212223242526272829303132class Solution { public: int removeDuplicates(vector<int>& nums) { int len=nums.size(); int cnt=1,L=1; for(int i=1;i<len;i++){ if(nums[i]==nums[i-1]){ if(cnt==2) continue; else cnt++,L++; } else{ L++; cnt=1; } } ...

动态规划 1234567891011121314151617181920212223242526class Solution { public: string longestPalindrome(string s) { int st = 0, L = 1; int len = s.size(); bool dp[1100][1100]; for(int i = 0; i < len; i ++) dp[i][i] = 1; //长度为1的子串都是回文串 for(int i = 2; i <= len; i ++) { //枚举长度 for(int j = 0; j + i - 1 < len; j ++) { //枚举位置 int k = j + i - 1; //结束位置 if(s[j] != s[k]) dp[j][k] = 0; //如果两 ...

考察了对链表的使用 特别注意的是在一个自己声明的函数中直接定义变量和使用new声明内存分配机制是不一样的，直接定义是由系统管理内存的分配与回收，而new则是由程序员自己分配与回收，所以在自定义函数中直接定义变量，然后把指针指向此变量会导致在函数结束后内存回收指针指向无效地址的错误，而new则避免了此问题。 123456789101112131415161718192021222324252627282930313233/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} ...

2021.12.04下午4点，第46届ACM/ICPC南京站圆满结束，同时这也寓意着我的ACM生涯到此也正式画上了句号。 生涯战绩 2020-河南省CCPC-银牌 2020-天梯赛-国三 2021-蓝桥杯-国二 2021-河南省ICPC-银牌 2021-天梯赛-国二 2021-河南省CCPC-银牌 2021-ICPC南京站-铜牌 相遇  我与ACM的接触纯属偶然，甚至对于计算机专业的选择我也并不自信，19年高考失利，伴随着不再复读的决心进入了我的分数可以达到的最好专业，刚入学时，因为对新事物的好奇，我奔走于各个社团之间，希望能丰富自己的大学生活。十月份学校举行百团大战活动，我在许多社团都填了报名表，但不幸的是，没有一个社团愿意收我咱也不知道他们收人的标准是什么咱也不敢问，当时我一直在参与微控科创协会的C语言培训，一周大概有3次，每次2个小时左右，当时我真的是一个纯小白，但经过了一段时间的C语言学习，我慢慢地爱上了这门语言，还记得当时在控制台打印出杨辉三角时，我内心不可言喻的欣喜。   某天晚上，班群里发来了算法协会的一个招新公告，我当时对 ...

通过Beautiful定位标签，获取图片链接，仅限于图片直接内嵌于网页源代码中，有的网站图片链接藏在js文件，无法爬取 1234567891011121314151617181920212223242526#爬取umei.cc中的图片import requestsfrom bs4 import BeautifulSoupdomain = "https://umei.cc/katongdongman/dongmantupian/" #网站地址headers = { "User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.45 Safari/537.36"}res = requests.get(domain, headers=headers)res.encoding = 'utf-8' #防止中文乱码conten ...

使用了request、re(正则)、csv模块 123456789101112131415161718192021222324252627282930#爬取豆瓣Top250的电影名称，评分，导演与演员import requestsimport reimport csvurl = "https://movie.douban.com/top250" #豆瓣链接headers = { # headers，伪装浏览器访问 "User-Agent":": Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.45 Safari/537.36"}obj = re.compile(r'<li>.*?<span class="title">(?P<name>.*?)</span>.*?&# ...

期望: 结果乘以结果出现的概率 $E(X+Y)=E(X)+E(Y)$ $E(XY)=E(X)E(Y)——(X和Y相互独立)$ 问题一描述投硬币，连续出现K次正面的投掷次数期望值。 解法假设已经连续抛出$n-1$次正面，需要$T{n−1}$次。想得到$n$次正面，则再进行一次投掷$Tn=T{n−1}+1+?$ 若硬币为正面则游戏结束，还需要抛0次$Tn=T_{n−1}+1+0.5∗0+?$） 如果硬币为反面，则游戏重来，还需要投掷$0.5∗Tn$次，递推公式如下所示： $Tn=T_{n−1}+1+0.5∗0+0.5∗Tn$ 求出通项公式: $Tn=2^{n+1}+2$ 问题二题目链接 设dp[i]表示i个座位最后坐满人的情况，那么对于n个座位而言，第一个人上车就有n个选择，坐在第一个位置，剩下的就是dp[n-2]，坐在第二个位置，剩下的就是$dp[0]+dp[n-3]$，坐在第三个位置，剩下的就是$dp[1]+dp[n-4]$，以此类推… 求个和，就是$2*sum[n-2]$，sum[n-2]表示前n-2项的前缀和(dp[0]=0) 还要把第一个人加上，因为有n个选择，所以加n，每 ...

POJ2420三分和二分输出答案是l还是r就看中间的判断条件，不满足条件更新的那个值就是要输出的值 12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <cmath>#include <iomanip>#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)#define endl '\n'using namespace std;const int N=1e3+100;const double eps=1e-5;int n;int a[N],b[N];double getdis(double x,double y){ double res=0; for(int i=1;i<=n;i++) res+=sqrt(pow(x-a[i],2)+pow(y-b[i],2)); return res;}double ...

Primality Test根据题意可知，求连续两个质数相加除以2向下取整后是否还是质数，因为是连续的两个质数，所以取中位数后一定不会是质数，1除外 123456789101112131415#include <bits/stdc++.h>using namespace std;typedef long long LL;LL t , n;int main(){ scanf("%lld" , &t); while (t --) { scanf("%lld" , &n); if (n == 1) printf("YES\n"); else printf("NO\n"); } return 0;} Nun Heh Heh Aaaaaaaaaaa给定一个字符串，求这个字符串有多少个子序列满足由前缀nunhehheh和k个a(k>0)组成。 例如nunhehhehaaaa ...