潜伏者
原题
R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则：
1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘A’-‘Z’构成（无空格等其他字符）。
2． S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。
3． 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。
例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。
现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C希望能通过这条信息，破译 S 国的军用密码。小 C 的破译过程是这样的：扫描原信息，对于原信息中的字母 x（代表任一大写字母），找到其在加密信息中的对应大写字母 y，并认为在密码里 y 是 x 的密字。如此进行下去直到停止于如下的某个状态：
1． 所有信息扫描完毕，‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应的“密字”。
2． 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。
3． 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。
例:如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。
在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C：通过内线掌握的信息，尝>试破译密码。然后利用破译的密码，翻译电报中的加密信息。
思路
本体并不复杂，但要注意限制条件的判断，具体见代码
代码
#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";//如果明文中有相同的字母但在密文中对应的字母不相同，程序错误输出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，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：
1． x 和 a0 的最大公约数是 a1；
2． x 和 b0 的最小公倍数是 b1。
Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。
思路
x与a0的最大公约数为a1，那么我们把
x/=a1,a0/=a1之后，x和a0不会再有除了1之外的公约数。
同样可以得出结论：b1/=b0,b1/=x两数也不应该有除了1之外的公约数。
代码
#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;
}
最优贸易
原题
C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。
设 C 国 n 个城市的标号从 1~ n，阿龙决定从 1 号城市出发，并最终在n 号城市结束自己的旅行。
在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1~n 号城市的水晶球价格分别为 4，3，5，6，1。
阿龙可以选择如下一条线路：
1->2->3->5，并在 2 号城市以 3 的价格买入水晶球，在 3号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。阿龙也可以选择如下一条线路
1->4->5->4->5，并在第 1 次到达 5 号城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入输出格式
输入格式：
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市y 之间的双向道路。
输出格式：
输出文件 trade.out 共 1 行，包含 1 个整数，表示最多能赚取的旅费。如果没有进行贸易，
则输出 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
思路
- 贪心
- 两次spfa，第一次正着找最小价格，第二次反着找最大价值 找出每一个点前水晶球的最小价格和这个点后的最大价值
- 用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;
}
靶形数独
题目描述
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即:
每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8 分，蓝色区域外面一圈（棕色区域）每个格子为 7 分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和
总分数即每个方格上的分值和完成这个数独时填在相应格上的数字
的乘积的总和。
如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。
输入输出格式
输入格式：
一共 9 行。每行 9 个整数（每个数都在 0―9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。
输出格式：
输出文件 sudoku.out 共 1 行。
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-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
思路
对于这道题，首先想到的就是搜索，但是数据太大，绝对TLE,这个时候就要用一些特殊的技巧.
- 如果我们自己来做数独题，会怎么做呢?一定会先填可选数字最少的那一格吧。搜索的顺序也是这样，每次都搜能填个数最少的那一行或一列，就可以过了
代码
#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;
}
