首页
music
关于
推荐
我的B站主页
GitHub主页
Codeforces
Search
1
《美丽数学》读书笔记
49 阅读
2
2023年10月11日创世之初
30 阅读
3
C语言基础
28 阅读
4
冒泡排序
24 阅读
5
排序算法
17 阅读
大事件
读书记录
C语言
SQL
C++
函数
算法
Python
数据结构
登录
Search
标签搜索
C语言
SQL
函数
Mellow-sky
累计撰写
23
篇文章
累计收到
1
条评论
首页
栏目
大事件
读书记录
C语言
SQL
C++
函数
算法
Python
数据结构
页面
music
关于
推荐
我的B站主页
GitHub主页
Codeforces
搜索到
9
篇与
的结果
2024-04-28
前缀和与差分
前缀和公式为 num[i] = num[i - 1] + a[i]差分公式为 diff[i] = a[i] - a[i - 1]前缀和与差分是能互相转换的前缀和数组进行一次差分可得原数组差分数组进行前缀和可得原数组原数组 ---前缀和---> 前缀和数组前缀和数组 ---差分---> 原数组原数组 ---差分---> 差分数组差分数组---前缀和---> 原数组前缀和数组 原数组 差分数组一维前缀和 题目描述 给定义一个数组𝑎,有𝑞+1次询问,对于每次询问:给定两个整数𝑙,𝑟,求出𝑎𝑙 + 𝑎𝑙+1 + ... + 𝑎𝑟的结果。输入描述 第一行一个整数表示样例个数T(1≤T≤10)。对于每组样例:第一行2个整数n(1≤n≤10^5),q(1≤q≤10^5),分别表示数组长度和询问次数。第二行n个整数,表示数组a(−10^9≤ai≤10^9)。接下来q行,每行两个整数r(1≤l≤r≤n)表示询问的区间。输出描述 对于每组样例,一行一个整数表示答案。输入样例1 25 31 2 3 4 51 22 53 47 2-1 9 -10 8 2 6 111 52 7 输出样例1 3147826题解 根据输入的数组,建立一个每次相加前一位的数组如输入的为1 2 3 4 5根据前缀进行和1,1+2=3,3+3=6,6+4=10,10+5=15建立的数组为1 3 6 10 15对于查询的区间(l,r)只需进行算出:r位减去(l-1)位之间的值即可如查询(2,5)之间的和,15-1即是(2,5)区间的和代码样例#include<iostream> #include<vector> using namespace std; using ll = long long; void vol() { ll m, n; cin >> m >> n; vector<ll>ve(m + 1 , 0); for (ll i = 1; i <= m; i++) { cin >> ve[i]; } vector<ll>cop(m + 1, 0); for (ll i = 1; i <= m; i++) { cop[i] = cop[i - 1] + ve[i]; } ll l, r; for (ll i = 1; i <= n; i++) { cin >> l >> r; cout << cop[r] - cop[l - 1] << '\n'; } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll t; cin >> t; while (t--) { vol(); } return 0; }一维差分 题目描述 给定一个长度为n的数组a,和两个整数p,q。先进行p次区间加操作:将区间[l,r]的数字都加上x。再进行q次区间查询操作:求出[l,r]的数字之和。对于每次区间查询操作,输出结果。 输入描述 第一行三个整数n,p,q。(1≤n≤10^5 ,0≤p≤10^5 ,0≤10^5 ≤q)第二行n个整数表示数组a。(−10^9 ≤ai ≤10^9 )接下来p行,每行三个整数l,r,x。(1≤l≤r≤n,−10^9 ≤x≤10^9 )接下来q行,每行两个整数(1≤l≤r≤n)输出描述 对于每次区间查询操作,输出结果。输入样例1 5 1 21 1 1 2 21 4 21 31 5 输出样例1 915题解 根据输入的数组建立一个差分数组如输入1,2,3,4,51-0=1,2-1=1,3-2=1,4-3=1,5-4=1因此建立的差分数组为1,1,1,1,1代码实例#include<iostream> using namespace std; const int N = 1e5+9; using ll = long long; ll a[N], diff[N], num[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n , p , q ; cin >> n >> p >> q ; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1]; while (p--) { ll l, r, x; cin >> l >> r >> x; diff[l] += x; diff[r + 1] -= x; } for (int i = 1; i <= n; i++) a[i] = diff[i] + a[i - 1]; for (int i = 1; i <= n; i++) num[i] = num[i - 1] + a[i]; while (q--) { ll l, r; cin >> l >> r; cout << num[r] - num[l - 1] << '\n'; } return 0; }二维前缀和 二维数组基本原理与一维前缀和几乎相同 注意重叠部分即可题目描述 给定一个n行m列的整数矩阵。 q个询问,每个询问格式为:x1,y1,x2,y2,表示一个子矩阵的左上角和右下角的坐标。对于每个询问,请回答子矩阵的所有数之和。输入格式 第一行包括三个整数n,m,q(1≤n,m≤10^3 ,1≤𝑞≤10^5,1≤q≤10^5 )。接下来n行,每行包括m个整数,表示整数矩阵(每个整数的取值范围为[1,10^5 ])。接下来q行,每行包括四个整数x1,y1,x2,y2(1<=x1<=x2<=n,1<=y1<=y2<=m),表示一个询问的左上角、右下角坐标。输出格式 共q行,第i(1≤i≤q)行输出第i个询问的结果。样例输入1 7 3 23 5 1 6 2 4 7 9 10 4 3 6 3 9 9 6 10 1 9 10 4 2 2 7 32 1 4 2 样例输出1 7731代码实例#include<iostream> #include<vector> using namespace std; using ll = long long; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m, q; cin >> n >> m >> q; vector<vector<ll> >a(n + 1, vector < ll >(m + 1, 0)); ll i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { cin >> a[i][j]; } } vector<vector<ll> >b(n + 1, vector < ll >(m + 1, 0)); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1]; } } while (q--) { ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1] << '\n'; } return 0; }二维差分 题目描述给定一个n行m列的整数矩阵。有q个操作,每个操作格式为:x1,y1,x2,y2,c,其中(𝑥1,𝑦1)、(x2,y2)分别表示一个子矩阵的左上角和右下角的坐标,每个操作将对应的子矩阵的每个元素加上c。请输出进行完所有操作后的矩阵。输入描述第一行包括三个整数n,m,q(1≤n,m≤10^3 ,1≤q≤10^5 )。输出描述共n行,每行包括m个整数,表示进行完所有操作后的矩阵。输入样例14 3 31 5 1 3 3 2 5 3 4 4 4 2 1 2 1 2 22 1 2 3 24 2 4 3 1输出样例11 7 1 5 5 4 5 3 4 4 5 3 代码示例//二维差分 #include<iostream> using namespace std; using ll = long long; const int N = 1e3 + 9; ll a[N][N], diff[N][N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } //差分 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += a[i][j]; diff[i + 1][j] -= a[i][j]; diff[i][j + 1] -= a[i][j]; diff[i + 1][j + 1] += a[i][j]; } } //修改 while (q--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; diff[x1][y1] += c; diff[x2 + 1][y2 + 1] += c; diff[x2 + 1][y1] -= c; diff[x1][y2 + 1] -= c; } //求原数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j]; cout << a[i][j] << " "; } cout << '\n'; } return 0; }
2024年04月28日
5 阅读
0 评论
1 点赞
2024-04-16
类的构造函数与析构函数
构造函数 构造函数的定义 class 类名{ public: 类名();//构造函数 }构造函数无返回类型也不需要写void构造函数会自动调用,无定义时为空实现。因此需要我们定义构造函数进行数据的初始化构造函数可以有参数也可以无参数,因此根据参数的类型构造函数可发生重载,且构造函数只能被调用一次。构造函数可按有无参数分为有参构造函数和无参构造函数 构造函数按类型可分为普通构造函数和拷贝构造函数构造函数参数类型一无参构造函数普通构造函数二有参构造函数拷贝构造函数注意 不要用拷贝构造函数进行初始化匿名对象 编译器会认为book(b2);等于book b2;会造成重定义以下为调用构造函数的实例:#include<iostream> using namespace std; class book { public: book() { cout << "类的无参构造函数" << endl; } book(int a) { b = a; cout << "类的有参构造函数" << b << endl; } book(const book& b) { cout << "类的拷贝构造函数" << b.b << endl; } int b; }; void test() { //调用有三种方法调用 //括号法 book b1; book b2(10); book b3(b2); //显示法 book b4; book b5 = book(10); book b6 = book(b5); //隐式转换法 book b7 = 10; book b8 = b7; } int main() { test(); return 0; }注意括号法的第一个: book b1; 不要在b1后面加(),如果加了会造成二义性,编译器无法识别构造函数的实例中的显示法的book(10)为匿名对象析构函数 析构函数的定义 class 类名{ public: ~类名();//析构函数 }析构函数与构造函数的区别相同 都会自动调用 不同在类名前加"~"析构函数无返回值且无参数,因此不可发生重载析构函数发生在对象的销毁时析构函数主要用于数据的销毁工作以下为调用析构函数的实例:#include<iostream> using namespace std; class person { public: ~person() { cout << "类的析构函数" << endl; } }; void test() { person p1; } int main() { test(); person p2; system("pause"); return 0; }注意:当运行到system("pause");时暂停,p2仍在main函数中,main函数为结束,因此p2为进行销毁,所以p2还未调用析构函数,当按任意键继续时main函数结束,p2内存回收,因此才会调用析构函数打印出信息。
2024年04月16日
8 阅读
0 评论
0 点赞
2024-04-13
各种函数的用法
sort函数 algorithm头文件中的sort函数运用作用: 对范围内元素进行排序语法: 需要声明algorithm头文件sort( first ,last ,comp );其中first与last为起始与终末位置first与last为地址并非值。comp是接收两个元素并返回bool类型的函数,注意并非函数调用,因此在函数名后面无需添加()comp函数不改变值,可以是函数指针或函数对象comp可以省略,当省略时将使用默认排序,默认排序为从小到大排序。 实例:#include<iostream> #include<algorithm> using namespace std; bool comp(int x, int y) { return x > y;//从大到小排序 } int main() { int arr[5] = { 52,23,71,17,89 }; sort(arr, arr+5,comp); for (int i = 0; i < 5; i++) { cout << arr[i]<<" "; } cout<<endl; return 0; }getline函数 作用: 对字符串进行输入 特点: 与cin不同可以读入cin不能读入的空格。 此函数可读取整行,包括前导和嵌入的空格,并将其存储在字符串对象中。 语法: getline(cin, inputLine); inputline是接收输入的字符串string变量的名字。 实例:#include<iostream> #include<string> using namespace std; int main() { string str; getline(cin, str); cout << str << endl; return 0; }
2024年04月13日
7 阅读
0 评论
0 点赞
2024-03-21
C++简单实现扫雷游戏
在test.cpp中测试#include"game.h" void menu() { //打印初始界面 cout << "******************" << endl; cout << "******************" << endl; cout << "****1.开始游戏*****" << endl; cout << "****0.结束游戏*****" << endl; cout << "******************" << endl; cout << "******************" << endl; } void game() { //实现扫雷游戏 //mine中存放雷 char mine[ROWS][COLS] = { '0' };//数组全部初始化为0 //show中存放排查出的雷的信息 char show[ROWS][COLS] = { '*' };//数组全部初始化为* //初始化棋盘 InitBoard(mine, ROWS, COLS, '0'); InitBoard(show, ROWS, COLS, '*'); //打印棋盘 //DisplayBoard(mine, ROW, COL); //DisplayBoard(show, ROW, COL); //布置雷 SetMine(mine,ROW,COL); //DisplayBoard(mine, ROW, COL); DisplayBoard(show, ROW, COL); //排查雷 FindMine(mine ,show,ROW,COL); } void test() { int input; srand((unsigned int)time(NULL)); do { menu(); cout << "请选择->" << endl; cin >> input; switch (input) { case 1: cout << "开始扫雷" << endl; game(); break; case 0: cout << "退出游戏" << endl; break; default : cout << "选择错误,请重新选择" << endl; } } while (input); } int main() { test(); return 0; } 在game.cpp中实现扫雷主要功能#include"game.h" #include<ctime> #include<cstdlib> //初始化棋盘 void InitBoard(char arr[ROWS][COLS], int rows, int cols,char temp) { for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { arr[i][j] = temp; } } } //打印棋盘 void DisplayBoard(char arr[ROWS][COLS], int row, int col) { int i; //打印列号 cout << "----------扫雷----------" << endl; for (i = 0; i <= COL; i++) { cout << i; } cout << endl; for (i = 1; i <= ROW; i++) { cout << i; for (int j = 1; j <= COL; j++) { cout << arr[i][j]; } cout << endl; } } //布置雷 void SetMine(char mine[ROWS][COLS], int row, int col) { int count = EASY_COUNT; while (count) { int x = rand() % row + 1; int y = rand() % col + 1; if(mine[x][y] == '0') { mine[x][y] = '1'; count--; } } } //计算周围雷的个数 static int GetMineCount(char mine[ROWS][COLS], int x, int y) { return mine[x + 1][y] + mine[x - 1][y] + mine[x + 1][y + 1] + mine[x][y + 1] + mine[x - 1][y + 1] + mine[x + 1][y - 1] + mine[x][y - 1] + mine[x - 1][y - 1] - 8 * '0'; } //找雷 void FindMine(char mine[ROWS][COLS], char show[ROWS][COLS], int row, int col) { int x; int y; while(1) { cout << "请输入要排查的雷" << endl; cin >> x >> y; //判断数据是否有效 if (x >= 1 && x <= row && y >= 1 && y <= col) { if (mine[x][y] == '1') { cout << "很遗憾你被炸死了"<<endl; DisplayBoard(mine, ROW, COL); break; } else { //该坐标不是雷,显示周围有几个雷 int count=GetMineCount(mine,x,y); show[x][y] = count + '0'; DisplayBoard(show, ROW, COL); } } else { cout << "输入无效,请重新输入"; } } }在game.h中声明行列,雷的个数,函数#pragma once #include<iostream> #include<ctime> #include<cstdlib> using namespace std; //控制行和列 #define ROW 9 #define COL 9 #define ROWS ROW+2 #define COLS COL+2 #define EASY_COUNT 10 //声明函数 void test(); void InitBoard(char arr[ROWS][COLS], int rows ,int cols,char set); void DisplayBoard(char arr[ROWS][COLS], int row, int col); void SetMine(char arr[ROWS][COLS],int row,int col); void FindMine(char mine[ROWS][COLS], char show[ROWS][COLS], int row, int col);
2024年03月21日
9 阅读
0 评论
2 点赞
1
2