2022.1.10 11:59
dfs 可以边通过枚举分支 边进行相应操作
2022.1.15 17:02
结构体排序
Student Stu[100];
bool cmp2(Student a,Student b)
{
return a.id>b.id;//按照学号降序排列
//return a.id<b.id;//按照学号升序排列
}
sort(Stu,Stu+100,cmp2);
2022.1.16 11:30
pair<>用法
#define x first
#define y second
typedef pair<int,int> PII;
vector <PII> cho;
for...
printf("%d%d",cho[i].x,cho[i].y);
2022.1.16 20:15
int 约等于 2*10^9
2022.1.19 14:13
打表 暴搜 推导数学问题
a/b上取整 (a+b-1)/b
2022.1.23 17:19
说明：next_permutation，重新排列范围内的元素[第一，最后一个）返回按照字典序排列的下一个值较大的组合。
返回值：如果有一个更高的排列，它重新排列元素，并返回true；如果这是不可能的（因为它已经在最大可能的排列），它按升序排列重新元素，并返回false。
取 mod n次答案不变
2022.2.12 2:32
scanf， cin 只能访问已经申请的内存空间
2022.2.14 18:38
强制转换错误：
int a_num = get_a_num(b[i]);
int c_num = get_c_num(b[i]);
ans += (long long ) (a_num * c_num);
其中a_num和c_num在括号里计算时已经爆掉 高位溢出 数据已经错了 这个时候再转换也是低位的部分 和原来的不同
正确写法：
int a_num = get_a_num(b[i]);
int c_num = get_c_num(b[i]);
ans += (long long ) a_num * c_num;
隐式自动类型转换 执行算术运算时，低类型(短字节)可以转换为高类型(长字节)；
或者：
long a_num = get_a_num(b[i]);
long c_num = get_c_num(b[i]);
ans += ( a_num * c_num);
注：所有的浮点运算都是以双精度进行的，即使仅含float单精度量运算的表达式，也要先转换成double型，再作运算。
细节看 https://baike.baidu.com/item/%E5%BC%BA%E5%88%B6%E7%B1%BB%E5%9E%8B%E8%BD%AC%E6%8D%A2/1580197
2022.2.15 8:45
二分模板
若为寻找第一个小于taget的下标或者第一个大于taget的下标，可把数组放进a[1]到a[n]间，左右边界设为0到n+1；当没有比taget小的值时，返回0，当没有比taget大的值时，返回n+1，若计算比taget小的个数或者大的个数时不需要特判。
while(l<r)
{
int mid = l + r + 1 >> 1;
if(a[mid] < taget) l = mid; //从taget左边，逼近到第一个小于taget的下标，可以改为 <= ，为逼近到第一个小于等于taget的下标。
else r = mid - 1;
}
while(l<r)
{
int mid = l + r >> 1;
if(a[mid] > taget) r = mid;//从tage右边，逼近到第一个大于taget的下标，可以改为 >= ，为逼近到第一个大于于等于taget的下标
else l = mid + 1;
}
2022.2.15 22:51
Acwing1236 前缀和的用法
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int as[N]; // as[i]表示在A[]中有多少个数小于b[i]
int cs[N]; // cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), a[i] ++ ;
for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]), b[i] ++ ;
for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]), c[i] ++ ;
// 求as[]
for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;
//cnt[x]指的是 a中x这个数值出现的次数
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i]; // 求cnt[]的前缀和
//s[x]指的是 a中小于等于这个数值的总个数
for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];
// 求cs[]
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]];
// 枚举每个b[i]
LL res = 0;
for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i];
cout << res << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/167113/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2022.2.15 23:02
把一个数每一位抠出来
while(x)
{
int a = x % 10;
x /= 10;
//a 可以拿去操作
}
把一个字符串数字 改写成数
for(int i = 0; i < s.size(); i++)
{
x = x * 10 + s[i] - '0';
//x可以拿去操作
}
2022.2.18 12:15
//读取整行数据时用getline(cin , str) 以字符串的形式保存在数组中， //把换行符替换成'\0',getline会读到回车符结束.
//当遇到第一个数用cin读入时，回车符仍在缓冲区中，为防止后续getline读第一行的回车符时，导致
//第一个数据是空，可以在后续加入getchar()或者getline(cin , str)把第一行的回车符读掉，这样
//不会影响后续数据
string line;
int cnt;
cin >> cnt;//读入第一行数据
getchar();
//回车还在缓冲区中，吃回车，防止后续第一个数据为空（也可以使用getline(cin,str).
while(cnt --)
{
getline(cin , line);
cout << line;
}
2022.2.18 13:18
” >> ; scanf()“是会过滤掉前导不可见字符（如 空格 回车，TAB 等）。但当scanf(“%c”)不会跳过空白符号，cin，scanf 以回车，空格，制表结束读取。当在输入区按下回车时，提示程序开始读取缓冲区 getline不会忽略空白字符， 遇到回车符时结束读取。
如1204
int x;
while (cin >> x)// cin 自动跳过前导空白和回车 读到返回1 没读到返回0
a[cnt ++ ] = x;
2022.2.18 15:36
stringstream对象为字符串流，可以将字符串转化成流，再将流读入
用法：stringstream scin(line);//将line写入流里，scin为字符串流
string line;
getline(cin, line);
stringstream scin(line);//将line写入流里
int x ;
while ( scin >> x) //当读入的为文件结束符时，返回0，这样就可以读入所有数据
{
ans[x] ++;
sum_num ++;
}
2022.2.20 2:34
打表：将所有情况通过暴力写入文件（因为本地没有时间限制），再在程序中情况写进数组，一一判定即可
条件表达式该括号还是括号
1 ()优先级最高;
2 ++ – ! & *（解引用）;
3 * /;
4 + - ;
5 == ;
6 < > <= >= ;
7 && 比 || 优先级要高
https://www.cnblogs.com/zhouhappy88/p/7674858.html
是不是倍数 %
// bool leap = year / 400 == 0 || year / 4 == 0 && year % 100;
bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
2022.2.20 15:40
归并排序模板
void merge_sort(int q[] , int l , int r )
{
if(l >= r) return;//如果分割到单一个元素 就返回
int mid = l + r >> 1;//分割中点
merge_sort(q , l , mid);//左边排序
merge_sort(q , mid + 1 , r);//右边排序
int k = 1 , i = l , j = mid + 1 , temp [100010]; //赋值排序两数组的双指针和汇总数组
while(i <= mid && j <= r) //将较小的元素塞进汇总数组
if(q[i] <= q[j]) temp[k ++] = q[ i++];
else temp[k ++] = q[j ++];
while(i <= mid) temp[k ++] = q[i ++];//若右半边已经无元素，将左半边元素塞进汇总数组
while(j <= r) temp[k ++] = q[j ++];//反之亦然
k = 1;
while(l <= r) q[l ++] = temp[k ++];//将汇总排序好的数组复原回排序区间l到r中
}
2022.2.24 16:10
1219移动距离 中可以看出,算曼哈顿距离或者欧几里得距离时可以用编号减一的方法，让下标更好算。下标从第0行第0列开始，这种方式不会影响提到的两种距离的计算结果，当编号为16，宽度为4时，则行为 （16-1）/ 4 = 3；列为（16 - 1）% 4 = 3；即下标为第3行第三列（从0，0）开始算。
#include <bits/stdc++.h>
using namespace std;
int main(){
int w, m, n;
cin >> w >> m >> n;
m --, n --;//序号减1，便于利用公式求行号和列号
int x1 = m / w, x2 = n / w;//行号
int y1 = m % w, y2 = n % w;//求列号
if(x1 & 1) y1 = w - 1 - y1;//特判，是否为奇数行
if(x2 & 1) y2 = w - 1 - y2;
//曼哈顿顿距离
cout << abs(x1 - x2) +abs(y1 - y2) << endl;
return 0;
}
作者：water-lover
链接：https://www.acwing.com/solution/content/9926/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2022.2.25
对于 scanf()，输入数据的格式要和控制字符串的格式保持一致。如scanf(“%d/%d”,&a,&b); 输入时必须按照x/x的格式输入。通过这种方法可以来读入题目中花里胡哨的输入。
如 01/03/02 0开头也可以当作int读入
printf(“%n.mlf\n”,a); n为一共多少位，m为小数后多少位。
格式控制字符串 为 %- 0 m.n l/h 格式字符，% 为格式说明的引导符号，- 为指定左对起输出，0为 指定空位填0，m.n 指定输出域宽及精度，l/h 输出长度的修正，格式字符为指定输出的数据类型。
如 printf(“%d-%02d-%02d\n”, year, month, day);
2022.2.27 13:50
1231航班问题中，没有思考怎么更方便的求时间差就开始做了，结果写了个60进制的加减法，给自己找了很多苦头，debug了很久，在一定时间内找到最方便得写法再开始，最开始想到得写法一般都不好写。（应该化为十进制来计算）。
在相似代码内容复制修改时，一定要检查检查再检查，检查是否全部修改正确，检查复制过后得变量得值是否需要重新赋0，防止变量的值不是预期
如1231中
int h1 , h2 , m1 , m2 , s1 , s2 ,a=0;
scanf("%d:%d:%d", &h1 , &m1 , &s1);
scanf("%d:%d:%d (+%d)", &h2 , &m2 , &s2 , &a);
h2 += (a * 24);
struct time gap1 = time_sub(h1 , h2 , m1 , m2 , s1 , s2 );
a=0;//a一开始应该为0
scanf("%d:%d:%d", &h1 , &m1 , &s1);
scanf("%d:%d:%d (+%d)", &h2 , &m2 , &s2 , &a);
h2 += (a * 24);
struct time gap2 = time_sub(h1 , h2 , m1 , m2 , s1 , s2 );
2022.3.3 11:29
一般dp和二分要看题目是什么题型
数据结构要看涉及到什么操作，每种操作有对应的数据结构来维护
如：如果题目要求对一个数组中的一个元素操作并且求前缀和，用树状数组来求复杂度（logn）
如果用前缀和数组来求，平均复杂度为（n）
2022.3.3 11:36
树状数组 :x的父节点为 x+lowbit[x] ， 其子结点为x-lowbit[x] ， tir[x] =(x - lowbit(x) , x]之间的和
1264题
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n , m , a[N] , tri[N];//原数组a[N] ,树状数组 tri[N];
//计算父子结点距离
int lowbit(int x )
{
return x & -x;
}
//当更新一个数的时候，加上新数和旧数的差值，由于当更新一个数时，tri数组中所有的tri[i]的父节//点，以及父节点的父节点，以及父节点····
都会加上新数和旧数的差值，所以更新tri[i]的值
void add (int x , int v)
{
for(int i = x ; i <= n ; i += lowbit(i) ) tri[i] += v;
}
//求某个位置的数的前缀和，由于tri[i]的值意义是(i - lowbit(i) , i]间内所有值的和，
//所以求第i个数的前缀和为tri[i] + tri[i - lowbit(i)]+tri[i - lowbit(i) - lowbit([i - loegit(i))]....
int query (int x)
{
int sum = 0 ;
for(int i = x; i > 0; i -= lowbit(i)) sum += tri[i];
return sum ;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) scanf("%d" , &a[i]);
//初始化树状数组可以看成把一个 全0的原数组的的树状数组 更新为 第i个位置加a[i]的原数组的树状数组。
for (int i = 1; i <= n; i ++ ) add( i , a[i] ) ;
while(m --)
{
int a = 0 , b = 0 , k = 0;
scanf("%d%d%d" , &k , &a , &b);
//b的前缀和减去a-1的前缀和为区间和。
if(k == 0) printf("%d\n" , query(b) - query(a - 1));
else add(a , b);
}
return 0;
}
2022.3.4 16:31
前缀和数组每次更新都需要更新后面所有的数组，复杂度太高，所以考虑树状数组，虽然也要更新，但是只有logn复杂度。
https://www.acwing.com/problem/content/description/1267/
