知识点：
1、基本输入输出语法： (1)如cin速度比scanf慢 两者遇到空格回车会停止读入 (2)若想读整行需要cin.getline()或gets函数 (3)读到文件尾用scanf()!=EOF等等 (4)占位符‘%’相关格式，如对齐方式，补0等。 2、C/C++库函数以及stl模板 (1)algorithm: sort next_permutation lower_bound/upper_bound (2)queue(priority_queue) stack vector set map基本操作等 3、数据结构 (1)结构体：注意结构体用sort排序，可自定义cmp函数，也可在结构体内重载“<”运算符。 (2)字符串：string类的使用、字典树（用于求解前缀和后缀问题）。 (3)栈、队列：前缀、后缀表达式计算等。 (4)图：两种表示方法，邻接表和邻接矩阵，当n较大时只能采用邻接表。 (5)树：树是一种特殊的图。如按层输出节点等 (6)线段树：基本的单点修改、区间修改、区间查询等。 4、算法 (1)暴力：蓝桥杯又称暴力杯，n<=1e3(1000)，O(n2)的代码大概率能解，如果1e4<=n<=1e6，则要考虑O(n*logn)的算法，不过蓝桥按测试点得分，实在不会，可用O(n2)骗分，骗到了就是赚到了。 (2)思维：不涉及算法，不涉及复杂数据结构，往往几行代码就可以解决，考验思维能力，多训练此类题目即可。 (3)模拟：模拟指根据题目描述，按部就班的写代码就可以AC，通常思路容易看出但是代码量较大，考验细节与心态。 ①大数加减法 ②进制转换 (4)数学问题： ①质数相关：埃式筛、欧拉筛、唯一分解定理等。 ②求最大公因数：要自己会写gcd函数（欧几里得算法） ③快速幂模板，矩阵快速幂模板 ④慢速乘模板（防止相乘的时候数太大爆掉long long） (5)贪心 (6)动态规划： ①最长公共子序列 ②最长上升/不下降子序列 ③背包问题（01背包、多重背包、完全背包等） ④前缀和问题（一维/二维前缀和） (7)搜索：搜索基本是必考的点，包括DFS/BFS，可分别用栈和队列模拟。记忆化搜索也是常考的点，用于避免重复搜索。 (8)图论： ①最短路：最基本要掌握两种求法，floyd算法和dijkstra算法。前者O(n^3)，适用于n不大于500的情况。后者dijkstra用的较多，数据结构实现有两种，邻接矩阵与邻接表，建议用邻接表（具体实现啊哈算法上有）。 ②最小生成树：kruscal算法和prim算法 ③拓扑排序 (9)字符串：回文、kmp算法（字符串匹配算法） (10)其他：并查集、二分/三分算法等
头文件
万能头文件 #include
实数函数及运算符
求幂次
pow(x,y);数据类型下x,y应为double型
移位运算符
x<
STL排序sort函数
void sort(first,last); void sort(first,last,comp); 复杂度为O(nlogn)，排序的范围为[first,last)，包括first不包括last。
STL全排列函数next_permutation()
string s=“bca”; sort(s.begin(),s.end());//字符串内部排序,得到最小的排列"abc" do{ cout< 初始化函数memset() 例如：memset(a,0,sizeof(a)) GCD(最大公约数)和LCM(最小公倍数) int gcd(int a,int b) { return b?gcd(b,a%b):a; } int lcm(int a,int b) { return a/gcb(a,b)*b; } C++字符串函数 find()函数：查找 substr()函数：查子串 按字典序反序排序 bool cmp(string a,string b){ return a+b>b+a; } 素数判断 bool is_prime(long long n){ If(n<=1) return false; For(long long i=2;i<=sqrt(n);i++) { If(n%i==0) return false; } Return true; } 快速幂 采用倍增的原理 int fastpow(int a,int b)//计算a的n次方 { Int ans=1; while(n){ If(n&1) ans*=a; a*=a; n>>=1;//n右移一位，把刚处理过的n的最后一位去掉 } return ans; } 幂运算的结果往往很大，一般题目会要求先取模再输出。根据取模的性质有:an mod m=(a mod m)n mod m。 Ll fastpow(ll a,ll b) { Ll ans=1; A%=mod; while(n){ If(n&1) ans=(ans*a)%mod; A=a*a%modl N>>=1; } Return ans; } 整数二分 Int L=1，R=N; //第一种写法 While(L Int mid=(L+R+1)/2; If(check(mid)) L=mid; Else R=mid-1; } Cout< //第二种写法 While(L Int mid=(L+R)/2; If(check(mid)) L=mid+1; Else R=mid; } Cout< 前缀和 For(int i=1;i Sum[i]=sum[i-1]+a[i]; } For(int i=1;i S+=sum[i-1]*a[i]; } Cout< 素数： 题目-纯质数 bool isPrime(int a){ // 判断是否为质数 if(a == 2){ return true; } if(a < 2 || a % 2 == 0){ return false; } for(int i = 3;i * i <= a;i += 2){ if(a % i == 0){ return false; } } return true; } bool isRealPrime(int a){ // 判断是否为纯质数 if(!isPrime(a)){ return false; } do{ if(!isPrime(a % 10)){ return false; } a /= 10; }while(a != 0); return true; } 日期闰年： if((i%4==0&&i%100!=0)||(i%400==0)){//闰年2月29天} 进制转换: 九进制转十进制,111=199+19+11=; 前缀和： 题目-统计子矩阵！！！ #include #define ll long long int using namespace std; const int N=510; int a[N][N],b[N][N]; int main() { int n,m,k; cin>>n>>m>>k; ll sum,cnt=0; for(int i=0;i for(int j=0;j cin>>a[i][j]; a[i][j]+=a[i][j-1]; } for(int i=0;i for(int j=i;j { sum=0; for(int l=0,r=0;r //这里的lr是上下 sum+=a[r][j]-a[r][i-1];//前缀和 while(sum>k&&l<=r){ sum-=a[l][j]-a[l][i-1]; l++; } if(sum<=k&&l<=r) cnt+=r-l+1; } } cout< return 0; } 状态dp: 计数类型的递推或者递归: 整数拼接：dp优化 #include using namespace std; typedef long long ll; const int N = 1e5 + 5; ll a[N], num[15]; bool vis[15]; ll connect(ll a, ll b) { ll bb = b; while (bb != 0) { a *= 10; bb /= 10; } a += b; return a; } int main(void) { int n, k, res = 0; cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i <= 9; i++) vis[(i * k) % 10] = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { ll x = a[i], y = a[j]; if (vis[y % 10] && connect(x, y) % k == 0) res++; if (vis[x % 10] && connect(y, x) % k == 0) res++; } } cout << res << endl; return 0; } Bitset用法：明码 #include #include #include using namespace std; unsigned int ans; int main() { // bitset<8> bt; // for(int i=0;i<10;i++) // { // for(int j=0;j<16;j++) // { // int a,b; // bitset<8> bt; // cin>>a>>b; // bt=a; // cout< // bt=b; // cout< // cout< // } // } ans=pow(9,9); cout< return 0; } 分治思想的快速排序 填空题 #include int quick_select(int a[], int l, int r, int k) { int p = rand() % (r - l + 1) + l;//产生r到l的随机数 int x = a[p]; {int t = a[p]; a[p] = a[r]; a[r] = t;} int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { a[j] = a[i]; j--; } while(i < j && a[j] > x) j--; if(i < j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return ***quick_select( a,i+1,r,k-i+l-1);*** //填空 else return quick_select(a, l, i - 1, k); } int main() { int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12}; printf("%d\n", quick_select(a, 0, 14, 5)); return 0; } 参考阅读
您阅读本篇文章共花了：
发表评论