概述
写在前面
第9篇博客,一共12道题,分成2篇来写.
6. Uva 232 - Crossword Answers
11:56开始
12:03写题意
给出r(10)行c(10)列的网格,里面有若干个’*’和大写字母.一个字母格被定义为合格的要求是左边或上边是’*’或者边缘.按从上到下从左到右的顺序给合格的格排序,然后分横竖输出所有词:合格的格横或竖连续走尽量多的字母格,是一个词.
读入后,找出合格的格,编号,遍历即可,模拟题.
15:18醒来,写代码.
16:10 AC
#include <bits/stdc++.h>
using namespace std;
char s[12][12];
struct item
{
int i;
int j;
int idx;
};
int main(void)
{
int n,m,kase=1;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
vector<item> si,sj;
int idx=1;
if(kase!=1)
printf("n");
for(int i=0;i<n;i++)
{
scanf("%s",s[i]);
for(int j=0;j<m;j++)
{
int flag=0;
if(isalpha(s[i][j])&&(i-1<0||s[i-1][j]=='*'))
{
si.push_back({i,j,idx});
flag=1;
}
if(isalpha(s[i][j])&&(j-1<0||s[i][j-1]=='*'))
{
sj.push_back({i,j,idx});
flag=1;
}
if(flag)
idx++;
}
}
printf("puzzle #%d:n",kase++ );
printf("Acrossn");
for(item x:sj)
{
printf("%3d.",x.idx);
int tj=x.j;
while(tj<m&&s[x.i][tj]!='*')
printf("%c",s[x.i][tj++]);
printf("n");
}
printf("Downn");
for(item x:si)
{
printf("%3d.",x.idx);
int ti=x.i;
while(ti<n&&s[ti][x.j]!='*')
printf("%c",s[ti++][x.j]);
printf("n");
}
}
return 0;
}提交了7次,有5个格式错误和1个逻辑错误……横纵坐标要对应啊!
7. uva 1368 - DNA Consensus String
给出n(1000)个长度为m的DNA串,求一个串到这些串的编辑距离和最小,并输出这个距离.
按每个字符遍历即可.
#include <bits/stdc++.h>
int save[1010][4];
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
memset(save,0,sizeof(save));
int n,m;
scanf("%d%d",&n,&m);
getchar();
for(int i=0;i<n;i++)
{
int t=0;
char c;
while((c=getchar())!='n')
{
int p=0;
switch(c)
{
case 'A':p=0;break;
case 'C':p=1;break;
case 'G':p=2;break;
case 'T':p=3;break;
}
save[t++][p]++;
}
}
int ans=0;
for(int i=0;i<m;i++)
{
int mx=save[i][0],p=0;
for(int j=1;j<4;j++)
if(mx<save[i][j])
mx=save[i][j],p=j;
ans+=n-mx;
char c=' ';
switch(p)
{
case 0:c='A';break;
case 1:c='C';break;
case 2:c='G';break;
case 3:c='T';break;
}
printf("%c",c );
}
printf("n%dn",ans);
}
return 0;
}AC时间:25分钟.
需要一种一一映射的结构.
8. uva 202 - Repeating Decimals 模拟,基础数学
输入整数a和b,求a/b的无限循环小数表示形式及循环节长度.(a,b<=3000)
若循环50位以上,输出…以表示.
若可以除尽,视为以0为循环节.
举例
1/397 = 0.(00251889168765743073047858942065491183879093198992…)
99 = number of digits in repeating cycle
整数部分a/b即可得到.
a%=b后有a<b,此时模拟竖式除法,开两个数组记录余数和每一位的商.
如果有两个相同的余数,即为一个循环.循环节就是商数组在那一段的内容.
由一个数学定理,n的倒数若为无限循环小数,循环节长度不会超过n-1,所以3000次以内必有结果.
代码中,fl存储小数点后的部分,下标在1-st存储不循环部分,st-cnt存储循环部分.
save实际为一个hash数组,同时值表示下标.
注意模拟除法时补0的情况(乘10后不能除则存入0,能除则存入商)(第21行)
#include <bits/stdc++.h>
int fl[3010], save[3010];
int main(void)
{
int a, b;
while(scanf("%d %d", &a, &b) != EOF)
{
printf("%d/%d = %d.", a, b, a / b );
memset(fl, 0, sizeof(fl)), memset(save, 0, sizeof(save));
int st, cnt = 1;
while(1)
{
a %= b;
if(save[a])
{
st = save[a];
break;
}
save[a] = cnt;
a *= 10;
fl[cnt++] = (a >= b) ? (a / b) : 0;
}
for(int i = 1; i < st; i++)
printf("%d", fl[i] );
printf("(" );
for(int i = st; i < cnt; i++)
{
if(i == 51)
{
printf("...");
break;
}
printf("%d", fl[i] );
}
printf(")n %d = number of digits in repeating cyclenn", cnt - st );
}
return 0;
}9. Uva 10340 - All in All 字符串
给定两个串s和t,询问s是否是t的子序列(可以不连续,字串需要连续).
子序列模板题,尽量往前匹配就好.简单的双指针扫描
#include <bits/stdc++.h>
char s[200000],t[200000];
int main(void)
{
while(scanf("%s %s",s,t)!=EOF)
{
int ls=strlen(s),lt=strlen(t);
int j=0;
for(int i=0;i<lt;i++)
{
if(t[i]==s[j])
j++;
}
if(j==ls)
printf("Yesn");
else
printf("Non");
}
return 0;
}10. Uva 1587 Box 模拟
给出6个矩形的相邻两边长,判断他们能否构成一个长方体.
很巧妙的一道题,题意简单但是很难判断.
小白书的进度到这里时,似乎只会数组和循环分支结构.
网上有一种方法是按长宽排序,然后判断是否两两一组.
很惭愧,我用了stl,还找了半天bug.
我的方法是先离散化,再把每个矩形的边按 宽-长 顺序排列,
然后把矩形存入map< <pair<int,int>,int >里.
一共只有三种情况能构成长方体:
mp[ {1, 1}] == 6;
mp[ {1, 1}] == 2 && mp[ {1, 2}] == 4;
mp[ {1, 2}] == 2 && mp[ {1, 3}] == 2 && mp[ {2, 3}] == 2;
以上其实是有bug的,大家可以想想为什么,代码里没有bug.
#include <bits/stdc++.h>
using namespace std;
int a[12], b[12];
//离散化,传入原数组,存放数组,长度.
template <class Typename> void discre(Typename *src, Typename *des, int n)
{
map<int, int> mp_discre;
memcpy(des, src, n * sizeof(src[0]));
sort(des, des + n);
int num = unique(des, des + n) - des;
for(int i = 0; i < num; i++)
mp_discre[des[i]] = i + 1;
for(int i = 0; i < n; i++)
des[i] = mp_discre[src[i]];
}
map<pair<int, int>, int> mp;
int main(void)
{
while(scanf("%d", &a[0]) != EOF)
{
mp.clear();
memset(b, 0, sizeof(b));
for(int i = 1; i < 12; i++)
scanf("%d", &a[i]);
discre(a, b, 12);
for(int i = 0; i < 6; i++)
{
if(b[i * 2] > b[i * 2 + 1])
mp[ {b[i * 2 + 1], b[i * 2 ]}]++;
else
mp[ {b[i * 2], b[i * 2 + 1 ]}]++;
}
if(mp[ {1, 1}] == 6)
printf("POSSIBLEn");
else if(mp[ {1, 1}] + mp[ {2, 2}] == 2 && mp[ {1, 2}] == 4)
printf("POSSIBLEn");
else if(mp[ {1, 2}] == 2 && mp[ {1, 3}] == 2 && mp[ {2, 3}] == 2)
printf("POSSIBLEn");
else
printf("IMPOSSIBLEn");
}
return 0;
}学习了unique函数的用法,改进了离散化模板.
11. Uva 1588 - Kickdown 字符串匹配
给定长度分别为n1,n2(100)的宽度为1的木条，木条同一侧上有一些长宽均为1的突起，需要将他们放如一个高度为3的容器里（如图）求最短的容器长度。
匹配原则是2和2不能配，其他都可以。
使用暴力方法，从长木条左端一个短木条的距离开始，到长木条右端，分别视为原点进行一个短木条的匹配。
一共分三种情况，左边超出，正好，右边超出。l1+l2为最坏情况.
感觉自己特别不严谨，出现了若干bug。
复杂度O((N1+N2)*N2)
如果使用KMP算法,应该可以优化到常数复杂度.
#include <bits/stdc++.h>
using namespace std;
char s1[110], s2[110];
char *p1, *p2;
int l1, l2;
//传入开头差(-l2<=piss<l1,-l2为最坏情况)
//如果可行,返回总长度(至少为l1),不可行返回l1+l2
int check(int piss)
{
if(piss < 0)
{
for(int i = 0; i < l2 + piss; i++)
if(p1[i] + p2[i - piss] > 3+'0'+'0')
return l1 + l2;
return l1 - piss;
}
else if(piss > l1 - l2)
{
for(int i = 0; i < l1 - piss; i++)
if(p1[i + piss] + p2[i] > 3+'0'+'0')
return l1 + l2;
return piss + l2;
}
else
{
for(int i = 0; i < l2; i++)
if(p1[i + piss] + p2[i] > 3+'0'+'0')
return l1 + l2;
return l1;
}
}
int main(void)
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%s %s", s1, s2) != EOF)
{
l1 = strlen(s1), l2 = strlen(s2);
p1 = s1, p2 = s2;
if(l1 < l2)
swap(p1, p2), swap(l1, l2);
int ans = l1 + l2;
for(int i = -l2; i < l1; i++)
{
//printf("i=%d check=%dn",i,check(i) );
ans = min(check(i), ans);
if(ans==l1)
break;
}
printf("%dn",ans );
}
return 0;
}12. Uva 11809 - Floating-Point Numbers 数学
介绍了浮点数在内存中的存储形式:(数字符号位,M位尾数,阶码符号位,E位阶码)
可以表示的最大浮点数为0.11111(M+1位2进制)*2^(111111(E位))
即(1-1/2^(M+1))*2^(2^E-1).
输入一个AeB的表示形式,求以A*10^B为最大值的浮点数的M和E.
(必有解,0<=M<=9, 1<=E<=30, 0<A<10)
打表,把300种M,E的组合对应的A,B求出,再由询问搜索即可.
表的数据结构,我用了一个map<pair<double,int>,pair<int,int> >,两个二维数组也是可以的.
一个难点在于,如何将最高2^(2^30-1)的数转化为科学计数法的表示形式:
二期校队选拔赛中做过类似的题,设10^x=2^(2^E-1),则x=(2^E-1)*log10(2),
用fmod函数将x分为整数部分xi和小数部分xf,
则A=(1-1/2^(M+1))*10^xf , B=10^xi
然后对A,B进行调整使A在[1,10)的范围内.
另一个难点是如何读入数据,C语言将AeB本身视为一个浮点数,读入后会变成inf.
我的方法是先读字符串,然后用sscanf_s读到e所在的位置,再分开读.
后来参考了网上的方法,还是先读字符串,然后执行*(strchr(str, ‘e’)) = ’ ‘;
再用sscanf正常读入就可以了.
还有一个坑点是浮点数精度问题,注意浮点数是不能直接比较相等的,所以验证时eps的选取要适中,精度太高会因为计算时的精度误差而WA,精度太低会因为比较错误而WA……经测试1e-4或者1e-5是可以AC的
最后是一个莫名其妙的坑点,坑了我两个小时.我用的
const double lg2=0.301029995663981;始终WA,但是换成log10(2)之后就可以过.
找不到原因,我认为它们是完全相同的如果哪位大佬知道请指点一下.
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-4;
#define p1 first
#define p2 second
char str[100];
map <pair<double, int>, pair<int, int> >mp;
int main(void)
{
double a;
int b;
for(int e = 1; e <= 30; e++)
{
double t = ((1 << e) - 1) * log10(2);
double prf = fmod(t, 1.0);
for(int m = 0; m < 10; m++)
{
a = ( 1 - 1.0 / (1 << (m + 1)) ) * pow(10, prf);
b = (int)(t - prf + 0.5);
while(a < 1)
a *= 10, b--;
if(a >= 10)
a /= 10, b++;
mp[ {a, b}] = {m, e};
}
}
while(cin >> str, strcmp(str, "0e0"))
{
*(strchr(str, 'e')) = ' ';
sscanf(str, "%lf %d", &a, &b);
if(a < 1)
a *= 10, b--;
for(auto x : mp)
{
if(fabs(x.p1.p1 - a) < eps && x.p1.p2 == b)
{
printf("%d %dn", x.p2.p1, x.p2.p2 );
break;
}
}
}
return 0;
}感想
12题写完,第三章就AK啦.
感觉,还是把自己估高了,越到后面的题真的越难做,思维难度和代码细节强度越来越大,stl和各种骚操作百般用尽还差点栽在这些C语言入门的题上.
做以后的例题和习题的时候,要量力而为,除了lrj要求掌握的题之外,其他的题先做够需要的数目,打完一周目再回来尝试AK,加油!
最后
以上就是帅气百合为你收集整理的算法竞赛入门经典 第三章习题题解(二)的全部内容，希望文章能够帮你解决算法竞赛入门经典 第三章习题题解(二)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复