【Acwing积累】第一周(完全数、只出现一次的字符)

简介: 【Acwing积累】第一周(完全数、只出现一次的字符)

题目1:725.完全数

思路1:暴力解法

两层循环,一层次数,一层判断求和:

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n,a;
    cin>>n;
    while(n--)
    {
        cin>>a;
        int sum=0;
        for(int i=1;i<a;i++)
        {
            if(a%i==0) sum+=i;
        }
        if(sum==a) printf("%d is perfect\n",a);
        else printf("%d is not perfect\n",a);
    }
    
    return 0;
}

结果:Time Limit Exceeded


因为这里限制了:时间小于1亿,但这里N为100,数字可以为1亿,总共100亿,时间超太多了。


优化:暴力解法

我们求x的约数,其实不用找全,找到小的那个(假设为d),大的那个(假设为e)也可以通过除法得到。因此我们可以通过数学推导:因为d*e=x那么一定有d*d<=x;因此我们可以少找一半的约数。一次循环数据量可以从最高100000000次变为10000,达到优化效果。

优化代码如下:

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n,a;
    cin>>n;
    while(n--)
    {
        cin>>a;
        int sum=0,b=0;
        for(int i=1;i*i<=a;i++)
        {
            if(a%i==0)
            {
                if(i!=1) b=a/i; //sum是不加本身的,b就是对应大的那个约数
                if(a!=1) sum+=i+b;//排除a=1特例
            }
        }
        if(sum==a) printf("%d is perfect\n",a);
        else printf("%d is not perfect\n",a);
    }
    return 0;
}

思路2:数学大佬~

数学部分:

100000000 内的完全数有且仅有 6,28,496,8128,335503366,28,496,8128,33550336 这五个.

根据上述内容, 这道题可以直接 O(1)O(1) 解决.


代码:


#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        if (n == 6 || n == 28 || n == 496 || n == 8128 || n == 33550336)  
            cout << n << " is perfect" << endl;
        else cout << n << " is not perfect" << endl;
    }

    return 0;
}

作者:vcrlwpx
链接:https://www.acwing.com/solution/content/10289/
来源:AcWing

借评论调侃:

题目2:772.只出现一次的字符

思路1:暴力遍历

两个循环,一一对比,复杂度O(n*n),比较烂。

思路2:正反查找

string类,合理运用成员函数:find和rfind。当正向遍历时,出现正反查找位置都是同一个的时候,表明该字符只出现一次。

代码实现:

#include<iostream>
using namespace std;

int main()
{
    string s1;
    cin>>s1;
    int flag=1;
    for(size_t i=0;i<s1.size();i++)
    {
        if(s1.find(s1[i])==s1.rfind(s1[i]))
        {
            cout<<s1[i];
            flag=0;
            break;
        }
    }
    if(flag) cout<<"no";
    return 0;
}

妙点积累:

  • 一眼异或!!!
  • ,逗号表达式,返回最后一个表达式的结果。再循环条件处使用,别出心裁~
  • 异或,按位与,按位或,位运算操作,结合使用,字节位次循环,确定数字的大小,特征。很巧妙~
相关文章
|
6月前
数字游戏2(数位dp)
数字游戏2(数位dp)
39 0
|
6月前
|
C语言
浙大版《C语言程序设计(第3版)》题目集 练习8-2 计算两数的和与差 (10分)
浙大版《C语言程序设计(第3版)》题目集 练习8-2 计算两数的和与差 (10分)
|
6月前
|
C语言
pta 浙大版《C语言程序设计(第3版)》题目集 习题6-6 使用函数输出一个整数的逆序数 (20分)
pta 浙大版《C语言程序设计(第3版)》题目集 习题6-6 使用函数输出一个整数的逆序数 (20分)
|
6月前
|
C语言
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-6 删除字符 (20分)
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-6 删除字符 (20分)
|
6月前
|
存储
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
30 0
|
6月前
|
机器学习/深度学习
蓝桥杯-2/14天-完全平方数【另类思路】
蓝桥杯-2/14天-完全平方数【另类思路】
2010湖南省赛C 数字整除(两种思路)
2010湖南省赛C 数字整除(两种思路)
60 1
|
Java 测试技术 C语言
【蓝桥杯基础题】2020年省赛填空题—回文日期
【蓝桥杯基础题】2020年省赛填空题—回文日期
【蓝桥杯基础题】2020年省赛填空题—回文日期
|
人工智能 算法 测试技术
【寒假每日一题】AcWing 4644. 求和(补)
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
83 0