0%

中国矿业大学数据结构实践1

如题,贴出AC代码,仅供参考不提供讲解

代码主打的就是一个叛逆

问题 A: 找新朋友

内存限制:32 MB

时间限制:1.000 S

题目描述

新年快到了,天勤准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。

输入

第一行是测试数据的组数CN(Case number,1<CN<10000),接着有CN行正整数N(1<n<32768),表示会员人数。

输出

对于每一个N,输出一行新朋友的人数,这样共有CN行输出。

样例输入

1
2
3
2
25608
24027

样例输出

1
2
7680
16016

代码

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int euler(int n){
int ans = n;
for (int i = 2; i*i <= n; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
inline void soluteA(){
int T;
cin>>T;
while(T--){
int N;
cin>>N;
cout<<euler(N)<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

soluteA();

return 0;
}

问题 B: 互质

内存限制:32 MB

时间限制:1.000 S

题目描述

给你一个正整数n,请问有多少个比n小的且与n互质的正整数?
两个整数互质的意思是,这两个整数没有比1大的公约数。

输入

输入包含多组测试数据。每组输入是一个正整数n(n<=1000000000)。当n=0时,输入结束。

输出

对于每组输入,输出比n小的且与n互质的正整数个数。

样例输入

1
2
3
7
12
0

样例输出

1
2
6
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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int euler(int n){
int ans = n;
for (int i = 2; i*i <= n; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
inline void soluteB(){
int T;
cin>>T;
while(T!=0){
cout<<euler(T)<<endl;
cin>>T;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

soluteB();

return 0;
}

问题 C: CPP2023-47-约瑟夫问题

内存限制:128 MB

时间限制:1.000 S

题目描述

n个人围成一圈,按1到n的顺序编号。从第一个人开始报数(从1到m报数),凡报到m的人退出圈子,问最后留下的是原来的第几号。

输入

首先输入两个正整数n和m,n表示n个人围一个圈子(n>=2),m表示从1报数到m的人退出圈子(1=<m)。

输出

最后剩下的人的编号。

样例输入 复制

1
2 3

样例输出 复制

1
2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int f(int n, int m){
return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n,m;
cin>>n,m;
cout<<f(n,m)+1;

return 0;
}

问题 D: CPP2023-25-进制转换

内存限制:128 MB

时间限制:1.000 S

题目描述

编写程序演示把一个10进制整数转换为R进制的转换结果。

输入

正整数N和R,空格分隔
N是输入的十进制数,R需要转换的进制数,2<=R<=20

输出

将10进制整数转换为R进制的转换结果,超过9的数字符号显示为A、B、C……Z等字母。

样例输入

1
10 16

样例输出

1
A

代码

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a, 0, sizeof(a))
using namespace std;
const char num[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
stack<int> st;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, r;
cin >> n >> r;
while (n > 0) {
st.push(n % r);
n /= r;
}
while (st.size() != 0) {
cout << num[st.top()];
st.pop();
}

return 0;
}

问题 E: 整数求和式的计算

内存限制:128 MB

时间限制:1.000 S

题目描述

输入两个整数的求和式,比如1+2=,输出求和式和对应结果。请编程实现。

输入

一个求和式,形如a+b=。

输出

求和式及对应结果。

样例输入

1
1+2=

样例输出

1
1+2=3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

char x[200];
cin>>x;
cout<<x;
int a,b,i=0;
while(x[i]!='+')i++;
x[strlen(x)-1]=x[i]=' ';
sscanf(x,"%d%d",&a,&b);
cout<<a+b;

return 0;
}

问题 F: 波兰表达式

内存限制:128 MB

时间限制:1.000 S

题目描述

波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) 4的波兰表示法为 + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。

输入

输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。

输出

输出为一行,表达式的值(保留6位小数)。

样例输入

1
* + 11.0 12.0 + 24.0 35.0

样例输出

1
1357.000000

代码

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
52
53
54
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a, 0, sizeof(a))
using namespace std;
struct calc {
bool is_op;
union F {
char op;
double num;
} mem;
};
int main() {

vector<calc> vt;
double a;
calc m;
char x[200];
while (cin >> x) {
if (x[0] > '9' || x[0] < '0') {
m.is_op = true;
m.mem.op = x[0];
} else {
m.is_op = false;
sscanf(x, "%lf", &a);
m.mem.num = a;
}
vt.push_back(m);
}
for (int i = vt.size() - 1; i >= 0; i--) {
if (vt[i].is_op) {
double &x = vt[i + 2].mem.num, &y = vt[i + 1].mem.num;
switch (vt[i].mem.op) {
case '+':
y += x;
break;
case '-':
y -= x;
break;
case '*':
y *= x;
break;
case '/':
y /= x;
break;
}
vt.erase(vt.begin() + i + 2);
vt.erase(vt.begin() + i);
}
}
printf("%.6lf", vt[0].mem.num);
return 0;
}

问题 G: 合并队列

内存限制:128 MB

时间限制:1.000 S

题目描述

上体育课的时候,老师已经把班级同学排成了两个队列,而且每个队列都是按照从底到高排好队,现在需要把两个队列合并,合并后需要保证还是从低到高排列。合并队列,你能编程实现吗?

输入

第1行为n,表示开始排成的每个队列的长度。第2、3行是代表从小到大的n个整数,每行的整数间有一个空格间隔。

输出

输出占一行,为从小到大的整数,每个整数间间隔一个空格。

样例输入 复制

1
2
3
5
1 3 5 8 15
2 3 4 6 9

样例输出 复制

1
1 2 3 3 4 5 6 8 9 15

代码

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin>>N;
int a[20000],b[200000];
for(register int i=0;i<N;i++) cin>>a[i];
for(register int i=0;i<N;i++) cin>>b[i];
int pa=0,pb=0;
while(pa<N&&pb<N){
if(a[pa]<b[pb])
cout<<a[pa++]<<" ";
else
cout<<b[pb++]<<" ";
}
if(pa+pb!=2*N){
if(pa==N){
for(int i=pb;i<N;i++)
cout<<b[i]<<" ";
} else {
for(int i=pa;i<N;i++)
cout<<a[i]<<" ";
}
}

return 0;
}
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道