洛谷 P1602 Sramoc問題

題目描述

話說員工們整理好了筷子之後，就準備将快餐送出了，但是一看訂單，都傻眼了:訂單上沒有留電話号碼,隻寫了一個sramoc（k，m）函數，這什麼東西？什麼意思？于是餐廳找來了資深顧問團的成員,YQ,SC,HQ，經過大量的查閱，大家獲得了一些資訊，Sramoc ( K , M ) 表示用數字0、1、２…、K-1組成的自然數中能被M整除的最小數。例如 K=2，M=7的時候，Sramoc( 2 , 7 ) = 1001。自然電話号碼就是1001，為了盡快将快餐送出，電腦組的童鞋們埋頭算起了這個齊葩的号碼。。。

輸入輸出格式

輸入格式：

第1行為兩個整數 k, m (2≤k≤10, 0≤m≤1000)。

輸出格式：

僅1行，那個電話号碼（最小的數）。

輸入輸出樣例

輸入樣例#1：

2 7      

輸出樣例#1：

1001      

吐槽

　　看題面應該是某次比賽的題目之一，比賽的題目背景都是連貫的，打比賽一大樂趣就是欣賞各種有趣的題目背景了。

　　被搬到公共題庫後，題目背景就支離破碎了。喪失了讀題目背景的樂趣，實在是一種損失……

解題思路

　　乍一看題，感覺是一道普通的數位搜尋，類似USACO1.5中一道名為 特殊的質數肋骨(Superprime Rib)的搜尋題。

　　于是按照題意敲了一波廣搜，每次拓展時按照0、1、2…k-1的順序在已有數字後面接數字，這樣就能保證搜尋到的數字是遞增出現的，第一個搜到的滿足條件的數字一定是最小的。交上去得了80分，一看，兩個點WA，輸出負數，應該是溢出了。把int改成long long，90分，還是WA了一個點，依然溢出。換成__int128，交上去還是90，然而那個不過的點TLE了……随着數位的增多，搜到的數是成指數型增長的啊……

　　瞄了一眼題解

　　這題正解可以是這樣——在廣搜時，隊列裡的每個元素由一個高精度的數(字元串)和那個數模m的值。拓展節點時，如果拓展得到的餘數為零，直接傳回輸出即可，要是這個餘數不為零且之前沒有出現過，就加入隊列，之前出現過，就舍棄吧。我不太明白為何出現過的相同的餘數不用加入隊列，是他們拓展結果重複嗎？先留坑

源代碼

#include<queue>
#include<cstdio>
#include<string>
#include<iostream>
int k,m;
struct Node{
    int yu;
    std::string s;
}n[1010],temp;
bool used[1010]={0};
Node bfs()
{
    std::queue<Node> q;
    for(int i=1;i<k;i++)
    {
        temp.yu=i%m;
        temp.s="";
        temp.s+=i%m+'0';
        q.push(temp);
        used[i%m]=1;
    }
    while(!q.empty())
    {
        temp=q.front();
        q.pop();
        for(int i=0;i<k;i++)
        {
            Node v=temp;
            v.s=temp.s;
            v.s+=i+'0';
            v.yu=(temp.yu*10+i)%m;
            if(v.yu==0) return v;
            if(!used[v.yu]) q.push(v),used[v.yu]=1;
        }
    }
}


int main()
{
    scanf("%d%d",&k,&m);
    std::cout<<bfs().s;
    return 0;
}