牛客练习赛-C-梦迹
题目:梦迹这道题和用树状数组求逆序对那道题目类似,都是把数组值作为树状数组下标,效果等价于权值线段树,本质上是一道树状数组的简单题。 每一个数字为答案的贡献等于getsum(W-num) 因此修改数字时就可以先减去修改前的贡献,加上修改后的贡献,树状数组的维护上,如果数字从a变为b,就把a位置加上-1,b位置加上1即可 考虑答案是否爆int,最差情况是n*(n-1)/2,到1e10,开longlong,其次注意树状数组下标从1开始,而题目a[i]从0开始,因此加上值为1的偏移量
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)#define endl '\n'#define int lo ...
LeetCode162-寻找峰值
LeetCode162-寻找峰值 二分找索引,对于mid,如果处于上坡,则答案在右边,如果处于下坡,答案在左边,如果处于低谷,答案任意,如果处于峰顶,即为答案。 注意特判0和nums.szie()-1两个位置
1234567891011121314151617181920212223class Solution { public: int findPeakElement(vector<int>& nums) { int l = 0, r = nums.size()-1, mid; int res; while(l <= r) { mid = (l + r) / 2;// cout << nums[mid] << endl; if((mid == 0 || nums[mid] > nums[mid - 1]) && (mid == nums.size() - ...
考研这一年
2020年,我考研的一年
1月1日,我正式开始考研我开始准备英语长难句,跟刘晓燕老师的语法课,每天跟群里面发的每日一句,坚持背单词,当时用app+实体书结合的方法进行背诵,A4纸的方法尤其有效,记得由于当时还是寒假在家,动力不足,每天有效学习时长可能只有6个小时左右,所以会花很多时间来背诵单词,当时我非常想考一所985院校,但也不清楚自己的实力,不了解考研流程,所以定了重庆大学这个984.5,有了目标,就有了动力,我从没有断过每日单词打卡,这个习惯我一直保持到10月3日,连续打卡301天,这是我考研路上引以为傲的一项战绩。我深知高数的重要性,所以很早就开始跟汤家凤的基础课,买了他的1800,每天下午都会听一会,做点题,但不多,整个寒假也只是过完了前3章(几乎没咋学)
3月初,开学考研步入正轨我开始提高每日学习时长,能翘的课都翘了,还发现了一个学习圣地,不需要预约,贼适合考研,强过图书馆一万倍,我把考研书籍搬到教室占位,当时的书籍很少,竟然都不需要书立,当时上午学习英语,其余时间留给数学,记得刚开始英语真题时,感觉题目贼难,文章单词都认识,放在一起就不会,题目也是很坑,当时每道阅读题 ...
Git命令
.gitnore文件配置忽视规则
12/文件夹 #忽略此文件夹!/文件夹 #表示此文件夹不忽略
123456789git init //初始化为git仓库git status //查看状态git add file1 file2 //未跟踪或改变文件推送到暂存区git add. //添加所有文件到缓存区git commit -m "备注信息" //将暂存区的文件提交到本地仓库git remote add origin "https://....git" //将本地仓库关联到远程仓库,origin是默认的代表远程仓库在本地的名称git remote -v //查看远程仓库在本地的名称及地址git pull --rebase origin master //和远程仓库的master分支建立联系git push -u origin master //推送到远程仓库,origin代表远程仓库,master代表本地分支
Leetcode-82 含有重复元素集合的组合
1234567891011121314151617181920212223242526272829303132class Solution { public: vector<vector<int>> res; void dfs(vector<int>& candidates,vector<int>& ans,int sum,int pos, int &target){ ans.push_back(candidates[pos]); if(sum+candidates[pos]==target) res.push_back(ans); else if(sum+candidates[pos]<target){ for(int i=pos+1;i<candidates.size();i++){ if(i>pos+1 && ...
Leetcode-1027最长等差数列
和最长上升子序列类似,这里多加了公差的性质,第一种想法是开一个结构体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 ...
Leetcode-80
写麻烦了,总之就是双指针,一个快指针一个慢指针
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; } } ...
Leetcode-2 两数相加
考察了对链表的使用
特别注意的是在一个自己声明的函数中直接定义变量和使用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) {} ...
Leetcode-5 最长回文子串
动态规划
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; //如果两 ...
纪念我逝去的ACM
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语言学习,我慢慢地爱上了这门语言,还记得当时在控制台打印出杨辉三角时,我内心不可言喻的欣喜。
某天晚上,班群里发来了算法协会的一个招新公告,我当时对 ...