• 【算法】PTA刷题记录

    1004 成绩排名

     题目很简单，但太久没敲过代码甚至不记得sort函数怎么用。

    把姓名，学号，成绩存进结构体里。写一个cmp，就可以对结构体数组按照成绩进行排序。

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. struct stud
    5. {
    6. 	string name,num;
    7. 	int score;
    8. }stu[N];
    9. bool cmp(stud a,stud b)
    10. {
    11. 	return a.score
    12. }
    13. signed main()
    14. {
    15. 	int n;
    16. 	cin>>n;
    17. 	for(int i=1;i<=n;i++)
    18. 	{
    19. 		cin>>stu[i].name>>stu[i].num>>stu[i].score; 
    20. 	}
    21. 	sort(stu+1,stu+n+1,cmp);
    22. 	
    23. 	cout<" "<
    24. 	cout<1].name<<" "<1].num;
    25. 	
    26. 	return 0;
    27. }

    1005 继续(3n+1)猜想

    这题重点在于理解题目意思，“现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字”。

    我开始理解的是要求每个数求解过程中出现的在a数组中的数，后来才发现，题目是要剔除那些在求解一个数过程中出现的数。

    比如：

    int:6
    out:3 5 6 7 8 11

    3-》5-》8-》4-》2-》1                                                 因此，5 8被剔除

    6-》3-》5-》8-》4-》2-》1                                          因此，3也被剔除

    7-》11-》17-》26-》13-》20-》10-》58-》4-》2-》1 因此，11也被剔除

    因而题目只剩下6，7。

    1. #include
    2. using namespace std;
    3. const int N=110;
    4. set<int> st;
    5. int ans[N],a[N];
    6. signed main()
    7. {
    8.     int n;
    9.     cin>>n;
    10.     for(int i=1;i<=n;i++)
    11.     {
    12.         cin>>a[i];
    13.         if(st.find(a[i])==st.end()) st.insert(a[i]);
    14.     }
    15.     for(int i=1;i<=n;i++)
    16.     {
    17.         int x=a[i];
    18.         while(x!=1)
    19.         {
    20.             if(x%2)	x=(3*x+1)/2;
    21. 			else	x/=2;
    22. 			
    23.             if(st.find(x)!=st.end()) st.erase(x);//删除过程中出现的数 
    24.         }
    25.     }
    26.     int j=0;
    27.     for(auto i:st)	ans[++j]=i;
    28. 	for(int i=j;i>=1;i--)
    29. 	{
    30. 		cout<
    31. 		if(i!=1) cout<<" ";
    32. 	}
    33.     
    34.     return 0;
    35. }

    1006 换个格式输出整数

    这题比较简单。只要注意存的字符串方向就行。 

    1. #include
    2. using namespace std;
    3. const int N=110;
    4.  
    5. signed main()
    6. {
    7.     string x;
    8.     cin>>x;
    9.     int n=x.length();
    10.     for(int i=0;i<=n-1;i++)
    11.     {
    12.     	int p=x[i]-'0';
    13.     	for(int j=1;j<=p;j++)
    14.     	{
    15.     		if((n-i)==3) cout<<"B";
    16.     		else if((n-i)==2) cout<<"S";
    17. 			else cout<
    18. 		}
    19. 	}
    20.     
    21.     return 0;
    22. }

     1007 素数对猜想

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. int cnt;
    5. int a[N];
    6. bool isprime(int x)
    7. {
    8. 	if(x==1) return false;
    9. 	for(int i=2;i<=x/i;i++)
    10. 	{
    11. 		if(x%i==0) return false;
    12. 	}
    13. 	return true;
    14. }
    15. signed main()
    16. {
    17. 	int n,k=0;
    18. 	cin>>n;    
    19.     for(int i=2;i<=n-2;i++)
    20.     {
    21.     	if(isprime(i)&&isprime(i+2))
    22.     	{
    23.     		cnt++;
    24. 		}
    25. 	}
    26. 	cout<
    27.     return 0;
    28. }

     1008 数组元素循环右移问题

    顺还队列的思想。

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. int a[N],b[N];
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	cin>>n>>m;
    9. 	for(int i=0;i
    10. 	{
    11. 		cin>>a[i];
    12. 	}
    13. 	for(int i=0;i
    14. 	{
    15. 		b[(i+m)%n]=a[i]; 
    16. 	}
    17. 	for(int i=0;i
    18. 	{
    19. 		cout<
    20. 		if(i!=n-1) cout<<" ";
    21. 	}
    22.     return 0;
    23. }

     1009 说反话

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. char g[85][20];
    5. signed main()
    6. {
    7. 	int i=1;
    8. 	while((scanf("%s",g[i++]))!=EOF){
    9. 		getchar();
    10. 	}
    11. 	for(int j=i-2;j>=1;j--)
    12. 	{
    13. 		cout<
    14. 		if(j!=1) cout<<" ";
    15. 	}
    16.     return 0;
    17. }

    1010 一元多项式求导

    1. #include
    2. using namespace std;
    3. signed main()
    4. {
    5.     int x,n;
    6.     scanf("%d %d",&x,&n);
    7.     if(n==0)printf("%d %d",0,0);
    8.     else  printf("%d %d",x*n,n-1);
    9.     while(scanf("%d %d",&x,&n)!=EOF)
    10.     {
    11.         if(n!=0)printf(" %d %d",n*x,n-1);
    12.     }
    13.     return 0;
    14. }

    1011 A+B 和 C

    题目很简单，复习一下进制。

     2的31次方：2147483648。也就是1e9-1e10

    int 范围是

    -2147483648～2147483647 也就是2的31次方

    long long的最大值：9223372036854775807

    所以开longlong不会爆

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4.  
    5. bool solve()
    6. {
    7. 	long long a,b,c;
    8. 	cin>>a>>b>>c;
    9. 	if(a+b>c) return true;
    10. 	else return false;
    11. }
    12. signed main()
    13. {
    14. 	int t;
    15. 	cin>>t;
    16. 	for(int i=1;i<=t;i++)
    17. 	{
    18. 		if(solve()) cout<<"Case #"<": true"<<"\n";
    19. 		else cout<<"Case #"<": false"<<"\n"; 
    20. 	}
    21. 	
    22.     return 0;
    23. }

     1012 数字分类

     没有思路可言，纯模拟题。

    1. #include
    2.  
    3. using namespace std;
    4.  
    5. int main() {
    6. 	//ios::sync_with_stdio(false);
    7. 	int n, num;
    8. 	int ans[6] = { 0 };
    9. 	double A4 = 0.0;
    10. 	cin >> n;
    11. 	int t = 1;
    12. 	bool flag[6] = { false };//判断每个类型的数是否有出现
    13.  
    14. 	for (int i = 0; i < n; i++) {
    15. 		cin >> num;
    16. 		if (num % 10 == 0 ) {
    17. 			ans[1] += num;
    18. 			flag[1] = true;
    19. 		}
    20. 		else if (num % 5 == 1) {
    21. 			ans[2] = ans[2] + num * t;
    22. 			t = -t;
    23. 			flag[2] = true;
    24. 		}
    25. 		else if (num % 5 == 2) {
    26. 			ans[3]++;
    27. 			flag[3] = true;
    28. 		}
    29. 		else if (num % 5 == 3) {
    30. 			ans[4]++;//统计被5除后余3的数字的个数
    31. 			A4 += num;
    32. 			flag[4] = true;
    33. 		}
    34. 		else if (num % 5 == 4) {
    35. 			if (ans[5] < num) ans[5] = num;
    36. 			flag[5] = true;
    37. 		}
    38. 	}
    39.  
    40. 	for (int i = 1; i < 6; i++) {
    41. 		if (i != 1) cout << " ";
    42. 		if (!flag[i]) {
    43. 			cout << "N";
    44. 		}
    45. 		else if (i == 4) {
    46. 			printf("%.1f", A4 / ans[4]);
    47. 		}
    48. 		else {
    49. 			cout << ans[i];
    50. 		}
    51. 	}
    52.  
    53. 	return 0;
    54. }
    55.

    1013 数素数 

    第四个测试点过不了，查到了原因

    把范围改到104730以内（因为第10000个素数等于104729），这个数既不爆也包含了第10000个素数 

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. int a[N];
    5. bool isprime(int x)
    6. {
    7. 	for(int i=2;i<=x/i;i++)
    8. 	{
    9. 		if(x%i==0) return false;
    10. 	}
    11. 	return true;
    12. }
    13. signed main()
    14. {
    15. 	int cnt=0,j=0;
    16. 	int n,m;
    17. 	cin>>n>>m;
    18. 	for(int i=1;i<=104730;i++)
    19. 	{
    20. 		if(isprime(i)) a[j++]=i;
    21. 	}
    22. 	for(int i=n;i<=m;i++)
    23. 	{
    24. 			cout<
    25. 			++cnt;
    26. 			if(cnt%10==0) cout<<"\n";
    27. 			else if(cnt%10&&i!=m) cout<<" ";
    28. 	}
    29.     return 0;
    30. }

     1014 福尔摩斯的约会

    1. #include
    2. #include
    3. using namespace std;
    4. int main()
    5. {
    6. 	int flag = 0;
    7. 	string s1, s2, s3, s4;
    8. 	cin >> s1 >> s2 >> s3 >> s4;
    9. 	string weight[7] = { "MON","TUE","WED","THU","FRI","SAT","SUN" };
    10. 	for (int i = 0; i < s1.size()&&isize(); i++)
    11. 	{
    12. 		if (flag)
    13. 		{
    14. 			if (s1[i]<='9'&&s1[i]>='0' && s1[i] == s2[i])
    15. 			{
    16. 				printf("%02d:", (s1[i] - '0'));
    17. 				break;
    18. 			}
    19. 			else if (s1[i] >= 'A'&&s1[i] <= 'N'&&s1[i] == s2[i])
    20. 			{
    21. 				printf("%02d:", (s1[i] - 'A' + 10));
    22. 				break;
    23. 			}
    24. 		}
    25. 		else if (s1[i] >= 'A'&&s1[i] <= 'G'&&s1[i] && s1[i] == s2[i])
    26. 		{
    27. 			flag = 1;
    28. 			cout << weight[s1[i] - 'A'] << " ";
    29. 		}
    30. 	}
    31. 	for (int i = 0; i < s3.size()&&isize(); i++)
    32. 	{
    33. 		if(isalpha(s3[i])&&s3[i]==s4[i])
    34. 		{
    35. 			printf("%02d",i);
    36. 		}
    37. 	}
    38. 	return 0;
    39. }

    1015 德才论 

    模拟题是真恶心啊，

    “，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。”看漏了就只有4分，

    另外这题卡cin，cout，因为数据量比较大。加了下面的才能过。

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    1. #include
    2. using namespace std;
    3. const int N=1e5+10;
    4. struct stu{
    5. 	string num;
    6. 	int de,cai;
    7. 	int sum;
    8. }a[N],b[N];
    9. mapint> mp;
    10. bool cmp2(stu st1,stu st2)
    11. {
    12. 	if(st1.sum!=st2.sum) return st1.sum>st2.sum;
    13. 	else if(st1.de!=st2.de) return st1.de>st2.de;
    14. 	else return st1.num
    15. }
    16. signed main()
    17. {
    18.     std::ios::sync_with_stdio(false);
    19.     std::cin.tie(nullptr);
    20. 	int n,l,h;
    21. 	cin>>n>>l>>h;
    22. 	int p=0;
    23. 	for(int i=1;i<=n;i++) 
    24. 	{
    25. 		cin>>a[i].num>>a[i].de>>a[i].cai;
    26. 		a[i].sum=a[i].cai+a[i].de;
    27. 		if(a[i].de>=h&&a[i].cai>=h)//德才均不低于优先录取线 
    28. 		{
    29. 			b[++p]=a[i];
    30. 			mp[a[i].num]=1;
    31. 		}
    32. 	}
    33. 	sort(b+1,b+p+1,cmp2);
    34. 	/*for(int i=1;i<=p;i++)
    35. 	{
    36. 		cout<
    37. 	}*/
    38. 	int q=p;
    39. 	for(int i=1;i<=n;i++) 
    40. 	{
    41. 		if(a[i].decontinue; 
    42. 		if(a[i].de>=h&&a[i].cai//才分不到但德分到优先录取线
    43. 		{
    44. 			b[++q]=a[i];
    45. 			mp[a[i].num]=1;
    46. 		}
    47. 	}
    48. 	sort(b+p+1,b+q+1,cmp2);
    49. 	
    50. 	int j=q;
    51. 	for(int i=1;i<=n;i++) 
    52. 	{
    53. 		if(a[i].decontinue; 
    54. 		if(a[i].de=a[i].cai&&!mp[a[i].num])
    55. 		{
    56. 			b[++j]=a[i]; //德才分均低于 H，但是德分不低于才分的考生
    57. 			mp[a[i].num]=1;
    58. 		}
    59. 	}
    60. 	sort(b+q+1,b+j+1,cmp2);
    61. 	int t=j;
    62. 	for(int i=1;i<=n;i++)
    63. 	{//其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。
    64. 		if(a[i].decontinue; 
    65. 		if(!mp[a[i].num])
    66. 		{
    67. 			b[++t]=a[i];
    68. 		}
    69. 	}
    70. 	sort(b+j+1,b+t+1,cmp2);
    71. 	
    72. 	cout<
    73. 	for(int i=1;i<=t;i++)
    74. 	{
    75. 		cout<" "<" "<
    76. 	}
    77.     return 0;
    78. }

  • 相关阅读:
    前端相关题目随笔
    一个比 ping 更强大、更牛逼的命令行工具
    RTOS任务调度过程（上下文切换）
    Zookeeper部署运行_集群安装
    芒果改进目录一览｜改进YOLOv5、YOLOv7等YOLO模型全系列目录
    信息系统集成专业技术知识
    Java - Gson和Fastjson如何选择？
    Jupyter的安装
    a16z公布AI产品流量排名，ChatGPT占据榜首
    Oracle/PLSQL: Acos Function
  • 原文地址：https://blog.csdn.net/m0_74183164/article/details/132922601