NOIP模拟題 2016.11.4 [數論] [費馬小定理] [最短路] [建圖]

細胞分裂

【問題描述】

小A 養了一大坨細胞。

最初小A 隻有1 個細胞。每秒，小A 的每個細胞都會分裂成2 個細胞。

已知：現在離“最初”已經過去了x 秒，那麼現在的細胞數當然是可以計算的。

小A 想知道的當然不是目前的細胞數。小A 知道他養的細胞的習性：每y

個細胞會聚成一團。經常會有剩下的細胞，那麼我們稱這些細胞是孤獨的。

小A 想知道的就是孤獨的細胞個數。

【輸入檔案】

輸入檔案為cell.in。

輸入檔案共一行，為兩個整數x y，以空格隔開。

【輸出檔案】

輸出檔案為cell.out。

輸出檔案共一行，為一個整數，即孤獨的細胞個數。

【輸入樣例】

3 3

【輸出樣例】

【資料規模和約定】

對于10%的資料，x<2^6。

對于20%的資料，x<2^17。

對于40%的資料，x<2^64。

對于70%的資料，x<2^2333。

對于100%的收，0≤x<2^233333，y 是3 到1000 之間（含兩端）的質數。

數論。

答案 ans = 2^x % y

但是要用費馬小定理加速。

PS 據說有人寫了100+高精度 EXM？？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=;
const int maxn = ;
char s[maxn];
int y,mod;
int main()
{
    freopen("cell.in","r",stdin);
    freopen("cell.out","w",stdout);
    scanf("%s%d",s,&y); mod = y-;
    int p = ;
    int lens = strlen(s);
    for(int i=;i<lens;i++) p=(p*+s[i]-'0')%mod;
    int ans = ;
    for(int i=;i<=p;i++) (ans<<=)%=y;
    printf("%d",ans);
    return ;
}

通風管

【問題描述】

你是一個Air Conditioning Machinery 公司（ACM）的技術人員（就是裝空調的）。不幸的是，當你到一個客戶那裡去裝空調管道的時候，你發現你的管道不夠了。你隻剩6 條管道，他們都是同一型号的彎管。

你必須在指定的空間内裝一個管道。空間是一個長方體，所有的邊的都是機關長度的整倍數，可以想象為一個空間堆滿了機關正方體。每個彎管占用恰好4個機關的正方體，如下圖1 所示。兩個彎管不能重合在同一個機關正方體上。每個彎管隻有2 個口，它們在圖形1 中以灰色顯示。你可以把2 個彎管接成一根長的管子，但是它們不得超過給定的空間。圖2 表示了其中一種對接方式。你的任務是接通入口和出口。入口和出口在給定空間的外表面上，和機關正方體對齊，如圖3 所示。為了減少開支，你必須用最少的彎管解決這個問題。

【輸入檔案】

輸入檔案為tube.in。

輸入包含一行，為11 個用空格隔開的值。

前3 個是整數(xmax,ymax,zmax)表示給定長方體的長寬高。長方體内的每個機關正方體用坐标(x,y,z)表示，其中1≤x≤xmax, 1≤y≤ymax, 1≤z≤zmax。

xmax,ymax,zmax 均為正且不大于20。

接下來3 個整數，表示入口所在機關立方體的坐标。

接下來是2 個字元構成的字元串，表示進入的朝向。可能為以下的一種：+x,-x,+y,-y,+z,-z。舉例來說，如果為+y，代表進入的方向為y 軸正方向，是以入口面向y 軸負方向。

接下來3 個整數，表示出口所在機關立方體的坐标。

最後是2 個字元構成的字元串，表示流出的朝向。可能為以下的一種：+x,-x,+y,-y,+z,-z。舉例來說，如果為+y，代表出去的方向為y 軸正方向，是以出口面向y 軸正方向。(注意與上面的不同之處。)

【輸出檔案】

輸出檔案為tube.out。

輸出一行，為接通管道，并且不超過指定空間，最少需要的彎管數。如果不

可能用6 個彎管完成，則輸出Impossible。

【輸入樣例1】

5 4 3 3 1 1 +z 5 4 3 +x

【輸出樣例1】

【輸入樣例2】

5 4 3 3 1 1 +z 1 2 3 -x

【輸出樣例2】

Impossible

【資料規模和約定】

10 個測試點的答案分别為：Impossible，1，1，2，2，3，3，4，5，6。

注意每個狀态都有八個形态可以轉移，由于不同方向上轉移後沒有相同的部分，隻好打表。。

其實直接搜尋也行。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=;
const int dx[][] =
{
    {,,,,,,,},
    {-,-,-,-,-,-,-,-},
    {,,-,,,,-,},
    {,,-,,,,-,},
    {,,-,,,,-,},
    {,,-,,,,-,}
};
const int dy[][] =
{
    {,,,-,,,,-},
    {,-,,,,-,,},
    {,,,,,,,},
    {-,-,-,-,-,-,-,-},
    {,,,-,,,,-},
    {,-,,,,-,,}
};
const int dz[][] =
{
    {-,,,,-,,,},
    {-,,,,-,,,},
    {,-,,,,-,,},
    {,,,-,,,,-},
    {,,,,,,,},
    {-,-,-,-,-,-,-,-}
};
const int dd[][] =
{
    {,,,,,,,},
    {,,,,,,,},
    {,,,,,,,},
    {,,,,,,,},
    {,,,,,,,},
    {,,,,,,,}
};
const int maxn = ;
int X,Y,Z;
inline bool inRange(int x,int y,int z) { return <=x&&x<=X && <=y&&y<=Y && <=z&&z<=Z; }
inline bool visible(char ch) { return ch=='+' || ch=='-' || ch=='x' || ch=='y' || ch=='z'; }
struct Node
{
    int x,y,z;
    int d;
    Node () {}
    Node (const int &_x,const int &_y,const int &_z,const int &_d) { x=_x; y=_y; z=_z; d=_d; }
    inline void read(bool adjust)
    {
        scanf("%d%d%d",&x,&y,&z);
        char op = (char) getchar();
        while(!visible(op)) op = (char) getchar();
        char ch = (char) getchar();
        while(!visible(ch)) ch = (char) getchar();
        if(op=='+')
            switch(ch)
            {
                case 'x': d = ; adjust?x--:; break;
                case 'y': d = ; adjust?y--:; break;
                case 'z': d = ; adjust?z--:; break;
            }
        else
            switch(ch)
            {
                case 'x': d = ; adjust?x++:; break;
                case 'y': d = ; adjust?y++:; break;
                case 'z': d = ; adjust?z++:; break;
            }
    }
}S,T;
queue <Node> que;
int dis[maxn][maxn][maxn][maxn];
bool inque[maxn][maxn][maxn][maxn];
int spfa()
{
    memset(dis,,sizeof(dis));
    memset(inque,,sizeof(inque));
    que.push(S); inque[S.x][S.y][S.z][S.d] = true;
    dis[S.x][S.y][S.z][S.d] = ;
    while(!que.empty())
    {
        Node now = que.front(); que.pop(); inque[now.x][now.y][now.z][now.d] = false;
        for(int k=;k<;k++)
        {
            int x = now.x + dx[now.d][k];
            int y = now.y + dy[now.d][k];
            int z = now.z + dz[now.d][k];
            int d = dd[now.d][k];
            if(!inRange(x,y,z)) continue;
            if(dis[x][y][z][d] > dis[now.x][now.y][now.z][now.d] + )
            {
                dis[x][y][z][d] = dis[now.x][now.y][now.z][now.d] + ;
                if(inque[x][y][z][d]) continue;
                inque[x][y][z][d] = true;
                que.push(Node(x,y,z,d));
            }
        }
    }
    return dis[T.x][T.y][T.z][T.d];
}
inline void init()
{
    scanf("%d%d%d",&X,&Y,&Z);
    S.read(true);
    T.read(false);
}
int main()
{
    freopen("tube.in","r",stdin);
    freopen("tube.out","w",stdout);
    init();
    int ans = spfa();
    if(ans > ) puts("Impossible");
    else printf("%d",ans);
    return ;
}

壓路機

【問題描述】

Johnny 開着一輛蒸汽壓路機（拖拉機？），像其他的蒸汽壓路機一樣，它很慢，而且要花更多的時間啟動，改變方向，或是停下。Johnny 剛剛完成了一天的工作并正在開着他的蒸汽壓路機回家去見他妻子。你的任務是找到對他和他的蒸汽壓路機而言的最短路。

Johnny 所住的城市是規則結構的（街道形成了正交系統）。城市街道編排在一個矩網格的節點間。每個節點和它的鄰居（最多四個）由街道相連。每個街道恰好1 機關長。當Johnny 進入一個街道，他必須到達另一端，從那裡，他可以選擇向四個方向行進到下一個節點，依次類推。

在研究了街道的路況之後，Johnny 計算了走過每一條街道的用時。這個時間對兩個方向來說是相同的。然而，Johnny 的計算隻滿足最理想的狀态——即蒸汽壓路機在進入這條街道時已經進入狀态而且不需要加速或刹車。隻要蒸汽壓路機在經過某條街道之前或之後立即改變方向，它經過這條街道的實際耗時會變為估計值的2 倍。這種情況對于壓路機從某個節點發動（比如Johnny 的起點）和到某個節點刹車（比如Johnny 的終點）也适用。

下面的圖檔是一個例子。數字說明了穿過對應街道的“理想”時間。沒有表明數字的街道不允許壓路機穿過。Johnny 想要從左上角到右下角。

全部是9 的那條路看起來更加快捷。然而，因為加速和刹車的限制，每一條邊都需要2 倍的時間，這使得總時間達到108。由10 組成的路徑更快，因為Johnny可以在其中的兩條路徑上全速通過，即總用時100。

【輸入檔案】

輸入檔案為roller.in。

第一行為六個正整數開頭：R C r1 c1 r2 c2。R 和C 描述了城市的大小，r1和c1 給出了起點坐标，r2 和c2 給出了Johnny 的家的位置。這兩個坐标必定不同。

下一行，有C-1 個非負整數用來描述(1,1)到(1,2)，(1,2)到(1,3)，(1,3)到(1,4)……的期望耗時。再下一行，有C 個非負整數描述(1,1)到(2,1)，(1,2)到(2,2)……的期望耗時。在下一行，又是C-1 個數描述下一行的期望耗時。輸入一直這樣延續直到描述全部街道。這些整數都表示的是不加速、刹車、轉向時的耗時。如果這些特殊情況中的一種或多種發生，那麼時間翻倍。這些整數中可能會有0，表示這條路不能經過。

【輸出檔案】

輸出檔案為roller.out。

輸出一個整數，即最短總耗時。如果不能到達，輸出Impossible。

【輸入樣例】

4 4 1 1 4 4

10 10 10

9 0 0 10

0 0 0

9 0 0 10

9 0 0

0 9 0 10

0 9 9

【輸出樣例】

100

【資料規模和約定】

對于50%的資料，R,C≤20。

對于100%的資料，輸入中所有數不會超過100。

據說是藍書上面的原題。。

用dp[x][y][d][opt]表示狀态，直接建圖spfa即可。。貌似Dijkstra更快但是我不會。。

每次轉移的時候可以從全速狀态轉移到減速狀态，但是還要加上原來的cost，用3-direction快速查詢。。

最後的答案還可能在全速狀态中，那麼就需要加上最後的這個cost。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=;
const int maxn = ;
const int dx[] = {-,,,};
const int dy[] = {,-,,};
int cost[maxn][maxn][];
int X,Y;
int Sx,Sy,Tx,Ty;
inline void init()
{
    scanf("%d%d%d%d%d%d",&X,&Y,&Sx,&Sy,&Tx,&Ty);
    memset(cost,,sizeof(cost));
    for(int k=;k<(X<<);k++)
        if(k&)
            for(int i=;i<Y;i++)
            {
                int tmp;
                scanf("%d",&tmp);
                if(!tmp) continue;
                cost[(k+)>>][i][] = tmp;
                cost[(k+)>>][i+][] = tmp;
            }
        else
            for(int i=;i<=Y;i++)
            {
                int tmp;
                scanf("%d",&tmp);
                if(!tmp) continue;
                cost[k>>][i][] = tmp;
                cost[(k>>)+][i][] = tmp;
            }
}
inline bool inRange(int x,int y) { return <=x&&x<=X && <=y&&y<=Y; }
struct Node
{
    int x,y,d,opt;
    Node (const int &_x,const int &_y,const int &_d,const int &_opt) { x=_x; y=_y; d=_d; opt=_opt; }
};
queue <Node> que;
int dis[maxn][maxn][][]; // 0 for full speed , 1 for blocked
bool inque[maxn][maxn][][];
int spfa()
{
    memset(dis,,sizeof(dis));
    memset(inque,,sizeof(inque));
    for(int k=;k<;k++)
    {
        int nowx = Sx + dx[k];
        int nowy = Sy + dy[k];
        if(!inRange(nowx,nowy) || cost[Sx][Sy][k]>=INF) continue;
        dis[nowx][nowy][k][] = cost[Sx][Sy][k] << ;
        que.push(Node(nowx,nowy,k,));
        inque[nowx][nowy][k][] = true;
    }
    while(!que.empty())
    {
        Node now = que.front(); que.pop();
        inque[now.x][now.y][now.d][now.opt] = false;
        for(int k=;k<;k++)
        {
            int x = now.x + dx[k];
            int y = now.y + dy[k];
            if(!inRange(x,y) || cost[now.x][now.y][k]>=INF) continue;
            int opt = !!(now.d^k);
            int val = dis[now.x][now.y][now.d][now.opt];
            if(opt)
            {
                val += cost[now.x][now.y][k] << ;
                if(!now.opt) val += cost[now.x][now.y][-now.d]; // same value as the opposite direction
            }
            else val += cost[now.x][now.y][k];
            if(dis[x][y][k][opt] > val)
            {
                dis[x][y][k][opt] = val;
                if(inque[x][y][k][opt]) continue;
                inque[x][y][k][opt] = true;
                que.push(Node(x,y,k,opt));
            }
        }
    }
    int ans = INF;
    for(int k=;k<;k++) smin(ans,min(dis[Tx][Ty][k][],dis[Tx][Ty][k][]+cost[Tx][Ty][-k]));
    return ans;
}
int main()
{
    freopen("roller.in","r",stdin);
    freopen("roller.out","w",stdout);
    init();
    int ans = spfa();
    if(ans >= INF) puts("Impossible");
    else printf("%d\n",ans);
    return ;

}

NOIP模拟題 2016.11.4 [數論] [費馬小定理] [最短路] [建圖]

繼續閱讀

如何下載下傳blob:https://www.bilibili.com/的視訊

HDU 5876 Sparse Graph

BZOJ3643 Phi的反函數（數論+搜尋）

hdu 1286 找新朋友（歐拉函數）

HDOJ 1286 找新朋友找新朋友

Codeforces Round #319 (Div. 2) B C D

Codeforces Round #369 (Div. 2) [D] Directed RoadsDirected Roads

Codeforces Round #264 (Div. 2) D

【多項式】拉格朗日插值

HDU 3268 Columbus’s bargain

PAT刷題小結

HDU 4725 The Shortest Path in Nya Graph

D. Dreamoon and Sets(構造+數論)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【趨高機器視覺】機器視覺技術原了解析及解決方案