POJ 1218 THE DRUNK JAILER （题目虽然简单，但是学到了很多）

女爷i 2022-06-10 13:55 183阅读 0赞

## [THE DRUNK JAILER][] ##

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked.  
One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the  
hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He  
repeats this for n rounds, takes a final drink, and passes out.  
Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.  
Given the number of cells, determine how many prisoners escape jail.

## Input ##

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

## Output ##

For each line, you must print out the number of prisoners that escape when the prison has n cells.

## Sample Input ##

2
    5
    100

## Sample Output ##

2
    10

## 题意： ##

类似紫书上面的关灯问题。监狱里有n扇门，标号从1到n，每次把次数倍数序号的门进行操作，如果开着，就关上，如果关着，就打开。一共重复n次。求最后有多少个门是打开的（刚开始，监狱里所有序号的门都是关着的 ). 问题就转化为，在 标号为 1---N 的整数里面，有多少个数，他们的约数有奇数个（包含1和数本身）

## 思路： ##

1.根据过程，暴力解决。

#include <cstdio>
    
    int main()
    {
        int n,T;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            int cnt,ans=0;
            for (int j=1; j<=n; j++) {
                cnt = 0;    //统计数字 j 的因子个数
                for (int k=1; k<=j; k++) {
                    if (j % k == 0)
                        cnt++;
                }
                if (cnt % 2 != 0)// 如果因子数为奇数
                    ans++;
            }
            printf("%d\n",ans);
        }
    }

## 或者就这样，直接模拟 ##

#include <cstdio>
    #include <cstring>
    int d[110];
    
    int main()
    {
        int n,T;
        scanf("%d",&T);
        while(T--){
            scanf("%d", &n);        //状态用0和1表示，0关1开
            int ans = 0;
            memset(d,0,sizeof(d));//初始化d[i]数组为0 ,表示 门全部关闭
            for(int j=1;j<=n;j++)
                for(int i=1;i<=n;i++)
                    if(i % j == 0){
                        d[i] = ! d[i];
                    }
            for(int i=1;i<=n;i++){
                if(d[i] == 1)
                   ans++;
            }
            printf("%d\n", ans);
        }
        return 0;
    }

2.寻找规律，简化计算。（忘记是哪位博主大神的代码了）

/*算法：一个正整数n是完全平方数的充分必要条件是n有奇数个因数（包括1和n本身）。
    因此，可以通过求[1,n]中有多少个完全平方数进行求解
    设a*a<=n && (a+1)*(a+1)>n
    那么，[1,n]中有a个完全平方数
    */
    #include <cstdio>
    #include <cmath>
    
    int main()
    {
        int T,n;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            printf("%d\n",int(sqrt(n*1.0)) );
        }
        return 0;
    }

## 感悟： ##

对于能够解决的问题，需要把关键的代码进一步优化，平常多交流沟通，互相学习。不然，如果数据量很大，O（n^2） 的复杂度必然 爆掉！！！

[THE DRUNK JAILER]: https://vjudge.net/problem/POJ-1218