单链表 // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } // 在链表头插入一个数a void insert(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; } // 将头结点删除，需要保证头结点存在 void remove() { head = ne[head]; }双链表 // e[]表示节点的值，l[]表示节点的左指针，r[]表示节点...

摘花生 题目描述： 给一个矩阵，从左上角走到右下角，每一个点有一个值，每一步你只能往右或者往下走，问怎样走，总和最大。 思路：DP；状态转移方程就是，每一个点他只能有他上访的那个点或者左方的那个点走过来， f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define sc(n) scanf("%d",&n) #def...

题目1 题意：给一个01串，问是1的连续串长度长还是0的连续串长度长，1返回true，0返回false； 签到题 class Solution { public: bool checkZeroOnes(string s) { int n=s.size(); int a=-1,b=-1,cnt1=0,cnt0=0; for(int i=0;i<n;){ if(s[i]=='1'){ while(s[i]=='1') cnt1++,i++; a=max(a,cnt1); cnt1=0; } if(s[i]=='0'){ while(s[i]=='0') cnt0++,i++; b=max(b...

题意：给一段l~r的区间，在这个区间内有多少个数是在二进制下1的个数是奇数，输出这个数https://ac.nowcoder.com/acm/contest/11173/B思路：首先用到二进制下求1的个数，lowbit； bool check(ll n){ ll cnt=0; while(n){ cnt++; n-=lowbit(n); } if(cnt&1) return true; return false; } 然后可以用一个sum函数求，1~n下这样的数有多少个，然后就有以下的表格，来自大佬的题解计算几何当n+1是4的倍数时，有以下规律，n=(n+1)/2;  代码： #inc...

题目描述：  思路：  交换之后的序列一定是长度为n，01序列或者10序列01010101010101010....或者10101010101010101....两种中的一种，所以我们就可以看看给的s串交换到这两种分别需要交换多少次，交换多少次取决于不同的字符有多少个，如果0和1的数量都不一样，那肯定交换不到目标序列，求最小的那个答案  代码： class Solution { public: int get(string a, string b) { int one = 0, zero = 0; for (int i = 0; i < a.size(); i ++ ) if (a[i]...

一. 题目描述：给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗？  结论：求区间和，可以通过前缀和来求出。sum[r]−sum[l−1]就是区间[l,r]的和。如果区间[l,r]的和是k的倍数则有(sum[r]−sum[l−1])%k==0，即sum[r]%k==sum[r]%k。因此，我们可以得到一个结论，对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间。  思考：有了这个结论之后，我们就可以使用两层for循环来计数k倍区间的个数...

1. #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #define m 3 #define MAXLEN 100 typedef char datatype; typedef struct node { datatype data; struct node *child[m]; } node; typedef node *tree; tree CreateTree(); /*按前序遍历顺序建立一棵3度树,返回树根地址 */ void L...

滑雪场设计 题目描述：  思路：其实贪心是不行的，让最低和最高的改成相差17的山峰之后，最高最低可能就改变了，不是最有答案。观察数据比较小，可以枚举，让每一坐山峰都符合17的差值； 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define sc(n) scanf("%d",&n) #define print(n) printf("%d\n",n) #define endl "\n"; #define ios ios:...

unordered_map<int, int> hashtable;  关键功能在于能够快速查找 两数之和  题意：在数组中找出两个数的和等于给定的一定目标值 这题暴力可以，数据很小，主要想学习一下哈希表的做法。 哈希表做法： class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); ++i) { aut...

关于二分  其实就是猜答案，通过验证不断地减小猜的区间  二分模板： int l=0,r=1e9; while(l<=r){ int mid=(l+r)>>1; if(chk(mid)) ans=mid,l=mid-1; else r=mid+1; }另外两种： bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >>...

字符串修改 #include<bits/stdc++.h> using namespace std; const int N=100010; string s; int a[N]; int main(){ int n; cin>>n>>s; s=" "+s; for(int i=1;i<=n;i++){ a[i]=s[i]-'a'+1; if(i&1) { a[i]=(a[i]+i%26)%26; if(a[i]==0) a[i]=26; } else { a[i]=(a[i]+26-i%26)%26; if(a[i]==0...

堆排序 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define sc(n) scanf("%d",&n) #define print(n) printf("%d\n",n) #define endl "\n"; #define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) const int N=1000001; const int MOD = 1e...

Tire树： 又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。 模板： nt son[N][26], cnt[N], idx; // 0号点既是根节点，又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量 // 插入一个字符串 void insert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a...

A. 题意：给你一个数组问它的所有每一个数组子序列的乘积是否一个平方数；子序列：在数组中删除一些数形成的序列。 思路：它的乘积要是平方数，那么它的序列里的每一个数都应该是平方数相乘之后才能够开方。所以只需要判断数组里头的每一个数是否都为平方数就可以， 代码： #include<bits/stdc++.h> using namespace std; const int N=100010; int a[N]; bool check(int n){ int t=sqrt(n); if(t*t==n) return true; return false; } int main(){ int...