首页
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
搜索到
14
篇与
的结果
2024-05-01
递归模拟
题目描述 Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup --- today's soup is made by mingling yesterday's soup and the day before yesterday's soup:S(1)="COFFEE";S(2)="CHICKEN";S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY's game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.输入描述: The first line of input is a single integer T (1≤T≤1000), denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k (1≤n≤500,1≤k≤min{∣S(n)∣,10^12 }). |S| denotes the length of string S. 输出描述: For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string. 示例1 输入 247 输出 FEECHICKENN题解 题目与斐波那契数列有关但是因为Sn的增长到后面过于爆炸,因此不能直接求Sn然后求十个字符需要转换一下,请观察下面的规律A 1 B 1 AB 2 BA 3 ABBAB 5 BABABBAB 8 ABBABBABABBAB 13 BABABBABABBABBABABBAB 21 ABBABBABABBABBABABBABABBABBABABBAB 34 BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB 45可以知道当前指向的位置大于a[n-2]就可以求a[n-1]的第k-a[n-2]个数(上面的数一数),如果小于等于a[n-2]就等于求a[n-2]的第几个数代码示例 #include<iostream> using namespace std; using ll = long long; ll a[700]; //mello函数记录Sn的字符串长度的值 void mello() { a[1] = 6;//6是COFFEE的长度 a[2] = 7;//7是CHICKEN的长度 for (int i = 3; i <= 60; i++) { a[i] = a[i - 1] + a[i - 2];//循环记录Sn的长度 } } int main() { mello(); int t; cin >> t; while (t--) { ll n, k; cin >> n >> k; //对于大于60的n,我们只需要取小的值替代即可,奇数用59,偶数用58 //为什么用60?因为k最多到1e12,当Sn大于58时长度就超过了1e12 if (n >= 60) { if (n % 2) n = 59; else n = 58; } for (ll i = k; i <= a[n] && i < k + 10; i++) { ll w = i, v = n;//w追踪当前位置,v追踪当前序列项 while (v != 1 && v != 2) {//不断递归减小,直到v选择COFFEE或CHICKEN if (w > a[v - 2]) { w = w - a[v - 2]; v -= 1; } else { v -= 2; } } if (v == 1) printf("%c", "COFFEE"[w - 1]); else if (v == 2) printf("%c", "CHICKEN"[w - 1]); } printf("\n"); } return 0; }
2024年05月01日
6 阅读
0 评论
0 点赞
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-22
简单的背包问题
描述 小冯有个存储重量为m的空间存储袋,现在有n件物品,每件物品的重量为w,价值为v。问小冯最多能装的最大价值为多少?输入 第一行输入两个数m、n,(1<=n,m<=1000)n表示物品数量,m表示存储袋的最大重量;接下来的n行,每行输出w,v,(1<=w,v <= 100)分别表示物品的重量,物品的价值; 输出 输出小冯能装的物品最大价值; 样例输入 70 371 10069 11 2 样例输出 3题解 利用动态空间规划可以建立一个二维数组存储物品价值,行为物品个数,列为重量比较和比这个物品重量小的物品的价值的和,和上一个物品价值的值哪个大否则返回上一个物品的价值个数/重量01230000010000200003000040000放入第一个物品重量为1,价值为2个数/重量01230000010222200003000040000放入第二个物品重量为2,价值为4个数/重量01230000010222202463000040000代码实例#include<iostream> #include<cstdlib> using namespace std; int m, n, i, j; int w[1000], c[1000], f[1000][1000]; int main() { cin >> m >> n;//m代表背包最大能装的重量,n代表物品的数量 for (i = 1; i <= n; i++) { cin >> w[i] >> c[i];//输入每个物品的重量和价值 } //i控制物品,j控制重量 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (j >= w[i]) { f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]); } else{ f[i][j] = f[i - 1][j]; } } } cout << f[n][m] << endl; return 0; }vector版:#include<iostream> #include<vector> #include<cstdlib> using namespace std; int n, w, i, j; int main() { cin >> w >> n; //定义容器行为几号物品,列为重量 vector<vector<int>>f(n + 1, vector<int>(w+1,0)); //定义重量与价值的容器 vector<int>weight(n +1); vector<int>price(n + 1); //输入 for ( i = 1; i <= n; i++) { cin >> weight[i] >> price[i]; } for (i = 1; i <= n; i++) { for (j = 1; j <= w; j++) { if (j >= weight[i]) { f[i][j] = max(f[i - 1][j - weight[i]] + price[i], f[i - 1][j]);//比较和比这个物品重量小的物品的价值的和,和上一个物品价值的值哪个大 } else { f[i][j] = f[i - 1][j];//否则返回上一个物品的价值 } } } cout << f[n][w] << "\n"; return 0; }
2024年04月22日
4 阅读
0 评论
0 点赞
2024-04-16
二进制,八进制,十进制,十六进制之间的互相转换
二进制 由“01”组成。逢2进1。 八进制 由“01234567”组成。逢8进1。一般由0开头 十进制 由“0123456789”组成。逢10进1。 十六进制 由“0123456789ABCDEF”。逢16进1。一般由0x开头十进制转换二进制,八进制,十六进制 设X为十进制数,Y为二,八,十六进制数。 由除法运算可知有整数Z和余数D 式子结构如:X/Y==Z... ...D 转换规则为用X除Y取余,再用Z除Y取余,,,重复操作直至Z无法再除 十进制转换二进制例子: 如:将十进制52转换为二进制数 52/2==26... ... 0 ---> 0 取余,将0放至最右边保留 26/2==13... ... 0 ---> 00 13/2==6 ... ... 1 ---> 100 6/2==3 ... ... 0 ---> 0100 3/2==1 ... ... 1 ---> 10100 1/2==0 ... ... 1 --->110100十进制转换八进制例子: 如:将575转换为八进制数 575/8==71... ... 7 ---> 7 操作与二进制一样 71/8== 8... ... 7 ---> 77 8/8== 1... ... 0 ---> 077 1/8== 0... ... 1 ---> 1077十六进制同理便不再赘述 十进制转N进制代码实例#include<iostream> #include<string> using namespace std; #define N 2//示例为十进制转换二进制,其他进制需要把2修改 string conversion(int num_10) { if (num_10 == 0) { string str = "0"; return str; } string temp = ""; string num_N = "01";//示例为十进制转换二进制,因此在""内为01,若为八进制则改为01234567 int i; for (i = 0; num_10 != 0; i++) { temp = num_N[num_10 % N] + temp; num_10 /= N; } return temp; } int main() { int num_10; string num_N; cin >> num_10; num_N=conversion(num_10); cout << num_N << endl; return 0; }N进制转换十进制 利用数的位权计算二进制数1111转换十进制过程如下12^3+12^2+1 2^1+12^0==15八进制数17转换十进制过程如下1 8^1+78^0==15十六进制同理便不再赘述 N进制转十进制代码实例//N进制转十进制 #include<iostream> #include<string> #include<cmath> using namespace std; #define N 2//示例为二进制转换十进制 int conversion(string num_N) { int i; int size = num_N.size(); int num=0,temp=0; for (i = 0; i < size; i++) { temp = num_N[i] - '0'; num = num + temp * pow(N, size - i - 1); } return num; } int main() { string num_N; int num_10; cin >> num_N; num_10 = conversion(num_N); cout << num_10 << endl; return 0; }以上两个为十进制转换N进制和N进制转换十进制当需要十六进制,八进制,二进制之间的转换可以先转换十进制,再转换进制
2024年04月16日
11 阅读
0 评论
0 点赞
1
2
3