递归模拟 题目描述 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; }

前缀和与差分 前缀和公式为 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; }

简单的背包问题 描述 小冯有个存储重量为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; }

二进制，八进制，十进制，十六进制之间的互相转换 二进制 由“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进制转换十进制当需要十六进制，八进制，二进制之间的转换可以先转换十进制，再转换进制

类的构造函数与析构函数 构造函数 构造函数的定义 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内存回收，因此才会调用析构函数打印出信息。