河南省第八届大学生程序设计竞赛
Problem A: A.挑战密室 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 55 Solved: 34 [Submit][Status][Web Board] Description R组织的特工Dr. Kong 为了寻找丢失的超体元素，不幸陷入WTO密室。Dr. Kong必须尽快找到解锁密码逃离，否则几分钟之后，WTO密室即将爆炸。
Dr. Kong发现密室的墙上写了许多化学方程式中。化学方程式，也称为化学反应方程式，是用化学式表示物质化学反应的式子。化学方程式反映的是客观事实。因此书写化学方程式要遵守两个原则：一是必须以客观事实为基础；二是要遵守质量守恒定律。
化学方程式不仅表明了反应物、生成物和反应条件。同时，化学计量数代表了各反应物、生成物物质的量关系，通过相对分子质量或相对原子质量还可以表示各物质之间的质量关系，即各物质之间的质量比。对于气体反应物、生成物，还可以直接通过化学计量数得出体积比。例如：2NaOH+H2SO4=Na2SO4+2H2O
经过多次试探、推理，Dr. Kong发现密码是4位数字，就隐藏在化学方程式等号后的第一个分子中，其分子量就可能是密码（若分子量不足4位，前面加0）。
好在Dr. Kong还记得墙上各化学方程式用到的化学元素的原子量如下：
N
C
O
Cl
S
H
Al
Ca
Zn
Na
14
12
16
35
32
2
27
40
65
23
你能帮Dr. Kong尽快找到密码吗？
【约束条件】
2≤K≤8 ，化学方程式的长度不超过50, 所有原子,分子的数量不超过9.小括号最多一层.
Input 第一行： K 表示有K个化学方程式；
接下来有K行，每行为一个化学方程式
Output 对于每个化学方程式输出一行：即密码。
Sample Input 3 2C+O2=2CO 2NaOH+H2SO4=Na2SO4+2H2O Ca2CO3+H2O=Ca2(OH)2+CO2 Sample Output 0056 0142 0116
分析： 题目意思很简单，就是让你去算一下等号后边那个化学式的分子质量。
我们首先要找到那个化学式吧。
化学式中有括号，我认为括号内其实就又是一个化学式，想用递归的思想来解决。
那么就设计一个递归函数，这个函数的作用就是算一个化学式的分子质量。
遇到括号就递归调用一下，让后把递归得到的结果乘以括号后面加的那个数字。
如果是普通的化学元素，那么我们就看一下当前元素的分子质量，然后乘以后边跟的那个数字。
最后不要忘了整个式子的最前面可能会出现一个数字，要先读取处理一下。
#include
using namespace std;
const int maxn=55;
map map1;
void init()
{
map1["N"]=14;
map1["C"]=12;
map1["O"]=16;
map1["Cl"]=35;
map1["S"]=32;
map1["H"]=2;
map1["Al"]=27;
map1["Ca"]=40;
map1["Zn"]=65;
map1["Na"]=23;
}
int T;
string str;
int cnt=0;
bool isnum(char &c)
{
return c>='0'&&c<='9';
}
bool isalpha(char &c)
{
return (c>='a'&&c='A'&&c<='Z');
}
int readnum()
{
int ans=0;
if(isnum(str[cnt]))
{
ans*=10;
ans+=(str[cnt]-'0');
cnt++;
}
return ans;
}
int read()
{
str="";
while(cin.peek()!='=')cin.get();
cin.get();
while(cin.peek()!='
'&&cin.peek()!='+')
{
str+=cin.get();
}
while(cin.peek()!='
')cin.get();
cin.get();
//cout<<str<<endl;
}
int readelement()
{
int ans=0;
while(cnt<str.size()&&str[cnt]!=')')
{
int ans2=0;
if(str[cnt]=='(')
{
cnt++;
ans2=readelement();
cnt++;
int tc=readnum();
if(!tc)tc=1;
ans2*=tc;
//cout<<ans2<<endl;
}
else
{
int tw,tc;
string el="";
while(isalpha(str[cnt]))
{
el+=str[cnt];
cnt++;
if(map1[el])break;
}
if(map1[el+str[cnt]])
{
el+=str[cnt];
cnt++;
}
tw=map1[el];
tc=readnum();
if(!tc)tc=1;
ans2=tw*tc;
//cout<<el<<" "<<tw<<" "<<ans2<<endl;
}
ans+=ans2;
}
return ans;
}
int main()
{
init();
while(~scanf("%d",&T))
{
while(T--)
{
cnt=0;
read();
int num1=readnum();
if(!num1)num1=1;
int ans = num1*readelement();
printf("%04d
",ans);
}
}
return 0;
}
Problem B: B.最大岛屿 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 27 Solved: 18 [Submit][Status][Web Board] Description 神秘的海洋，惊险的探险之路，打捞海底宝藏，激烈的海战，海盗劫富等等。加勒比海盗，你知道吧？杰克船长驾驶着自己的的战船黑珍珠1号要征服各个海岛的海盜，最后成为海盗王。 这是一个由海洋、岛屿和海盗组成的危险世界。面对危险重重的海洋与诡谲的对手，如何凭借智慧与运气，建立起一个强大的海盗帝国。
杰克船长手头有一张整个海域的海图，上面密密麻麻分布着各个海屿的位置及面积。他想尽快知道整个海域共有多少岛屿以及最大岛屿的面积。
【约束条件】
①若一个陆地八个方向之一（上、下、左、右、左上、右上、左下、右下）的位置也是陆地，则视为同一个岛屿。
② 假设第一行，最后一行，第一列，最后一列全为0.
③ 1<M, N≤500 1<T≤100000
Input
第1行: M N T 表示海域的长，宽及一个单位表示的面积大小
接下来有M行 ,每行有N个01组成的序列以及其中穿插一些空格。0表示海水，1表示陆地，其中的空格没用，可以忽略掉。
Output
输出一行，有2个整数，一个空格间隔，表示整个海域的岛屿数，以及最大岛屿的面积
Sample Input 8 16 99 00000000 00000000 0000110011000000 0001111000111000 0000000 00 0000000 00111 111000001 10 001110000 0000000 0100001111 111100 0000000000000000
Sample Output 5 990
深搜一下就好。
#include
using namespace std;
const int maxn = 550;
bool map1[maxn][maxn];
bool vis[maxn][maxn];
int m, n, T;
char c;
int flag = 0;
int maxans = 0;
int cnt = 0;
int num = 0;
void dfs(int s, int e)
{
num++;
int ans = 1;
vis[s][e] = 1;
if (!vis[s + 1][e-1] && map1[s + 1][e-1] == flag)
{
vis[s+1][e-1] = 1;
dfs(s + 1, e-1);
}
if (!vis[s + 1][e] && map1[s + 1][e] == flag)
{
vis[s+1][e] = 1;
dfs(s + 1, e);
}
if (!vis[s + 1][e+1] && map1[s + 1][e+1] == flag)
{
vis[s+1][e+1] = 1;
dfs(s + 1, e+1);
}
if (!vis[s][e + 1] && map1[s][e + 1] == flag)
{
vis[s][e + 1] = 1;
dfs(s, e + 1);
}
}
int main()
{
memset(vis, 0, sizeof(vis));
memset(vis[0], 1, sizeof(vis[0]));
cin >> m >> n >> T;
memset(vis[m - 1], 1, sizeof(vis[m - 1]));
for (int i = 0; i != m; i++)
{
vis[i][0] = vis[i][n - 1] = 1;
}
cin.get();
for (int i = 0; i != m; i++)
{
for (int j = 0; j != n; j++)
{
c = cin.get();
while (c == ' ')c = cin.get();
map1[i][j] = (c - '0');
}
cin.get();
}
for (int i = 1; i != m; i++)
{
for (int j = 1; j != n; j++)
{
if (!vis[i][j])
{
flag = map1[i][j];
num = 0;
dfs(i, j);
if (flag)
{
cnt++;
if (num>maxans)maxans = num;
}
}
}
}
cout << cnt << " " << T * maxans << endl;
return 0;
}
Problem D: D.引水工程 Time Limit: 2 Sec Memory Limit: 128 MB Submit: 18 Solved: 13 [Submit][Status][Web Board] Description
南水北调工程是优化水资源配置、促进区域协调发展的基础性工程，是新中国成立以来投资额最大、涉及面最广的战略性工程，事关中华民族长远发展。 “南水北调工程”，旨在缓解中国华北和西北地区水资源短缺的国家战略性工程。就是把中国长江流域丰盈的水资源抽调一部分送到华北和西北地区。我国南涝北旱，南水北调工程通过跨流域的水资源合理配置，促进南北方经济、社会与人口、资源、环境的协调发展。
整个工程分东线、中线、西线三条调水线。东线工程位于东部，因地势低需抽水北送至华北地区。中线工程从汉水与其最大支流丹江交汇处的丹江口水库引水，自流供水给黄淮海平原大部分地区，20多座大中城市；西线工程在青藏高原上，由长江上游向黄河上游补水。
现在有N个区域需要建设水资源工程，它们可以自建水库解决缺水问题，也可以从已有水源的地区建立管道引水过来。当然，这些建设都需要大量投资。
你能不能给出一个优化水资源配置方案，在保证每个区域都能用上水的前提下，使得整个引水工程费用最低。
【约束条件】
2≤k≤10 1≤N≤200 1≤Wi Pij≤100000 Pij = Pji Pii=0 (i=1,…, N)
所有数据都是整数。 数据之间有一个空格。
Input
第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N 表示有N个区域（ 1<=N<=300 ）
第2 行： W1 W2 …. WN Wi表示第i个区域自建水库需要的费用
再有N行： Pi1 Pi2 …. Pin Pij表示建立第i个区域与第j个区域引水管道的费用
Output 对于每组测试数据，输出占一行，即建立整个引水工程的最小费用。
Sample Input 1 5 5 4 4 3 6 0 2 2 2 2 2 0 3 3 3 2 3 0 4 5 2 3 4 0 1 2 3 5 1 0 Sample Output 10
对于每个点我们有两种操作，第一种我们在这个点建立水库，第二种就是我们找一条边用其他地方的水。
我们每次操作不是加边就是加点，那么是不是每次操作找最小的花费就行呢？
也不是，你总不能全建成边吧，所有我们还是先去找一个花费最小的点，先建立一个水库。 剩下的，我们看看是直接建水库好，还是因一条边到有水的地方好。
实现一下就好。
其中那个dijkstra函数我就是感觉分集合的思想有点像，所以叫了给dijkstra，其实和dijkstra没啥关系
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=301;
int T,n,t;
int a[maxn];
int map1[maxn][maxn];
int ans=0;
bool build[maxn];
int p1,p2;
int findp()
{
int cost=inf;
for(int i=1;i<=n;i++)
{
if(build[i])continue;
if(cost>a[i])
{
cost=a[i];
p1=i;
}
}
return cost;
}
int finde()
{
int cost=inf;
for(int i=1;i<=n;i++)
{
if(!build[i])continue;
for(int j=1;j<=n;j++)
{
if(build[j])continue;
if(cost>map1[i][j])
{
cost=map1[i][j];
p2=j;
}
}
}
return cost;
}
void dijkstra()
{
for(int i=0;i!=n-1;i++)
{
int t1=findp();
int t2=finde();
if(t1<t2)
{
build[p1]=1;
ans+=t1;
}
else
{
build[p2]=1;
ans+=t2;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
memset(build,0,sizeof(build));
ans=inf;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(ans>a[i])
{
ans=a[i];
t=i;
}
}
build[t]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&t);
map1[i][j]=t;
}
}
dijkstra();
printf("%d
",ans);
}
}
return 0;
}