昨天因为要给可儿讲睡前故事,所以没有刷水题,今天继续:

  • 1224: 相当水的一道题,就是考冒泡排序的次数,不过题目中相当于是一个循环序列,分析示例可以发现,其实就是相当于把这个循环的序列在中间分成两部分,然后对两部分进行冒泡排序,比如`1 2 3 4,可以分成1 23 41 2 3 4 5可以分成1 23 4 5,来分别进行排序,再把次数相加即可得到答案。

    代码如下:

    #include <iostream>
    using namespace std;
    
    int main(){
        int amount, n;
        cin >> amount;
        while(amount){
            cin >> n;
            if(n % 2 == 0)
                cout << n / 2 * (n / 2 - 1) << endl;
            else
                cout << n / 2 * (n / 2 - 1) / 2 + n / 2 * (n / 2 + 1) / 2 << endl;
            amount--;
        }
    }
    
  • 1247: 我发现ACM很喜欢在质数啊、互质、因数啊这些概念上出题啊。。。
    这道题如果真的一个个去求约数然后求和,结果想都不用想肯定是超时,我感觉没有什么思路,点进Discuss,发现一个大牛给了一个方法,用筛法,直接打表给答案,筛法,感觉很高端的样子啊,立刻Google之,发现原来是一种求质数的方法,在百度百科上找到了解释:

    先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。

    而这题使用筛法,思路就是,建立一个全为0的数组num[n],然后从1开始遍历数组,对每一个项num[i],其之后所有角标能被i整除的项,值都加上i。比如遍历到2,就把num[4], num[6], num[8]…的值加2,这样,数组中任意一项,其角标对应的约数和就是这一项的值。然后有输入时,直接查数组输出即可。

    代码如下:

    #include <iostream>
    #include <iomanip>
    using namespace std;
    
    int main(){
        int num[60001], tmp;
        for(int i = 0; i < 60001; i++)
            num[i] = 0;
        for(int i = 1; i <= 60000; i++){
            for(int j = i * 2; j <= 60000; j += i)
                num[j] += i;
        }
        cout << "PERFECTION OUTPUT" << endl;
        while(cin >> tmp){
            if(tmp == 0){
                cout << "END OF OUTPUT" << endl;
                break;
            }else{
                cout << setw(5) << tmp << "  ";
                if(num[tmp] == tmp)
                    cout << "PERFECT" << endl;
                else if(num[tmp] > tmp)
                    cout << "ABUNDANT" << endl;
                else
                    cout << "DEFICIENT" << endl;
            }
        }
    }