# C++编程模板

⭐️Coding做题步骤

1、选择『数据结构』承载
- 看到题目，先想能用什么数据结构
2、针对『数据结构』设计『算法』

<font style="background:yellow">

# 目录

目录
✔️1.常量定义和变量名
✔️2.格式化输出模板
✔️3.『四舍五入』模板
⭐️C++通用编码方式
⭐️常用内容记忆
⭐️输入输出提升
- 3.1.cin和scanf速度相关
- 3.2.getchar设计read函数快速读入（正负）
⭐️类型转换记忆
- 4.1.函数to_string 将数字转换为string『⭐️C++11』
- 4.2.string→int/long long /double等
⭐️sscanf/sprintf的使用+记忆法
✔️memset和fill
⭐️C++中string⇔C语言风格的字符数组⇔char
✔️int->char->string
编程技巧：逆向思维
ACM课程
模板1-正整数string转化为正整数

[TOC]

# ✔️1.常量定义和变量名

static const int maxn=1e5+5;

# ✔️2.格式化输出模板

while( loop-- )
{
    printf("%d%c",solve[loop], loop?' ': '\n'); 
    //32是空格的ASCII，10是换行符号的ASCII
    //等价于printf("%d%c",solve[loop], loop?: 32 : 10);
    //ASCII炫技，很不妥了，可读性很尴尬
}

1
2
3
4
5
6
7

下面的有2个技巧

#include<bits/stdc++.h>
using namespace std;

//第1个地方，这个方式可以用于区分在本地和OJ
//#define HACV	

int main()
{
	for(int i=0; i<10; ++i)
	{
        //第2个地方，和前面炫技有异曲同工之妙
		printf( (i!=9) ? "num=%d\n" : "Last num=%d\n" , i);
	}

	#ifdef HACV
	system("pause");
	#endif

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# ✔️3.『四舍五入』模板

# 3.1.printf的格式化输出

%3d表示输出3位数，不满3位的高位补『空格』
%03d表示输出3位整数，不满3位的高位补『0』

# 3.2.四舍五入『模板』

+0.5是精髓
但是，一直，不晓得是哪节课，讲解了sqrt在之前还是啥的，要和0.5啥的？哪个技巧没做到笔记（后面找到了笔记，eps）

double num=3.5;
printf("%d\n",num);//直接截取
printf("%d\n", (int)(num+0.5));//四舍五入

//num=(num*pow(10,2)+0.5)/pow(10,2);  
//注意，pow(10,需要保留的位数)
////如果采用『四舍五入』
printf("第%d名选手的最好成绩为:%.2lf\n", (3-loop), num );

1
2
3
4
5
6
7
8

#include<stdio.h>
#include<math.h>
#include<stdlib.h>


struct node
{
	double val[3];
} solve[3];


int main()
{



	//第（3-loop）个选手的成绩
	int loop=3;
	while( loop-- )
	{
		printf("请输入第%d名选手的三次成绩\n", (3-loop) );

		//输入第（tag+1）个成绩
		int tag=0;
		while( tag<3 )
		{
			//如果输入错误则要求强制重新输入
			while( 1 )
			{	
				double num;
				scanf("%lf",&num);
				if( (num-0.0)>0.0001 && (num-10.0)<0.0001 )
				{
					solve[loop].val[tag]=num;
					break;//关键之处：用while(1)和break的组合来弄出那样的效果
				}
				else
				{
					printf("输入错误,请重新输入！\n");
				}
			}//#end while( 1 )

			++tag;
		}//#end while( tag<3 )

			
	}//#end while( loop-- )


	loop=3;
	while( loop-- )
	{
		double num=solve[loop].val[0];
		int i=1;
		for(; i<3; ++i)
		{
			if( num<solve[loop].val[i] )
			{
				num=solve[loop].val[i];
			}
		}
		printf("第%d名选手的最好成绩为:%.2lf\n", (3-loop), num );

	}


	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

# 3.3;注意事项

%d   是直接将double第1位小数截取
    
%.1f 是指将第二位小数直接去掉还是要四舍五入？ 
    答：%.1f (注意是1)对第二位小数，四舍五入！

1
2
3
4

%.2lf竟然是四舍五入的！

以此留念。

1
2
3

C语言printf函数%.2f输出为什么四舍五入实现机制不同？

知乎上回答 (opens new window)

# ⭐️C++通用编码方式

# 1.1.判断某个整数奇/偶

int n;
if( n&1 )
{
    //奇数
}
else
{
	//偶数
}

1
2
3
4
5
6
7
8
9

# 1.2.判断是否`非0`

int n;
if( n )
{
	//n=1，还有n=-1啥的
}

1
2
3
4
5

# 1.3.二维数组遍历技巧『✔️技巧』

使用余数和模来确定二维数组的Row和Col
- 行=pos/col『col表示列』
- 列=pos%col『col表示列』
- 记忆方法：裂(列)开了

vector<vector<int>> ans(row, vector<int>(col));	//row行col列的数组

//注意：pos是从0到『m*n』！
for (int pos = 0; pos < m * n; ++pos) 
{
    ans[ pos/col ][ pos%col ] = nums[ pos/n ][ pos%n ];	//获得ans数组的行和列
}

return ans;

1
2
3
4
5
6
7
8
9

技巧参考自：LeetCode题解 (opens new window)

# 1.4.函数`random_shuffle`打乱『✔️C++』

//1、播种随机数种子，如果不播种，也行，只是每次运行随机都是一样的。 
srand(time(0));
random_shuffle( arr.begin() , arr.end() );//arr是vector
reverse( arr.begin(), arr.end() );//arr是vector

1
2
3
4

# 1.5.给二维的vector初始化row和col『✔️C++』

记忆技巧：

//初始化solve，行为3，列为4
vector< vector<int> >  solve( 3 , vector<int>(4) );

1
2

解释：临时变量vector<int>(4)表示：弄一个含有4个元素的vector<int>

# ⭐️常用内容记忆

# 2.1.常用字符函数『记忆』

注意：is表示，判别是否

常用的『判别7子』
分类函数,所在函数库为ctype.h

//如果是'0'-'9'返回对应的ASCII码，否则返回0『表示不是』
int isdigit( int ch ); 
int isxdigit(int ch);
//若ch是16进制数('0'-'9','A'-'F','a'-'f')返回非0值, 否则返回0

//如果是'a'-'z'返回对应的ASCII码，否则返回0『表示不是』
int islower( int ch ); 
//如果是'A'-'Z'返回对应的ASCII码，否则返回0『表示不是』
int isupper( int ch ); 
//如果是'a'-'z'或者'A'-'Z'，返回对应的ASCII码，否则返回0『表示不是』
int isalpha( int ch ); 

//单词来源：alnum= alpha+num
//如果是'0'-'9'或'a'-'z'或者'A'-'Z'，返回对应的ASCII码，否则返回0『表示不是』
int isalnum( int ch );

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

转换类

//如果是'A'-'Z'返回对应的'a'-'z'，否则返回它本身『也就是不变化』
int tolower( int ch ); 

int toupper( int ch ); //小写转大写

1
2
3
4

测试上面代码

//测试代码
char a='A';
char b='+';
printf("%c %c\n", tolower(a), tolower(b) );

1
2
3
4

# 2.2.字符串比较『记忆法』

记忆方法：类比数学
strcmp(a,b)>0  表示a-b>0  也就是，表示a比b的字典序大
strcmp(a,b)<0  表示a-b<0  也就是，表示a比b的字典序小
strcmp(a,b)==0  表示a-b=0  也就是，表示a和b相同

1
2
3
4

# 2.3.记忆`g++`中的宏✔️

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a=INT_MAX;
    //long long 最大值
	cout<<LONG_LONG_MAX<<endl;
    
    //unsigned long long的最大值
	cout << ULONG_LONG_MAX << endl;
    
    //用signed输出，会溢出，发现是-1
	printf("%lld\n",ULONG_LONG_MAX);
    //用unsigned的输出就不会溢出
	printf("%llu\n", ULONG_LONG_MAX);
	printf("%u\n", INT_MAX);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第2组测试

#include<bits/stdc++.h>
using namespace std;

int main()
{
	cout<<INT_MIN<<endl;
	printf("%d\n",0x80000000);
	cout<<0x80000000<<endl;	//注意：这个将溢出的进行了转型

	cout<<INT_MAX<<endl;
	cout<<0x7fffffff<<endl;
	return 0;
}
/*
-2147483648
-2147483648
2147483648
2147483647
2147483647
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 2.4.常见数据表示的范围

long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615
__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615

最大值的优缺点：

对于无穷大的初始化：
const int inf = 0x3f3f3f3f;
const int INF = 0x7fffffff;

memset(a, inf, sizeof(a)); //正确
memset(a, INF, sieof(a)); //错误

对于int型数组a可以用0x3f3f3f3f初始化，但不可以用0x7fffffff，如果非要把a数组初始化为0x7ffffff，可以用语句 fill(a, a+n, INF); //n为元素个数

1
2
3
4
5
6
7
8

# 2.4.`long long`和`double`在ICPC中

样题：a+b+c+d (opens new window)

# 常见错误答案

错在：范围是可能等于2⁶¹的，那么4个long long相加会超过

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	scanf("%d",&n) ;
	{
		while( n-- )
		{
			long long a,b,c,d;
			scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
			printf("%lld\n", a+b+c+d );
		}
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 解决方案

原因是double能承载更多『记住这个小技巧』

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    int T;
    scanf("%d", &T);
    while(T--) 
    {
        double a, b, c, d;
        scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
        double sum=a+b+c+d;
        printf("%.0lf\n", sum);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 2.5.✔️位运算实现大小写转换

'a'^' '=='A';	//'a'^32=='A'
'A'^' '=='a';	//'A'^32=='a'

1
2

参考题目：2309. 兼具大小写的最好英文字母 (opens new window)

class Solution {
public:
    string greatestLetter(string s) {
        int myHash[256]={0};
        for( auto c : s )
        {
            myHash[c]++;
        }
        string res;
        set<char> help;
        for(int loop=s.size()-1; loop>=0; --loop)
        {
            if( myHash[ s[loop]^' ' ] ) //✔️位运算实现大小写转换
            {
                if( 'A'<=s[loop] && s[loop]<='Z' )
                {
                    help.insert( s[loop] );
                }
                else
                {
                    help.insert( s[loop]^' ' );
                }
            }
        }
        
        if( 0==help.size() )    //防止res+空的help 的元素，报错
        {
            return res;
        }
        else
        {
            return res+=( *help.rbegin() );
        }
        
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# ⭐️输入输出提升

# 3.1.cin和scanf速度相关

sync_with_stdio  site: https://blog.nowcoder.net/hacv

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)



ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
在ACM里，经常出现数据集超大造成 cin TLE的情况。这时候大部分人认为这是cin的效率不及scanf的错，甚至还上升到C语言和C++语言的执行效率层面的无聊争论。
    其实像上文所说，这只是C++为了兼容而采取的保守措施。我们可以在IO之前将stdio解除绑定，这样做了之后要注意不要同时混用cout和printf之类。

在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 3.2.`getchar`设计read函数快速读入（正负）

即输入字符转换成数字，效率高，在输入数据量特别大的时候采用快速读入可以『避免超时』
Q：为什么要写快读，cin，scanf不是很简单吗，难道这很慢吗，真的！（之前Pascal就无所谓，全部都read/readln）
A：我们知道读入字符却是很快的(即getchar)，那么很显然，我们可以用读入字符转数字来加快读入
A：写成inline函数是为了加速读入『C++技巧』

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	//res表示数字本身,NumSign代表正负,最后乘上res就可以了。
	int res=0;
	int NumSign=1;
	char c=getchar();

	//c如果是非数字字符
	while( c<'0'||c>'9' ) 
	{
		//如果c是负号就把NumSign赋为-1
		if( '-'==c )
		{
			NumSign=-1;
		}
		c=getchar();
	}

	while( c>='0'&&c<='9' ) 
	{
		res= res*10 + c-'0';
		c=getchar();
	}
	
	return NumSign*res;//乘起来输出
}


int main()
{
	int n;
	n=read();

	if( n<=0 )
	{
		printf("num=%d\n",n);
		system("pause");
	}
	int solve[n];
	int loop=n;
	while( loop-- )
	{
		scanf("%d",&solve[loop]);
	}

	for(int i=0; i<n; ++i)
	{
		printf("%d%c",solve[i], i!=(n-1) ? ' ' : '\n' );
	}
	
	system("pause");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

# 『关于getchar的轶事』

有人说：getchar()的作用，某大学ICPC有人，每次输入输出用getchar()，从来不用cin和scanf，那个要很久。能够省略0.4s，那次就竟然，就AC了，那次是卡的常数。那次，卡点，AC了
个人观点：
- 这些技巧学学就好了，算法才是硬实力，算法学习不能太推崇对这些这种奇技淫巧的喜爱！
- 编码技巧不应该是算法课程的注重点。
- 我们应该把重点在于如何提高我们的算法能力！
- 那些技巧，能学会也好，但是不要太依赖那些！！

# 『ICPC轶事』

印度尼西亚赛区，出现过一上来就AC，10分钟一道万能程序：
据说原理是：『多次提交，读到答案』

# ⭐️类型转换记忆

# 4.1.函数`to_string` 将数字转换为string『⭐️C++11』

记录一下用到过的int转换成string的两种方法 C++11标准增加了全局函数std::to_string，以及std::stoi/stol/stoll等等函数（这几个就是string转int，long，以及long long啦~） to_string这个函数还是很强大的

string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val)
不仅int可以转换成string，这些都可以哦~

1
2
3
4
5
6
7
8
9
10

注意：to_string函数是C++11才提供的！
LeetCode剑指 Offer 45. 把数组排成最小的数 (opens new window)

bool cmp(string s1 , string s2)
{
    return (s1+s2)<(s2+s1);
}

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> solve;
        int len=nums.size();
        for( int i=0; i<len; ++i )
        {
			//此处使用了
            solve.push_back( to_string( nums[i] ) );
        }
        sort( solve.begin(), solve.end(), cmp);
        string rt;
        for(int i=0; i<len; ++i)
        {
            rt+=solve[i];
        }
        return rt;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 4.2.`string→int/long long /double`等

string str="123.2";

int x=stoi(str);
long x=stol(str);
long long x=stoll(str);

float x=stof(str);
double x=stod(str);
long double x=stold(str);

1
2
3
4
5
6
7
8
9

参考自：《C++程序设计语言》第4部分：标准库，P154

# ⭐️`sscanf/sprintf`的使用+记忆法

记忆方法：借助，scanf和sprintf的使用

long long  n;
scanf("%lld",&n);
printf("%lld",n);

1
2
3

注意，scanf和printf的『尾部不变』之后，修改为（重点记忆）

char str[100];
long long n;
sscanf(  str  ,"%lld",&n);//尾部2个不变
sprintf( str  ,"%lld",n);//尾部2个不变

1
2
3
4

# 1.综述

正则表达式Regex(regular expression)是一种强大的描述字符序列的工具。在许多语言中都存在着正则表达式.
sscanf可以用来实现一些简易的类正则表达式功能，提高对字符串的处理效率，但却没有正则表达式强大,所以如果对于比较复杂的字符串处理,建议使用正则表达式。
注：C语言中sscanf实现的只是的类正则表达式功能，并不是真的支持正则表达式

C++语言中，也只有C++11的时候，才将正则表达式纳入了新标准的一部分

不仅如此，它还支持了6种不同的正则表达式的语法，分别是：ECMASCRIPT、basic、extended、awk、grep和egrep。其中ECMASCRIPT是默认的语法，具体使用哪种语法我们可以在构造正则表达式的时候指定。（本段文字还未考证）

C++11中使用正则表达式，需要include头文件（regex.h）

在DevC++中编译器默认没有开C++11标准的编译，所以显示没有这个头文件。（但你可以在DevC++中自行启用编译选项，加入（-std=c++11）用C++11就有了）

《C和指针》一书中描述P308
scanf函数家族的格式代码都以一个百分号开头，后面可以是：
- （1）一个可选的星号（'*'）
- （2）一个可选的宽度（scanf("%4s",buff)）
- （3）一个可选的限定符
- （4）格式代码

# 2.sscanf的用法

# 2.1.跳过数据

语法：

跳过的话，就是加一个*，然后就可以跳过*后面的那种

比如，%*s或%*d

例: sscanf("1234 5678", "%*d %s", buf);
//这里的d和后面的%之间有个空格
//%d的话就是要一个整数，而<b>%*d就是将整数跳过</b>

1
2
3

例子：

#include<stdio.h>
int main()
{
	char buff[20];
	sscanf("1234 5678","%*d %s",buff); //跳过1234，然后隔一个空格再获取字符串
	printf("%s",buff);
	
	return 0;
}
//输出为：
//5678

1
2
3
4
5
6
7
8
9
10
11

# 2.2.读指定宽度的数据

语法：

比如，%[width]s ，%[width]d 其中，[]表示的是可选（也就是可以省略的意思）

例: sscanf("12345678", "%4s", buf);

//例1 :
#include<stdio.h>
int main()
{
	char buf[20];
	sscanf("12345678","%4s", buf); //从字符串中获取字符串，只要4个字节，存放在buf中
	printf("%s\n",buf);
	return 0; 
} 
//输出：
//1234

1
2
3
4
5
6
7
8
9
10
11

//例2 :
#include<stdio.h>
int main()
{
	int num;
	sscanf("12345678","%3d",&num);
	printf("%d\n",num) ;
	
	return 0;
}
//输出的：
//123

1
2
3
4
5
6
7
8
9
10
11
12
13

//例3 :(综合1和2)
#include<stdio.h>
int main()
{
	int num;
	sscanf("12345678","%*3d%3d",&num);
	printf("%d\n",num) ;
	
	return 0;
} 
//输出：
//456

1
2
3
4
5
6
7
8
9
10
11
12

# 2.3.支持集合操作

注意：只支持获取到字符串中去，不能获取到整数中去！

语法：

%[a-z]表示匹配a到z中任意字符(具有贪婪性——尽可能多的匹配)

%[^a-z]表示读取除a-z以外的所有字符,其实，你可以a-z也可以b-f，他是一个ASCII码范围。

%[aBc]匹配a、B、c中这几个列出了的字符中的，贪婪性

%[^aFc]匹配非aFc的任意字符，贪婪性

//例1：
#include<stdio.h>
int main()
{
	char buf[20] ;
	sscanf ("agkd32DajfDdFF", "%[a-z]",buf);//从字符串中获取输入只要'a''g''k''d'
	printf ("%s\n",buf) ;
	return 0;
}
//结果为agkd

1
2
3
4
5
6
7
8
9
10

//例2：(综合1和3)
#include<stdio.h>
int main()
{
	char buf[20] ;
	sscanf ("agkd32DajfDdFF", "%*[a-z]%[^a-z]",buf);
    //先跳过，然后要ASCII码不是a-z区间的字符	 
	printf ("%s\n",buf) ;
	return 0;
}
//结果为32D

1
2
3
4
5
6
7
8
9
10
11

//例3：(综合2和3)
#include<stdio.h>
int main()
{
	char buf[20] ;
	sscanf ("agkd32DajfDdFF","%*[a-z]%5s",buf);
    //先跳过，然后扫描进5个字节的字符
	printf ("%s\n",buf) ;
	return 0;
}
//结果为32Daj

1
2
3
4
5
6
7
8
9
10
11

本样例，需注意

//例4：
#include<stdio.h>
int main()
{
	char buf[20];
	//一旦碰到我不要的，后面的也不看
	sscanf("ASHJ$12agkd32DajfDdFF","%[^a-z]",buf);
	printf("%s\n",buf);
	return 0;
}
//结果为ASHJ$12

1
2
3
4
5
6
7
8
9
10
11

//例5：
#include<stdio.h>
int main()
{
	char buf[20];
	sscanf("acsfsacssss","%[absc]",buf);
	printf("%s\n",buf);
	
	return 0;
}
//结果为acs

1
2
3
4
5
6
7
8
9
10
11

易错样例：

#include<stdio.h>
int main()
{
	char buf[20] ;
	
	sscanf ("32DajfDdFF", "%[1-9]",buf);//先跳过，然后要ASCII码不是a-z区间的	 
	printf ("%s\n",buf) ;
	//输入32
	 
	int num; 
	sscanf ("32DajfDdFF", "%[1-9]",num);//先跳过，然后要ASCII码不是a-z区间的	 
	printf ("%d\n",num) ;
	// 出错，不支持，扫描到数字中去！！！
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2.3.深刻理解

借此来深刻理解，为什么以前我们要记忆那么多所谓的格式字符了
sscanf和scanf和printf的联系

#include<stdio.h>
int main()
{
	int num;
	sscanf("AAA123BBB456","%*[^0-9]%i",&num); 
	//先跳过，然后扫描整数  
	//其实上面一句等价于，sscanf("AAA123BBB456","%*[^0-9]%d",&num); 
	//也就是%d和%i都是十进制整数的格式字符，我之所以在这用的是%i
	//是为了将正则表达式中类似的语法导入进来，i（integer整数） 
	//此外，我们可以发现，其实我们在scanf扫入和printf输出的时候，也都用了格式字符 
	printf("%d\n",num);
	
	return 0;
}
//结果为123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<stdio.h>
int main()
{
	char c;
	sscanf("AAA123BBB456","%*[^0-9]%c",&c); 
	printf("%c\n",c);
	
	return 0;
}
//结果为1

1
2
3
4
5
6
7
8
9
10

//补充例子
#include<stdio.h>
int main()
{
	char  *line="6161665058";
	char buff[20];
	sscanf(line,"%2[{0|1|6}]",buff);
	printf("%s\n",buff);
	
	return 0;
}
//结果为61

1
2
3
4
5
6
7
8
9
10
11
12

（此处还需补充更好的例子）

# ✔️`memset`和`fill`

# 1.给数组赋相同值—Memset

C语言:头文件string.h
C++：头文件cstring

# 1.1.memset对数组中每个元素赋值

# ⭐️DevC++中memset源代码的声明

void * __cdecl memset(void *_Dst,int _Val,size_t _Size);

所以常用下面的

int a[10];//一维数组
memset(a,0,sizeof(a));

1
2

int a[10][10];//二维数组
memset(a,-1,sizeof(a));

memset(a,0x3f,sizeof(a)); //给int的数字赋值0x3f3f3f3f

1
2
3
4

#include<string.h>
#include<stdio.h>

int main()
{
	char a[10][10];//一维字符数组。
	memset(a,65,sizeof(a));
	
	for(int i=0;i<10 ;i++)
	{
		for(int j=0;j<10 ;j++)
		{
			printf("%c %d\n",a[i][j],a[i][j]);
		}
	}
		
	return 0;
}
//测试结果是循环输出A 65
//原因，65的二进制`0100` `0001‬，它的最后一个字节是也正好是这个  
//然后，我要重复使用这个字节填入char，也正好一个字节，那就正好是它了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 1.2.`memset`底层原理⭐️

原理：取二进制位的最后一个字节，重复使用它给目标赋值。

验证上述的例子：

#include<string.h>
#include<stdio.h>

int main()
{
	int a[10];
	memset(a,-1023,sizeof(a));
	
	for(int i=0;i<10 ;i++)
	{	
		printf("%d\n",a[i]);	
	}
		
	return 0;
}
////测试结果是循环输出16843009

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解释，首先我们看一下**-1023**用int类型表示的补码是

‭1111 1111 1111 1111 1111 1100 0000 0001‬
发现，最后一个字节的bits是0000 0001‬
我们将这个字节重复使用，放到一个int类型中去，也就组成了
0000 0001‬ 0000 0001‬ 0000 0001‬ 0000 0001‬
然后，我们将这个二进制化为十进制发现，是这样的，正好等于16843009

# 1.3.解释一些说法

正是由于，只看那个最后一个字节。
所以，我们在编码的时候，常用用这个初始化全0，或者全-1
因为，他们的补码最后一个字节分别是0000 0000 和 1111 1111
而其他的的最后一个字节的重复使用，对于赋值给不同类型的数据，效果不同，也就比较少用了。
- PS:个人习惯的话，看自己喜欢吧，以前写俄罗斯方块，最初用的数组，后面学了位运算，发现还能这样精确的控制bit，我还优化了一次。（虽说，那样的思维强度比直观的用数组高一点）
  当然，要是从可读性方面来看，还是数组的好一点，位运算的，可能对看自己代码的不友好。
- 此外，memset比C++中fill的速度快，所以，做OJ的一些题目，能用这种提速就尽量用这种。

# 2.给数组赋相同值—fill

C++中头文件#include<algorithm>
fill可以将数组（我记得我看过的有一本书，似乎上面说，数组其实在C++中也是一容器（北大郭炜的书中写的）或容器中的某一段区间赋为某个相同的值。

# 2.1.fill的常用用法

fill的源代码

# ⭐️DevC++中fill源代码的声明

template<typename _FIter, typename _Tp>
void  fill(_FIter, _FIter, const _Tp&);

1
2

和memset不同，这下你想给那个数组赋值是多少就可以任意选，你完全不用从bit的角度来思考很直观。

显然，这个模板函数，和其他模板函数比如sort一样，使用的迭代器
- 而，对于int数组，没有迭代器，就使用指针

int a[5];//一维数组
fill(a,a+5,233);

1
2

OJ中，做图论等一些题目，用邻接矩阵常用下面的方式

const int INF=0x3f3f3f3f;
const int MAXN=200;
int a[MAXN][MAXN];//二维数组
fill(a[0],a[0]+MAXN*MAXN,INF);//注意这里a[0]

//对于STL中的fill的使用是『现在，一切都知道了』
vector<int> help( nums.size() );
fill( help.begin() , help.end() , 1);

1
2
3
4
5
6
7
8

十六进制0x3f3f3f3f
对应二进制
‭0011 1111 0011 1111 0011 1111 0011 1111‬
Tips:看二进制，个人还是习惯直接用Windows的calc

# ⭐️C++中`string`⇔C语言风格的`字符数组`⇔`char`

快速转换『两种方式』
- 受到C语言中sscanf和sprintf的启发

# 5.1.string→字符数组

方法1、用string类的成员函数copy
注意，其实，C语言输入输出和C++输入输出，最好不要混合输入输出，我这样写只是为了论证这样可以

#include<iostream>
#include<string> 
#include<cstring> 
using namespace std;

int main()
{
	
	while(1)
	{
		string str;
		cin>>str;
		char test[10]; 
		memset(test,-1,sizeof(test));
		//上面的memset是我故意，用来让自己注意
		//string转换到字符数组后，末尾的'\0'要手动加，不然就不行
		str.copy(  test ,  str.size()  );
		test[str.size()]='\0';
		 
		printf("%s\n",test);
	} 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法2、string的c_str()和C语言中的strcpy
重点：返回的是“const char*”，不是什么string类

#include<iostream>
#include<string> 
#include<cstring> 
using namespace std;

int main()
{
	
	while(1)
	{
		string str;
		cin>>str;
		char test[10]; 
		memset(test,-1,sizeof(test));
		//上面的memset是我故意，告诉我们这样就不用管这些 
		
		strcpy(  test,  str.c_str()  ); 
		printf("%s\n",test);
	} 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

cplusplus.com上的声明如下

const char* c_str() const;	//返回一个以'\0'结尾的字符串的首地址

Get C string equivalent
Returns a pointer to an array that contains a null-terminated sequence of characters (i.e., a C-string) representing the current value of the string object.
This array includes the same sequence of characters that make up the value of the string object plus an additional terminating null-character ('\0') at the end.
翻译：该数组包括组成字符串对象值的相同字符序列，最后还有一个额外的终止空字符（'\ 0'）

1
2
3
4

从说明来看，我们使用这个进行string到字符数组的转换，我们就不要担心在字符数组后有没有加'\0'了，而如果用string类的成员函数copy()来进行转换，它却没有给我们在最后加'\0'，容易导致一些人误用

# 用法1

//主要要注意，这种const修饰，表示指向位置的内容不准修改。

#include<iostream>

#include<string>

using namespace std;



int main()

{

	string str;

	str="abscv";

	//主要要注意，这种const修饰，表示指向位置的内容不准修改。

	const char * p=str.c_str(); 

	

	printf("%c\n",p[1]);

	printf("%c\n",p[2]);

	

	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 用法2（常用）

用这种复制的方式，就突破了，上一种方式无法修改的桎梏

#include<iostream>

#include<string>

#include<cstring>

using namespace std;



int main()

{

	string str;

	str="abscv";

	

	char p[10];

	//用这种复制的方式，就突破了，上一种方式无法修改的桎梏 

	strcpy(p,str.c_str());

	

	p[1]='K'; 

	printf("%c\n",p[1]);

	printf("%c\n",p[2]);

	

	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 5.2.字符数组→string

string (1)	
	string& operator= (const string& str);
c-string (2)	
	string& operator= (const char* s);
character (3)	
	string& operator= (char c);
initializer list (4)	
	string& operator= (initializer_list<char> il);
move (5)	
	string& operator= (string&& str) noexcept;

1
2
3
4
5
6
7
8
9
10

#include<iostream>
#include<string> 
#include<cstring> 
using namespace std;

int main()
{
	char test[10];
	while(~scanf("%s",test))
	{
		
		string str;
		str=test;//字符数组转换为string ，注意，这个是可以的『因为重载了operator::=()』去
        //参考：http://www.cplusplus.com/reference/string/string/operator=/
		
		printf("%s\n",str.c_str());
	} 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

另一种用构造函数写的，但是有坑，那就是只能在构造的时候，初始化时

#include<iostream>
#include<string> 
#include<cstring> 
using namespace std;

int main()
{
	char test[10];
	while(~scanf("%s",test))
	{
		
		string str(test);//注意——只能在初始化的时候，字符数组转换为string 
		
		//注意——下面这种方式不准！！ 
//		string str;
//		str(test);
		
		printf("%s\n",str.c_str());
	} 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 5.3.转换`string`→`char`

# 5.3.1.`[]`运算符重载

# 1.cplusplus.com（我常用这个）上的声明如下

重点：返回的是“字符”，不是什么string类

const char& operator[] (size_t pos) const;

char& operator[] (size_t pos);

1
2
3

有C++教程上写的声明是，显然是参考的这，并且教程讲参考手册的改为这样，增加了可读性。

const char & operator[] (int n) const;
char & operator[] (int n);
const char & at(int n) const;

1
2
3

# 2.zh.cppreference声明如下

// 元素访问

    constexpr const_reference operator[](size_type pos) const;
    constexpr reference       operator[](size_type pos);
    constexpr const_reference at(size_type n) const;
    constexpr reference       at(size_type n);

1
2
3
4
5
6
7

知乎 (opens new window)上对于constexpr的解释

constexpr是`C++11`引入的，
1、一方面是为了引入更多的编译时计算能力
2、另一方面也是解决 C++98 的 const 的双重语义问题。

在 C 里面，const 很明确只有「只读」一个语义，不会混淆。
C++ 在此基础上增加了「常量」语义，也由 const 关键字来承担，引出来一些奇怪的问题。
C++11 把「常量」语义拆出来，交给新引入的 constexpr 关键字。

在 C++11 以后，建议凡是「常量」语义的场景都使用 constexpr，只对「只读」语义使用 const。

1
2
3
4
5
6
7
8
9

# 5.4.转换`char`→`string`

这个转换是最简单的，但是也是一个坑

char c='a';
string str;	//注意，不能使用string str=c;	//因为没有char→string的函数来转换
str+=c;

1
2
3

# 5.5.C语言字符数组和字符到string类

C语言字符数组和字符到string类都很简单，因为都实现了运算符+=和=的重载

# 1.`+=`重载（字符用）

#include<iostream>
using namespace std;

int main()
{
	char c='9';
	string str="432";
	str+=c;//原型是string& operator+= (char c);
	cout<<str; 
	return 0;
 }

1
2
3
4
5
6
7
8
9
10
11

# 2.`=`重载（字符用）

#include<iostream>
using namespace std;

int main()
{
	char c='9';
	string str="432";
	str=c;//原型是string& operator= (char c);
	cout<<str; 
	return 0;
}
//输出9

1
2
3
4
5
6
7
8
9
10
11
12

# 3.`+=`重载（字符串用）

#include<iostream>
using namespace std;

int main()
{
	char test[]="356425462";
	string str;
	str+=test;//原型string & operator+=(const char * s);
	cout<<str; 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11

# 4.`=`重载（字符串用）

#include<iostream>
using namespace std;

int main()
{
	char test[]="11111";
	string str="432";
	str=test;//原型为 string& operator= (const char* s);
	cout<<str; 
	return 0;
} 
//输出11111

1
2
3
4
5
6
7
8
9
10
11
12

# ✔️关于C++的string建议：

强化string类的成员函数（熟练到，心到码到）
深信服的笔试似乎蛮喜欢考字符串的。
CCF/CSP好像蛮喜欢那些字符串。

# ✔️`int->char->string`

1002. 查找常用字符 (opens new window)

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        int resHash[256];
        memset( resHash, 0x3f, sizeof( resHash ) );
        int tempHash[256];

        for( auto str : words )
        {
            memset( tempHash, 0, sizeof(tempHash) );
            for( auto c : str )
            {
                tempHash[ c ]++;
            }

            for( int i=0; i<256; ++i )
            {
                resHash[ i ]=min( resHash[i], tempHash[i] );
            }

        }

        vector<string> res;
        for( int i=0; i<256; ++i )
        {
            while( resHash[i]-- )
            {
                //注意，我的这种方式从int->char->string
                char c=( i-'A' )+'A';
                string temp;
                temp+=c;
                //注意，我的这种方式从int->char->string
                res.push_back( temp );
            }
        }

        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 编程技巧：逆向思维

反转反转，这种逆向思维，来自高中物理，在代码中也有用到
- 比如，大数加法

# ACM课程

讲解了：

现在的ACM不是很卡内存了所以，上课没讲空间复杂度（这逻辑绝了）现在不讲空间复杂度了，比如长春赛区，开了二维线段树，很大，接近4G也AC了所以现在，一般你的电脑能开多大内存，一般也能给你弄 现在比赛一般不卡内存了。
还是有卡内存的题目，比如幻方矩阵。

比赛也很少考常数（常数级别算法？）的，也就是1-2倍的区别

比赛一般放8倍

暴力算法是我们进步的阶梯

每次自己写快速排序，不。每早，打快排(也就是公众号中所说的，我们要做的事情是熟练)

string公式要记忆，组合数，估计阶乘，估计，可以使得题目简单

2020-09-12 eps经验

负值，不能开根号啦

# 浮点数，计算的精度

是的，开根号有误差第二，在X取整之前需要加0.05，为什么不加？

(int)6.99

//上面强制类型转换后是6而不是7

1, 10, 100, 1000...
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 915, Accepted users: 691
Problem 10238 : No special judgement
Problem description
Let's consider an infinite sequence of digits constructed of ascending powers of 10 written one after another. Here is the beginning of the sequence: 110100100010000... You are to find out what digit is located at the definite position of the sequence.

Input
There is the only positive integer number N in the first line, N < 65536. The i-th of N left lines contains the positive integer Ki - the number of position in the sequence. It's given that Ki < 231..

Output
You are to output N digits 0 or 1 separated with a space. More precisely, the i-th digit of output is to be equal to the Ki-th digit of described above sequence.

Sample Input
4
3
14
7
6
Sample Output
0 0 1 0
Problem Source
USU Open. October'2002 Junior

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# AC的代码

#include<cstdio>
#include<cmath>

const double eps=0.05;

int test(int n)
{
	double x=sqrt(8.0*n+1);
	
	//用这种，0.05的来在强制转换（int)前是为了防止
	//本来经过很多次计算，应该获得是（int)7.00，最终是7
	//但是可能出现(int)6.999就变成了6这样的情况 
	//但是有一说一，有这比较方式，还不如，直接fabs(x-x)<=eps 
	if(0==x-(int)(x+eps))
	{
		return 1;
	}
	else
	{
		return 0;
	}
} 
 
 
int main()
{
	int n;
	int temp;
	while(~scanf("%d",&n))
	{
		while(n--)
		{
			scanf("%d",&temp);
			//可读性极差，。。
			printf("%d%c",test(temp-1),n?32:10);
		}
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 一行区别的WA

#include<cstdio>
#include<cmath>

const double eps=0.05;

int test(int n)
{
    double x=sqrt(8.0*n+1);
    
    //用这种，0.05的来在强制转换（int)前是为了防止
    //本来经过很多次计算，应该获得是（int)7.00，最终是7
    //但是可能出现(int)6.999就变成了6这样的情况 
    //但是有一说一，有这比较方式，还不如，直接fabs(x-x)<=eps 
    if(0==x-(int)(x+eps))
    {
        return 1;
    }
    else
    {
        return 0;
    }
} 
 
 
int main()
{
    int n;
    int temp;
    while(~scanf("%d",&n))
    {
        while(n--)
        {
            scanf("%d",&temp);
            //32是空格的ASCII，10是换行符号的ASCII
            //这样写代码很炫，但是，可读性极差，。。。炫技 
//            printf("%d%c",test(temp-1),n?32:10);
            printf("%d\n",test(temp-1));
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 模板1-正整数string转化为正整数

165. 比较版本号 (opens new window)

for(int i=0; i<version1.size(); ++i)
{
    val=val*10;	//学习
		val+=( version1[i]-'0' );
}

1
2
3
4
5

# C++编程模板

# 目录

# ✔️1.常量定义和变量名

# ✔️2.格式化输出模板

# ✔️3.『四舍五入』模板

# 3.1.printf的格式化输出

# 3.2.四舍五入『模板』

# 3.3;注意事项

# ⭐️C++通用编码方式

# 1.1.判断某个整数奇/偶

# 1.2.判断是否非0

# 1.3.二维数组遍历技巧『✔️技巧』

# 1.4.函数random_shuffle打乱『✔️C++』

# 1.5.给二维的vector初始化row和col『✔️C++』

# ⭐️常用内容记忆

# 2.1.常用字符函数『记忆』

# 2.2.字符串比较『记忆法』

# 2.3.记忆g++中的宏✔️

# 2.4.常见数据表示的范围

# 2.4.long long和double在ICPC中

# 常见错误答案

# 解决方案

# 2.5.✔️位运算实现大小写转换

# ⭐️输入输出提升

# 3.1.cin和scanf速度相关

# 3.2.getchar设计read函数快速读入（正负）

# 『关于getchar的轶事』

# 『ICPC轶事』

# ⭐️类型转换记忆

# 4.1.函数to_string 将数字转换为string『⭐️C++11』

# 4.2.string→int/long long /double等

# ⭐️sscanf/sprintf的使用+记忆法

# 1.综述

# 2.sscanf的用法

# 2.1.跳过数据

# 2.2.读指定宽度的数据

# 2.3.支持集合操作

# 2.3.深刻理解

# ✔️memset和fill

# 1.给数组赋相同值—Memset

# 1.1.memset对数组中每个元素赋值

# ⭐️DevC++中memset源代码的声明

# 1.2.memset底层原理⭐️

# 1.3.解释一些说法

# 2.给数组赋相同值—fill

# 2.1.fill的常用用法

# ⭐️DevC++中fill源代码的声明

# ⭐️C++中string⇔C语言风格的字符数组⇔char

# 5.1.string→字符数组

# 用法1

# 用法2（常用）

# 5.2.字符数组→string

# 5.3.转换string→char

# 5.3.1.[]运算符重载

# 1.cplusplus.com（我常用这个）上的声明如下

# 2.zh.cppreference声明如下

# 5.4.转换char→string

# 5.5.C语言字符数组和字符到string类

# 1.+=重载（字符用）

# 2.=重载（字符用）

# 3.+=重载（字符串用）

# 4.=重载（字符串用）

# ✔️关于C++的string建议：

# ✔️int->char->string

# 编程技巧：逆向思维

# ACM课程

# 浮点数，计算的精度

# AC的代码

# 一行区别的WA

# 模板1-正整数string转化为正整数

# 1.2.判断是否`非0`

# 1.4.函数`random_shuffle`打乱『✔️C++』

# 2.3.记忆`g++`中的宏✔️

# 2.4.`long long`和`double`在ICPC中

# 3.2.`getchar`设计read函数快速读入（正负）

# 4.1.函数`to_string` 将数字转换为string『⭐️C++11』

# 4.2.`string→int/long long /double`等

# ⭐️`sscanf/sprintf`的使用+记忆法

# ✔️`memset`和`fill`

# 1.2.`memset`底层原理⭐️

# ⭐️C++中`string`⇔C语言风格的`字符数组`⇔`char`

# 5.3.转换`string`→`char`

# 5.3.1.`[]`运算符重载

# 5.4.转换`char`→`string`

# 1.`+=`重载（字符用）

# 2.`=`重载（字符用）

# 3.`+=`重载（字符串用）

# 4.`=`重载（字符串用）

# ✔️`int->char->string`