更新日志
- 2017-3-25更新了页面排版
- 2017-3-25新增了悬浮工具栏→
- 2017-4-26删除了丑陋的悬浮工具栏
【问题描述】
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：通过内线掌握的信息，尝试破译密码。然后利用破 译的密码，翻译电报中的加密信息。【输入输出样例 1】
AA AB EOWIE
【输入输出样例 2】
QWERTYUIOPLKJHGFDSAZXCVBN
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO
【输入输出样例 3】
MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL FLSO
水题一道，没什么技术含量，简单映射就好，需要注意的是第一个样例数据看不得，这道题所有的测试数据(包括加密信息和原字符串)长度都是>=26个字符的，正如原题目里所说的“1．所有信息扫描完毕，‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应的“密字”。”，这点很容易被忽视。直接上代码。
#include#include #include using namespace std;bool a[26] = { 0};char key[30];char que[105];char past[105];char sour[105];int Is[30];int main(){ freopen("spy.in", "r", stdin); freopen("spy.out", "w", stdout); gets(past+1); gets(sour+1); gets(que+1); int len_p = strlen(past+1); int len_s = strlen(sour+1); int len_q = strlen(que+1); for (int i = 1; i <= len_p; i++) { a[sour[i] - 64] = 1; if (key[past[i] - 64] != sour[i]) Is[past[i] - 64]++; key[past[i] - 64] = sour[i]; } for (int i = 1; i <= 26; i++) if (a[i] == 0) { cout << "Failed" << endl; return 0; } for (int i = 1; i <= 26; i++) if (i == past[i] - 64) { int k = i; if (Is[k] == 0 || Is[k] > 1) { cout << "Failed" << endl; return 0; } } for (int i = 1; i <= len_q; i++) cout << key[que[i] - 64]; return 0;}
接下来看第二道：
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 的个数。请你帮助他编程求解这个问题。【输入样例1】
2
41 1 96 288 95 1 37 1776【输出样例1】
6
2
这道题十分神奇，正解应该是分解质因数，但是用优化的枚举一样可以，这里直接上代码。
#include#include #include #define lnt long long using namespace std;int n, ans;lnt x, a0, a1, b0, b1;inline lnt gcd(lnt a, lnt b){ if (b == 0) return a; else return gcd(b, a%b);}inline lnt lcm(lnt a, lnt b){ return a * b / gcd(a, b);}inline void solve(int x){ if ( gcd(x, a0) == a1) if (lcm(x, b0) == b1) ans++;}int main(){ cin >> n; while(n--) { ans = 0; scanf("%d%d%d%d", &a0, &a1, &b0, &b1); for (int i = 1; i * i <= b1; i++) if (b1 % i == 0) { solve(i); if (i * i != b1) solve(b1 / i); } cout << ans << endl; } return 0;}
但是这样只能过9个点，有一个点还是会T掉，这我至今都没有想通，这里再附上的代码，做法一样但耗时不同。
#include#include using namespace std;template inline void readin(T &res){ static char ch; while((ch=getchar())<'0'||ch>'9');res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=ch-48+res*10;}int n,a0,a1,b0,b1,ans;int gcd(int x,int y){ return y==0?x:gcd(y,x%y);}int lcm(int x,int y){ return x/gcd(x,y)*y;}bool judge(int x){ if(gcd(x,a0)!=a1)return 0; if(lcm(x,b0)!=b1)return 0; return 1;}int main(){ freopen("son.in","r",stdin); freopen("son.out","w",stdout); readin(n); while(n--){ int ans=0; readin(a0),readin(a1),readin(b0),readin(b1); for(int i=1;i*i<=b1;i++){ if(b1%i==0){ if(judge(i))ans++; if(i*i!=b1)if(judge(b1/i))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 条道路的信息（每条道路所连接的两个城市的编号
以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。【输入样例】
5 5
4 3 5 6 11 2 11 4 12 3 23 5 14 5 2【输出样例】
5
【数据范围】
输入数据保证1号城市可以到达n号城市。 对于10%的数据，1≤n≤6。 对于30%的数据，1≤n≤100。 对于50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。 对于100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球价格≤100。这道题可以用双向SPFA来解决，当然万能的搜索也可以解决，这里两种都贴上。
首先是两次BFS。
#include#include #include #include #define MAXN 100010using namespace std;struct T{ int v; int next;}edge[500050],edge2[500050];int n, m;int cnt, cnt2;int head[MAXN], head2[MAXN];int mx[MAXN], mp[MAXN], w[MAXN];bool able[MAXN], vis[MAXN];inline void get(int &x){ char c = getchar(); x = 0; while(c < '0' || c > '9') c = getchar(); while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();}inline void add_edge(int u,int v){ edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++;}inline void add_edge2(int u,int v){ edge2[cnt2].v = v; edge2[cnt2].next = head2[u]; head2[u] = cnt2++;}void bfs1(){ memset(mp,0x3f,sizeof mp); queue queue; queue.push(1); vis[1] = 1; while(!queue.empty()) { int u = queue.front(); vis[u] = 0; queue.pop(); mp[u] = min(mp[u],w[u]); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(mp[v] > mp[u]) { mp[v] = mp[u]; if(!vis[v]) { vis[v] = 1; queue.push(v); } } } }}void bfs2(){ memset(mx,0,sizeof mx); queue queue; queue.push(n); able[n] = 1; while(!queue.empty()) { int u = queue.front(); able[u] = 0; queue.pop(); mx[u] = max(mx[u],w[u]); for(int i = head2[u]; i != -1; i = edge2[i].next) { int v = edge2[i].v; if(mx[v] < mx[u]) { mx[v] = mx[u]; if(!able[v]) { able[v] = 1; queue.push(v); } } } }}int main(){ freopen("trade.in", "r", stdin); freopen("trade.out", "w", stdout); memset(head, -1, sizeof(head)); memset(head2, -1, sizeof(head2)); get(n);get(m); for (int i = 1; i <= n; i++) get(w[i]); for(int i = 1; i <= m; i++) { int x,y,z; get(x);get(y);get(z); add_edge(x,y); add_edge2(y,x); if(z == 2) { add_edge(y,x); add_edge2(x,y); } } bfs2(); bfs1(); int ans = 0; for (int i = 1; i <= n ; i++) ans = max(ans, mx[i] - mp[i]); cout << ans;}
接着是双向SPFA的。
#include#define rez(i,x,y) for(int i=x;i>=y;i--)#define res(i,x,y) for(int i=x;i<=y;i++)#define INF 210000#define ll long long#define N 100001#define clr(x) memset(x,0,sizeof(x))#define NAME "trade" using namespace std;vector first[N];vector second[N];int n,m,ans;int v[N],mfirst[N],temp[N],msecond[N]; void spfa_first(){ queue q; q.push(1); temp[1]=1;mfirst[1]=v[1]; while(!q.empty()){ int u=q.front(); for(int i=0;i