AcWing 95. 费解的开关

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围

0<n≤500

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

题目分析：

某个灯改变，该灯和上下左右一共5个灯需要改变，需要找下规律。
逐行来看，如果第一行中有个点为0，我们想要改变为1，又不想改变它左边的点，因为左边的点已经是1了
我们可以按下一行同一列的灯，按完后，上方的灯会变为1，但是上方灯的左边和右边都不会受影响。
我们考虑固定第一行的所有点，然后按该行为0的下方的灯，如 $arr[i][j]=0$ ，那么我们就按 $arr[i+1][j]$
逐行从上往下一直到倒数第二行，然后我们判断一下最后一行里面有没有0，有0就不成立。
因为我们固定了第一行，但是其实第一行我们也可以先按，第一行一共有 $2^5$ 种状态。

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int INF=1e9;
char arr1[5][5],arr[5][5];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,-1,1};

void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int curx=x+dx[i];
        int cury=y+dy[i];
        if(curx>=0&&cury>=0&&curx<5&&cury<5)
        {
            arr[curx][cury]^=1;
        }
    }
}

int work()
{
    int ans=INF;
    for(int k=0;k<1<<5;k++)
    {
        memcpy(arr,arr1,sizeof arr1);//把arr1copy一份，每次操作新数组，arr1一直不变。
        int res=0;
        for(int j=0;j<5;j++)
        {
            if(k>>j&1)
            {
                res++;
                turn(0,j);
            }
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(arr[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);
                }
            }
        }
        bool flag=true;
        for(int i=0;i<5;i++)
        {
            if(arr[4][i]=='0')
            {
                flag=false;
                break;
            }
        }
        if(flag) ans=min(ans,res);
    }
    if(ans>6)
        return -1;
    return ans;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i=0;i<=4;i++)  cin>>arr1[i];//此时是arr1
        cout<<work()<<endl;
    }
}

AcWing 96. 奇怪的汉诺塔

汉诺塔问题，条件如下：

1、这里有A、B、C和D四座塔。

2、这里有n个圆盘，n的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔A转移到塔D上。

6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。

汉诺塔参考模型.jpg

输入格式

没有输入

输出格式

对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行。

输入样例：

没有输入

输出样例：

参考输出格式

题目分析：

之前做汉诺塔问题都是用递归的方法来做，这次看yxc的视频，学到了用dp来做的方法，感觉更为简单，记录一下。
如果只有1层，那么只需要1次操作。
如果有2层，需要先把第1个放到一个汉诺塔上，然后把第2个移动到目标塔上，最后需要再移动第1个。
如果有3层，需要先把前2个放到一个汉诺塔上，然后把第3个移动到目标塔上，最后再移动前两个。
。。。
如果有n层，需要先把前n-1个放到一个汉诺塔上，然后把第n个移动到目标塔上，最后再移动前n-1个。

所以我们用 $f[i]$ 表示移动i个圆盘到目标塔需要的操作，那么根据上方的推导，我们可以得到状态转移方程如下：

$f[i]=f[i-1]+1+f[i-1]$

题目中是4个汉诺塔，
如果只有1个，只需要1次操作。
如果有两个，需要把第一个放到1个汉诺塔上，然后把第2个移动到目标塔上，最后再移动第1个。
如果有三个，我们可以把第1个放到某个汉诺塔上，然后用剩下的三个汉诺塔来移动剩下的2个圆盘。当然我们也可以把前2个放到某个汉诺塔上，然后用剩下的三个汉诺塔来移动剩下的1个圆盘。
。。。。
如果有n层，我们可以把第k个放到某个汉诺塔上，然后用剩下的三个汉诺塔移动剩下的n-k个圆盘，然后判断k的取值里面的最小值，就是最小移动次数。

代码如下：

#include<iostream>
#include<cstring>

using namespace std;

int d[15],f[15];

int main()
{
    d[1]=1;
    for(int i=2;i<=12;i++)
        d[i]=d[i-1]+d[i-1]+1;
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=12;i++)
    {
        for(int k=1;k<=i;k++)
        {
            f[i]=min(f[i],f[i-k]+f[i-k]+d[k]);
        }
    }
    for(int i=1;i<=12;i++)
        cout<<f[i]<<endl;
}

AcWing 97. 约数之和

假设现在有两个自然数A和B，S是AB的所有约数之和。

请你求出S mod 9901的值是多少。

输入格式

在一行中输入用空格隔开的两个整数A和B。

输出格式

输出一个整数，代表S mod 9901的值。

数据范围

$0≤A,B≤5×107$

输入样例：

2 3

输出样例：

15
注意: A和B不会同时为0。

题目分析：

首先，A是可能有约数的。如果A和B没有约数就太简单了。
假设A有p种约数，分别是p1,p2,p3,...,pk
$A=p1^{k1}*p2^{k2}*p3^{k3}*...*pn^{kn}$
p1有k1+1种选法，...，pn有kn+1种选法。
总共的约数个数为 $(k1+1)*(k2+1)*(k3+1)*...*(kn+1)$ 个。
组合分别为 $(p1^0+p1^1+p1^2+...+p1^{k1})*(p2^0+p2^1+p2^2+...+p2^{k2})*...*(pn^0+pn^1+pn^2+...+pn^{kn})$
上式就是最后A的所有约数的和

怎么求这个式子呢。
就是等比数列求和，然后相乘，但是等比数列公式有除法，这里有取模运算，所以要想用就要用逆元。
我们在这用递归的思想来做

$sum(p,k) = p^0+p^1+p^2+...+p^k$
= $p^0+p^1+p^2+...+p^{k/2}+p^{k/2+1}+p^{k/2+2}+...+p^{k}$
= $p^0+p^1+p^2+...+p^{k/2}+p^{k/2+1}*(p^0+p^{1}+...+p^{k/2})$
= $(1+p^{k/2+1})*sum(p,k/2)$
k为奇数时，可以直接用上述sum计算，k为偶数时，先计算p^k，然后再用上述sum

A^B的情况如下
$A^B=p1^{k1B}*p2^{k2B}*p3^{k3B}*...*pn^{knB}$
总共的约数个数为 $(k1+1)*(k2+1)*(k3+1)*...*(kn+1)$ 个。
组合分别为 $(p1^0+p1^B+p1^{2B}+...+p1^{k1B})*(p2^0+p2^B+p2^{2B}+...+p2^{k2B})*...*(pn^0+pn^B+pn^{2B}+...+pn^{knB})$

代码如下：

#include<iostream>
#include<algorithm>

using namespace std;
const int mod=9901;

int a,b;

int qml(int a,int b)
{
    a%=mod;
    int res=1;
    while(b)
    {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int sum(int p,int k)
{
    if(k==0) return 1;
    if(k%2==0) return (p%mod*sum(p,k-1)+1)%mod;
    return (1+qml(p,k/2+1))*sum(p,k/2)%mod;
}

int main()
{
    cin>>a>>b;
    int res=1;
    for(int i=2;i<=a;i++)
    {
        int s=0;
        while(a%i==0)
        {
            s++;
            a/=i;
        }
        res=res*sum(i,s*b)%mod;
    }
    if(!a) res=0;
    cout<<res<<endl;
    return 0;
}

AcWing 98. 分形之城

城市的规划在城市建设中是个大问题。

不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

city.png

当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。

对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。

输入格式

第一行输入正整数n，表示测试数据的数目。

以下n行，输入n组测试数据，每组一行。

每组数据包括三个整数 N,A,B, 表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出n行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

$1≤N≤31,$
$1≤A,B≤22N,$
$1≤n≤1000$

输入样例：

3
1 1 2
2 16 1
3 4 33

输出样例：

10
30
50

思路分析：

分析题目，发现数据的编号和正常数组下表不能一一对应，所以需要做下标转换来求。
如3号点对应的数组下标为（1,0），8号点对应的数组下标为（1,2）。

我们来看一下等级为2的这张图，它是以等级为1的这张图转变过来的，把等级为2的这张图分为4部分，
先看一下左上角这张图和等级为1的图的关系，是等级为1的图顺时针转90度，然后翻转得到，
这里我们只看标号的大小顺序关系
左上角和等级为1，对应坐标关系为（x,y）--->（y,x）
右上角和等级为1，对应坐标关系为（x,y）--->（x,y+len）
右下角和等级为1，对应坐标关系为（x,y）--->（x+len,y+len）
左下角和等级为1，对应坐标关系为（x,y）--->（-y+2*len-1,-x+len-1）

接下来，我们分别求a,b对应与数组的下标，就可以直接求距离了。

代码如下：

#include<iostream>
#include<cmath>

using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;

PLL get(LL n,LL m)
{
    if(n==0) return {0,0};
    LL len=1<<n-1,cnt=1ll<<2*n-2;
    auto pos=get(n-1,m%cnt);
    auto x=pos.first,y=pos.second;
    auto z=m/cnt;
    if(z==0) return {y,x};
    if(z==1) return {x,y+len};
    if(z==2) return {x+len,y+len};
    return {-y+2*len-1,-x+len-1};
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        LL N,A,B;
        cin>>N>>A>>B;
        auto a=get(N,A-1);
        auto b=get(N,B-1);
        double x=a.first-b.first,y=a.second-b.second;
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}

感谢yxc大神的视频

Acwing 算法竞赛进阶指南打卡行动递归（开关、奇怪汉诺塔、约数之和，分形之城）

Acwing 算法竞赛进阶指南打卡行动递归（开关、奇怪汉诺塔、约数之和，分形之城）

AcWing 95. 费解的开关

输入格式

输出格式

数据范围

输入样例：

输出样例：

题目分析：

AcWing 96. 奇怪的汉诺塔

输入格式

输出格式

输入样例：

输出样例：

题目分析：

AcWing 97. 约数之和

输入格式

输出格式

数据范围

输入样例：

输出样例：

题目分析：

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路分析：

代码如下：

Acwing 算法竞赛进阶指南打卡行动 递归（开关、奇怪汉诺塔、约数之和，分形之城）

AcWing 95. 费解的开关

输入格式

输出格式

数据范围

输入样例：

输出样例：

题目分析：

AcWing 96. 奇怪的汉诺塔

输入格式

输出格式

输入样例：

输出样例：

题目分析：

AcWing 97. 约数之和

输入格式

输出格式

数据范围

输入样例：

输出样例：

题目分析：

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路分析：

代码如下：

Acwing 算法竞赛进阶指南打卡行动递归（开关、奇怪汉诺塔、约数之和，分形之城）