前言警告：
1、注意数据的边界，数组不能越界！
2、 时间复杂度
3、开long long
4、注意输出的四舍五入
printf("%d %.0f\n",k,sum*1.0/k);//double类型输出会自动四舍五入；5、让Dev C++支持C++11
先在dev的【工具】里找到【编译选项】
打勾输入:
-std=c++11
C++语法
输出随机数
#include<stdlib.h>
#include<time.h>
int main()
{
int X=17;
srand(time(NULL));
printf("%d",rand()%X);//输出一个0~X-1的随机整数。
return 0;
}print一堆
printf(R"()"); printf(R"( ,----, ,--, ____
,----.. .' .`| ,--.'| ,---, ,----.. ,' , `.
/ / \ .' .' ; ,--, | : ,--, ' .' \ / / \ ,-+-,.' _ |
| : : ,---, ' .',---.'| : ' ,'_ /| / ; '. | : : ,-+-. ; , ||
. | ;. / | : ./ | | : _' | .--. | | : : : \ . | ;. / ,--.'|' | ;|
. ; /--` ; | .' / : : |.' |,'_ /| : . | : | /\ \ . ; /--` | | ,', | ':
; | ; __ `---' / ; | ' ' ; :| ' | | . . | : ' ;. : ; | ; | | / | | ||
| : |.' .' / ; / ' | .'. || | ' | | | | | ;/ \ \| : | ' | : | : |,
. | '_.' : ; / /--, | | : | ': | | : ' ; ' : | \ \ ,'. | '___ ; . | ; |--'
' ; : \ | / / / .`| ' : | : ;| ; ' | | ' | | ' '--' ' ; : .'|| : | | ,
' | '/ .'./__; : | | ' ,/ : | : ; ; | | : : ' | '/ :| : ' |/
| : / | : .' ; : ;--' ' : `--' \| | ,' | : / ; | |`-'
\ \ .' ; | .' | ,/ : , .-./`--'' \ \ .' | ;/
`---` `---' '---' `--`----' `---` '---'
)");\n\
打印转行的格式
#include<iostream>
using namespace std;
int main(){
cout<<"4396 = 28 x 157\n5346 = 18 x 297\n\
5346 = 27 x 198\n5796 = 12 x 483\n\
5796 = 42 x 138\n\
6952 = 4 x 1738\n\
7254 = 39 x 186\n\
7632 = 48 x 159\n\
7852 = 4 x 1963\n";
}
output：
4396 = 28 x 157
5346 = 18 x 297
5346 = 27 x 198
5796 = 12 x 483
5796 = 42 x 138
6952 = 4 x 1738
7254 = 39 x 186
7632 = 48 x 159
7852 = 4 x 1963
\\n ，\"
需要输出特殊符号，则在前面加 ' \ '
printf("printf(\"Hello world!\\n\");\n");
printf("cout << \"Hello world!\" << endl;");output：
printf("Hello world!\n");
cout << "Hello world!" << endl;
%% ，%.nf
%%输出”%“ ，%.nf精确到小数点后n位
(double类型 %.lf )
printf("%.3f%%",m);output：
2.684%
getline(cin,a)与getchar()
输入带空格的字符串
#include<cstring>
string a;
getline(cin,a);//默认遇到/n后截至
getline(cin, b,'E');//设置遇到字符E后停止当前面用了cin，需要用getchar（）接收\n，才能用getline
cin>>n;
getchar();//必须要，否则getline会接收\n
getline(cin,str);在输入结束后，还要输入字符则中间必须跟getchar()吃掉回车
scanf("%c %d",&c,&n);
getchar(); //吞换行回车
scanf("%c %d",&c,&n);
getchar();
cin>>c;while(cin>>a>>b)
用于输入多组数据
unsigned long long n
遇到问题： 一个数在64位二进制补码表示下，一共有多少个1？时用
‘long long’ 只有32位
%x和%o
输出十六进制数 和八进制
int a=11,b=1;
printf("%x",a+b);//十六进制
printf("%o",a+b);//八进制c
14
math库
pow(x,1.0/n)
开x的n次方，开二次方为sqrt（）
#include<cmath>
cin>>n;
double m=pow(n,1.0/3); //开三次方
ceil() 向上取整
取整用于模2余0.5情况
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
if(n%2==0)
cout<<n/2<<endl;
else
cout<<(n+1)/2<<endl;
return 0;
}真向上取整，适用于所有情况：
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
int n;
cin>>n;
int m=ceil(n*1.0/2);
cout<<m<<endl;
return 0;
}日期计算
#include<iostream>
using namespace std;
int main()
{
int y,m,d;
scanf("%d-%d-%d",&y,&m,&d);
d-=2;
if(d<=0)
{
m--;
if(m<1)
{
y--;
m+=12;
}
if(m>=1)
{
if(m==1||m==3||m==5||m==7||m==8||m==10||m==12) d+=31;
else if(m==2)
{
if(y%400==0||(y%4==0&&y%100!=0)) d+=29;
else d+=28;
}
else d+=30;
}
}
printf("%d-%02d-%02d",y,m,d);
return 0;
}自测输入：2020-05-01
实际输出：2020-04-29
排除变量确定阈值
T-排队领水_ (nowcoder.com)
有不少于a个人在他前面，有不多于b个人在他后面，计算一下懒羊羊有多少个可能的位置
#include<iostream>
using namespace std;
int main()
{
int n,a,b;
cin>>n>>a>>b;
if(n-b>a)
cout<<b+1<<endl;
else if(n-a<=b)
cout<<n-a<<endl;
return 0;
}可知前面要大于等于a人，后面小于等于b人，当n-a<=b时，那么对于b这个变量怎么样都成立，写出有关于a的结果表达式即可。同理，当n-b>a时，可以不考虑a。
fib数列
a[1]=1,a[2]=1;
for(int i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];求绝对值abs()
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
int a=1,b=10;
float c=1.2,d=10.9;
double e=1.123,f=10.2;
cout<<"b-a="<<abs(b-a)<<endl;
cout<<"c-d="<<abs(c-d)<<endl;
cout<<"e-f="<<abs(e-f)<<endl;
}b-a=9
c-d=9.7
e-f=9.077
log函数
#include<stdio.h>
#include<math.h>
int main(){
printf("%f\n",log(10)); //以e为底的对数函数
printf("%f\n",log10(100)); //以10为底的对数函数
printf("%f\n",log(8)/log(2)); //计算log2^8,运用换底公式
printf("%f\n",exp(1)); //计算自然常数e
return 0;
}取精确小数
//法一:
if(ans>=11625907.5798&&ans<=11625907.5799)
printf("%.7f \n",ans);
//法二
if(abs(ans-11625907.5798)<0.0001)
printf("%.7f \n",ans);常见经典题
进制转换
二进制，八进制，十进制，十六进制的相互转换【简单易懂】
n进制转10进制
for(int i=0;i<s.size();i++)
{
if(s[i]>'9')num=num*n+s[i]-'A'+10;
else num=num*n+s[i]-'0';
}10进制转n进制
void hw(int sum,int n)
{
int num=0;
int c[10010]={0};
string s="";
while(sum)
{
c[num++]=sum%n; //连除法
sum/=n;
}
for(int i=num-1;i>=0;i--) //对应前面，“从下到上输出”
{
if(c[i]>=10) s+=(char)(c[i]+'A'-10);
else s+=(char)(c[i]+'0');
}
cout<<s<<endl;
}
1019-[NOIP2006]数列
对于n进制问题，我们可以尝试把n进制看出二进制的转换，然后通过%2求出’1‘的个数，以便于得到排序
//k进制 ，第n项
while(n!=0)
{
if(n%2==1){
sum+=pow(k,wei);
}
wei++;
n/=2;
}
判断质数
int zs(int n)
{
if(n<2) return 0;
for(int j=2;j<=sqrt(n);j++)
if(n%j==0) return 0;
return 1;
}负数的进制转换
核心操作与正数一样，需要多解决在C++中取模给出了负数的问题
已知：商*除数+余数=被除数，则样例为 2 * (-7) + (-1) = -15，如何把余数变成正数？
简单的数学思想，加除数减除数即可： 2 * (-7) +（-7）-（-7）+ (-1) = -15 == 3*（-7）+6=-15
1028-[NOIP2000]进制转换
#include<bits/stdc++.h>
using namespace std ;
int main()
{
int n , r ;
long long ans=0 ;
cin >> n >> r ;
int m = n ;
string s ;
while(m)
{
int mod = m%r ;
if(mod < 0)
{
mod -= r ; //余数-除数转为正
m += r ; //加回去保证公式不变
}
char c = '0' + mod ;
if(c > '9') c = 'A'+ (c -'0'-10) ;//转为数字再转字符
s += c ;
m /= r ;
}
if(n==0) s = "0" ;
reverse(s.begin() , s.end()) ;
cout << n << '=' << s << "(base" << r << ')' <<endl ;
return 0 ;
}反转字符串
#include<algorithm>
reverse(s.begin(),s.end());判断回文数
int huiw(int a)
{
int ans=a,sum=0;
while(a)
{
sum=sum*10+a%10;
a/=10;
}
if(sum==ans) return 1;
return 0;
}bool is_p(string n)
{
for (int i = 0; i < n.size()/2+1; i ++)
if (n[i] != n[n.size() - i - 1])
return false;
return true;
}分解质因数
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)//i为质数
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;//最多只有一个大于平方根下n的质因子（两个相乘就大于n了）
cout << endl;
}
蛇形与回型矩阵
回型：
#include <iostream>
using namespace std;
//先初始化数组和想要输入的行数和列数
int q[105][105],n,m;
int main(){
cin>>n;
//定义我们的方向dx，dy，以及方向标”d“
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int x=0,y=0,d=1;
for(int i=1;i<=n*n;i++){
q[x][y] = i;
//每次a，b指下一个填数坐标
int a =x+dx[d],b =y+dy[d];
//考虑如果超出数组边界或者前方即将填的空格已经被填充了，则立即转变方向，改写a，b
if(a<0 || a>=n || b<0 || b>=n || q[a][b])
{
d = (d+1)%4;
a = x+dx[d],b = y+dy[d];
}
x = a,y =b;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cout<<q[i][j]<<" ";
cout<<endl;
}
return 0;
}1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
蛇形
#include<iostream>
using namespace std;
int a[1000][1000];
int main()
{
int n,i,j,sum=0;
cin>>n;
for(i=1;i<=2*n-1;i++)
for(j=i;j>0;j--)
{
//if(j<=n&&i+1-j<=n)
sum++;
if(i%2==0)
a[i+1-j][j]=sum;
else
a[j][i+1-j]=sum;
}
for(i=1;i<=2*n-1;i++)
{
for(j=1;j<=2*n-1;j++)
printf("%6d",a[i][j]);
cout<<"\n";
}
}1 2 6 7 15 16 28
3 5 8 14 17 27 0
4 9 13 18 26 0 0
10 12 19 25 0 0 0
11 20 24 0 0 0 0
21 23 0 0 0 0 0
22 0 0 0 0 0 0
#include<iostream>
using namespace std;
int a[1000][1000];
int main()
{
int n,i,j,sum=0;
cin>>n;
for(i=1;i<=2*n-1;i++)
for(j=i;j>0;j--)
{
if(j<=n&&i+1-j<=n)
sum++;
if(i%2==0)
a[i+1-j][j]=sum;
else
a[j][i+1-j]=sum;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<"\n";
}
}1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
最大公约数与最小公倍数
求最大公约数gcd()
int gcd(int a,int b)
{
int t;
while(a%b)
{
t=a%b;
a=b;
b=t;
}
return b;
}
最小公倍数：(a*b)/gcd(a,b)
实用技巧
string类型用printf输出
加 .c_ str()
#include<iostream>
using namespace std ;
int main(){
string str="hello";
printf("%s",str.c_str()); // 调用c_str()函数
return 0;
}数组去重unique
假设有a = {1, 2, 2, 3, 3, 4, 4, 5, 5, 5} （使用unique必须先排序）
使用 unique() 函数去除重复元素，得到的结果是：a = {1, 2, 3, 4, 5, ?, ?, ?, ?, ?}
unique(a, a + n) 返回去重后数组的尾后迭代器，即指向数组中第一个未定义的元素的位置，a 是一个指向数组首元素的指针，所以 a 表示数组的起始地址，unique(a, a + n)-a则可以得到去重后数组的长度
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
cin>>n;
int a[n] ;
for(int i = 0;i < n;i++){
cin>>a[i];
}
//必须先排序
sort(a,a+n);
for(int i = 0;i < n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
//去重同时更新数组长度
n=unique(a,a+n) -a;
for(int i = 0;i < n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
//去重后的数组长度
cout<<n<<endl;
}
input:
11
4 1 4 4 3 2 2 5 6 7 5
output:
1 2 2 3 4 4 4 5 5 6 7 //排序
1 2 3 4 5 6 7 //去重
7 //去重后数组元素个数
map的使用
#include<map>
//常用
map<int,int> mp;
map<string,int> mp;
mp[a[i]]++;
for(auto it:mp)
{
if(it.first==xx)
cout<<it.second<<endl;
}
//记录字符串
map<int, string> m;
// 用数组方式插入
m[123] = "dd";
m[456] = "ff";
int len=mp.size();获取到map中映射的次数typedef pair<int, int> PII;
map<PII,int> mp;
mp[{x,y}] ++;
用十进制表达二进制(n>>i)%2
long long f(int n)
{
long long sum=0;
for(int i=30;i>=0;i--)
{
sum=sum*10+(n>>i)%2;
}
return sum;
}筛质数
void get_primes(int n)
{
cnt=0;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i)
st[j]=true;
}
}
cout << cnt << endl;
}
//st[i]存储合数，primes[]存储质数memset设置数组值
int A[2];
memset(A, -1, sizeof A); //只能赋0和-1
memset(A, 0, sizeof A);
int a[100];
memset(a , 0x3f , sizeof a); //无穷大赋值
按字节赋值，要想赋值正确，value的值只能是-1或0，因为-1和0转化成二进制后每一位都是一样的，设int型占4个字节，则-1=0XFFFFFFFF, 0=0X00000000。
a的每个元素赋值为0x3f3f3f3f，十进制是 1061109567也就是10^9级别的
对结构体排序
1031-[NOIP2009]分数线划定
对于给出数字
id： f： 9848 90 6731 88 1422 95 8805 95 4162 88要求分数f降序排序，分数相同的则按id升序排序，得到如下：
1422 95 8805 95 9848 90 4162 88 6731 88
struct code{
int a,b;
}s[5010];
int cmp(code x,code y)
{
if(x.b==y.b) return x.a<y.a;//分数相同则按id升序排
return x.b>y.b;
}
for(int i=0;i<n;i++)
cin>>s[i].a>>s[i].b;//用结构体存储数字
sort(s,s+n,cmp);栈stack
#include<stack>
stack<int> q; //以int型为例
int x;
q.push(x); //将x压入栈顶
q.top(); //返回栈顶的元素
q.pop(); //删除栈顶的元素
q.size(); //返回栈中元素的个数
q.empty(); //检查栈是否为空,若为空返回true,否则返回false
set容器
内部元素有序
begin() ,返回set容器的第一个元素
end() ,返回set容器的最后一个元素
clear() ,删除set容器中的所有的元素
empty() ,判断set容器是否为空
size() ,返回当前set容器中的元素个数
s.erase() ，删除一个元素
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
cout<<"set 的 size 值为 ："<<s.size()<<endl;
cout<<"set 中的第一个元素是 ："<<*s.begin()<<endl;
cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;
cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;
s.clear();
if(s.empty())
{
cout<<"set 为空 ！！！"<<endl;
}
return 0;
}set 的 size 值为 ：3
set 中的第一个元素是 ：1
set 中的最后一个元素是:3
set 中 1 出现的次数是 ：1
set 为空 ！！！
大小根堆priority_queue
#include <queue>
priority_queue<int> q //大根堆
priority_queue<int,vector<int>,greater<int> > q //小根堆
#include <iostream>
#include<queue>
using namespace std;
struct node{
int x,y;
bool operator< (const node &b) const{
return this->y >b.y;
}
};
// struct node{
// int x,y;
// bool operator< (const node &b) const{
// return this->x >b.x;
// }
// };
int main()
{
priority_queue<node> que;
que.push((node){1,5});
que.push((node){2,3});
que.push((node){7,-1});
que.push((node){-3,3});
while(!que.empty()){
cout<<que.top().x<<" "<<que.top().y<<endl;
que.pop();
}
return 0;
}大根堆对y从小到大排：
7 -1
2 3
-3 3
1 5
vector的erase
erase() 函数在删除元素时，会将删除位置后续的元素陆续前移，并将容器的大小减 1
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int>demo{ 1,2,3,4,5 };
cout << "size is :" << demo.size() << endl;
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
cout<<endl;
demo.erase(demo.begin() + 1);//删除元素 2
//输出 dmeo 容器新的size
cout << "size is :" << demo.size() << endl;
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}字符串操作
字符串查找find（）
目标字符在字符串中第一次出现位置
str1.find(str2);//从串str1中查找时str2，返回str2中首个字符在str1中的地址
str1.find(str2,5);//从str1的第5个字符开始查找str2
string c="bob";
string s="abobwsdwdbobobobob";
int t=s.find(c);
//t输出1找不到返回-1
if((int)s.find("str")!=-1) cnt++;
//如果找到了则cnt++
//注意用(int)将-1变为数字查找个数
string s="dede",f="666";
ans=0,a=0;
while(str.find(s,a)!=-1)
{
a=str.find(s,a)+f.size()-1;
ans++;
}数字转化为字符串to_string()
string s="";
for(int i=1;i<=20;i++)
{
s+=to_string(i);
}
cout<<s<<endl;1234567891011121314151617181920
字符串转数字stoi()
#include<cstring>
string s = "12345";
int num1 = stoi(s);字符串替换replace()
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
string s="abcdefghijklmn";
string t="1234";
s.replace(2,t.size(),t);//从第2个开始换，t.size为替换长度， t是要替换成的字符串
cout<<s<<endl;
return 0;
}ab1234ghijklmn
sort对字符串长短排序
#include<algorithm>
int cmp(string a,string b){
return a.size()<b.size();
}
string s[5];
sort(s+1,s+5,cmp);字符串插入insert（）
#include<iostream>
using namespace std;
int main()
{
string str="abcdefg";
string s="666";
str.insert(1,s);//在原串下标为1的字符a前插入字符串s
cout<<str<<endl;
string str1="hhhhhhhh";
char c='w';
str1.insert(4,5,c);//在原串下标为4的字符前插入5个字符c
cout<<str1<<endl;
string str2="oooooooo";
string s2="abcdefg";
str2.insert(0,s2,1,3);//将字符串s2从下标为1的b开始数3个字符，分别是bcd，插入原串的下标为0的字符前
cout<<str2<<endl;
return 0;
}
a666bcdefg
hhhhwwwwwhhhh
bcdoooooooo
ascll码表
字符串模拟练习
7-24 估值一亿的AI核心代码 - 团体天梯赛L1
L1-24估值一亿的AI核心代码 (20分)
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string old[100],ne[100];
int o,x;
int main()
{
int n;
cin >> n;
getchar();
string s;
while (n--)
{
getline(cin, s);
old[o++]=s;
//找到其中第一个空格的位置
string res = "";
int i = 0;
while (s[i] == ' ') i++;
for (; i < s.size(); i++) {
if (s[i] == ' ' && i + 1 < s.size() && isalnum(s[i + 1])) {
res += s[i];//只有下面是字母的时候才会选择保留空格
}
if (s[i] != ' ')
res += s[i];
}
//将?转化为!
for (int i = 0; i < res.size(); i++) {
if (res[i] == '?') res[i] = '!';
if (res[i] >= 'A' && res[i] <= 'Z' && res[i] != 'I') {
res[i] = 'a' + (res[i] - 'A');
}
}
ne[x++]=res;
}
// for(int i=0;i<x;i++)
// {
// cout<<old[i]<<endl;
// cout<<ne[i]<<endl;
// }
for(int i=0;i<x;i++)
{
cout<<old[i]<<endl;
for (int beg = 0;; beg++)
{
beg = ne[i].find("can you", beg);
if (beg == -1)break;
//如果独立
if ((beg == 0 || !isalnum(ne[i][beg-1])) && ( beg + 7 == ne[i].size() || !isalnum(ne[i][beg+7])) )
{
ne[i].replace(beg, 7, "A can");
}
}
for (int beg = 0;; beg++)
{
beg = ne[i].find("could you", beg);
if (beg == -1)break;
//如果独立
if ((beg == 0 || !isalnum(ne[i][beg-1])) && ( beg + 9 == ne[i].size() || !isalnum(ne[i][beg+9])))
{
ne[i].replace(beg, 9, "A could");
}
}
for (int beg = 0;; beg++)
{
beg = ne[i].find("I", beg);
if (beg == -1)break;
//如果独立
if ((beg == 0 || !isalnum(ne[i][beg-1])) && ( beg + 1 == ne[i].size() || !isalnum(ne[i][beg+1])))
{
ne[i].replace(beg, 1, "you");
}
}
for (int beg = 0;; beg++)
{
beg = ne[i].find("me", beg);
if (beg == -1)break;
//如果独立
if ((beg == 0 || !isalnum(ne[i][beg-1])) && ( beg +2 == ne[i].size() || !isalnum(ne[i][beg+2])))
{
ne[i].replace(beg, 2, "you");
}
}
for (int j = 0; j<ne[i].size(); j++)
{
if (ne[i][j] == 'A') ne[i][j] = 'I';
}
cout << "AI: " << ne[i] << endl;
}
}算法
二分查找模板
初始化时left=1，right=N+10;(left不用初始化为0）
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
C++ 代码模板：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
C++ 代码模板：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}前缀和
一维前缀和
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];//构造前缀和数组
}
while(q--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
二维前缀和
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &a[i][j]);
//构造前缀和数组
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
//利用容斥原理
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
bfs模板
算法训练营 - 广度优先BFS_图的bfs模板
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N], d[N][N];
int bfs()
{
queue< pair<int, int> > q;
q.push({0, 0});
memset(d, -1, sizeof(d));
d[0][0] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size())//队列不为空
{
PII t = q.front();//取队头元素
q.pop();//出队
for (int i = 0; i < 4; i++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;//当前点到起点的距离
q.push({x, y});//将新坐标入队
}
}
}
return d[n - 1][m -1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
高精度乘法
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
string a,b;
while(t--){
int ans[101]={0};//每一轮都要重置
cin>>a>>b;
int x=a.size(),y=b.size();
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
ans[i+j]+=(a[i]-'0')*(b[j]-'0');//存储竖式上每一位的和
}
}
for(int i=x+y-1;i>0;i--){
ans[i-1]+=ans[i]/10;//进位
ans[i]%=10;
}
for(int i=0;i<x+y-1;i++){
printf("%d",ans[i]);
}
printf("\n");
}
return 0;
}
原理非常简单，模拟乘法运算，a0存最高位，乘法结果得数长度为a.size+b.size-1：
高精度加法
正序，相加，除前导0， 倒序输出
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s1,s2;
cin>>s1>>s2;
int a[5005]={0},b[5005]={0},c[5005]={0};
int x=s1.size(),y=s2.size();
for(int i=0;i<x;i++)
a[i]=s1[x-i-1]-'0';
for(int i=0;i<y;i++)
b[i]=s2[y-i-1]-'0';
int z=max(x,y);
for(int i=0;i<z;i++)
{
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;
}
while(c[z]==0)//去除前导0
z--;
for(int i=z;i>=0;i--)
cout<<c[i];
cout<<endl;
}
}二叉树的构建与使用
//构建树
vector<long long> tree[10010];
for (int i = 2; i <= n; ++i) {
ll parent;
cin >> parent;
tree[parent].push_back(i);
}
//n表示树的大小
//构建n-1个节点的位置，i表示节点，parent表示节点的父亲
//遍历使用
void dfs(ll x)
{
for (auto child : tree[x]) {
dfs(child);
}
}
//可以遍历x为根的子树
dfs(x)