蓝桥杯c ++笔记(含算法 贪心+动态规划+dp+进制转化+便利等)

蓝桥杯

+++

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std; 
//常使用的头文件

动态规划

小蓝在黑板上连续写下从 11 到 20232023 之间所有的整数，得到了一个数字序列： S=12345678910111213…20222023

这里问题在于要记录下s 就要拼接数字到之前记录的后面 但是strcat 只可以拼接字符串 不可以拼接数字 因此要转化

#include <bits/stdc++.h>
#define int long long       //这里的long long 是64位的整数
using namespace std;       signed main() {      //与int 差不多 但是表示返回一个有符号的整数 而且方式更简洁  而且前面使用了define int long long  string s;int dp[4] = {0};for (int i = 0; i <= 2023; i++) {s += to_string(i);}for (int i = 0; i < s.size(); i++) {if (s[i] == '2') {dp[0]++;dp[2] += dp[1];} else if (s[i] == '0') {dp[1] += dp[0];} else if (s[i] == '3') {dp[3] += dp[2];}}cout << dp[3] << endl;}

c语言方法sprintf(temp.%d,i);
strcat(s,temp);
// sprintf(要存储的地方,要转变为字符串之前的形式,原本的数据)
// strcat(要存储的最终地方要存储的地方,)

时间戳

#include <stdio.h>
#include <time.h>int main() {// 1. 读取打卡记录文件 FILE *fp = fopen("record.txt",  "r");time_t t[1000]; // 假设最多存1000条打卡记录 char line[30];  // 存储每行时间字符串 int cnt = 0;    // 记录实际读取的打卡次数 // 2. 逐行解析时间 while (fgets(line, sizeof(line), fp)) {struct tm tm = {0};sscanf(line, "%d-%d-%d %d:%d:%d",&tm.tm_year,  &tm.tm_mon,  &tm.tm_mday, &tm.tm_hour,  &tm.tm_min,  &tm.tm_sec); tm.tm_year  -= 1900;  // 年份从1900开始算 tm.tm_mon  -= 1;      // 月份范围0-11 t[cnt++] = mktime(&tm); // 转为秒级时间戳 }fclose(fp);// 3. 冒泡排序时间戳（简单但直观）for (int i = 0; i < cnt; i++) for (int j = i+1; j < cnt; j++)if (t[i] > t[j]) {time_t tmp = t[i];t[i] = t[j];t[j] = tmp;}// 4. 计算总工作时长 long sum = 0;for (int i = 0; i < cnt; i += 2) // 每两个为一组（上班+下班）sum += t[i+1] - t[i];        // 下班时间 - 上班时间 printf("2022年总工作时长：%ld秒\n", sum);return 0;
}

票据问题(c++)

每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID。

数据保证断号不可能发生在最大和最小号。

输入格式
一个整数 N(N<100) 表示后面数据行数，接着读入 N 行数据，每行数据长度不等，是用空格分开的若干个（不大于 100100 个）正整数（不大于 10^5），每个整数代表一个 ID 号。

输出格式
要求程序首先输入要求程序输出 11 行，含两个整数 m，n，用空格分隔，其中，m 表示断号 ID，n 表示重号 ID。

输入输出样例
输入

2

5 6 8 11 9

10 12 9

输出

7 9

#include<bits/stdc++.h>
using namespace std;
#define N 10010
int n;
int main()
{int cnt;cin >> cnt;vector<int>a;string line;getline(cin,line);   //吃掉一个回车int t;for(int i=0;i<cnt;i++){getline(cin,line);          。。读取一行stringstream ssin(line);        //将字符串转化为数字while(ssin >> t){          //将ssin 中的东西给到t 中 并且由t给到aa.push_back(t);}}sort(a.begin(), a.end());int res1, res2;for (int i = 1; i < a.size(); i++){if (a[i] == a[i - 1]) res2 = a[i];//重号if(a[i]>a[i-1]+1)res1 =a[i-1]+1;}cout << res1 << " " << res2 << endl;return 0;
}

卡片问题

小蓝有很参考数字卡片，每张卡片上都是数字 0 到 9。

小蓝准备用这些卡片来拼一望数字，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不准用来拼其它数字了。

小蓝想知道自己能从 1 拼到多少。

例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是在拼 11 时卡片 1 已经只有一张了，不够拼出 11。

现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？

#include <iostream>
using namespace std;
int main(){int i,t,a[9];for(i=0;i<10;i++){a[i] = 2021;}for(i=1;;i++){t = i;while(t){if(a[t%10]==0){       //这是获取要组成数字的数的个位 例如卡片10  有0 和 1 组成cout << i-1;return 0;
}a[t%10]--;  //每次使用后卡片数-1t /= 10;           //获取110 中的1 
}}return 0;}

货物摆放 求非常大的n=a *b *c的方法

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL yue[101000],cnt;int main()
{LL n=2021041820210418;for(LL i=1;i<=n/i;i++){if(n%i==0){yue[++cnt]=i;if(i*i!=n)yue[++cnt]=n/i;}}//sort(yue+1,yue+cnt+1);//for(int i=1;i<=cnt;i++)cout<<yue[i]<<" ";//cout<<cnt;int ans=0;for(int i=1;i<=cnt;i++){for(int j=1;j<=cnt;j++){if(n%(yue[i]*yue[j])==0)ans++;}}cout<<ans;return 0;
}

我的

 #include<bits/stdc++.h>using namespace std;
typedef long long ll;
ll cnt[101000],yue=0;
int main(){ll n= 2021041820210418;int i;for(ll i=1;i<=n/i;i++){if(n%i==0){cnt[yue++]=i;if(i*i!=n){cnt[yue++] = n/i;}}}int cns = 0;for(int j=0;j<yue;j++){for(int k=0;k<yue;k++){if(n%(cnt[j]*cnt[k])==0){cns++;}}}cout << cns;return 0;}

路径(贪心)

基础：喝水问题

#include<bits/stdc++.h>
#include <iostream>
using namespace std;int main()
{int a[201] = {0};int n,s=0,r,i;cin >> n >> r;        //r是水龙头的数量 N是有n个人for(i=1;i<=n;i++){cin >> a[i];}sort(a,a+n);for(i=1;i<=n;i++){if(i>=r+1){a[i] = a[i] + a[i-r];}s = s + a[i];}cout << s;return 0;}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2510;
int g[N][N],dist[N],st[N];
int n=2021;
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;       //return 判断式? 选择一 : 选择二
}
int lcm(int a,int b){return a*b/gcd(a,b);
}int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j] && (t==-1 || dist[j]<dist[t]))t=j;}st[t]=1;for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);     //返回两个参数中的最小值 }}return dist[n];
}
int main(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i!=j){if(fabs(i-j)<=21){      //计算绝对值g[i][j]=lcm(i,j);g[j][i]=lcm(i,j);}else{g[i][j]=0x3f3f3f3f;g[j][i]=0x3f3f3f3f;}}}cout<<dijkstra();//cout<<0x3f3f3f3f;return 0;
}//dist[i]：从起点（这里是节点 1）到节点 i 的当前最短路径长度。
受不了了 这个我是在理解不了

过河卒问题

精简(没马的)

#include<bits/stdc++.h>
#include <iostream>
using namespace std;int main()
{int a[30][30] = {0};    //坐标int n,m;cout << "请你输入吗马所在的位置";cin >> n >> m;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)	{if(i==0&&j==0){continue;}if(i==0||j==0){a[i][j] = 1;}else{a[i][j] = a[i-1][j] + a[i][j-1];}	}
}cout << a[n][m];return 0;
}

#include <stdio.h>
#include <stdlib.h>#include <math.h>
#define OK 1
#define ERROR 0typedef struct Node {        //创建结构体int data;struct Node *next;
} Node, *Snode;Snode Createlist() {            //创建一个链表Snode head = NULL;Snode next = NULL;int num;while (1) {scanf("%d", &num);if (num == -1) {break;}Snode newNode = (Snode)malloc(sizeof(Node));if (newNode == NULL) {printf("分配内存失败");exit(1);}newNode->data = num;newNode->next = head;head = newNode;}return head;
}Snode mergeList(Snode T1, Snode T2) {   //合并两个链表Snode head = NULL;Snode tail = NULL;while (T1 != NULL && T2 != NULL) {if (T1->data > T2->data) {    //这里降序将数据合并if (head == NULL) {head = T1;tail = T1;} else {tail->next = T1;
//				tail = tail->next;tail = T1;}T1 = T1->next;} else {if (head == NULL) {head = T2;tail = T2;} else {tail->next = T2;
//				tail = tail->next;tail = T2;}T2 = T2->next;}}if (T1 != NULL) {     //这里处理剩余节点if (head == NULL) {head = T1;} else {tail->next = T1;}}if (T2 != NULL) {if (head == NULL) {head = T2;} else {tail->next = T2;}}return head;
}void printList(Snode list) {         //这里打印链表Snode head = list;while (head != NULL) {printf("%d ", head->data);head = head->next;}printf("\n");}void freeList(Snode head) {Snode temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}int main() {         //主函数的使用printf("创建你的第一个链表(输入-1结束):");Snode T1 = Createlist();printf("创建你的第二个链表(输入-1结束):");Snode T2 = Createlist();printf("\n");printf("你的第一个链表中元素为:");printList(T1);printf("\n");printf("你的第二个链表的元素为:");printList(T2);Snode mergeT = mergeList(T1, T2);printf("\n");printf("两个链表合并之后(降序排列)为");printList(mergeT);freeList(mergeT);return 0;}

二分法简便

#include<algorithm>
using namespace std;
int main(){{int data[200];for(int i = 0 ; i < 200 ; i ++)data[i] = 4 * i + 6;int n;cin>>n;cout<<lower_bound(data,data+200,n)-data<<endl;return 0;
}

正常二分法

#include <iostream>
using namespace std;int main() {int arr[200];for(int i = 0; i < 200; i++) arr[i] = 4 * i + 6;int n;cin >> n;int mid, left, right;left = 0;right = 199; // 数组最后一个索引while (left <= right) {mid = (left + right) / 2;if (arr[mid] == n) {cout << mid << endl;return 0; // 找到后退出} else if (arr[mid] < n) {left = mid + 1; // 跳过 mid} else {right = mid - 1; // 跳过 mid}}cout << "-1" << endl; // 未找到return 0;
}

这个运行2ms 但是正常的循环便利要29ms

输入一端数组让他从大到小 小到大排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int N;cin >> N;vector<int>a(N);    //这里注意是()for (int i = 0; i < N; i++) {cin >> a[i];}sort(a.begin(), a.end());      //先begin 后endfor (int num : a) {cout << num << " ";}cout << endl;sort(a.begin(), a.end(), greater<int>()); for (int num : a) {cout << num << " ";}return 0;
}

输入一串数字得到最大值和最小值还有平均值

#include <iostream>
#include <iomanip>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{int N,i;cin >> N;vector<int>a(N);for(i=0;i<N;i++){cin >> a[i];          //注意endl只适用于cout 不适用于cin}int min ,max;float ave,sum=0;min = a[0];max = a[0];for(i=0;i<N;i++){if(a[i]<min){min = a[i];}if(a[i]>max){max = a[i];}sum+=a[i];}ave = sum/N;cout << max << endl<< min << endl<<fixed << setprecision(2)<<ave<<endl;   //这里的注意点是c++中想要输出的小数精度为2时候该怎么写return 0;
}

简便的方法

#include <bits/stdc++.h>   //这是一个万能头文件 可以省去很多麻烦using namespace std;int main() {vector<int>a;int N;cin >> N;a.resize(N);       //这个作用是给数组a分配你输入的N的空间int i;for (i = 0; i < N; i++) {cin >> a[i];}cout << *max_element(a.begin(), a.end()) << endl;cout << *min_element(a.begin(), a.end()) << endl;double sum;for (int ele : a) {    //这里将a容器中的元素一个个给ele然后加入到sum中sum += ele;}cout << fixed << setprecision(2) << sum / N;   return 0;}

CLZ 银行问题

题目
题目描述
CLZ 银行只有两个接待窗口，VIP 窗口和普通窗口，VIP 用户进入 VIP 窗口排队，剩下的进入普通窗口排队。现有 M 次操作，操作四种类型，如下：

IN name V：表示一名叫 name 的用户到 VIP 窗口排队
OUT V：表示 VIP 窗口队头的用户离开排队
IN name N：表示一名叫 name 的用户到普通窗口排队
OUT N：表示普通窗口队头的用户离开排队
求M 次操作结束后 VIP 窗口队列和普通窗口队列中的姓名。
输入描述
第一行是一个整数 M（1≤M≤1000），表示一共有 M 次操作。

第二行到第 M+1 行输入操作，格式如下：

IN name V

OUT V

IN name N

OUT N

输出描述
输出M 次操作后 VIP 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 VIP 窗口队列后输出普通窗口队列。

示例 1

输入

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V

输出

Adel
CLZ
laozhao
————————————————

#include <bits/stdc++.h>using namespace std;int main() {int N;cin >> N;string a;queue <string>n, v;for (int i = 0; i < N; i++) {cin >> a;if (a == "IN") {           //这里分为两类 一类IN  一类out  然后又细分两类一个vip身份 一个正常身份string name, p;cin >> name >> p;if (p == "V")v.push(name);else n.push(name);} else  {        //注意这里要有if 因为else 后面不可以直接跟你要判断的条件string p;cin  >> p;if (p == "V")v.pop();elsen.pop();}}while (v.size()) {         //这里将v中的内容输出cout << v.front() << endl;v.pop();     //每次输出之后将这个元素弹出}while (n.size()) {cout << n.front() << endl;n.pop();}return 0;}

分糖果

题目
问题描述
最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了 n 个不同种类的糖果，用小写的阿拉伯字母表示。每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串 s[i] 的字典序。肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的max(s[1],s[2],s[3],…,s[x]) 。

输入描述
第一行输入两个整数
n 和x ，分别表示有 n 个糖果 x 个同学。

第二行输入一个长度为 n 的字符串S S[i] 表示第 i 个糖果的种类。

数据保证

1≤n≤10 ^6 ,1≤x≤n,S[i]∈[ ′ a ′ , ′ z ′ ] 。

输出描述
输出一个字符串，为所有糖果组成的字符串中字典序最大的字符串最小的可能值。

样例输入
6 2

caabdc
样例输出
abccd
说明
一个最优分配方案是一个同学拿到 abccd ，一个同学拿到 a 。

合并果子（贪心+最小成本）

题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力 =3+12=15。可以证明 15 为最小的体力耗费值。

输入描述
输入两行。

第一行是一个整数 n(1≤n≤10^4 )，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数 (1≤a i≤2×10 4 ) 是第 i 种果子的数目。

输出描述
输出一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31 。

输入输出样例
示例 1
输入

3
1 2 9
输出

15
————————————————

芝士：

priority 是一个堆

priority_queue<T,Container,Compare> pq;     //pq 是一个名字 优先队列的对象名字

• T 是存储的数据类型 如 int long long
• Container 是底层容器 一般是vector
• Compare 是比较器 决定大堆还是小堆
  • greater 顶部是小堆
  • less 顶部是最大堆

push(x)：插入元素 x，时间复杂度 O(log n)。

top()：返回顶部元素（最小或最大值，取决于堆类型），时间复杂度 O(1)。

pop()：删除顶部元素，时间复杂度 O(log n)。

size()：返回队列中元素个数，时间复杂度 O(1)。

empty()：检查队列是否为空，时间复杂度 O(1)。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;int f, e; long long sum = 0;priority_queue<long long, vector<long long>, greater<long long>>pq;for (int i = 0; i < n; i++) {int t;cin >> t;       //这里逐个将堆中的元素录入pq.push(t);}while (pq.size() > 1) {f = pq.top();           pq.pop();e = pq.top();pq.pop();             //分别将堆中两个最小的数字取出sum += (f + e); //计算两个数字的和pq.push(f + e);   //将取出的两个数字的和再放入堆中便于之后一起算最小成本}cout << sum;return 0;
}

扫雷问题

拓展给数组每个元素赋值某个值的方法>

vector <int>a(N,0)      //将一维数组中每个元素赋值为0

vector<vector<int>> a(n,vector<int>(m,0))  //给n , m的二维数组每个元素赋值为0

题目描述
在一个 n 行 m 列的方格图上有一些位置有地雷，另外一些位置为空。请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。

输入描述
输入的第一行包含两个整数 n,m。第 2 行到第 n+1 行每行包含 m 个整数，相邻整数之间用一个空格分隔。如果对应的整数为 0，表示这一格没有地雷。如果对应的整数为 1，表示这一格有地雷。其中，1≤n,m≤100 分钟后还是在当天。

输出描述
输出 n 行，每行 m 个整数，相邻整数之间用空格分隔。对于没有地雷的方格，输出这格周围的地雷数量。对于有地雷的方格，输出9。

输入输出样例
示例 1
输入

3 4
0 1 0 0
1 0 1 0
0 0 1 0

输出

2 9 2 1
9 4 9 2
1 3 9 2

这道题的诀窍就是设置数组的时候设置一个可以把原本数组包围起来的数组 也就是顶部加一行 底部加一行 左边加一列 右边加一列 之后通过循环逐个索引

#include <bits/stdc++.h>using namespace std;int main() {int n, m, count = 0;cin >> n >> m;vector<vector<int>> a(n + 2, vector<int>(m + 2, 0));  //初始化数组 并且其中的值都设置为0vector<vector<int>> b(n + 2, vector<int>(m + 2, 0));for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {cin >> a[i][j];}}for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {if (a[i][j] == 1) {b[i][j] = 9;} else {for (int p = -1; p < 2; p++) {for (int q = -1; q < 2; q++) {if (a[i + p][j + q] == 1) {count++;}}}b[i][j] = count;}count = 0;}}for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {cout << b[i][j] << " ";}cout << endl;           //这里注意在第一个for循环之后换行}return 0;}

灌溉问题

题目描述
小蓝负责花园的灌溉工作。

花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？

输入描述
输入的第一行包含两个整数 n,m。

第二行包含一个整数 t，表示出水管的数量。

接下来 t 行描述出水管的位置，其中第 i 行包含两个数r,c 表示第 r 行第 c 列有一个排水管。

接下来一行包含一个整数 k。

其中，1≤n,m≤100,1≤t≤10,1≤k≤100。

输出描述
输出一个整数，表示答案。

输入输出样例
示例 1
输入

3 6
2
2 2
3 4
1

输出

9

这个问题有个关键就是必须要有两个数组 不可以仅仅对着一个数组操作 因为操作的过程会使条件改变 导致循环和判断中的不对

#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> a(n + 2, vector<int>(m + 2, 0));
//初始化主数组int x;cin >> x;for (int i = 1; i <= x; i++) {int l, k;cin >> l >> k;a[l][k] = 1;
//给有水管的地方赋值为1}int fen;cin >> fen;vector<vector<int>> t(n + 2, vector<int>(m + 2, 0));for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {t[i][j] = a[i][j];}}for (int s = 1; s <= fen; s++) {for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {if (a[i][j] == 1) {t[i - 1][j] = 1;t[i][j - 1] = 1;t[i + 1][j] = 1;t[i][j + 1] = 1;}   //给上下左右面浇树水 也就是赋值为1 }}for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {a[i][j] = t[i][j];}}}int count = 0;for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {if (a[i][j] == 1) {count++;}}}cout << count;return 0;
}

十六进制转化为十进制

请问十六进制数 2021ABCD 对应的十进制是多少？

解决 ：先将十六进制转化为二进制 再将二进制转化为十进制

#include <stdio.h>
#include <math.h>int main() {long long int a[32] = {0b00100000001000011010101111001101}   ;//唯一需要注意的就是为了确保输入的是十进制 所以需要前面加一个0blong long int x, sum = 0;for (int i = 0; i < 32; i++) {x = a[i] * pow(2, i);sum += x;}printf("%lld", sum);return 0;
}

进制转化升阶

题目描述
给定一个 N 进制数 S，请你将它转换为 M 进制。

输入描述
第一行为一个整数 T，表示测试数据数量。 (1≤T≤10^5)每个测试用例包含两行，第一行包含两个整数 N,M。

第二行输入一个字符串 S，表示 N 进制数。

数据范围保证：2≤N,M≤16，若 N≥10，则用 A∼F 表示字码 10∼15。保证 S 对应的十进制数的位数不超过 10。

输出描述
输出共 T，每行表示一组数据的答案。

输入样例
2
2 10
10101
11 2
1793A5068

输出样例
21
10101111001010100111010101011

这里解决问题的有几个关键

• 任何进制转化为另一个进制 要先转化为十进制
• 那么 因为输入的一连串数字是string 类型如果直接 所以要先通过循环转化为
• 再通过循环转化为十进制
• 之后再使用while语句中的取余和除 得出对应的进制数
• 注意的是string 可以使用s[i] 索引其中的元素

#include <bits/stdc++.h>
using namespace std;int main() {char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};int T;int a[50];cin >> T;while (T--) {int N, M;cin >> N >> M;        //几进制到几进制的转化string s;cin >> s;        //目标字符for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9')       //单引号是指ASCII值a[i + 1] = s[i] - '0';elsea[i + 1] = s[i] - 'A' + 10;     //将string 类型转化为数字类型}
//161514321long long x = 0;for (int i = 1; i <= s.size(); i++)x = x * N + a[i];       //转化为十进制string ans;while (x) {ans += ch[x % M];    //这里的+=是字符串的拼接x = x / M;}reverse(ans.begin(), ans.end());cout << ans << endl;}return 0;}

字母数

请找到一个大于 20222022 的最小数，这个数转换成二进制之后，最低的 66 个二进制位全为 00 。

请将这个数的十进制形式作为答案提交。

#include <bits/stdc++.h>
using namespace std;int main() {int x = 2023, temp, t;for ( ; x <= 10000; x++) {temp = x;t = x;string ans;while (temp) {ans += temp % 2 + '0';temp = temp / 2;}         //转化为2进制reverse(ans.begin(), ans.end());     //倒着排序bool a = true;if (ans.size() > 6) {for (int i = ans.size() - 6; i < ans.size(); i++) {if (ans[i] != '0') {        //注意这里是减去' '  因为ans的类型是ststring 类型a = false;break;              //判断最低六位是否为0}}} else {a = false;}if (a) {cout << t;break;}}return 0;}

背包问题

拓展知识

max(a, b) 返回 a 和 b 中较大的值。

#include <bits/stdc++.h>
using namespace std;const int N = 100;
int n, weightBag;
int weight[N], value[N];int select(int i, int j) {  //i 是第几个物品  J是物品重量int result;if (i == n) {        //检查有没有该物品return result;            } else if (j < weight[i]) {         //要是物品的重量大于背包的容量result = select(i + 1, j);} else {           //背包有该物品且物品的重量小于背包的容量 接下来判断该不该挑选这个物品result = max(select(i + 1, j), select(i + 1, j - weight[i]) + value[i]);}return result;}int main() {cout << "请输入物品的数量和背包的重量" << endl;cin >> n >> weightBag;                 // 有几个物品 背包的重量是多少cout << "请分别输入物品的重量" << endl;for (int i = 0; i < n; i++) {cin >> weight[i];}cout << "请分别输入物品的价值" << endl;for (int i = 0; i < n; i++) {cin >> value[i];}cout << select(0, weightBag) << endl;return 0;}

三元便利数组

（可以把一堆数字中按照三个一组全部便利一遍）

for(i=0;i<N-2;i++){for(j=i+1;j<N-1;j++){for(k=j+1;k<N;k++){}} 
}

+++

memset函数

(将一个数组或内存中的数全部变为0，这也叫做初始化)

场景：例如要让你走在一个棋盘之中，你走过的路径都要标记为1，没有走过的都是0，那么你一开始就要memset();

memset(要设置的区域的起始地址,要设置的value,sezeof(数组))//要设置的字节数

+++

dfs函数

(深度遍历要走的路径，直到找到满意的路径，使用递归和回溯)

场景:例如要让你走在一个棋盘当中，你要走每一个格子，并且要找到出去的最优解（格子中有丈量你走的价值的东西),这时候就要用到dfs

拼接函数

模仿strcat

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main() {int i;char x[100000] = ""; // 用于存储拼接结果的字符数组// 注意：连接数字时需要先把数字转成字符串for (i = 1; i <= 2023; i++) {char temp[50]; // 临时存储数字的字符串sprintf(temp, "%d", i); // 将数字 i 转换为字符串strcat(x, temp); // 拼接到 x 后面// 如果需要将 i++ 放在不同的字符串中，可以这样做sprintf(temp, "%d", i + 1); // 将 i+1 转换为字符串strcat(x, temp); // 拼接到 x 后面}// 打印最终结果printf("%s\n", x); return 0;
}/*sprintf函数用于将某种类型转化为字符类型，因为strcat函数是要拼接字符串类型的数据的sprintf(转化的东西所在的位置,转化前的类型,要转化的内容)

]) + value[i]);

}return result;

}

int main() {
cout << “请输入物品的数量和背包的重量” << endl;
cin >> n >> weightBag; // 有几个物品 背包的重量是多少
cout << “请分别输入物品的重量” << endl;
for (int i = 0; i < n; i++) {

	cin >> weight[i];
}
cout << "请分别输入物品的价值" << endl;
for (int i = 0; i < n; i++) {cin >> value[i];
}
cout << select(0, weightBag) << endl;return 0;

}

## 三元便利数组（可以把一堆数字中按照三个一组全部便利一遍）```c
for(i=0;i<N-2;i++){for(j=i+1;j<N-1;j++){for(k=j+1;k<N;k++){}} 
}

+++

memset函数

(将一个数组或内存中的数全部变为0，这也叫做初始化)

场景：例如要让你走在一个棋盘之中，你走过的路径都要标记为1，没有走过的都是0，那么你一开始就要memset();

memset(要设置的区域的起始地址,要设置的value,sezeof(数组))//要设置的字节数

+++

dfs函数

(深度遍历要走的路径，直到找到满意的路径，使用递归和回溯)

场景:例如要让你走在一个棋盘当中，你要走每一个格子，并且要找到出去的最优解（格子中有丈量你走的价值的东西),这时候就要用到dfs

拼接函数

模仿strcat

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main() {int i;char x[100000] = ""; // 用于存储拼接结果的字符数组// 注意：连接数字时需要先把数字转成字符串for (i = 1; i <= 2023; i++) {char temp[50]; // 临时存储数字的字符串sprintf(temp, "%d", i); // 将数字 i 转换为字符串strcat(x, temp); // 拼接到 x 后面// 如果需要将 i++ 放在不同的字符串中，可以这样做sprintf(temp, "%d", i + 1); // 将 i+1 转换为字符串strcat(x, temp); // 拼接到 x 后面}// 打印最终结果printf("%s\n", x); return 0;
}/*sprintf函数用于将某种类型转化为字符类型，因为strcat函数是要拼接字符串类型的数据的sprintf(转化的东西所在的位置,转化前的类型,要转化的内容)