潛伏者

原題

R 國和 S 國正陷入戰(zhàn)火之中，雙方都互派間諜，潛入對方內(nèi)部，伺機(jī)行動。歷盡艱險后，潛伏于 S 國的 R 國間諜小 C 終于摸清了 S 國軍用密碼的編碼規(guī)則：
1． S 國軍方內(nèi)部欲發(fā)送的原信息經(jīng)過加密后在網(wǎng)絡(luò)上發(fā)送，原信息的內(nèi)容與加密后所得的內(nèi)容均由大寫字母‘A’-‘Z’構(gòu)成（無空格等其他字符）。
2． S 國對于每個字母規(guī)定了對應(yīng)的“密字”。加密的過程就是將原信息中的所有字母替換為其對應(yīng)的“密字”。
3． 每個字母只對應(yīng)一個唯一的“密字”，不同的字母對應(yīng)不同的“密字”?！懊茏帧笨梢院驮帜赶嗤?。
例如，若規(guī)定‘A’的密字為‘A’，‘B’的密字為‘C’（其他字母及密字略），則原信息“ABA”被加密為“ACA”。

現(xiàn)在，小 C 通過內(nèi)線掌握了 S 國網(wǎng)絡(luò)上發(fā)送的一條加密信息及其對應(yīng)的原信息。小 C希望能通過這條信息，破譯 S 國的軍用密碼。小 C 的破譯過程是這樣的：掃描原信息，對于原信息中的字母 x（代表任一大寫字母），找到其在加密信息中的對應(yīng)大寫字母 y，并認(rèn)為在密碼里 y 是 x 的密字。如此進(jìn)行下去直到停止于如下的某個狀態(tài)：

1． 所有信息掃描完畢，‘A’-‘Z’ 所有 26 個字母在原信息中均出現(xiàn)過并獲得了相應(yīng)的“密字”。
2． 所有信息掃描完畢，但發(fā)現(xiàn)存在某個（或某些）字母在原信息中沒有出現(xiàn)。
3． 掃描中發(fā)現(xiàn)掌握的信息里有明顯的自相矛盾或錯誤（違反 S 國密碼的編碼規(guī)則）。
例:

如某條信息“XYZ”被翻譯為“ABA”就違反了“不同字母對應(yīng)不同密字”的規(guī)則。

在小 C 忙得頭昏腦漲之際，R 國司令部又發(fā)來電報，要求他翻譯另外一條從 S 國剛剛截取到的加密信息?，F(xiàn)在請你幫助小 C：通過內(nèi)線掌握的信息，嘗>試破譯密碼。然后利用破譯的密碼，翻譯電報中的加密信息。

思路

本體并不復(fù)雜，但要注意限制條件的判斷，具體見代碼

代碼

#include<iostream>
using namespace std;
char ch[26]={'0'};
int main()
{
    string str1,str2,str3;
    cin>>str1>>str2>>str3;//str1為密文，str2為明文，str3為需要翻譯的密文
    int len1=str1.length(),len3=str3.length();//獲取密文的長度
    if(len1<26)
    {
        cout<<"Failed";
        return 0;//若果密文的長度比26個字母長度短，就輸出Failed，終止程序
    }
    for(int i=0;i<len1;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(str2[i]==str2[j]&&str1[i]!=str1[j])
            {
                cout<<"Failed";//如果明文中有相同的字母但在密文中對應(yīng)的字母不相同，程序錯誤輸出Failed，終止程序
                return 0;
            }
        }
        ch[str1[i]-'A']=str2[i];
    }
    for(int i=0;i<len3;i++)  cout<<ch[str3[i]-'A'];
}

Hankson的趣味題

原題

Hanks 博士是 BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家，他的兒子名叫 Hankson。現(xiàn)在，剛剛放學(xué)回家的 Hankson 正在思考一個有趣的問題。
今天在課堂上，老師講解了如何求兩個正整數(shù) c1 和 c2 的最大公約數(shù)和最小公倍數(shù)。現(xiàn)在 Hankson 認(rèn)為自己已經(jīng)熟練地掌握了這些知識，他開始思考一個“求公約數(shù)”和“求公倍數(shù)”之類問題的“逆問題”，這個問題是這樣的：已知正整數(shù) a0,a1,b0,b1，設(shè)某未知正整數(shù) x 滿足：

1． x 和 a0 的最大公約數(shù)是 a1；
2． x 和 b0 的最小公倍數(shù)是 b1。

Hankson 的“逆問題”就是求出滿足條件的正整數(shù) x。但稍加思索之后，他發(fā)現(xiàn)這樣的x 并不唯一，甚至可能不存在。因此他轉(zhuǎn)而開始考慮如何求解滿足條件的 x 的個數(shù)。請你幫助他編程求解這個問題。

思路

x與a0的最大公約數(shù)為a1，那么我們把x/=a1 , a0/=a1之后，x和a0不會再有除了1之外的公約數(shù)。
同樣可以得出結(jié)論：b1/=b0, b1/=x兩數(shù)也不應(yīng)該有除了1之外的公約數(shù)。

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int ans;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int T,i,j,a0,a1,b0,b1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        //len=sqrt(b1+0.5);
        ans=0;
        for(i=1;i*i<=b1;i++)
        {
            if(b1%i==0){
                if(i%a1==0&&(gcd(i/a1,a0/a1)==1)&&(gcd(b1/b0,b1/i)==1))
                  ans++;
                j=b1/i;
                if(j%a1!=0||i==j) continue;
                if((gcd(j/a1,a0/a1)==1)&&(gcd(b1/b0,b1/j)==1))
                  ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

最優(yōu)貿(mào)易

原題

C 國有 n 個大城市和 m 條道路，每條道路連接這 n 個城市中的某兩個城市。任意兩個城市之間最多只有一條道路直接相連。這 m 條道路中有一部分為單向通行的道路，一部分為雙向通行的道路，雙向通行的道路在統(tǒng)計條數(shù)時也計為 1 條。
C 國幅員遼闊，各地的資源分布情況各不相同，這就導(dǎo)致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。
商人阿龍來到 C 國旅游。當(dāng)他得知同一種商品在不同城市的價格可能會不同這一信息之后，便決定在旅游的同時，利用商品在不同城市中的差價賺回一點旅費。
設(shè) C 國 n 個城市的標(biāo)號從 1~ n，阿龍決定從 1 號城市出發(fā)，并最終在n 號城市結(jié)束自己的旅行。
在旅游的過程中，任何城市可以重復(fù)經(jīng)過多次，但不要求經(jīng)過所有 n 個城市。阿龍通過這樣的貿(mào)易方式賺取旅費：他會選擇一個經(jīng)過的城市買入他最喜歡的商品――水晶球，并在之后經(jīng)過的另一個城市賣出這個水晶球，用賺取的差價當(dāng)做旅費。
由于阿龍主要是來 C 國旅游，他決定這個貿(mào)易只進(jìn)行最多一次，當(dāng)然，在賺不到差價的情況下他就無需進(jìn)行貿(mào)易。
假設(shè) C 國有 5 個大城市，城市的編號和道路連接情況如下圖，單向箭頭表示這條道路為單向通行，雙向箭頭表示這條道路為雙向通行。

輸入輸出格式

輸入格式：

第一行包含 2 個正整數(shù) n 和 m，中間用一個空格隔開，分別表示城市的數(shù)目和道路的數(shù)目。
第二行 n 個正整數(shù)，每兩個整數(shù)之間用一個空格隔開，按標(biāo)號順序分別表示這 n 個城市的商品價格。
接下來 m 行，每行有 3 個正整數(shù)，x，y，z，每兩個整數(shù)之間用一個空格隔開。如果 z=1，表示這條道路是城市 x 到城市 y 之間的單向道路；如果 z=2，表示這條道路為城市 x 和城市y 之間的雙向道路。

輸出格式：

輸出文件 trade.out 共 1 行，包含 1 個整數(shù)，表示最多能賺取的旅費。如果沒有進(jìn)行貿(mào)易，
則輸出 0。

輸入輸出樣例

輸入樣例#1：

5 5 
4 3 5 6 1 
1 2 1 
1 4 1 
2 3 2 
3 5 1 
4 5 2 

輸出樣例#1：

5

思路

1. 貪心
2. 兩次spfa，第一次正著找最小價格，第二次反著找最大價值 找出每一個點前水晶球的最小價格和這個點后的最大價值
3. 用max-min更新答案

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

const int MAXN = 500000;

int n, m, e = 1, ans, head[MAXN][2], MAX[MAXN], MIN[MAXN], Data[MAXN];
bool inq[MAXN];

queue<int>q;

struct node {
    int v, next;
}edge[MAXN];

inline void add(int u, int v) {
    edge[e].next = head[u][0]; edge[e].v = v; head[u][0] = e++;
    edge[e].next = head[v][1]; edge[e].v = u; head[v][1] = e++;
}

inline void init() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &Data[i]), MIN[i] = 105;

    int u, v, k;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &k);
        add(u, v);
        if (k == 2) add(v, u);
    }
}

inline void spfa_1()
{
    q.push(1); inq[1] = true;
    MIN[1] = Data[1];
    while (!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = false;

        for (int i = head[x][0]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (MIN[v] > MIN[x] || MIN[v] > Data[v]) {
                MIN[v] = min(MIN[x], Data[v]);
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }

}

inline void spfa_2()
{
    q.push(n); 
    inq[n] = true;
    MAX[n] = Data[n]; ans = max(ans, MAX[n] - MIN[n]);

    while (!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = false;

        for (int i = head[x][1]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (MAX[v] < MAX[x] || MAX[v] < Data[v]) {
                MAX[v] = max(MAX[x], Data[v]);
                ans = max(MAX[v] - MIN[v], ans);
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
}

int main()
{
    init();
    spfa_1();
    memset(inq, 0, sizeof(inq));
    spfa_2();
    printf("%d\n", ans);
    return 0;
}

靶形數(shù)獨

題目描述

小城和小華都是熱愛數(shù)學(xué)的好學(xué)生，最近，他們不約而同地迷上了數(shù)獨游戲，好勝的他們想用數(shù)獨來一比高低。但普通的數(shù)獨對他們來說都過于簡單了，于是他們向 Z 博士請教，Z 博士拿出了他最近發(fā)明的“靶形數(shù)獨”，作為這兩個孩子比試的題目。
靶形數(shù)獨的方格同普通數(shù)獨一樣，在 9 格寬×9 格高的大九宮格中有 9 個 3 格寬×3 格高的小九宮格（用粗黑色線隔開的）。在這個大九宮格中，有一些數(shù)字是已知的，根據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入 1 到 9 的數(shù)字。每個數(shù)字在每個小九宮格內(nèi)不能重復(fù)出現(xiàn)，每個數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨有一點和普通數(shù)獨不同，即:
每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。（如圖）

上圖具體的分值分布是：最里面一格（黃色區(qū)域）為 10 分，黃色區(qū)域外面的一圈（紅色區(qū)域）每個格子為 9 分，再外面一圈（藍(lán)色區(qū)域）每個格子為 8 分，藍(lán)色區(qū)域外面一圈（棕色區(qū)域）每個格子為 7 分，最外面一圈（白色區(qū)域）每個格子為 6 分，如上圖所示。比賽的要求是：每個人必須完成一個給定的數(shù)獨（每個給定數(shù)獨可能有不同的填法），而且要爭取更高的總分?jǐn)?shù)。而這個總分?jǐn)?shù)即每個方格上的分值和完成這個數(shù)獨時填在相應(yīng)格上的數(shù)字的乘積的總和
總分?jǐn)?shù)即每個方格上的分值和完成這個數(shù)獨時填在相應(yīng)格上的數(shù)字
的乘積的總和。
如圖，在以下的這個已經(jīng)填完數(shù)字的靶形數(shù)獨游戲中，總分?jǐn)?shù)為 2829。游戲規(guī)定，將以總分?jǐn)?shù)的高低決出勝負(fù)。

由于求勝心切，小城找到了善于編程的你，讓你幫他求出，對于給定的靶形數(shù)獨，能
夠得到的最高分?jǐn)?shù)。
輸入輸出格式
輸入格式：
一共 9 行。每行 9 個整數(shù)（每個數(shù)都在 0―9 的范圍內(nèi)），表示一個尚未填滿的數(shù)獨方
格，未填的空格用“0”表示。每兩個數(shù)字之間用一個空格隔開。

輸出格式：
輸出文件 sudoku.out 共 1 行。
輸出可以得到的靶形數(shù)獨的最高分?jǐn)?shù)。如果這個數(shù)獨無解，則輸出整數(shù)-1。

輸入輸出樣例

輸入樣例#1：

7 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0 
0 0 0 2 0 0 0 8 0 
0 0 5 0 2 0 0 0 3 
0 0 0 0 0 0 6 4 8 
4 1 3 0 0 0 0 0 0 
0 0 7 0 0 2 0 9 0 
2 0 1 0 6 0 8 0 4 
0 8 0 5 0 4 0 1 2

輸出樣例#1：

2829

思路

對于這道題，首先想到的就是搜索，但是數(shù)據(jù)太大，絕對TLE,這個時候就要用一些特殊的技巧.

• 如果我們自己來做數(shù)獨題，會怎么做呢?一定會先填可選數(shù)字最少的那一格吧。搜索的順序也是這樣，每次都搜能填個數(shù)最少的那一行或一列，就可以過了

代碼

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
int a[10][10],fenshu[10][10],vis1[30][10],vis2[10][10],vis3[10][10],b[10][10],ans = -1;

void dfs()
{
    int x,y,step = 10;
    for (int i = 1; i <= 9; i++)
    for (int j = 1; j <= 9; j++)
    {
        if (!a[i][j])
        {
            int s = 0;
            for (int k = 1; k <= 9; k++)    
            if (!vis1[b[i][j]][k] && !vis2[i][k] && !vis3[j][k])
            s++;
            if (s < step)
            {
                step = s;
                x = i;
                y = j;
            }
        }
    }
    if (step == 10) 
    {
        int k = 0;
        for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
        k += a[i][j] * fenshu[i][j];
        ans = max(ans,k); 
    }
    for (int k = 1; k <= 9; k++)
    if (!vis1[b[x][y]][k] && !vis2[x][k] && !vis3[y][k])
    {
        vis1[b[x][y]][k] = vis2[x][k] = vis3[y][k] = 1;
        a[x][y] = k;
        dfs();
        a[x][y] = 0;
        vis1[b[x][y]][k] = vis2[x][k] = vis3[y][k] = 0;
    }
}

int main()
{
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
    memset(vis3,0,sizeof(vis3));
    for (int i = 1; i <= 9; i++)
    for (int j = 1; j <= 9; j++)
    {
    scanf ("%d",&a[i][j]); 
    fenshu[i][j] = 10 - max(abs(i - 5),abs(j - 5));
    b[i][j] =  (i - 1) / 3 * 3 + (j - 1) / 3 + 1;
    vis1[b[i][j]][a[i][j]] = 1;
    vis2[i][a[i][j]] = 1;
    vis3[j][a[i][j]] = 1; 
}
dfs();
    printf("%d",ans);
    
    return 0;
}