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

你玩過(guò)“拉燈”游戲嗎？25盞燈排成一個(gè)5x5的方形。每一個(gè)燈都有一個(gè)開關(guān)，游戲者可以改變它的狀態(tài)。每一步，游戲者可以改變某一個(gè)燈的狀態(tài)。游戲者改變一個(gè)燈的狀態(tài)會(huì)產(chǎn)生連鎖反應(yīng)：和這個(gè)燈上下左右相鄰的燈也要相應(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個(gè)待解決的游戲初始狀態(tài)。

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

輸出格式

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

對(duì)于某一個(gè)游戲初始狀態(tài)，若6步以內(nèi)無(wú)法使所有燈變亮，則輸出“-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

題目分析：

某個(gè)燈改變，該燈和上下左右一共5個(gè)燈需要改變，需要找下規(guī)律。
逐行來(lái)看，如果第一行中有個(gè)點(diǎn)為0，我們想要改變?yōu)?，又不想改變它左邊的點(diǎn)，因?yàn)樽筮叺狞c(diǎn)已經(jīng)是1了
我們可以按下一行同一列的燈，按完后，上方的燈會(huì)變?yōu)?，但是上方燈的左邊和右邊都不會(huì)受影響。
我們考慮固定第一行的所有點(diǎn)，然后按該行為0的下方的燈，如 $arr[i][j]=0$ ，那么我們就按 $arr[i+1][j]$
逐行從上往下一直到倒數(shù)第二行，然后我們判斷一下最后一行里面有沒有0，有0就不成立。
因?yàn)槲覀児潭说谝恍校瞧鋵?shí)第一行我們也可以先按，第一行一共有 $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);//把a(bǔ)rr1copy一份，每次操作新數(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];//此時(shí)是arr1
        cout<<work()<<endl;
    }
}

AcWing 96. 奇怪的漢諾塔

漢諾塔問(wèn)題，條件如下：

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

2、這里有n個(gè)圓盤，n的數(shù)量是恒定的。

3、每個(gè)圓盤的尺寸都不相同。

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

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

6、每次可以移動(dòng)一個(gè)圓盤，當(dāng)塔為空塔或者塔頂圓盤尺寸大于被移動(dòng)圓盤時(shí)，可將圓盤移至這座塔上。

請(qǐng)你求出將所有圓盤從塔A移動(dòng)到塔D，所需的最小移動(dòng)次數(shù)是多少。

漢諾塔參考模型.jpg

輸入格式

沒有輸入

輸出格式

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

輸入樣例：

沒有輸入

輸出樣例：

參考輸出格式

題目分析：

之前做漢諾塔問(wèn)題都是用遞歸的方法來(lái)做，這次看yxc的視頻，學(xué)到了用dp來(lái)做的方法，感覺更為簡(jiǎn)單，記錄一下。
如果只有1層，那么只需要1次操作。
如果有2層，需要先把第1個(gè)放到一個(gè)漢諾塔上，然后把第2個(gè)移動(dòng)到目標(biāo)塔上，最后需要再移動(dòng)第1個(gè)。
如果有3層，需要先把前2個(gè)放到一個(gè)漢諾塔上，然后把第3個(gè)移動(dòng)到目標(biāo)塔上，最后再移動(dòng)前兩個(gè)。
。。。
如果有n層，需要先把前n-1個(gè)放到一個(gè)漢諾塔上，然后把第n個(gè)移動(dòng)到目標(biāo)塔上，最后再移動(dòng)前n-1個(gè)。

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

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

題目中是4個(gè)漢諾塔，
如果只有1個(gè)，只需要1次操作。
如果有兩個(gè)，需要把第一個(gè)放到1個(gè)漢諾塔上，然后把第2個(gè)移動(dòng)到目標(biāo)塔上，最后再移動(dòng)第1個(gè)。
如果有三個(gè)，我們可以把第1個(gè)放到某個(gè)漢諾塔上，然后用剩下的三個(gè)漢諾塔來(lái)移動(dòng)剩下的2個(gè)圓盤。當(dāng)然我們也可以把前2個(gè)放到某個(gè)漢諾塔上，然后用剩下的三個(gè)漢諾塔來(lái)移動(dòng)剩下的1個(gè)圓盤。
。。。。
如果有n層，我們可以把第k個(gè)放到某個(gè)漢諾塔上，然后用剩下的三個(gè)漢諾塔移動(dòng)剩下的n-k個(gè)圓盤，然后判斷k的取值里面的最小值，就是最小移動(dòng)次數(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)在有兩個(gè)自然數(shù)A和B，S是AB的所有約數(shù)之和。

請(qǐng)你求出S mod 9901的值是多少。

輸入格式

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

輸出格式

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

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

$0≤A,B≤5×107$

輸入樣例：

2 3

輸出樣例：

15
注意: A和B不會(huì)同時(shí)為0。

題目分析：

首先，A是可能有約數(shù)的。如果A和B沒有約數(shù)就太簡(jiǎn)單了。
假設(shè)A有p種約數(shù)，分別是p1,p2,p3,...,pk
$A=p1^{k1}*p2^{k2}*p3^{k3}*...*pn^{kn}$
p1有k1+1種選法，...，pn有kn+1種選法。
總共的約數(shù)個(gè)數(shù)為 $(k1+1)*(k2+1)*(k3+1)*...*(kn+1)$ 個(gè)。
組合分別為 $(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ù)的和

怎么求這個(gè)式子呢。
就是等比數(shù)列求和，然后相乘，但是等比數(shù)列公式有除法，這里有取模運(yùn)算，所以要想用就要用逆元。
我們?cè)谶@用遞歸的思想來(lái)做

$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ù)時(shí)，可以直接用上述sum計(jì)算，k為偶數(shù)時(shí)，先計(jì)算p^k，然后再用上述sum

A^B的情況如下
$A^B=p1^{k1B}*p2^{k2B}*p3^{k3B}*...*pn^{knB}$
總共的約數(shù)個(gè)數(shù)為 $(k1+1)*(k2+1)*(k3+1)*...*(kn+1)$ 個(gè)。
組合分別為 $(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è)中是個(gè)大問(wèn)題。

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

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

city.png

當(dāng)城區(qū)規(guī)模擴(kuò)大之后，F(xiàn)ractal 的解決方案是把和原來(lái)城區(qū)結(jié)構(gòu)一樣的區(qū)域按照?qǐng)D中的方式建設(shè)在城市周圍，提升城市的等級(jí)。

對(duì)于任意等級(jí)的城市，我們把正方形街區(qū)從左上角開始按照道路標(biāo)號(hào)。

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

街區(qū)的距離指的是街區(qū)的中心點(diǎn)之間的距離，每個(gè)街區(qū)都是邊長(zhǎng)為 10 米的正方形。

輸入格式

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

以下n行，輸入n組測(cè)試數(shù)據(jù)，每組一行。

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

輸出格式

一共輸出n行數(shù)據(jù)，每行對(duì)應(yīng)一組測(cè)試數(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ù)的編號(hào)和正常數(shù)組下表不能一一對(duì)應(yīng)，所以需要做下標(biāo)轉(zhuǎn)換來(lái)求。
如3號(hào)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)為（1,0），8號(hào)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)為（1,2）。

我們來(lái)看一下等級(jí)為2的這張圖，它是以等級(jí)為1的這張圖轉(zhuǎn)變過(guò)來(lái)的，把等級(jí)為2的這張圖分為4部分，
先看一下左上角這張圖和等級(jí)為1的圖的關(guān)系，是等級(jí)為1的圖順時(shí)針轉(zhuǎn)90度，然后翻轉(zhuǎn)得到，
這里我們只看標(biāo)號(hào)的大小順序關(guān)系
左上角和等級(jí)為1，對(duì)應(yīng)坐標(biāo)關(guān)系為（x,y）--->（y,x）
右上角和等級(jí)為1，對(duì)應(yīng)坐標(biāo)關(guān)系為（x,y）--->（x,y+len）
右下角和等級(jí)為1，對(duì)應(yīng)坐標(biāo)關(guān)系為（x,y）--->（x+len,y+len）
左下角和等級(jí)為1，對(duì)應(yīng)坐標(biāo)關(guān)系為（x,y）--->（-y+2*len-1,-x+len-1）

接下來(lái)，我們分別求a,b對(duì)應(yīng)與數(shù)組的下標(biāo)，就可以直接求距離了。

代碼如下：

#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大神的視頻

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

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

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

題目分析：

AcWing 96. 奇怪的漢諾塔

輸入格式

輸出格式

輸入樣例：

輸出樣例：

題目分析：

AcWing 97. 約數(shù)之和

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

題目分析：

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

思路分析：

代碼如下：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

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

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

題目分析：

AcWing 96. 奇怪的漢諾塔

輸入格式

輸出格式

輸入樣例：

輸出樣例：

題目分析：

AcWing 97. 約數(shù)之和

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

題目分析：

輸入格式

輸出格式

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

輸入樣例：

輸出樣例：

思路分析：

代碼如下：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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