原题链接 P1957 口算练习题
题目描述5+8 \texttt{5+8} 5+8 5 \texttt 5 5 8 \texttt 8 8 5+8=13 \texttt{5+8=13} 5+8=13 6 6 6 i i i i i i a \texttt a a b \texttt b b c \texttt c c 2 × i 2\times i 2 × i
1 2 3 4 5 4 a 64 46 275 125 c 11 99 b 46 64
样例输出 #1
1 2 3 4 5 6 7 8 64+46=110 9 275+125=400 11 11*99=1089 10 46-64=-18 9
提示50 % 50\% 5 0 % 0 < i ≤ 50 0<i\leq 50 0 < i ≤ 5 0 10000 10000 1 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <cstdio> #include <cstring> using namespace std;int main () int n, a, b, c; char last, s[20 ], ans[20 ]; scanf ("%d\n" , &n); while (n--) { fgets (s, sizeof (s), stdin); if (s[0 ] == 'a' || s[0 ] == 'b' || s[0 ] == 'c' ) last = s[0 ]; s[0 ] = ' ' ; sscanf (s, "%d %d" , &a, &b); switch (last) { case 'a' : c = a + b; sprintf (ans,"%d+%d=%d" , a, b, c); break ; case 'b' : c = a - b; sprintf (ans,"%d-%d=%d" , a, b, c); break ; case 'c' : c = a * b; sprintf (ans,"%d*%d=%d" , a, b, c); break ; } printf ("%s\n%d\n" , ans, strlen (ans)); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <iostream> #include <cstdio> #include <cstring> #define LOCAL using namespace std;int main () #ifdef LOCAL freopen ("data.in" , "r" , stdin); freopen ("data.out" , "w" , stdout); #endif char a[10 ], ans[100 ]; char temp; int n, x, y; scanf ("%d" , &n); while (n--) { scanf ("%s" , a); if (a[0 ] >= 'a' && a[0 ] <= 'c' ) { temp = a[0 ]; scanf ("%d %d" , &x, &y); } else { x = atoi (a); scanf ("%d" , &y); } memset (ans,0 ,sizeof (ans)); switch (temp) { case 'a' : sprintf (ans, "%d+%d=%d" , x, y, x + y); break ; case 'b' : sprintf (ans, "%d-%d=%d" , x, y, x - y); break ; case 'c' : sprintf (ans, "%d*%d=%d" , x, y, x * y); break ; } printf ("%s\n%d\n" , ans, strlen (ans)); } }
scanf遇到空格换行停止读入
sscanf(s,“%d”,&a);就可以从字符串s中读入一个整数a。
sprintf将数据输入到字符串，sprintf(ans, “%d*%d=%d”, x, y, x * y);就是以%d*%d=%d的格式输入到字符串ans中ans存储x*y=xy。
atoi ((表示 ascii to integer)是把字符串转换成整型数的一个函数)头文件为#include<stdlib.h>
题目描述0 0 0
1 str：后接插入，在文档后面插入字符串 str \texttt{str} str 2 a b：截取文档部分，只保留文档中从第 a a a b b b 3 a str：插入片段，在文档中第 a a a str \texttt{str} str 4 str：查找子串，查找字符串 str \texttt{str} str − 1 -1 − 1 str \texttt{str} str q q q q q q str \texttt{str} str q q q n n n 1 , 2 , 3 1,2,3 1 , 2 , 3 4 4 4
1 2 3 4 5 6 4 ILove 1 Luogu 2 5 5 3 3 guGugu 4 gu
样例输出 #1
1 2 3 4 ILoveLuogu Luogu LuoguGugugu 3
提示1 ≤ q ≤ 100 1 \leq q\le 100 1 ≤ q ≤ 1 0 0 ≤ 100 \leq 100 ≤ 1 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <iostream> #include <string> using namespace std;int main () string s, a; int opt, q, begin, end; cin >> q; cin >> s; while (q--) { cin >> opt; if (opt == 1 ) { cin >> a; s.append (a); cout << s << endl; } else if (opt == 2 ) { cin >> begin >> end; s = s.substr (begin, end); cout << s << endl; } else if (opt == 3 ) { cin >> begin >> a; s = s.insert (begin, a); cout << s << endl; } else if (opt == 4 ) { cin >> a; cout << (int )s.find (a) << endl; } } return 0 ; }
1.引入头文件 #include <string>string s
1 2 3 4 5 string a,b; a="LUOGU" b=a; char a="abc" 是错误的。因为字符数组名a，本质上是一个地址，不可以用来直接复制和相互赋值。
3.常用操作
s+=str或s.append(str):在字符串s后拼接字符串str。
s < str：比较字符串s的字典序是否在字符串str之前
s.size()或s.length()：得到字符串s的长度
s.substr(pos,len)以字符串数组来理解
1 2 3 4 5 6 string a="acwing" cout << a.substr (0 , 3 ) << endl; cout << a.substr (1 , 3 ) << endl; cout << a.substr (0 , 9 ) << endl; cout << a.substr (1 ) << endl; cout << a.substr (0 ) << endl;
str1（被插入字符串）.insert(pos(插入位置),str2（被插入字符串），n ，m)下方代码有存疑还未解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 string a; a.push_back ('a' ); cout<<a<<endl; a.insert (a.begin (),'1' ); string str2="hello" ; string s2="weakhaha" ; str2.insert (0 ,s2,1 ,3 ); cout<<str2<<endl; string str2="hello" ; string s2="weakhaha" ; str2.insert (1 ,s2,1 ,3 ); cout<<str2<<endl;
s.find(str,[pos]):在字符串第pos个字符开始寻找str，并返回位置，如果找不到返回-1.pos可以省略，默认值是0。（读者可以试一下直接使用cout输出，这个数字会是什么）
此处内容参考【C++】算法竞赛常用STL万字总结 指定位置插入字符串（c++insert函数、find函数使用） C++中的find函数用法
P1923 【深基9.例4】求第 k 小的数 ,快排优化还没想明白
需要引入头文件#include< algorithm >
sort()函数是类似于快速排序的方法，时间复杂度为n*log2(n)，执行效率较高。并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。所以说sort()是一个比较灵活的函数，它也会根据我们数据的需要进行排序，所以我们就不用担心以上的问题了。对于大部分的排序需求，sort()都是可以满足的。
其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。greater<int>() 就是对int数组进行排序，例如 sort(a,a+n,greater<int>());
当然<>中我们也可以写double、long、float 等等。
也可以以自定义排序准则的形式来写cmp函数如
1 2 3 bool cmp (int a,int b) return a>b; }
可能你有点懵，不知道这是什么原理，为什么要这么写。c++应用sort函数时的cmp函数怎么写
如果我们需要按照其他的排序准则，那么就需要我们自己定义一个bool类型的函数来传入。比如说我们按照每个数的个位进行从大到小排序，我们就可以根据自己的需求来写一个函数作为排序的准则传入到sort()中。
1 2 3 bool cmp (int x,int y) return x % 10 > y % 10 ; }
然后我们将这个cmp函数作为参数传入sort()中即可实现了上述排序需求。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> #include <algorithm> using namespace std;bool cmp (int x,int y) return x % 10 > y % 10 ; } int main () int num[10 ] = {65 ,59 ,96 ,13 ,21 ,80 ,72 ,33 ,44 ,99 }; sort (num,num+10 ,cmp); for (int i=0 ;i<10 ;i++){ cout<<num[i]<<" " ; } return 0 ; }
C++ sort()排序详解
[NOIP2007 普及组] 奖学金5 5 5 3 3 3 3 3 3 5 5 5 7 7 7 279 279 2 7 9 5 5 5 279 279 2 7 9 7 7 7 5 5 5 279 279 2 7 9 7 7 7 5 5 5 279 279 2 7 9 7 7 7 279 279 2 7 9 n + 1 n+1 n + 1 1 1 1 n ( ≤ 300 ) n ( \le 300) n ( ≤ 3 0 0 ) 2 2 2 n + 1 n+1 n + 1 3 3 3 0 0 0 100 100 1 0 0 j j j 3 3 3 j − 1 j-1 j − 1 1 ∼ n 1\sim n 1 ∼ n 1 1 1 5 5 5 5 5 5
1 2 3 4 5 6 7 8 9 10 11 12 13 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 ``` 样例输出 #2
8 265
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ```c++ #include <iostream> #include <algorithm> using namespace std; typedef struct student { int id; int score[3]; int total; } STUDENT; STUDENT a[310]; bool cmp(student x, student y) { if (x.total != y.total) return x.total > y.total; if (x.score[0] != y.score[0]) return x.score[0] > y.score[0]; return x.id < y.id; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { a[i].id = i; cin >> a[i].score[0] >> a[i].score[1] >> a[i].score[2]; a[i].total = a[i].score[0] + a[i].score[1] + a[i].score[2]; } sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= 5; i++) { cout << a[i].id << " " << a[i].total << endl; } return 0; } ``` ##### 利用字符串进行排序 >P1781宇宙总统 题目描述 地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。 输入格式 第一行为一个整数 $n$，代表竞选总统的人数。 接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。 输出格式 共两行，第一行是一个整数 $m$，为当上总统的人的号数。 第二行是当上总统的人的选票。 样例 #1 样例输入 #1
5
4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 提示 票数可能会很大，可能会到 $100$ 位数字。 $1 \leq n \leq 20$ ```c++ #include <iostream> #include <algorithm> using namespace std; struct node { int id;//编号 string num;//票数 } a[25]; bool cmp(node x, node y) { if(x.num.length()!=y.num.length())return x.num.length()>y.num.length();//a比b位数多时a在前面 return x.num>y.num;//位数相同，但a字典序排列比b大 //字符串的比较是比较字典序（第一位小的在前面，如果相同比较第二位，以此类推）例如10000小于1200小于200； } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { a[i].id = i; cin >> a[i].num; } sort(a + 1, a + n + 1, cmp); cout << a[1].id << endl << a[1].num ; return 0; }
unique() 去重函数
需要引入头文件#include< algorithm >
unique()函数是一个去重函数，STL中unique的函数 unique的功能是去除相邻的重复元素(只保留一个)
[NOIP2006 普及组] 明明的随机数N N N 1 1 1 1000 1000 1 0 0 0 ( N ≤ 100 ) (N\leq100) ( N ≤ 1 0 0 ) 1 1 1 1 1 1 N N N 2 2 2 N N N 1 1 1 1 1 1 M M M 2 2 2 M M M
1 2 10 20 40 32 67 40 20 89 300 400 15
样例输出 #1
1 2 8 15 20 32 40 67 89 300 400
AC(运用)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <algorithm> using namespace std;int a[200 ];int main () int n,cnt; cin>>n; for (int i=0 ;i<n;i++){ cin>>a[i]; } sort (a,a+n); cnt=unique (a,a+n)-a; cout<<cnt<<endl; for (int i=0 ;i<cnt;i++){ cout<<a[i]<<" " ; } } ``` ## 第15 章线性表 ### 数组 #### 例15.1 >深基15. 例1 】询问学号 题目描述 有 $n (n \le 2 \times 10 ^6 )$ 名同学陆陆续续进入教室。我们知道每名同学的学号（在 $1 $ 到 $10 ^9 $ 之间），按进教室的顺序给出。上课了，老师想知道第 $i$ 个进入教室的同学的学号是什么（最先进入教室的同学 $i=1 $），询问次数不超过 $10 ^5 $ 次。 输入格式 第一行 $2 $ 个整数 $n$ 和 $m$，表示学生个数和询问次数。 第二行 $n$ 个整数，表示按顺序进入教室的学号。 第三行 $m$ 个整数，表示询问第几个进入教室的同学。 输出格式 输出 $m$ 个整数表示答案，用换行隔开。 样例 #1 样例输入 #1
10 3
1
##### AC代码
```c++
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> stu;
int n, m, temp;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> temp;
stu.push_back(temp);
//cin >> stu[i];这种输入不行
}
for (int i = 0; i < m; i++)
{
cin >> temp;
cout << stu[temp - 1] << endl;
}
return 0;
}
alipay
wechat