C_Basics

恼

1. 符号字符可以直接用hhd输入 无符号u unsigned long long llu
2. int转化为long long（尤其是在加和乘中会经常遇到）时要
3. 一些常见的超大数字
   long long c=0x7fffffff;
   unsigned int d=2147483748;
   int占用4字节，32比特，数据范围为-21474836482147483647 -2^ 312^31-1 10
4. 有除法先讨论0 以及是整数吗 如果发现就是浮点数的运算非必要一定不要出现整除的nt行为（）
   • 但是在比较大小的时候，可以出现除以0，认为是“无穷”即可
5. math函数返回double类型 不要强制转换
6. 存在整形相乘时，注意及时修改中间变量类型，避免数据溢出（二分法找x的平方根）
7. 输出百分号是 %% -如何输出%%? That's imp0ssib1e百分号输出有两个！两个！
8. unsigned int不要用int!一定要全用这个类型！范围不一样！
9. c语言中没有布尔型运算 要输入头文件#include<stdbool.h>
10. 好好扫描他的输出，看看是不是输入坐标也有br的cd空格
12. 浮点数判断大小
13. 注意数据类型 尤其是题给函数 加乘开大 除法看是否浮点数
14. 整除问题标记是否为0（eg连分数）
15. 开数组之前可以思考一下 比方说矩阵的加法 其实不一定非得要开两个数组 或许可以直接计算出结果
16. 余子式新矩阵的下标错了捏
17. 四舍五入输出 加0.5后强制整数阶段转换

基础知识&语句

输出

cout

• 可以智慧地识别出数据类型，不需要人为指定。

  cout << carrots;

printf用法小全

%[标志][最小宽度][.精度][类型长度]type
%S可以打印宽字符串 以两个’\0’为结尾
%e``%E输出科学计数法

-结果左对齐 右边填空格 默认右对齐 左边填空格
+输出符号
0输出前补0直到占满给定列宽
#对八进制和十六进制加前缀 对ef强制输出小数点

printf("%*d",m,1000)可以指定输出最小宽度m
printf("%.*f",m,1000)可以指定输出精度m 整数会自动补0 字符串超过指定长度截断
判断一个数是否为整数并依此保留精度不同printf(“%.*lf\n”,(fabs(ave-(int)ave))<1e-6?0:2,ave);

一些细碎的知识点

数据处理

1. 常用数据类型以及存储范围(单位：字节，一个字节是8位即$2^8$)
   char 1
   short int 2
   (unsigned)int 4 -21474836482147483647 -2^ 312^31-1
   long logn 8 2^ 63
   float 4
   double 8
2. C++提供了一种灵活的标准，确保最小长度

• short不短于16
• int不短于short
• long不短于int，至少32位
• long long不短于long，至少64位
• float至少32位，都变了至少48位（double通常位64位）

3. const限定，在建立变量的同时要对其赋值，否则该常量值不定且无法修改

• 常量存储小数默认使用double类型，如果想得到浮点加后缀f/F，想得到long double加后缀l/L

4. 浮点数表示的范围大于整数，但是运算速度和精度会有所降低

• eg.float类型的数字1.23e+23，对其加1输出不变，因为float只能表示前七位，因而第23位变化对这个值不会有任何影响

基础语句

2. 逻辑语句

• &&优先级大于||
• a<b<c中 关系运算符是左结合的 实质是只要c大于1 该式恒成立

3. 条件运算符

   z=(a>b)?A:B

一个复杂的嵌套举例：根据变量的值输出ab大小关系的陈述语句

printf(“a is %s b”, (a>b) ? “greater than” : (a<b) ? “less than” : “equal to”)

4. switch语句

    switch (n){
       case0:    ;break;
       case1:    ;break;....
   }

   不同的case可以共享同一组语句序列和打印结果 可以写在同一行

5. 函数

6. 格式

   类型名 函数名（参数列表）
   {
   函数体
   }

7. 声明（函数本体可写于程序最后）去掉函数体后加分号

8. 赋值语句：可以连续使用，从右到左赋值

复合类型

数组基础

1. 数组是存放在连续内存空间上的相同类型数据的集合
2. 只能覆盖，无法删除
3. 对于一维数组，内存空间的地址是连续的
4. 对于二维数组，地址并非连续的矩阵，而是row个连续的内存条
5. sizeof()表整个数组所占字节数（字节数/类型长度=数组元素数），如果作用于数组元素，得到以字节为单位的长度
6. int a[10]={1,2,3,4,5},i其中i为偏移量，部分初始化时其余元素为0；只有{}时全设为0；初始化时=可省略
   数组访问中数组名作为表达式的值等于该数组的首地址

一维数组

二分法

1. 有序数组
2. 元素唯一
3. 关键是确定区间两端的开闭
4. 时间复杂度O(log n)；空间复杂度O(n);
   eg. 左闭右闭

   while(l<=r)
   r=mid-1;
   l=mid+1;

字符串

• 需要以空字符\0标记结尾
• 一种简练初始化的方法,

  char tag[] = "I'm Gamer";

基本操作

1. 拼接：cout会把两个用空格、换行符、制表符分隔的字符串直接合并为一个
2. strlen返回字符串长度，只计算可见字符，忽略空字符

• 因而数组长度的长度要加1

3. .size()可以获取vector类型的长度

string类

1. 可以将字符串声明为简单变量
2. 最初创建的是一个长度为0的string对象，读入之后，可以自动调整该对象的长度，但是最后不会加空格

   #include<string>
   string str1;
   string str2 = "panther"; //创造一个初始化过的string对象
   //类似数组初始化： string str2 = {"panther"};
   cin >> str1; //会自动调整大小

3. 可以将一个string对象赋给另一个string对象（数组不能）
4. 可以使用“+”拼接字符串到末尾
5. string变量要在主函数中建立
6. .length()获取字符串长度
7. 简单遍历对比

for(string& str:strs)	生成str对每个值引用，对其操作会影响到原容器
for(string str:strs)	生成str对每个值复制，对其操作不会影响到原容器

输入

cin输入

* 使用空白（空格、制表符、换行符）确定字符串结束的位置
* 输入之后，cin把字符放到数组中，自动在结尾添加空字符

面向行的输入

getline()

1. 回车键输入的换行符来确定输入结尾
2. cin.getline(name,length+1)两个参数调用
3. 不保存换行符，更换为空字符

get()

1. 保留换行符，存储队列
2. 把输入中连续的两航存储在两个数组中:

   cin.getline(name1, length).getlinie(name2, length);

3. 可以根据get()的输出来检查错误，是数组溢出还是正常换行

对比~

%c输入要注意前边加一个空格把所有空格吃掉

scanf("%[^\n]",str);读入一行不包括行尾换行符的字符串作为带查找的字串

getchar()只在回车处停
putchar()输出字符的速度更快,输出的是字符,所以括号里有数字时会自动转换ASCII值
putchar(10)换行

输入方式	特征
gets()	从标准输入文件中读入一行字符，最终字符串不含’\n’ 最后也不会自动加空格 长度就是输入的长度
puts()	在最后额外输出一个换行符
fgets(char *s,int n,stdin)	至多读入n-1个字符，自动添加结尾字符串结束符
fputs(char *s,int n,stdout)	不会额外输出换行符

n均可省略

输入数组就不要加&和[i]

存储日期 定义并竖着初始化日期名 列保证大于最长字符串长度

询问操作

比较字典序 实际上指针指向的是该地址以后的字符串
比较strcmp(str1,str2,num)相等返回0 小于返回负数 大于返回正数 均视为无符号字符

复制memcpy(destination, source,num)返回destination 只负责赋值num个字节全部复制建议用sizeof(source) 不会检查NULL指针
此函数为内存复制函数

查找memchr(str,s,num)在str的前num位中寻找s 返回一个unsigned字符 表示下标（%d）输出即可 找不到返回NULL

strchr(char *str,int c) 在str中查找c首次出现的位置的指针
strrchr(char *str,int c) 在str中查找c最后一次出现的位置的指针

strstr(char *str,char *s1) 在str中查找s1首次出现的位置的指针

查找子串出现的次数

for(char *p=strstr(str,s);p!=NULL;p=strstr(p+1,s))
    sum++;

输出子串区间

char *p=str;
int len=strlen(s);
while((p=strstr(p,b))!=NULL)
{
    int idx=p-a;
    int r=idx+len-1;
    p+=len;
}

修改操作

s+i表示的就是字符串s的第i个字符 也表示自第i个字符向后（包括第i个）

操作	含义
strcat(s,str+i)插入串+插入地址；	将s插入到str的第i位之前，后边的字符向后顺移
strcpy(str+i,s)插入地址+串；	将s插入到str的第i位之前，后边的字符向后顺移
strncat(s,str+i);strncpy(str+i,s);	加了参数n，表示最大许用参数，更安全；

删除第i个字符以后的内容

实现指定位置字符串截断 将截断第一位换成’0’后面就不会输出啦

str[i]='\0';

使用\0相当于截断

删除一个字符串的第i位到第j位

strcpy(str+i,str+j+1);

将s插入到str的第i位之前，后边的字符向后顺移

strcat(s,str+i);
strcpy(str+i,s);

从 str 的第i位开始用s覆盖

覆盖指从第i位开始，将str的字符依次替换为s的字符，如果str长度不够，则向后延长直到s结束，如果长度不到str结尾，则后续字符保留str原字符

int len=strlen(s);
if(len<strlen(str)-i)  memcpy(str+i,s); 
else strcpy(str+i,s);

char strcpy(char dest, const char *src);
功能：把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间
用法：strcpy(s,t);
strcpy会复制\0而memcpy不会
拷贝函数源地址和目标地址不能有任何重叠

char *strcat(char *dest,char *src);
功能：把src所指字符串添加到dest结尾处(覆盖dest结尾处的’\0’)并添加’\0’
用法：strcat(s,t);
strcpy(char *dst,const char *src) 将src复制到dst中
strncpy(char *dst,const char *src,size_t n)

strcat(char *dst,const *src) 将字符串src追加到字符串dst后
strncat(char *dst,const *src，size_t n)

代码	含义
isalnum(int c)	c是否是字母或数字
isalpha(int c)	c是否是字母
iscntrl(int c)	c是否是控制符(0x00~0xlf,0x7f)
isdigital(int c)	c是否是数字
isxdigit()	c是否是16进制数字
islower()	小写字母
isupper()
isgraph()	是否是可打印字符（空格除外）
isprintf()	是否是可打印字符
ispunct()	是否是符号，可打印但非字母数字
isspace()	是否是空白符（’ ‘,’\n’,’\r’,’\t’,’\v’）

容器

map

普通map

1. 头文件

   include <map>

2. 定义&初始化

   map<keytype,valuetype> name;
   //假设存在map名为m
   map<keytype,valuetype> m2(m);
   //创建了m的副本m2
   map<keytype,valuetype> m3(m.begin(),m.end());
   //创建了map的对象m3，存储迭代器内指定范围的Entry（此处是整个m）
   std::map<std::string, int> mymap = {
           {"alpha", 0}, {"beta", 0}, {"gamma", 0}};//初始化

元素访问

• 下标[]和at()操作只能用于非const的map和unordered_map
• []访问不会做下标检查，对于不存在的key会设定value为默认值（一般为空/False）
• at()访问会做下标检查，不存在key时报错

  mymap[key] = value;
  mymap.at(key) = value;

元素修改

1. 下标[]

• 用下标访问不存在的元素会自动添加，用下标访问存在的元素时会覆盖原元素

2. insert()

   //插入单个值
   map.insert(pair<keytype,valuetype>(key,value));
   map.insert(make_pair(key,value));
   //指定位置插入，不同位置的效率不同，涉及到重排
   std::map<char, int>::iterator it = mymap.begin();
   mymap.insert(it,std::pair<keytype,valuetype>('b',300));
   //范围内多值插入
   std::map<keytype,valuetype>map2;
   map2.insert(mymap.begin(),mymap.end());
   //列表形式插入
   map2.insert()({{'d',100},{'e',200}});

   注意，insert插入位置已经存在值时，插入失败，value保持原值。
3. erase()

   mymap.erase(0);//删除key为0的元素
   mymap.erase(mymap.begin());//删除迭代器指向的位置元素

4. count(k)
   查找关键字k出现的次数
5. find(k)
   查找元素，存在时返回指向该key的迭代器；不存在时返回迭代器的尾指针，即mymap.end()/-1;

unordered_map

• 所有元素都是pair（对组）
• pair中第一个元素为key，做索引；第二个元素为value;
• 不允许有重复元素，自动开链法储存
• 底层结构是哈希表

修改操作

操作	含义
mp[key].pishback()	把源字符串放在相同的key对应的val

访问操作

循环map，获取每个键值对的key和val

actor<vector<string>> ans; //建立一个容器，用于储存结果
for(unordered_map<string,vector<string>>::iterator it=mp.begin();it!=mp.end();it++)
//unordered_map<string,vector<string>>::iterator 等价于auto
ans.push_back(it->first);//获取key
ans.push_back(it->second);//获取val

vector(向量类型)

一个很好的入门教程

• 是一种容器，可以容纳许多类型的数据
• 动态数组，封装好的类
• 头文件#include<vector>

初始化

尖括号内可以是任何合法的数据类型

结构体

基本操作

1. 定义

   typedef struct sentence{
   	int l,x;
   	char s[10005];
   }sen; 

2. 初始化
   {}来初始化，空括号可以将每个元素置为0；
3. 不允许缩窄转换

排序

其中sen为类型名 x为比较量

只是用于整数大小比较

int compare(const void *e1, const void *e2)
{
return ((sen *)e1)->x - ((sen *)e2)->x;
}
qsort(name, n, sizeof(type), compare);

浮点型+字符串比较

int compare(const void *e1, const void *e2)
{
	if((((star *)e1)->d - ((star *)e2)->d)>eps)
		return 1;
	else if((((star *)e1)->d - ((star *)e2)->d)<-eps)
		return -1;
	else return strcmp(((star *)e1)->s,((star *)e2)->s);
}

共用体(Union)

与结构体的区别：共用体只能存储其中一个，在给其中一个变量赋值之后，其余变量的值自动丢失。

• 数据使用多种格式，但不同时使用时，可以节省空间。比如说商品ID中有字符串有数字。
• 主要用途就是节省空间，嵌入式系统里用的多

1. 变量建立

   union one4all
   {
       int int_val;
       long long_val;
       double double_val;
   }

2. 赋值语法与调用与结构体相同

位运算

整型中不会发生数据溢出
对于十六进制 一个f相当于二进制中一个字节1111 如果要批量处理数据的话用十六进制会更简单 一样的东西 把操作的数字变成0x····

正负数判断 看最左侧的一位 0为正 1为负

n&=(n-1)消去最低位的1 用于统计一个二进制数中1的个数

&

1. 对整数x的特定位清0 ：取操作数a使其特定位为0 其余位为1 然后&

   a=((1<<m)|(1<<n)....)
   x=x&(~a)

2. 判断奇偶性 ： 看最后一位是1还是0
   在看某一位是1还是0的时候直接用操作&计算 看等不等于0 让他进入循环就可以

   if((a&1)==1) 奇数

|

1. 将一个数的特定位设为1

   a=a=((1<<m)|(1<<n)....)
   x=x|a

^

对一个数的特定位数进行取反

~

3=4
`x&1将一个数x的最低位置0 其他位不变 ~n+1`对一个整数取相反数
· 这是一个对数字的操作 优先级最高

1. 输出二进制数表达

   printf("0B")#或者0b
   while(x!=0)
       	    {
       	 	printf("%lld",~(x%2));
       	 	x=x/2;
       	    }
       	    if(x%2==0) printf("1");
       	    else printf("0");

   八进制前要加0 十六进制前要加0X或0x
2. 一个数的某些位设为0

   x=x&~(1<<m)

< >

将一个数的二进制左右移动 多者溢出
· 在不溢出的情况下 左移一位*2 右移一位/2
左移是很有效的乘二运算
· 对有符号数 左补符号位（算数位移：负数情况下补1）

1. 求平均值(x+y)>>1
2. 求2的n次方（很快而且不会超界）1<<n

综合实例

常用(x>>i)&1获得一个数的补码各位 i从0开始由低到高获得
注意操作对象是补码还是二进制数 如果是二进制数要手动转 不过如果是unsigned int就没事了 但是在相加运算时必须要使用同种类型 否则会超界
注意超界 如果要用longlong应当加后缀1ll

1. 特定位设置
   将二进制的某一位置1

   num|=1<<i;

   置0

   num&=-(1<<i);

   构造一个前i位均为1的数

   int num=(1<<i-1);

把一个无符号整数a的七至十七位赋值为937 21至25位赋值为17

unsigned int a = 0XC305BAD3
a & =~(((1<<11)-1)<<7)//transform 7~17 to 0 and save others
a|=937<<7//赋值
a&=~(((1<<5)-1)<<21)
a|17<<21
printf("a = 0X%X",a)

2. 交换一个数的高位与低位

      unsigned int n;
   cin>>n;
   cout<<(n>>16)+(n<<16);
   # or cout<<((n&0xffff0000)>>16)+((n&0x0000ffff)<<16);

3. 利用按位运算的性质处理数据(一个也不能少)
4. 得到一个数的补码(可补前导0版 以八位为例)
   计算机本身存储的就是补码 所以直接对二进制的存储进行检查就可以！ 所有对二进制的按位操作都是对补码操作！

   for(int i=7;i>=0;i--)
   printf("%d",(x>>i)&1);#自左向右检查每一位是否为0

   补码翻转得到新的数

   for(int i=0;i<=7;i++)
   ans|=((x>>i)&1)<<(7-i);
   printf("%hhd",ans);

5. 反码计算机
   正负数分离
   化归思想 把所有负的都转成正的
   如果是正数，本身就是反码，如果是负数，直接对对应正数取反就能得到反码
   重点是“得到一个数的反码” 对数本身操作

   int n,a,b;
   void print(int k)
   {
   	if(k>=0)
   		printf("%d\n",k);
   	else
   	{
   			printf("-%d\n",~k);
   	}
   }
   int main()
   {
       if(scanf(" -%d",&a))
       	a=~a;
       else
       	scanf("%d",&a);
       if(scanf(" -%d",&b))
       	b=~b;
       else
       	scanf("%d",&b);
       print(a&b);
       print(a|b);
       print(a^b);
       return 0;
   }

数的编码

原码：最高位为符号位（0为正数 1为负数） 其余各位表示数本身的绝对值
反码：正数的反码与源码相同 若为负数 其绝对值的原码的各位取反
补码：正数的原码、反码和补码都相同 若为负数 对其反码加1（若有进位则进位舍弃）

指针

注意

指针运算时要加括号 保证先运算再解引用
指针计算注意不要越界！
指针相减：计算偏移量
指针相加无意义 指针二分mid=low+(high-low)/2
前排指针小

错过的结构设计

2. 在立flag以及数据初始化的时候改变操作要放在判断操作以后
   （eg.驼峰命名法转换 先确定flag是1否 后判定下划线 判断完后要恢复）
3. 异或运算规律：只看1的个数 奇数个1异或是1 偶数个1异或是0 0异或结果都是0

一些规则

循环不变量

二分查找：区间定义

递归、搜索与回溯算法

框架一

int search(int x)
{
  for(int i=1;i<=算符种数n；i++)
   if(satisfy)
   {
      secure the result(include 'x')
      if(x==n-1)
       print the result
      else search(x+1) //继续进行这个元素后的排列
      recover(satisfy to enter the if) 
   }
}

框架二

if(reach the goal print)
else
 for(int i=1;i<=n;i++)
 if(satisfy)
  {
    secure the result 
    search(x+1)
    recover
  }

Examples

1. 全排列：实际上需要找出每一个排列后的全排列

   char s[10],ch[10];
   int n;
   bool p[10];
   void search(int x)
   {
   	for(int i=0;i<n;i++)
   	 if(p[i]==0)     //该字符未参与排列
   	  {
   	  	p[i]=1;      //标记该位置的字符已经参与排列
   	  	ch[x]=s[i];        //存储字符
   	  	if(x+1==n)     //字符串是从0开始记 此时所有位置的字符已经排列完毕
   	  	 cout<<ch<<endl;
   	  	else
   	  	 search(x+1);    //让下一个字符作为后一个排列的第一个进行全排列
           p[i]=0;         //只有本排列中参与的字符才会标记为已参与
   	  }
   }
   int main()
   {
   	cin>>s;
   	n=strlen(s);
   	search(0);
   	return 0;
   }

2. 最大公因数gcd

   int gdc(int m,int n) //前提：n＞m 条件-真-假
   {return n%m==0?m:gdc(m,n%m)} //n与m和m与n%m公因数相同捏

3. 爬楼梯
   法一 找出基础方法 每层递归一直计数到底层
   实际上仍带有p[x]判定

   int n,p[x];
   int t(int x)
   {
       if(p[x]) return p[x]; //如果本层走法数已算出 直接返回走法
   	if(x==1) return p[x]=1;
   	if(x==2) return p[x]=2;
   	return p[x]=t(x-1)+t(x-2); //每一层走法数=少一层全走法数+少两层全走法数
   }
   int main()
   {
       scanf("%d",&n)   //在一直有输入的情况下持续循环 
   	   cout<<t(n)<<endl;
       return 0;
   }

   法二 实际上是直接累加

   void t(int x)
   {
       if(x==1) ans++;
       if(x==2) ans+=2;
       else t(x-1),t(x-2);
   }

4. 汉诺塔问题

   int n,f[25],ans,x;
   char a,b,c;
   char t(int n,char a,char b,char c)
   {
   	if(n>1)
   	 t(n-1,a,c,b);
   	cout<<a<<"->"<<n<<"->"<<b<<endl;
   	if(n>1)
   	 t(n-1,c,b,a);
   }
   int main()
   {
       cin>>n>>a>>b>>c;
       t(n,a,b,c);
   	return 0;
   }

5. c数简单递归 但是记忆

   long long ans,x[20];
   long long c(int n)
   {
   	long long sum=0;
   	if(n==0 || n==1) return 1;
   	if(x[n]) return x[n];
   	for(int i=0;i<n;i++)
   		sum+=1ll*c(i)*c(n-i-1);	
   	x[n]=sum;
   	return sum;
   }

肖老师说

局部视角在于数数 整体视角在于坐标
注意分解问题
数学问题建议下标与平时习惯一致

常量重在表达 变量重在类型
整型重在范围 浮型重在精度
函数重在接口 递归重在调用
内存重在管理 区分数组指针

int sprintf(charbuf,charformat[,argument]…);
例：
int m;
double x;
char buf[32];
scanf(“%lf%d”,&x,&m);
sprintf(buf,”%%.%df\n”,m);
printf(buf,sin(x));
printf是按格式把输出送到屏幕上
sprintf是按格式把输出送到buf对应的字符数组中
sprintf常用于需要动态生成字符串的场合

int sscanf(const char *buf, char *format [, arg]…);
例：
int day, year, h, m, s;
char mon[4], zone[6];
char buf[] = “12/Nov/2020:12:15:00 +0800”;
sscanf(buf, “%d/%3c/%d:%d:%d:%d %s”, &day, mon, &year, &h, &m, &s, zone);
mon[3] = ‘\0’; // 什么作用？
printf(“%d\n%s\n%d\n%d\n%d\n%d\n%s”, year, mon, day, h, m, s, zone);
scanf 是按要求的格式从键盘输入数据到对应的地址（变量地址或数组）
sscanf 是按要求的格式从 buf 读入数据（也是在<stdio.h>里定义）
返回值也是成功读入的字段数，一般弃之不用