AcWing 95. 費解的開關(guān)

你玩過“拉燈”游戲嗎搂擦？25盞燈排成一個5x5的方形稳诚。每一個燈都有一個開關(guān)，游戲者可以改變它的狀態(tài)瀑踢。每一步扳还，游戲者可以改變某一個燈的狀態(tài)。游戲者改變一個燈的狀態(tài)會產(chǎn)生連鎖反應(yīng)：和這個燈上下左右相鄰的燈也要相應(yīng)地改變其狀態(tài)橱夭。

我們用數(shù)字“1”表示一盞開著的燈氨距，用數(shù)字“0”表示關(guān)著的燈。下面這種狀態(tài)

10111
01101
10111
10000
11011
在改變了最左上角的燈的狀態(tài)后將變成：

01111
11101
10111
10000
11011
再改變它正中間的燈后狀態(tài)將變成：

01111
11001
11001
10100
11011
給定一些游戲的初始狀態(tài)棘劣，編寫程序判斷游戲者是否可能在6步以內(nèi)使所有的燈都變亮俏让。

輸入格式

第一行輸入正整數(shù)n，代表數(shù)據(jù)中共有n個待解決的游戲初始狀態(tài)茬暇。

以下若干行數(shù)據(jù)分為n組首昔，每組數(shù)據(jù)有5行，每行5個字符糙俗。每組數(shù)據(jù)描述了一個游戲的初始狀態(tài)勒奇。各組數(shù)據(jù)間用一個空行分隔。

輸出格式

一共輸出n行數(shù)據(jù)巧骚，每行有一個小于等于6的整數(shù)赊颠，它表示對于輸入數(shù)據(jù)中對應(yīng)的游戲狀態(tài)最少需要幾步才能使所有燈變亮。

對于某一個游戲初始狀態(tài)劈彪，若6步以內(nèi)無法使所有燈變亮竣蹦，則輸出“-1”。

數(shù)據(jù)范圍

0<n≤500

輸入樣例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

輸出樣例：

3
2
-1

題目分析：

某個燈改變沧奴，該燈和上下左右一共5個燈需要改變痘括，需要找下規(guī)律。
逐行來看滔吠，如果第一行中有個點為0远寸，我們想要改變?yōu)?，又不想改變它左邊的點屠凶，因為左邊的點已經(jīng)是1了
我們可以按下一行同一列的燈，按完后肆资，上方的燈會變?yōu)?矗愧，但是上方燈的左邊和右邊都不會受影響。
我們考慮固定第一行的所有點，然后按該行為0的下方的燈唉韭，如 $arr[i][j]=0$ 夜涕，那么我們就按 $arr[i+1][j]$
逐行從上往下一直到倒數(shù)第二行，然后我們判斷一下最后一行里面有沒有0属愤，有0就不成立女器。
因為我們固定了第一行，但是其實第一行我們也可以先按住诸，第一行一共有 $2^5$ 種狀態(tài)驾胆。

代碼如下：

#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一份，每次操作新數(shù)組贱呐，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的數(shù)量是恒定的隧出。

3、每個圓盤的尺寸都不相同筑悴。

4谁鳍、所有的圓盤在開始時都堆疊在塔A上癞季，且圓盤尺寸從塔頂?shù)剿字饾u增大。

5倘潜、我們需要將所有的圓盤都從塔A轉(zhuǎn)移到塔D上绷柒。

6、每次可以移動一個圓盤涮因，當塔為空塔或者塔頂圓盤尺寸大于被移動圓盤時废睦，可將圓盤移至這座塔上。

請你求出將所有圓盤從塔A移動到塔D养泡，所需的最小移動次數(shù)是多少嗜湃。

漢諾塔參考模型.jpg

輸入格式

沒有輸入

輸出格式

對于每一個整數(shù)n(1≤n≤12),輸出一個滿足條件的最小移動次數(shù)，每個結(jié)果占一行澜掩。

輸入樣例：

沒有輸入

輸出樣例：

參考輸出格式

題目分析：

之前做漢諾塔問題都是用遞歸的方法來做购披，這次看yxc的視頻，學到了用dp來做的方法肩榕，感覺更為簡單刚陡，記錄一下。
如果只有1層，那么只需要1次操作筐乳。
如果有2層歌殃，需要先把第1個放到一個漢諾塔上，然后把第2個移動到目標塔上蝙云，最后需要再移動第1個氓皱。
如果有3層，需要先把前2個放到一個漢諾塔上勃刨，然后把第3個移動到目標塔上波材，最后再移動前兩個。
朵你。各聘。。
如果有n層抡医，需要先把前n-1個放到一個漢諾塔上躲因，然后把第n個移動到目標塔上，最后再移動前n-1個忌傻。

所以我們用 $f[i]$ 表示移動i個圓盤到目標塔需要的操作大脉，那么根據(jù)上方的推導，我們可以得到狀態(tài)轉(zhuǎn)移方程如下：

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

題目中是4個漢諾塔水孩，
如果只有1個镰矿，只需要1次操作。
如果有兩個俘种，需要把第一個放到1個漢諾塔上秤标，然后把第2個移動到目標塔上，最后再移動第1個宙刘。
如果有三個苍姜，我們可以把第1個放到某個漢諾塔上，然后用剩下的三個漢諾塔來移動剩下的2個圓盤悬包。當然我們也可以把前2個放到某個漢諾塔上衙猪，然后用剩下的三個漢諾塔來移動剩下的1個圓盤。
布近。垫释。。撑瞧。
如果有n層棵譬，我們可以把第k個放到某個漢諾塔上，然后用剩下的三個漢諾塔移動剩下的n-k個圓盤预伺，然后判斷k的取值里面的最小值茫船，就是最小移動次數(shù)琅束。

代碼如下：

#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. 約數(shù)之和

假設(shè)現(xiàn)在有兩個自然數(shù)A和B，S是AB的所有約數(shù)之和算谈。

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

輸入格式

在一行中輸入用空格隔開的兩個整數(shù)A和B料滥。

輸出格式

輸出一個整數(shù)然眼，代表S mod 9901的值。

數(shù)據(jù)范圍

$0≤A,B≤5×107$

輸入樣例：

2 3

輸出樣例：

15
注意: A和B不會同時為0葵腹。

題目分析：

首先高每，A是可能有約數(shù)的。如果A和B沒有約數(shù)就太簡單了践宴。
假設(shè)A有p種約數(shù)鲸匿，分別是p1,p2,p3,...,pk
$A=p1^{k1}*p2^{k2}*p3^{k3}*...*pn^{kn}$
p1有k1+1種選法，...阻肩，pn有kn+1種選法带欢。
總共的約數(shù)個數(shù)為 $(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的所有約數(shù)的和

怎么求這個式子呢烤惊。
就是等比數(shù)列求和乔煞，然后相乘，但是等比數(shù)列公式有除法柒室，這里有取模運算渡贾，所以要想用就要用逆元。
我們在這用遞歸的思想來做

$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為奇數(shù)時雄右，可以直接用上述sum計算空骚，k為偶數(shù)時，先計算p^k擂仍，然后再用上述sum

A^B的情況如下
$A^B=p1^{k1B}*p2^{k2B}*p3^{k3B}*...*pn^{knB}$
總共的約數(shù)個數(shù)為 $(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. 分形之城

城市的規(guī)劃在城市建設(shè)中是個大問題。

不幸的是防楷，很多城市在開始建設(shè)的時候并沒有很好的規(guī)劃牺丙，城市規(guī)模擴大之后規(guī)劃不合理的問題就開始顯現(xiàn)。

而這座名為 Fractal 的城市設(shè)想了這樣的一個規(guī)劃方案复局，如下圖所示：

city.png

當城區(qū)規(guī)模擴大之后冲簿，F(xiàn)ractal 的解決方案是把和原來城區(qū)結(jié)構(gòu)一樣的區(qū)域按照圖中的方式建設(shè)在城市周圍，提升城市的等級亿昏。

對于任意等級的城市峦剔，我們把正方形街區(qū)從左上角開始按照道路標號。

雖然這個方案很爛角钩，F(xiàn)ractal 規(guī)劃部門的人員還是想知道吝沫，如果城市發(fā)展到了等級 N呻澜，編號為 A 和 B 的兩個街區(qū)的直線距離是多少。

街區(qū)的距離指的是街區(qū)的中心點之間的距離惨险，每個街區(qū)都是邊長為 10 米的正方形羹幸。

輸入格式

第一行輸入正整數(shù)n，表示測試數(shù)據(jù)的數(shù)目辫愉。

以下n行栅受，輸入n組測試數(shù)據(jù)，每組一行恭朗。

每組數(shù)據(jù)包括三個整數(shù) N,A,B, 表示城市等級以及兩個街區(qū)的編號屏镊，整數(shù)之間用空格隔開。

輸出格式

一共輸出n行數(shù)據(jù)痰腮，每行對應(yīng)一組測試數(shù)據(jù)的輸出結(jié)果而芥，結(jié)果四舍五入到整數(shù)。

數(shù)據(jù)范圍

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

輸入樣例：

3
1 1 2
2 16 1
3 4 33

輸出樣例：

10
30
50

思路分析：

分析題目膀值，發(fā)現(xiàn)數(shù)據(jù)的編號和正常數(shù)組下表不能一一對應(yīng)棍丐，所以需要做下標轉(zhuǎn)換來求。
如3號點對應(yīng)的數(shù)組下標為（1,0）虫腋，8號點對應(yīng)的數(shù)組下標為（1,2）骄酗。

我們來看一下等級為2的這張圖，它是以等級為1的這張圖轉(zhuǎn)變過來的悦冀，把等級為2的這張圖分為4部分趋翻，
先看一下左上角這張圖和等級為1的圖的關(guān)系，是等級為1的圖順時針轉(zhuǎn)90度盒蟆，然后翻轉(zhuǎn)得到踏烙，
這里我們只看標號的大小順序關(guān)系
左上角和等級為1，對應(yīng)坐標關(guān)系為（x,y）--->（y,x）
右上角和等級為1历等，對應(yīng)坐標關(guān)系為（x,y）--->（x,y+len）
右下角和等級為1讨惩，對應(yīng)坐標關(guān)系為（x,y）--->（x+len,y+len）
左下角和等級為1，對應(yīng)坐標關(guān)系為（x,y）--->（-y+2*len-1,-x+len-1）

接下來寒屯，我們分別求a,b對應(yīng)與數(shù)組的下標荐捻，就可以直接求距離了。

代碼如下：

#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 算法競賽進階指南打卡行動遞歸（開關(guān)曙搬、奇怪漢諾塔、約數(shù)之和，分形之城）

Acwing 算法競賽進階指南打卡行動遞歸（開關(guān)纵装、奇怪漢諾塔征讲、約數(shù)之和，分形之城）

AcWing 95. 費解的開關(guān)

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

題目分析：

AcWing 96. 奇怪的漢諾塔

輸入格式

輸出格式

輸入樣例：

輸出樣例：

題目分析：

AcWing 97. 約數(shù)之和

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

題目分析：

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

思路分析：

代碼如下：

Acwing 算法競賽進階指南打卡行動 遞歸（開關(guān)纵装、奇怪漢諾塔征讲、約數(shù)之和，分形之城）

AcWing 95. 費解的開關(guān)

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

題目分析：

AcWing 96. 奇怪的漢諾塔

輸入格式

輸出格式

輸入樣例：

輸出樣例：

題目分析：

AcWing 97. 約數(shù)之和

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

題目分析：

輸入格式

輸出格式

數(shù)據(jù)范圍

輸入樣例：

輸出樣例：

思路分析：

代碼如下：

Acwing 算法競賽進階指南打卡行動遞歸（開關(guān)纵装、奇怪漢諾塔征讲、約數(shù)之和，分形之城）