c++算法学习
一个素数，若依次从低位去掉一位、两位、……若所得各数仍都为素数，则称该数为超级素数。例如：由于239、23、2均为素数，则239为超级素数。求：[2, n)以内的超级素数，输出时用空格隔开。
这里记录了我大一入学至今的c++学习历程，目前只更新到bfs，后续的dp以及图论等内容，我会及时补上
一.简单字符串
1． ISBN 号码
题目
题目描述
每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 9 位数字、 1 位识别码和 3 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 670 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以 1 加上次位数字乘以 2 ……以此类推，用所得的结果 mod 11 ，所得的余数即为识别码，如果余数为 10 ，则识别码为大写字母 X 。例如 ISBN 号码 0-670-82162-4 中的识别码 4 是这样得到的：对 067082162 这 9 个数字，从左至右，分别乘以 1,2,......,9 再求和，即 0 *s 1+6 *s 2+……+2 *s 9=158 ，然后取 158 mod 11 的结果 4 作为识别码。
你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出你认为是正确的 ISBN 号码。
输入格式
一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。
输出格式
一行，假如输入的 ISBN 号码的识别码正确，那么输出 Right，否则，按照规定的格式，输出正确的 ISBN 号码（包括分隔符 -）。
样例1
0-670-82162-4
Right
样例2
0-670-82162-0
0-670-82162-4
解题报告
读题与思路
由题可知，所输入字符串的长度是固定的，为了方便下文的按规定输出，可以用char存储
首先，要提取出其中数字，然后单独处理(?)，并依次计算乘积，相加，再判断是否符合
其次，判断数据类型的大小，最大不过9 *（1+2+3+4+5+6+7+8+9），只用int存储就可以
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
char x[13];
for(int i = 0; i <= 12; i++)
cin >> x[i];
int sum = 0, k = 1;
for(int i = 0; i <= 10; i++)
if(i != 1 && i != 5)
{
sum += (x[i] - '0') * k;
k++;
}
if( (sum % 11) == (x[12] - '0') || sum % 11 == 10 && x[12] == 'X')
cout << "Right";
else
{
for(int i = 0; i <= 11; i++)
cout << x[i];
if(sum % 11 != 10) cout << sum % 11;
else cout << "X";
}
}
2.字符串的展开c
题目
题目描述
在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于 d-h 或者 4-8 的字串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为 defgh 和 45678。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号 - ，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。
(2) 参数 p1 ：展开方式。 p1=1 时，对于字母子串，填充小写字母； p1=2 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。 p1=3 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 * 来填充。
(3) 参数 p2 ：填充字符的重复个数。 p_2=k 表示同一个字符要连续填充 k 个。例如，当 p_2=3 时，子串d-h 应扩展为 deeefffgggh。减号两边的字符不变。
(4) 参数 p3 ：是否改为逆序： p3=1 表示维持原来顺序， p_3=2 表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当 p1=1 、 p2=2 、 p3=2 时，子串 d-h 应扩展为 dggffeeh。
(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：d-e 应输出为 de，3-4 应输出为 34。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：d-d 应输出为 d-d，3-1 应输出为 3-1。
40\% 的数据满足：字符串长度不超过 5 。
100\% 的数据满足： 1<=p1<=3, 1<=p2<=8, 1<=p3<=2 。字符串长度不超过 100 。
输入格式
共两行。
第 1 行为用空格隔开的 3 个正整数，依次表示参数 p1,p2,p3 。
第 2 行为一行字符串，仅由数字、小写字母和减号 - 组成。行首和行末均无空格。
输出格式
共一行，为展开后的字符串。
样例 1
2 8 2 --09-8-w-er-7h-08w-e7-hc-r890-q7w-eh-rc98-07-q8-ewr-8h-c-8-294-5-dsf--k-h-2-48-3k-h-sd-fq-a-
--09-8-w-er-7h-08w-e7-hcQQQQQQQQPPPPPPPPOOOOOOOONNNNNNNNMMMMMMMMLLLLLLLLKKKKKKKKJJJJJJJJIIIIIIIIHHHHHHHHGGGGGGGGFFFFFFFFEEEEEEEEDDDDDDDDr890-q7w-ehQQQQQQQQPPPPPPPPOOOOOOOONNNNNNNNMMMMMMMMLLLLLLLLKKKKKKKKJJJJJJJJIIIIIIIIrc98-07-q8-ewr-8h-c-8-2945-dsf--k-h-23333333348-3k-hRRRRRRRRQQQQQQQQPPPPPPPPOOOOOOOONNNNNNNNMMMMMMMMLLLLLLLLKKKKKKKKJJJJJJJJIIIIIIIIsdEEEEEEEEfq-a-
样例 2
3 1 1 -z-l-k-d-h-f-q-w-y-e-r-o-i-q-u-y-e-s-a-k-j-d-h-f-l-a-k-s-d-h-f-i-q-u-i-y-r-q-l-w-e-h-k-z-x-h-d-f-l-k
-z-l-k-d***h-f**********q*****w*y-e************r-o-i*******q***u***y-e*************s-a*********k-j-d***h-f*****l-a*********k*******s-d***h-f**i*******q***u-i***************y-r-q-l**********w-e**h**k**************z-x-h-d*f*****l-k
解题报告
读题与思路
先用ok_for_rule（）函数，判断是否符合将 c1-c2 展开的规定
然后符合的话，就利用p1_do（）函数进行处理，再根据p2,p3具体的值进行处理；
不符合就直接输出当前字符
易错点是每次判断 ‘“ - ”’时，要补充的字符的个数，以及正序和倒序输出时的起点与终点。
代码实现
#include<bits/stdc++.h>
using namespace std;
bool ok_for_rule(char a, char b, char c)
{
if(a >= 'a' && c <= 'z' || a >= '0' && c <= '9')
if(a < c && b == '-') return 1;
return 0;
}
void p2_do(char a, int p2)
{
while(p2) p2--, cout << a;
}
void p3_do(char a, char b, int p2, int p3)
{
a++, b--;
if(p3 == 1) while(a <= b) p2_do(a, p2), a++;
else while(a <= b) p2_do(b, p2), b--;
}
void p1_do(char a, char b, int p1, int p2, int p3)
{
if(p1 == 1) p3_do(a, b, p2, p3);
else if(p1 == 2)
{
if(a >= '0' && a <= '9')
p3_do(a, b, p2, p3);
else
a -= 32, b -= 32, p3_do(a, b, p2, p3);
}
else
{
a++, b--;
while(a <= b) p2_do('*', p2), a++;
}
}
int main()
{
int p1, p2, p3;
cin >> p1 >> p2 >> p3;
string s1, s2;
cin >> s1;
cout << s1[0];
int x1 = s1.size(), x2 = 1;
for(int i = 1; i < x1 - 1; i++)
{
if( ok_for_rule(s1[i - 1], s1[i], s1[i + 1]) )
p1_do(s1[i - 1], s1[i + 1], p1, p2, p3);
else cout << s1[i];
}
cout << s1[x1 - 1];
}
3.四舍五入
题目
题目描述
将浮点数 x 四舍五入保留 k 位小数后输出。
输入格式
第一行一个浮点数 x
第二行一个非负整数 k
输出格式
输出一个浮点数。
样例 1
3.14 9
3.140000000
样例 2
3.14159 3
3.142
解题报告
读题与思路
如果，只用double，发现简单的四舍五入对于k = 9时会出错。
不如用字符串处理，先用string读入，然后看看小数点前有几个数，小数点后有几个数。
再根据保留的小数的位数的下一位，看看是不是大于等于5，然后决定上一位要不要进一
另外要特别处理，保留0位小数时，整数进一的问题
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int k;
cin >> s >> k;//3.1415
int len = s.length();
int i, r = 0;
for(i = 0; i < len; i++)
{
if(s[i] == '.')
break;
}
r = len - i - 1;//4
if(k == 0)
{
if(s[i + 1] >= '5')
s[i - 1]++;
for(int j = 0; j < i; j++)
cout << s[j];
}
else
{
if(r > k)
{
if(s[i + k + 1] >= '5') s[i + k]++;
for(int j = 0; j < len - (r - k); j++)
cout << s[j];
}
else if(r != k)
{
cout << s;
for(int j = 0; j < k - r; j++)
cout << '0';
}
}
}
4.查找资料
题目
题目描述
南师大敬文图书馆的资料太多了。小明和小璐想编个程序，帮助自己快速的查找资料。
输入格式
输入两行，第一行是想找的资料字符串，长度不超过10万。第二行是一个关键词字符串，长度不超过100。
输出格式
输出一行，关键词在资料中出现的次数。
样例1
We love world, We love human, We love animal. love
3
样例2
aaaaaaaaaaaa aaaa
3
解题报告
读题与思路
新生赛里卡掉的题，如今突然做出来了。用比较简短的代码实现这个
首先是对未知长度的字符串的读取，利用get_line()函数；
然后遍历这个长字符串，并对关键词进行对照；
困难的一点，是不知道如何对照，如果是python的话，一个in就解决了(?)。
当长字符串中的某个字母和关键词的第一个字母相同时，开始第二层遍历，一旦不一样就打断，并返回第一层的遍历，
而且第二层遍历时 i 与 j 要同时++
第一次提交通过了第一组测试数据，而没能通过第二组。
分析后发现，第一二组的区别在于连续与否，第二组长字符串a是连续的，所以i与j同时++，会导致i多进一个，
所以下文计数时，补充了一个 i--
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s[10010];
cin.getline(s, 10010);
string s1 = s;
string s2;
cin >> s2;
int x1 = s1.size();
int x2 = s2.size();
int cnt = 0;
for(int i = 0; i < x1; i++)
{
int tmp = i;
for(int j = 0; j < x2; j++)
{
if(s2[j] == s1[i])
{
i++;
continue;
}
else break;
}
if((i - tmp) == x2)
{
i--;
cnt++;
}
}
cout << cnt;
}
5.文字处理软件
题目
题目描述
你需要开发一款文字处理软件。最开始时输入一个字符串作为初始文档。可以认为文档开头是第 0 个字符。需要支持以下操作：
-
1 str：后接插入，在文档后面插入字符串 str ，并输出文档的字符串； -
2 a b：截取文档部分，只保留文档中从第 a 个字符起 b 个字符，并输出文档的字符串； -
3 a str：插入片段，在文档中第 a 个字符前面插入字符串 str ，并输出文档的字符串； -
4 str：查找子串，查找字符串 str 在文档中最先的位置并输出；如果找不到输出 -1 。
为了简化问题，规定初始的文档和每次操作中的 str 都不含有空格或换行。最多会有 q 次操作。
数据保证， 1 <= q <= 100 ，开始的字符串长度 <= 100 。
输入格式
第一行输入一个正整数 q ，表示操作次数。
第二行输入一个字符串 str ，表示最开始的字符串。
第三行开始，往下 q 行，每行表示一个操作，操作如题目描述所示。
输出格式
一共输出 q 行。
对于每个操作 1,2,3 ，根据操作的要求输出一个字符串。
对于操作 4 ，根据操作的要求输出一个整数。
样例
4 ILove 1 Luogu 2 5 5 3 3 guGugu 4 gu
ILoveLuogu Luogu LuoguGugugu 3
解题报告
读题与思路
无非就是写四个函数分别实现四个功能，但是如果写函数，这个初始字符串就无法更新，所以使用静态变量static
关于四个函数，
第二个类似于切片，我们用临时变量 s0 存储，然后再把 s0 的值赋给 s
第四个函数,就是一个简单的查找函数，从s[0]开始遍历到s[n],
分别比较s[i + j] 与 s0[ j ]，但凡有一个字符不匹配，就打断。否则，如果这个循环结束之后，如果 s0 里的字符完全遍历了，就是匹配到了。
再不然，s的所有字符匹配完之后没找到，就输出-1;
代码实现
#include<bits/stdc++.h>
using namespace std;
static string s;
void fun1()
{
string st;
cin >> st;
s += st;
cout << s << endl;
}
void fun2()
{
int a, b;
cin >> a >> b;
string s0;
for(int i = a; i < a + b; i++)
s0 += s[i];
s = s0;
cout << s << endl;
}
void fun3()
{
int a;
string str, s0;
cin >> a >> str;
for(int i = 0; i < a; i++)
s0 += s[i];
s0 += str;
for(int i = a; i < s.size(); i++)
s0 += s[i];
s = s0;
cout << s << endl;
}
void fun4()
{
string s0;
cin >> s0;
int i = 0;
for(; i < s.size(); i++)
{
int j = 0;
for(; j < s0.size(); j++)
{
if(s[i + j] != s0[j])
break;
}
if(j == s0.size())
{
cout << i << endl;
break;
}
}
if(i == s.size())
cout << -1 << endl;
}
int main()
{
int q;
cin >> q >> s;
for(int i = 0; i < q; i++)
{
int t;
cin >> t;
if(t == 1) fun1();
else if(t == 2) fun2();
else if(t == 3) fun3();
else fun4();
}
}
二.简单自定义函数
1.超级素数
题目
一个素数，若依次从低位去掉一位、两位、……若所得各数仍都为素数，则称该数为超级素数。例如：由于239、23、2均为素数，则239为超级素数。求：
[2, n)以内的超级素数，输出时用空格隔开。
解题报告
读题与思路
相对于使用自定义函数，直接实现这一功能需要多个循环的套用，而且判断的条件也比较绕，导致会在细节处出错。而自定义函数实现起来，
只需要先写一个判断本身是否为素数的函数，再写一个能右移(10)的函数，将两层函数套用即可实现。
但要注意的一点是，1作为特殊数，不应被判断为素数
代码实现
#include<bits/stdc++.h>
using namespace std;
bool sushu(int a)
{
if(a == 1) return 0;
else
{
for(int i = 2; i * i <= a; i++)
if(a % i == 0)return 0;
return 1;
}
}
bool superss(int a)
{
while(a > 0)
{
if(sushu(a) == false)
return false;
a /= 10;
}
return 1;
}
int main()
{
int n;
cin >> n;
for(int i = 2; i < n; i++)
if(superss(i)) cout << i << " ";
}
2. Function
题目
题目描述
对于一个递归函数 w(a,b,c)
-
如果 a <= 0 或 b <= 0 或 c <= 0 就返回值 1 。
-
如果 a>20 或 b>20 或 c>20 就返回 w(20,20,20)
-
如果 a<b 并且 b<c 就返回 w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c) 。
-
其它的情况就返回 w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
这是个简单的递归函数，但实现起来可能会有些问题。当 a,b,c 均为 15 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 w(30,-1,0) 又满足条件 1 又满足条件 2 ，请按照最上面的条件来算，答案为 1 。
输入格式
会有若干行。
并以 -1,-1,-1 结束。
输出格式
输出若干行，每一行格式：
w(a, b, c) = ans
注意空格。
数据规模与约定
保证输入的数在 [-9223372036854775808,9223372036854775807] 之间，并且是整数。
保证不包括 -1, -1, -1 的输入, 行数 T 满足 1 <= T <= 100000 。
样例
1 1 1 2 2 2 -1 -1 -1
w(1, 1, 1) = 2 w(2, 2, 2) = 4
解题报告
读题与思路
输入的数据确保在long long int之中，如果只用单纯的递归，会导致出一个大问题，比如题目中所说(15，15，15)会卡好几秒才会算出来,
但如果我们将每个可能出现的数对（a, b, c）都存到数组里，就没必要把做过的再重新遍历一遍，由于20以上都会归于20，所以我们只存0到20就可，
总共是20 *20 *20 = 8000次，电脑运行也就一下下。
另外需要注意，本题必须用else if 而不能只使用if ，因为第一个和第二个if 会重复执行
代码实现
#include<bits/stdc++.h>
using namespace std;
long long int w[30][30][30] = {0};
int ww(long long int a, long long int b, long long int c)
{
if(a <= 0 || b <= 0 || c <= 0)return 1;
else if(a > 20 || b > 20 || c > 20)return ww(20,20,20);
else if(a < b && b < c)return w[a][b][c - 1] + w[a][b - 1][c - 1] - w[a][b - 1][c];
else return w[a - 1][b][c] + w[a - 1][b - 1][c] + w[a - 1][b][c - 1] - w[a - 1][b - 1][c - 1];
}
int main()
{
for(int i = 0; i <= 20; i++)
for(int j = 0; j <= 20; j++)
for(int k = 0; k <= 20; k++)
w[i][j][k] = ww(i, j, k);
while(1)
{
long long int a, b, c;
cin >> a >> b >> c;
if(a == -1 && b == -1 && c == -1)
break;
else
cout << "w(" << a << ", " << b << ", " << c << ") = " << ww(a, b, c) << endl;
}
}
3.国王的魔镜
题目
题目描述
国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用AB来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为ABBA。如果再用一端接触的话，则会变成ABBAABBA（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。
输入格式
只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。
输出格式
只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。
样例
ABBAABBA
2
解题报告
读题与思路
ABBA ABBA --> AB BA --> AB
由此可知，明显是个回文串的判断，以及回文串砍半之后继续判断。
而且本题目中的回文串长度一定是偶数，所以奇数一定不是由魔镜变换而来。
看起来不算难，但还有一些点需要注意。
首先是字符串长度为2时的判断，
for(int i = 0; i < x1 / 2 - 1; i++) if(s1[i] != s1[x1 - i - 1]) return 0; return 1；
如果这样来写，就会导致 x 1 = 2 时，不进入循环，导致误判为字符串；
再次，是读题问题，输出的是最初的项链的长度，而不是项链切半的次数。
代码实现
核心代码如下，第一个自定义函数判断是否为回文串，第二个则求出原来项链的长度。
#include<bits/stdc++.h>
using namespace std;
bool huiwen(string s1, int x1)
{
if(x1 % 2 != 0) return 0;
else
{
if(x1 == 2)
if(s1[0] == s1[1]) return 1;
else return 0;
else
{
for(int i = 0; i < x1 / 2 - 1; i++)
if(s1[i] != s1[x1 - i - 1]) return 0;
return 1;
}
}
}
void su(string s2)
{
int x2 = s2.size(); int t = x2;
while(huiwen(s2, x2))
{
x2 /= 2;
t = x2;
}
cout << t;
}
int main()
{
string s;
cin >> s;
int x = s.size();
su(s);
}
4.谁拿了最多的奖学金
题目
题目描述
某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：
-
院士奖学金，每人 8000 元，期末平均成绩高于 80 分（ >80 ），并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得；
-
五四奖学金，每人 4000 元，期末平均成绩高于 85 分（ >85 ），并且班级评议成绩高于 80 分（ >80 ）的学生均可获得；
-
成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（ >90 ）的学生均可获得；
-
西部奖学金，每人 1000 元，期末平均成绩高于 85 分（ >85 ）的西部省份学生均可获得；
-
班级贡献奖，每人 850 元，班级评议成绩高于 80 分（ >80 ）的学生干部均可获得；
只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 87 分，班级评议成绩 82 分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是 4850 元。
现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。
输入格式
第一行是 1 个整数 N ，表示学生的总数。(1 <= N <= 100 )
接下来的 N 行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 20 的字符串（不含空格）；期末平均成绩和班级评议成绩都是 0 到 100 之间的整数（包括 0 和 100 ）；是否是学生干部和是否是西部省份学生分别用 1 个字符表示， Y 表示是， N 表示不是；发表的论文数是 0 到 10 的整数（包括 0 和 10 ）。每两个相邻数据项之间用一个空格分隔。
输出格式
共 3 行。
-
第 1 行是获得最多奖金的学生的姓名。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。
-
第 2 行是这名学生获得的奖金总数。
-
第 3 行是这 N 个学生获得的奖学金的总数。
样例
4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1
ChenRuiyi 9000 28700
解题报告
读题与思路
很显然，这是一个要应用结构体的排序题。题目繁琐，直接暴力实现即可，
但是在计算出每个学生的总奖学金得数后，还有考虑如果两位并列第一的情况，所以在结构体中还要添加一项，即他的序号。
bool cmp(student s1, student s2)
{
if(s1.jxj != s2.jxj)
return s1.jxj > s2.jxj;
return s1.px < s2.px;
}
核心代码如上图所示，如果奖学金数量不一样，就按从大到小排列，反之则按排名先后。然后再配合sort函数，可以轻松ac
最后再单独设一个变量来计算奖学金总量即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
struct student
{
string name;
int g1, g2;
char gb, xb;
int p, jxj, px;
};
bool cmp(student s1, student s2)
{
if(s1.jxj != s2.jxj)
return s1.jxj > s2.jxj;
return s1.px < s2.px;
}
int main()
{
int n, z = 0;
cin >> n;
student s[103];
for(int i = 0; i < n; i++){
cin >> s[i].name >> s[i].g1;
cin >> s[i].g2 >> s[i].gb;
cin >> s[i].xb >> s[i].p;
s[i].px = i;
s[i].jxj = 0;
if(s[i].g1 > 80 && s[i].p >= 1)
s[i].jxj += 8000;
if(s[i].g1 > 85 && s[i].g2 >80)
s[i].jxj += 4000;
if(s[i].g1 > 90)
s[i].jxj += 2000;
if(s[i].g1 > 85 && s[i].xb == 'Y')
s[i].jxj += 1000;
if(s[i].g2 > 80 && s[i].gb == 'Y')
s[i].jxj += 850;
}
for(int i = 0; i < n; i++)
z += s[i].jxj;
sort(s, s + n, cmp);
cout << s[0].name << endl << s[0].jxj << endl << z;
}
三.基础高精度
1.阶乘之和
题目
题目描述
用高精度计算出 S = 1! + 2! + 3! + ...... + n! （ n <= 50 ）。
其中 ! 表示阶乘，定义为 n!=n * (n-1) * (n-2) * ...... * 1 。例如， 5! = 5 * 4 * 3 * 2 * 1=120 。
输入格式
一个正整数 n 。
输出格式
一个正整数 S ，表示计算结果。
样例
3
9
解题报告
读题与思路
阶乘之和，如果n比较小，就这样就行
int a = 1, b = 0;
for(int i = 1; i <= n; i++)
{
a *= i;
b += a;
}
但是n很大之后会溢出所以用数组存，我们先用a[ ]存 i 的阶乘
然后b[ ]存a[0]+a[1]+...+a[n-1];
for(int i = 1; i <= n; i++)
{
na = mul(a, i, na);
add(b, a, na);
}
思路是类似的，所以只需要写出mul和add两个函数
add函数这里，下面我加了注释的两行，本来是用的 n b 存b数组的大小，但是对于这道题，当n变大时，a[i]对于b[i-1]是大一位甚至两位，
而此处也不会出现9999 + 1这种极端情况，所以相加时恰巧可以不用处理最高位进位的特殊情况，//当然，如果处理了将会更加保险
代码实现
#include<bits/stdc++.h>
using namespace std;
void Output(int a[], int na)
{
for(int i = na - 1; i >= 0; i--)
cout << a[i];
cout << endl;
}
int mul(int a[], int x, int na)
{
int jw = 0;
for(int i = 0; i < na; i++)
{
a[i] = a[i] * x + jw;
jw = a[i] / 10;
a[i] %= 10;
}
while(jw > 0)
{
a[na] += jw % 10;
jw /= 10;
na++;
}
return na;
}
void add(int b[], int a[], int na)
{
for(int i = 0; i < na; i++)
{
b[i] += a[i];
if(b[i] >= 10)
{
b[i + 1] += 1;
b[i] %= 10;
}
}
//if(b[nb] > 0) na++;
//return na;
}
int main()
{
int n, na;
cin >> n;
int a[10000] = {0}, b[10000] = {0};
a[0] = 1, na = 1;
for(int i = 1; i <= n; i++)
{
na = mul(a, i, na);
add(b, a, na);
}
Output(b, na);
}
2. k进制的高精度整数
题目
题目描述
自定义函数Mul(…)，实现一个K进制的高精度整数和一个常规整数的乘法运算。 编写main()函数，输入正整数x和n和k；然后以Mul函数为工具，计算x的n次方，并输出其k进制的表示形式。（x<10000，k<=16，最终运算结果的长度不超过10万）
解题报告
读题与思路
首先,先用a数组存下x的n次方,其次是10进制转换为其他进制,如果是转换为11到16进制,则需要补充大写字母。
10进制转换为k进制，需要整个数组除以k，然后用b数组存储余数，直到a数组除不开k。
a数组除以k时，从最高位开始除以，用一个临时变量x储存的a[ i max ]值，
如果x<k, 则需x = x * 10 + a[ i max - 1]，然后依次遍历下去
另外需要去除前导零，即最高位如果为零，就把a数组的长度减1，直到最高位不为零
代码实现
#include<bits/stdc++.h>
using namespace std;
int Mul(int a[],int na, int x)
{
int jw = 0;
for(int i = 0; i < na; i++)
{
int y = a[i] * x + jw;
a[i] = y % 10;
jw = y / 10;
}
while(jw > 0)
{
a[na] = jw % 10;
jw = jw / 10;
na++;
}
return na;
}
int change(int a[], int na, int k, int b[], int nb)
{
int x = 0, tmp = 0;
for(int i = na - 1; i >= 0; i--)
{
x += a[i];
if(x / k > 0)
{
a[i] = x / k;
x %= k;
}
else
a[i] = 0;
if(i == 0) b[nb] = x;
x *= 10;
}
while(1)
if(a[na-1] == 0)na--;
else break;
return na;
}
void clean(int b[], int nb)
{
for(int i = nb - 1; i >= 0; i--)
{
if(b[i] >= 10)
cout << char('A' + b[i] - 10);
else cout << b[i];
}
}
int main()
{
int x, n, k;
int a[10000] = {0}, na, b[10000] = {0}, nb = 0;
na = 1, a[0] = 1;
cin >> x >> n >> k;
for(int i = 1; i <= n; i++)
na = Mul(a, na, x);
while(na >= 1)
{
na = change(a, na, k, b, nb);
nb++;
}
clean(b, nb);
return 0;
}
3.小数的循环节
题目
题目描述
自定义函数Div (…)，将一个整数除以另一个整数，得到小数部分的循环节。 编写main()函数，依次输入正整数x1,y1和x2,y2（x1,y1,x2,y2<1亿）；然后分别调用Div函数，计算x1/y1和x2/y2的小数部分的循环节，并按照测试案例的格式输出之。（测试案例保证两数相除得到是无限循环小数，并且循环节的长度小于1000）
解题报告
读题与思路
关键在于，当除数再次出现时，将进入循环
求的是小数的循环节，所以只输出前导零和循环节即可。因此可以先令x取余y，这样确保小数点之前的都是0
定义一个商数组，与一个余数数组。每次相除，我们把除得小数存到商数组里，余数存到余数数组里，并且每次比较余数是否重新出现，
出现即结束。然后用s来保存输出的字符串
代码实现
#include<bits/stdc++.h>
using namespace std;
string Div(int x, int y)
{
x %= y;
int shang[1001] = {0}, yushu[1001] = {0}, pd = 1;
yushu[0] = x;
string s = "";
int first_forf, second_forf;
for(int i = 1; pd == 1; i++)
{
yushu[i] = x * 10;
shang[i] = yushu[i] / y;
x = yushu[i] % y;
for(int j = 1; j < i; j++)
{
if(yushu[i] == yushu[j])
{
first_forf = j;
second_forf = i;
pd = 0;
break;
}
}
}
s += "0.";
for(int i = 1; i < first_forf; i++)
s += "0";
s += "(";
for(int i = first_forf; i < second_forf; i++)
s += to_string(shang[i]);
s += ")";
return s;
}
int main()
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << Div(x1, y1) << endl;
cout << Div(x2, y2);
return 0;
}
四.简单模拟
1.报数
题目
题目描述
报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 7 的倍数，或十进制表示中含有数字 7 ，就必须跳过这个数，否则就输掉了游戏。
在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来！
形式化地，设 p(x) 表示 x 的十进制表示中是否含有数字 7 ，若含有则 p(x) = 1 ，否则 p(x) = 0 。则一个正整数 x 不能被报出，当且仅当存在正整数 y 和 z ，使得 x = yz 且 p(y) = 1 。
例如，如果小 r 报出了 6 ，由于 7 不能报，所以小 z 下一个需要报 8 ；如果小 r 报出了 33 ，则由于 34 = 17 * 2 ， 35 = 7 * 5 都不能报，小 z 下一个需要报出 36 ；如果小 r 报出了 69 ，由于 70 \sim 79 的数都含有 7 ，小 z 下一个需要报出 80 才行。
现在小 r 的上一个数报出了 x ，小 z 想快速算出他下一个数要报多少，不过他很快就发现这个游戏可比原版的游戏难算多了，于是他需要你的帮助。当然，如果小 r 报出的 x 本身是不能报出的，你也要快速反应过来小 r 输了才行。
由于小 r 和小 z 玩了很长时间游戏，你也需要回答小 z 的很多个问题。
输入格式
第一行，一个正整数 T 表示小 z 询问的数量。
接下来 T 行，每行一个正整数 x ，表示这一次小 r 报出的数。
对于 70% 的数据， T <= 10000 ， x <= 2 * {10}^5 。
对于 100% 的数据， 1 <= T <= 2 * {10}^5 ， 1 <= x <= {10}^7 。
输出格式
输出共 T 行，每行一个整数，如果小 r 这一次报出的数是不能报出的，输出 -1 ，否则输出小 z 下一次报出的数是多少。
样例 1
4 6 33 69 300
8 36 80 -1
样例 2
5 90 99 106 114 169
92 100 109 -1 180
解题报告
读题与思路
这是NOIP 2021提高组的一道题，我的思路是先利用noseven函数判断这个数含不含7，不含七再判断是不是素数，如果不是素数就一定有因子，再判断这个数的因子里有没有7；
思路清晰不过后三组数据超时了，留到以后再说吧。
代码实现
#include<bits/stdc++.h>
using namespace std;
bool isprime(int a)
{
if(a == 1) return 0;
for(int i = 2; i <= sqrt(a); ++i)
{
if(a % i == 0)return 0;
}
return 1;
}
bool noseven(int a)
{
int tmp = a;
while(tmp > 0)
{
if(tmp % 10 == 7)return 0;
tmp /= 10;
}
return 1;
}
bool yinshu_isnotprime(int a)
{
for(int i = 2; i <= sqrt(a); ++i)
{
if(a % i == 0)
{
int tmp = a / i;
if(!noseven(tmp) || !noseven(i))return 0;
}
}
return 1;
}
bool pd(int a)
{
if(noseven(a) && (isprime(a) || (!isprime(a) && yinshu_isnotprime(a))))
return true;
return false;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; ++i)
{
int x;
cin >> x;
if(pd(x))
{
for(int j = x + 1; ; ++j)
if(pd(j))
{
cout << j << endl;
break;
}
}
else cout << -1 << endl;
}
}
2.玩具谜题
题目
题目描述
小南有一套可爱的玩具小人, 它们各有不同的职业。
有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:
这时 singer 告诉小南一个谜題: “眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个玩具小人那里。 ”
小南发现, 这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人, 它的左边是顺时针方向, 右边是逆时针方向; 而面向圈外的玩具小人, 它的左边是逆时针方向, 右边是顺时针方向。
小南一边艰难地辨认着玩具小人, 一边数着:
singer 朝内, 左数第 3 个是 archer。
archer 朝外,右数第 1 个是 thinker 。
thinker 朝外, 左数第 2 个是 writer。
所以眼镜藏在 writer 这里!
虽然成功找回了眼镜, 但小南并没有放心。 如果下次有更多的玩具小人藏他的眼镜, 或是谜题的长度更长, 他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。 这样的谜題具体可以描述为:
有 n 个玩具小人围成一圈, 已知它们的职业和朝向。现在第 1 个玩具小人告诉小南一个包含 m 条指令的谜題, 其中第 z 条指令形如“左数/右数第 s ,个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。
输入格式
输入的第一行包含两个正整数 n,m ，表示玩具小人的个数和指令的条数。
接下来 n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 0 表示朝向圈内， 1 表示朝向圈外。 保证不会出现其他的数。字符串长度不超过 10 且仅由英文字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。
接下来 m 行，其中第 i 行包含两个整数 a_i,s_i ，表示第 i 条指令。若 a_i=0 ，表示向左数 s_i 个人；若 a_i=1 ，表示向右数 s_i 个人。 保证 a_i 不会出现其他的数， 1 <= s_i < n 。
输出格式
输出一个字符串，表示从第一个读入的小人开始，依次数完 m 条指令后到达的小人的职业。
样例 1
7 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2
writer
样例 2
10 10 1 C 0 r 0 P 1 d 1 e 1 m 1 t 1 y 1 u 0 V 1 7 1 1 1 4 0 5 0 3 0 1 1 6 1 2 0 8 0 4
y
解题报告
读题与思路
此处用结构体存储小人的职业和朝向
题目描述小人是逆时针排序的，所以处理时为了不必要的麻烦，可以把小人面向的方向反过来，用一个下标来存每一步的位置，
为了避免越界，可以每次处理后进行判断，然后再处理。
代码实现
#include<bits/stdc++.h>
using namespace std;
struct make
{
int way;
string career;
};
make a[100010];
int where(int sta, int step, make a[], int n, int pd)
{
if(a[sta].way == pd)
{
sta += step;
if(sta >= n)sta -= n;
}
else
{
sta -= step;
if(sta < 0)sta += n;
}
return sta;
}
int fun(int sta, int lr, int step, make a[], int n)
{
if(lr == 1) sta = where(sta, step, a, n, 0);
else sta = where(sta, step, a, n, 1);
return sta;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
{
cin >> a[i].way >> a[i].career;
}
int lr, step, sta = 0;
for(int i = 0; i < m; i++)
{
cin >> lr >> step;
sta = fun(sta, lr, step, a, n);
}
cout << a[sta].career;
}
3.均分纸牌
题目
题目描述
有 N 堆纸牌，编号分别为 1,2,....,N 。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4 时， 4 堆纸牌数分别为 9,8,17,6 。
移动 3 次可达到目的：
-
从第三堆取 4 张牌放到第四堆，此时每堆纸牌数分别为 9,8,13,10 。
-
从第三堆取 3 张牌放到第二堆，此时每堆纸牌数分别为 9,11,10,10 。
-
从第二堆取 1 张牌放到第一堆，此时每堆纸牌数分别为 10,10,10,10 。
输入格式
第一行共一个整数 N ，表示纸牌堆数。 第二行共 N 个整数 A_1,A_2,......,A_N ，表示每堆纸牌初始时的纸牌数。
输出格式
共一行，即所有堆均达到相等时的最少移动次数。
样例
4 9 8 17 6
3
解题报告
读题与思路
这道题看上去没什么思路，实际上就是个纸老虎。但实际上只用贪心就可以解决
由于题目规定纸牌总数为n的倍数，所以可以利用平均值。
再者，纸牌移动只能向左或向右，这一点就可以保证，不会有复杂的最优解，因为如果只有相隔较远的两堆不是平均值，移动起来会非常麻烦。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, a[101];
cin >> n;
int sum = 0, cnt = 0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
}
int aver = sum / n;
for(int i = 0; i < n; i++)
{
if(a[i] != aver)
{
cnt++;
a[i + 1] += a[i] - aver;
a[i] = aver;
}
}
cout << cnt;
}
4.我是拼写大王
题目
题目描述
定义：
-
若字符串 s， t 满足 = s=t，则称它们内容完全一致。
-
若字符串s,t 满足以下条件之一，则称它们内容相似.
-
在 s 中任意位置添加一个字符，可以得到 t。
-
在 s 中任意位置删去一个字符，可以得到 t。
-
在 s 中任意位置改变一个字符，可以得到 t。
-
现给定字典 D 和待检查的字符串 s(s 中包含由空格组成的若干单词)，请设计一个拼写检查程序，对于 s 输出修改建议。具体来说：
-
对于 s 中的某个单词，如果字典中存在该单词，则拼写无误，不需要修改。
-
否则（字典中不存在该单词的情况），如果字典中存在 唯一 的 内容相似 的单词，请将该单词修改为该单词，作为修改建议。
-
对于其他情况，在该单词末尾添加一个问号'?'，表示此处需要手动检查单词的拼写是否有误。
例如, D={this,is,a,bat,that,cat,b,c},s=thus was a hat，则：
-
第一个单词无法在字典中找到，但有唯一修改方案 this
-
第二个单词无法在字典中找到，但是字典中没有相似单词，所以直接插入一个 '?'
-
第三个单词正确，能找到原单词。所以不考虑两个相似的单词 b 和 c。
-
第四个单词无法在字典中找到，但是有两种修改方案 bat 和 cat，所以直接插入一个 '?'
因此，修改建议为:′this was? a hat?′，注意字符串原来的空格保持不变。
输入格式
第一行一个正整数 n，表示字典的单词数。
接下来一行 n 个单词 di 用单个空格隔开，表示字典中的单词。
第三行仅一个字符串 s，表示待分析的字符串。
输出格式
一个字符串，表示修改意见。
遇到字典中存在的单词时，原样输出。
否则，遇到字典中唯一相似的单词时，修改为该单词。
否则，在该单词末尾添加问号 ?。
样例 1
8 this is a bat that cat b c thus was a hat
this was? a hat?
样例 2
4 a ab abc c abcd acbd adbc bc
abc acbd? abc bc?
解题报告
读题与思路
一道稍微大一点的模拟，我觉得是这样。
先输入n个单词，我用存到结构体数组里。
其次输入一个带空格的字符串，我用away函数将字符串的单词提取出来，存到另一个结构体数组里，k代表单词个数
对于这道题，无非就是把这k个单词，分别和字典里的n个单词比较
而比较结果分三种：
1.字母个数相同： 可能相同或相似或不同
2.字母个数相差1： 可能相似或不同
3.字母个数相差 >= 2： 不同
对于第一种的判断（pd），按题目来说，只有一个字母不同才是相似。
所以我的思路是，如果遇到不一样的就跳过，如果又遇到不一样的就是不同。否则就是相似。再否则就是相同
对于第二种的判断，题目规定只允许有一个字母多了或少了，
此处这么处理：遇到不一样的字母，我们就存一下该字母的下标，然后去掉这个字母存到新的临时字符串里，将这个字符串与另一个字符串对比，如果相同，则返回相似，否则返回不同。
！！！好处是能解决adcd 和 abc， abcd和abc这两种情况；坏处就是写的有点乱，感觉还能优化一点！！！
另外我分别用0， 1， -1保存相同或相似等情况，有点乱，导致代码可读性下降
代码实现
#include<bits/stdc++.h>
using namespace std;
struct make
{
string s;
int len = 0;
int xs = 0;
};
int away(make b[], string t)
{
int x = t.size();
int k = 0;
for(int i = 0; i < x; i++)
{
if( t[i] >= 'a' && t[i] <= 'z')
{
b[k].s += t[i];
b[k].len++;
}
else k++;
}
return k + 1;
}
bool xiangsi(string s1, string s2)
{
int cnt = 0;
int x1 = s1.size(), x2 = s2.size();
int i1 = 0, i2 = 0;
while(i1 < x1 && i2 < x2)
{
if(s1[i1] != s2[i2])
{
string st1, st2;
for(int j = 0; j < x1; j++)
if(j != i1) st1 += s1[j];
for(int j = 0; j < x2; j++)
if(j != i2) st2 += s2[j];
if(s2 == st1 || s1 == st2)return true;
return false;
}
else cnt++;
i1++, i2++;
}
if(cnt == x1 || cnt == x2)return true;
return false;
}
int pd(string s1, string s2, int t1, int t2)
{
if(abs(t1 - t2) >= 2)
return -1;
else if(abs(t1 - t2) == 1)
{
if(xiangsi(s1, s2)) return 1;
return -1;
}
else
{
int cnt = 0;
for(int i = 0; i < t1; i++)
if(s1[i] != s2[i])cnt++;
if(cnt == 1) return 1;
if(cnt == 0) return 0;
return -1;
}
}
int main()
{
make a[5002], b[5002];
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i].s;
a[i].len = a[i].s.size();
}
string t; getchar();
getline(cin, t);
int k = away(b, t);
for(int i = 0; i < k; i++)
{
int tmp1, pd1 = 0;
string st;
for(int j = 0; j < n; j++)
{
tmp1 = pd(b[i].s, a[j].s, b[i].len, a[j].len);
if(tmp1 == 0)
{
pd1 = 1;
cout << b[i].s << " ";
break;
}
if(tmp1 == 1)
{
b[i].xs++;
st = a[j].s;
}
}
if(pd1 != 1)
{
if(b[i].xs != 1)
cout << b[i].s << "? ";
else cout << st << " ";
}
}
}
5.乒乓球
题目
题目描述
华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 11 分制和 21 分制下，双方的比赛结果（截至记录末尾）。
比如现在有这么一份记录，（其中 W 表示华华获得一分，L 表示华华对手获得一分）：
WWWWWWWWWWWWWWWWWWWWWWLW
在 11 分制下，此时比赛的结果是华华第一局 11 比 0 获胜，第二局 11 比 0 获胜，正在进行第三局，当前比分 1 比 1 。而在 21 分制下，此时比赛结果是华华第一局 21 比 0 获胜，正在进行第二局，比分 2 比 1 。如果一局比赛刚开始，则此时比分为 0 比 0 。直到分差大于或者等于 2 ，才一局结束。
你的程序就是要对于一系列比赛信息的输入（ WL 形式），输出正确的结果。
输入格式
每个输入文件包含若干行字符串，字符串有大写的 W 、 L 和 E 组成。其中 E 表示比赛信息结束，程序应该忽略 E 之后的所有内容。
输出格式
输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是 11 分制下的结果，第二部分是 21 分制下的结果，两部分之间由一个空行分隔。
样例 1
WWWWWWWWWWWWWWWWWWWW WWLWE
11:0 11:0 1:1 21:0 2:1
解题报告
读题与思路
这道题让我想起我错过的一道高中数学排列组合题，也是讲的乒乓球赛规
所以最开始读题我犯了同样的错误，可是题目所给的样例描述太过宽泛，让人看不透规则。所以我去百度搜了一下，11分制，一定是有人达到11分才算一局结束，然后这一局赢的多的计一分，
然后当局数分差大于等于2时比赛结束。
此处由于有换行，所以要用临时变量c存一下。而后续要对所给的字符串操作两遍，所以要用数组存起来，当然也可以用string字符串。
后续就是简单的判断处理了。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
char c;
vector<char>v;
while(1)
{
cin >> c;
if(c == 'E') break;
v.push_back(c);
}
int W = 0, L = 0;
for(int i = 0; i < v.size(); i++)
{
if(v[i] == 'W') W++;
else if(v[i] == 'L')L++;
if((W >= 11 || L >= 11) && abs(W - L) >= 2)
{
cout << W << ":" << L << endl;
W = 0, L = 0;
}
}
cout << W << ":" << L << endl;
cout << endl;
W = 0, L = 0;
for(int i = 0; i < v.size(); i++)
{
if(v[i] == 'W') W++;
else if(v[i] == 'L')L++;
if((W >= 21 || L >= 21) && abs(W - L) >= 2)
{
cout << W << ":" << L << endl;
W = 0, L = 0;
}
}
cout << W << ":" << L << endl;
}
6.确定进制
题目
题目描述
6 * 9=42 对于十进制来说是错误的，但是对于 13 进制来说是正确的。你的任务是写一段程序读入三个整数 p,q 和 r，然后确定一个进制 B(2 <= B <= 16) 使得 p* q=r。如果 B 有很多选择，则输出最小的一个。
例如：p=11,q=11,r=121，则有 11{(3)}\ * 11{(3)}=121{(3)}，因为 11{(3)}=1\ * 3^1+1\ * 3^0=4{(10)} 和 121{(3)}=1\ * 3^2+2\ * 3^1+1\ * 3^0=16{(10)}。对于进制 10, 有 11{(10)}\ * 11{(10)}=121{(10)}。这种情况下，应该输出 3。如果没有合适的进制，则输出 0。
输入格式
一行，包含三个整数 p,q,r，相邻两个整数之间用单个空格隔开。
输出格式
一个整数：即使得 p * q=r 成立的最小的 B。如果没有合适的 B，则输出 0。
样例
6 9 42
13
p,q,r 的所有位都是数字，并且 1 <= p,q,r <= 10^6。
解题报告
读题与思路
这道题就是简单的进制转换的操作，首先是找到输入的三个数中的出现过的最大数字，例如123最大是3，那么这个数一定是4-16进制。
总体思路就是，从k开始，把这三个数看成k进制，把前两个数变成十进制，然后相乘，最后与十进制下的第三个数比较。
此处的k即是首句中的最大数字加一。另外需要用longlong存
代码实现
#include<bits/stdc++.h>
using namespace std;
long long int find(long long int a)
{
long long int t = 0;
while(a > 0)
{
t = max(t, a % 10);
a /= 10;
}
return t;
}
long long int change(long long int a, long long int base)
{
long long int res = 0, i = 0;
while(a)
{
res += (a % 10) * (long long int)( pow(base, i) );
++i;
a /= 10;
}
return res;
}
int main()
{
long long int p, q, r;
cin >> p >> q >> r;
long long int k = max(find(p), find(q));
k = max(k, find(r));
for(int i = k + 1; i <= 16; i++)
{
long long int t1 = change(p ,i) * change(q ,i);
long long int t2 = change(r ,i);
if(t1 == t2)
{
cout << i;
return 0;
}
}
cout << 0;
}
7.Vigenère 密码
题目
16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法 Vigenère 密码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。
在密码学中，我们称需要加密的信息为明文，用 M 表示；称加密后的信息为密文，用 C 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 k。在 Vigenère 密码中，密钥 k 是一个字母串，k=k_1,k_2,…,k_n。当明文 M=m_1,m_2,…,m_n 时，得到的密文 C=c_1,c_2,…,c_n，其中 ，
Ci = Mi # Ki运算 # 的规则如下表所示：
Vigenère 加密在操作时需要注意：
-
#运算忽略参与运算的字母的大小写，并保持字母在明文 M 中的大小写形式；
-
当明文 M 的长度大于密钥 k 的长度时，将密钥 k 重复使用。
例如，明文 M={Helloworld}，密钥 k={abc} 时，密文 C={Hfnlpyosnd}。
输入格式
共 2 行。
第一行为一个字符串，表示密钥 k，长度不超过 100，其中仅包含大小写字母。
第二行为一个字符串，表示经加密后的密文，长度不超过 1000，其中仅包含大小写字母。
输出格式
一个字符串，表示输入密钥和密文所对应的明文。
样例
CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm
Wherethereisawillthereisaway
解题报告
读题与思路
初看题目确实被吓到，但本质只是一个小模拟，对于K中的任意一个字母，Ki - 'a' 或 Ki - ‘A’，就是明文加密时，后移的个数。该题所给的是暗文，所以要变成明文，则需要前移。而当k字符串长度小于m时，k需要重复利用。
所以，先把k全部转换成小写字母，以确定前移次数。
需要注意的是，例如Mi = a, Ki = b,此时Mi前移一位，a应该移动到z。所以代码中有一处比较，来决定是不是向前越界。
代码实现
#include<bits/stdc++.h>
using namespace std;
string change(string k, string m)
{
int x1 = k.size(), x2 = m.size();
for(int i = 0; i < x1; i++)
if(k[i] <= 'Z')
k[i] += 32;
int cmp1 = 0, cmp2 = 0;
int t = 0;
for(int i = 0; i < x2; i++)
{
if(m[i] <= 'Z') cmp1 = m[i] - 'A';
else cmp1 = m[i] - 'a';
cmp2 = k[t++] - 'a';
if(cmp1 >= cmp2) m[i] -= cmp2;
else m[i] = m[i] + 26 - cmp2;
if(t == x1) t = 0;
}
return m;
}
int main()
{
string k, m;
cin >> k >> m;
cout << change(k,m);
}
五.其他
1.求和
题目
题目描述
给定 n 个整数 a{1}, a{2}, ......, a_{n} , 求它们两两相乘再相加的和，即
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n 个整数 a{1}, a{2}, ..... ,a_{n} 。
输出格式
输出一个整数 S ，表示所求的和。请使用合适的数据类型进行运算。
样例 1
4 1 3 6 9
117
对于 30% 的数据, 1 <= n <= 1000,1 <= a_{i} <= 100 。
对于所有评测用例, 1 <= n <= 2 * 10^5, 1 <= a_{i} <= 1000 。
解题报告
读题与思路
这是一道去年蓝桥杯的简单题目，但是蕴含着前缀和这一简化方法。
也就是说，S = A1 * (A2 +...+ An) + A2 *(A3 +... + An) + ... + An-1 * (An)
设每一项后面的乘数项为Sn，则容易发现S1 = S2 + A2，... ，Sn-1 = Sn + An
这样只需最开始记录一个S1 = A1 +...+An, 然后每次遍历减去 A i 即可
代码实现
#include<bits/stdc++.h>
using namespace std;
int a[200005];
long long int sum1 = 0, sum2 = 0;
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
sum1 += a[i];
}
for(int i = 0; i < n; i++)
{
sum1 -= a[i];
sum2 += a[i] * sum1;
}
cout << sum2;
}
2.机器翻译
题目
题目描述
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M-1 ，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入格式
共 2 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 M,N ，代表内存容量和文章的长度。
第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000 ）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
输出格式
一个整数，为软件需要查词典的次数。
样例
3 7 1 2 1 5 4 4 1
5
样例解释
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
-
1：查找单词 1 并调入内存。 -
1 2：查找单词 2 并调入内存。 -
1 2：在内存中找到单词 1。 -
1 2 5：查找单词 5 并调入内存。 -
2 5 4：查找单词 4 并调入内存替代单词 1。 -
2 5 4：在内存中找到单词 4。 -
5 4 1：查找单词 1 并调入内存替代单词 2。
共计查了 5 次词典。
解题报告
读题与思路
可以用队列来实现，不过只用队列貌似比较麻烦，查找时还需要单独写一个函数。
用map<int, bool>来保存这个数是否在队列里。
对于读入的每一个数，
如果在队列里，就不处理。
如果不在，先判断队列满了吗，
满了：把队列的第一个踢出去，需要先把状态改成0，再移出队首。再把他移进来，状态改成1
不满：直接移进来，状态改成1；
当然，不在队列，就说明需要查字典，find++。
代码实现
#include<bits/stdc++.h>
using namespace std;
map<int, bool> m;
queue<int> q;
int main()
{
int M, N;
cin >> M >> N;
int cnt = 0, find = 0;
for(int i = 0; i < N; i++)
{
int t; cin >> t;
if( !m[t] )
{
m[t] = 1;
q.push(t);
if(cnt == M)
{
m[q.front()] = 0;
q.pop();
}
else
{
m[t] = 1;
cnt++;
}
find++;
}
}
cout << find;
}
六.递归 及推广
1.过河卒
题目
题目描述
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示， A 点 (0, 0) 、 B 点 (n, m) ，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 B 点坐标和马的坐标。 1 <= n, m <= 20 ， 0 <= 马的坐标 <= 20 。
输出格式
一个整数，表示所有的路径条数。
样例 #1
6 6 3 3
6
解题报告
读题与思路
有点像斐波那契数列，到某一点的路径数等于到能走这一点的两个点的路径之和。
我用 f 函数，来更新到该点的路径数，用 fw 数组存储避免重复调用以超时。// 纯递归超时代码见文件夹
cut函数判断该点是不是马的控制点，如果是，那么卒子不可能走到这一点，所以该点的路径是0。
不过记得用long long
代码实现
#include<bits/stdc++.h>
using namespace std;
long long int fw[21][21]={0};
long long int f(int a, int b, long long int f[21][21])
{
if(a == 0 && b == 0)return 1;
if(a < 0 || b < 0) return 0;
return fw[a][b];
}
bool cut(int mx, int my, int x, int y)
{
if(x == mx + 1 && y == my + 2 || x == mx + 2 && y == my + 1 ) return 1;
if(x == mx - 1 && y == my + 2 || x == mx + 2 && y == my - 1 ) return 1;
if(x == mx + 1 && y == my - 2 || x == mx - 2 && y == my + 1 ) return 1;
if(x == mx - 1 && y == my - 2 || x == mx - 2 && y == my - 1 ) return 1;
if(x == mx && y == my) return 1;
return 0;
}
int main()
{
int bx, by, mx, my, t1, t2;
cin >> bx >> by >> mx >> my;
for(int i = 0; i <= bx; i++)
{
for(int j = 0; j <= by; j++)
if( cut(mx, my, i, j) ) fw[i][j];
else
{
if( cut(mx, my, i - 1, j) ) t1 = 0;
else t1 = f(i - 1, j, fw);
if( cut(mx, my, i, j - 1) ) t2 = 0;
else t2 = f(i, j - 1, fw);
fw[i][j] = t1 + t2;
}
}
cout << fw[bx][by];
}
2.汉诺塔
题目
为了使汉诺塔更加生动形象，对于第 i 层，0 <= i <= n-1，我们赋予其为1，2，4.....2 ^ (i - 1)，并用每一座塔上的数的和来表示该塔的状态，请用代码
实现汉诺塔的最小步数解，要求每一步移动生动可见。
解题报告
读题与思路
最开始是打算用队列解决，顺便利用队列特点，逐步实现，
即先分别展现出三座塔最顶上的，比如三层的1 0 0 变成 2 0 1， 变成4 2 1，可是队列是先进先出，下一步4 2 1变成4 2 0，而不是预想的4 1 0，
幸好，队列不符合，栈符合。
接下来就是求和问题。用三个全局变量a1，b1，c1分别存储栈的和，然后弹出时或压入时相应地进行加减。
代码实现
#include<iostream>
#include<stack>
using namespace std;
stack <int> a, b, c;
int a1 = 0, b1 = 0, c1 = 0;
void move(char A, char C)
{
if (A == 'A')
{
if (C == 'C')
c.push(a.top()), a1 -= a.top(), c1 += a.top(), a.pop();
else
b.push(a.top()), a1 -= a.top(), b1 += a.top(), a.pop();
}
else if (A == 'B')
{
if(C == 'A')
a.push(b.top()), b1 -= b.top(), a1 += b.top(), b.pop();
else
c.push(b.top()), b1 -= b.top(), c1 += b.top(), b.pop();
}
else
{
if (C == 'A')
a.push(c.top()), c1 -= c.top(), a1 += c.top(), c.pop();
else
b.push(c.top()), c1 -= c.top(), b1 += c.top(), c.pop();
}
cout << a1 << " " << b1 << " " << c1 << endl;
}
void hanoi(int n, char A, char B, char C)
{
if (n == 1) move(A, C);
else
{
hanoi(n - 1, A, C, B);
move(A, C);
hanoi(n - 1, B, A, C);
}
}
int main()
{
int n, k;
cin >> n;
for (int i = n - 1; i >= 0; i--)
{
int t = pow(2, i);
a1 += t;
a.push(t);
}
cout << a1 << " " << b1 << " " << c1 << endl;
hanoi(n, 'A', 'B', 'C');
}
3.外星密码
题目
题目描述
有了防护伞，并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串 X 会压缩为 [DX]的形式（D是一个整数且 1<=D<=99），比如说字符串 CBCBCBCB 就压缩为 [4CB] 或者[2[2CB]，类似于后面这种压缩之后再压缩的称为二重压缩。如果是 [2[2[2CB]]]则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。
输入格式
输入一行，一个字符串，表示外星人发送的密码。
输出格式
输出一行，一个字符串，表示解压缩后的结果。
样例
AC[3FUN]
ACFUNFUNFUN
解题报告
读题与思路
最开始没注意到单词展开的次数最多是99。可知数字要么是一位要么两位。
展开时先找第一个右括号，再找往左找第一个左括号，这样有了内层左右括号的下标，从而展开，我把展开后的存到一个新字符串里。
如果新字符串不含括号，那么解压缩完毕，否则继续解压缩，即重复上述过程。//虽然洛谷给的是普及/提高-，但感觉难度甚至不如一些普及-
代码实现
#include<bits/stdc++.h>
using namespace std;
bool have_kuohao(string s)
{
for(int i = 0; i < s.size(); i++)
if(s[i] == '[')return 1;
return 0;
}
string open(string s)
{
if(!have_kuohao(s)) return s;//判断是否含括号
int left, right; //寻找内层括号下标
for(int i = 0; i < s.size(); i++)
if(s[i] == ']')
{ right = i; break;}
for(int i = right; i >= 0; i--)
if(s[i] == '[')
{ left = i; break;}
int time = 0, k = 0; //求解压缩的次数
for(int i = left + 1; i < right && s[i] <= '9'; i++, k++)
time = time * 10 + s[i] - '0';
string s1, s2; //去括号并展开
for(int i = 0; i < left; i++)
s1 += s[i];
for(int i = right + 1; i < s.size(); i++)
s2 += s[i];
for(int j = 0; j < time; j++)
for(int i = left + 1 + k; i < right; i++)
s1 += s[i];
s1 += s2;
return open(s1);
}
int main()
{
string s;
cin >> s;
s = open(s);
cout << s;
}
4.赦免战俘
题目
题目描述
现有 2^n * 2^n (n<=10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。
给出 n，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。
输入格式
一个整数 n。
输出格式
(2^n) * (2^n) 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。
样例
3
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1
解题报告
读题与思路
由于题目说是小于二的十次方，所以弄成一个1024*1024的全局数组，并初始化为1，memset不知道为何只能初始为0或-1，所以被迫手动赋值。
这道题主要是分治的思想。虽然知道要写成递归，却没找到下标的处理方法，被迫参考题解。
的确是知识盲区，没想到void也能使用递归，停止时直接return即可，不需要return值；
div函数主要是给将左上角的正方形数组赋值为0，其余三个正方形则递归调用；当n的值变成1即结束。
难就难在下标的处理上，不过写完一遍倒过来再看，也不是那么麻烦的。
代码实现
#include<bits/stdc++.h>
using namespace std;
int a[1025][1025], n;
void make1(int t, int a[1025][1025])
{
for(int i = 1; i <= t; i++)
for(int j = 1; j <= t; j++)
a[i][j] = 1;
}
void div(int n, int x, int y)
{
if(n == 1) return;
for(int i = x; i <= x + n / 2 - 1; i++)
for(int j = y; j <= y + n / 2 - 1; j++)
a[i][j] = 0;
div(n / 2, x + n / 2, y);
div(n / 2, x + n / 2, y + n / 2);
div(n / 2, x, y + n / 2);
}
void output(int t, int a[1025][1025])
{
for(int i = 1; i <= t; i++)
for(int j = 1; j <= t; j++)
cout << a[i][j] << " ";
cout << endl;
}
int main()
{
cin >> n;
int t = pow(2, n);
make1(t, a);
div(t, 1, 1);
output(t, a);
}
快速构建 Web 应用程序
更多推荐
27
0- 0
已为社区贡献1条内容
所有评论(0)