算法竞赛入门刷题
按照书中的顺序刷题,太简单直接给答案。
第一章
第4题可以使用KMP算法,但是用暴力方法也能过;第8题提供了一种高精度浮点数除法的思路;第10题不要想太多,直接写if;
1、Score UVA-1585
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;
char S[100];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", S);
int len = strlen(S);
int k = 0;
int ans = 0;
for (int i = 0; i < len; ++i) {
if (S[i] == 'O') ans += ++k;
else k = 0;
}
printf("%d\n", ans);
}
return 0;
}
2、Molar mass UVA-1586
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;
char S[100];
int M[256] = {0};
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", S);
char ch = 'C';
int len = strlen(S);
int k = 0;
int ans = 0;
for (int i = 0; i <= len; ++i) {
if (S[i] >= '0' && S[i] <= '9') {
if (k == -1) k = S[i] - '0';
else k = k * 10 + S[i] - '0';
} else {
M[ch] += (k == -1 ? 1 : k);
ch = S[i], k = -1;
}
}
printf("%.3lf\n", M['C'] * 12.01 + M['H'] * 1.008 + M['O'] * 16.00 + M['N'] * 14.01);
memset(M,0,sizeof(M));
}
return 0;
}
3、Digit Counting UVA-1225
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;
char S[100];
int M[10] = {0};
int main() {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int k = i;
while (k)++M[k % 10], k /= 10;
}
printf("%d %d %d %d %d %d %d %d %d %d\n",
M[0], M[1], M[2], M[3], M[4], M[5], M[6], M[7], M[8], M[9]);
memset(M,0,sizeof(M));
}
return 0;
}
4、Periodic Strings UVA - 455
KMP 算法求最大周期: n-next[n], 非常简单证明其正确性。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <cstring>
using namespace std;
char S[100];
char N[100] = { -1,0 };
int main() {
//freopen("out.txt","w+",stdout);
int T, f = 0;
scanf("%d", &T);
while (T--) {
scanf("\n%s",S);
int n = strlen(S);
int i = 1, j = 0;
while (i < n) {
if (S[i] == S[j]) N[++i] = ++j;
else if (j == 0) N[++i] = 0;
else j = N[j];
}
if (f) puts(""); f = true;
if(n%(n-N[n]) == 0)printf("%d\n", n - N[n]);
else printf("%d\n", n);
}
return 0;
}
5、Puzzle UVA-227
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
int kase=0;
char P[10][10];
char GetChar(){
char ch = '\n';
while(ch == '\n') ch = getchar();
return ch;
}
int main()
{
char ch;
int nx,ny;
while((ch = GetChar())!= EOF){
int x=0,y=0;
bool f = false;
if(ch == 'Z') break;
P[0][0] = ch;
for(int i = 0; i < 5; ++i){
for(int j = i==0?1:0; j < 5; ++j) {
P[i][j] = GetChar();
if(P[i][j] == ' ') x=i,y=j;
}
ch = -1;
while(ch!='\n') ch = getchar();
}
while((ch = GetChar())!= '0'){
if(f) continue;
nx = x,ny = y;
if(ch == 'A') nx = nx - 1;
else if(ch == 'B') nx = nx + 1;
else if(ch == 'L') ny = ny - 1;
else if(ch == 'R') ny = ny + 1;
else f=true;
if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) f = true;
if(f) continue;
swap(P[x][y],P[nx][ny]);
x = nx;
y = ny;
}
if(kase)puts("");
printf("Puzzle #%d:\n",++kase);
if(f) printf("This puzzle has no final configuration.\n");
else{
for(int i = 0; i < 5; ++i){
for(int j = 0; j < 5; ++j) {
printf("%c", P[i][j]);
if(j!=4)printf(" ");
}
printf("\n");
}
}
}
return 0;
}
6、Crossword Answers UVA-232
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char S[15][15];
char B[15][15];
int N[15][15];
int kase = 0 ;
int main()
{
int m,n;
while(~scanf("%d",&m)){
if(m==0) return 0;
scanf("%d",&n);
int no=0;
for(int i = 0; i < m; ++i)scanf("%s",S[i]);
for(int i = 0 ; i < m; ++i){
for(int j = 0; j< n;++j){
if(S[i][j] == '*') continue;
if(i==0 || j == 0 || S[i-1][j]=='*' ||S[i][j-1]=='*' ) N[i][j] = ++no;
}
}
memcpy(B,S,sizeof(S));
if(kase)printf("\n");
printf("puzzle #%d:\nAcross\n",++kase);
for(int i = 0 ; i < m; ++i){
for(int j = 0; j< n;++j){
int x = j;
if(S[i][x] == '*') continue;
else printf("%3d.",N[i][j]);
while(S[i][x] != '*' && x < n) putchar(S[i][x]),S[i][x++]='*';
printf("\n");
}
}
printf("Down\n");
for(int i = 0 ; i < m; ++i){
for(int j = 0; j< n;++j){
int x = i;
if(B[x][j] == '*') continue;
else printf("%3d.",N[i][j]);
while(B[x][j] != '*' && x < m) putchar(B[x][j]),B[x++][j]='*';
printf("\n");
}
}
//printf("\n");
}
return 0;
}
7、DNA Consensus String UVA-1368
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char S[55][1005];
int M[255] ={0};
int main()
{
int T;
scanf("%d",&T);
while(T--){
int m,n,ans=0;
scanf("%d%d",&m,&n);
for(int i = 0; i < m; ++i)scanf("%s",S[i]);
for(int i = 0 ; i < n; ++i){
memset(M,0,sizeof(M));
for(int j = 0; j< m;++j) ++M[S[j][i]];
int t = M['A'];
char ch = 'A';
if(M['C'] > t) t=M[ch='C'];
if(M['G'] > t) t=M[ch='G'];
if(M['T'] > t) t=M[ch='T'];
putchar(ch);
ans += m - t;
}
printf("\n%d\n",ans);
}
return 0;
}
8、 ⭐Repeating Decimals UVA-202
本题方法值得借鉴
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
map<int,int> X;
int N[55000];
int main()
{
int a,b,x;
while(~scanf("%d%d",&a,&b)){
X.clear();
printf("%d",a);
N[0] = a / b;
int i = 1 ,j = 0, k = 1, f = 0, t;
while(true){
a = (a % b) * 10;
if(t = X[a]) break;
else X[a] = i;
N[i++] = a / b;
}
printf("/%d = %d.",b,N[0]);
while(true){
if(k == t) printf("("), f = 1;
printf("%d", N[k++]);
if(f) ++j;
if(k == i || j == 50) break;
}
if(k!=i)printf("...)\n");
else printf(")\n");
printf(" %d = number of digits in repeating cycle\n\n",i-t);
}
return 0;
}
9、 All in All UVA-10340
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char A[100005];
char B[100005];
int main()
{
while (~scanf("%s%s", A, B)) {
int m = strlen(A);
int n = strlen(B);
int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] == B[j])++i;
++j;
}
if (i == m) puts("Yes");
else puts("No");
}
return 0;
}
10、Box UVA-1587
长方体,只需要判断3个面
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
long long int F[6];
int H[3][2];
int main()
{
int a, b;
while (true) {
bool f = false, ans = false;
for (int i = 0; i < 6; ++i) {
if (~scanf("%d%d", &a, &b)) {
if (a > b)F[i] = a * 100005 + b;
else F[i] = b * 100005 + a;
}
else return 0;
}
sort(F, F + 6);
for (int i = 0; i < 3; ++i) {
if (F[2 * i] != F[2 * i + 1]) {
f = true;
break;
}
H[i][0] = F[2 * i] / 100005;
H[i][1] = F[2 * i] % 100005;
}
if (!f && H[0][0] == H[1][0]) {
if (H[0][1] == H[2][0] && H[1][1] == H[2][1]) ans = true;
else if (H[0][1] == H[2][1] && H[1][1] == H[2][0]) ans = true;
}
if (!f && H[0][0] == H[1][1]) {
if (H[0][1] == H[2][0] && H[1][0] == H[2][1]) ans = true;
else if (H[0][1] == H[2][1] && H[1][0] == H[2][0])ans = true;
}
if (!f && H[0][0] == H[2][0]) {
if (H[0][1] == H[1][0] && H[2][1] == H[1][1])ans = true;
else if (H[0][1] == H[1][1] && H[2][1] == H[1][0])ans = true;
}
if (!f && H[0][0] == H[2][1]) {
if (H[0][1] == H[1][0] && H[2][0] == H[1][1])ans = true;
else if (H[0][1] == H[1][1] && H[2][0] == H[1][0])ans = true;
}
if (f || !ans)puts("IMPOSSIBLE");
else puts("POSSIBLE");
}
return 0;
}
11、Kickdown UVA-1588
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
char A[205];
char B[205];
int solve(char* a, char* b) {
int m = strlen(a);
int n = strlen(b);
for (int i = 0; i < m; ++i) {
int ans = 0;
int j = 0;
while (j < n) {
int x = a[i + j] ? a[i + j] - '0' : 0;
int y = b[j] ? b[j] - '0' : 0;
if (x + y > 3)break;
++j;
}
if (j == n) return max(j + i, m);
}
return m + n;
}
int main()
{
// freopen("in.txt","r",stdin);
while (~scanf("%s%s",A,B)) {
printf("%d\n", min(solve(A, B), solve(B, A)));
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
}
return 0;
}
12、Floating-Point Numbers UVA-11809
根据题目得到公式,直接枚举
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-6;
int main()
{
// freopen("in.txt","r",stdin);
char S[256];
while (~scanf("%s",S) && strcmp(S,"0e0") != 0) {
double a, b;
*strchr(S, 'e') = ' ';
sscanf(S, "%lf%lf", &a, &b);
for (int i = 0; i < 10; ++i) {
for (int j = 1; j <= 30; ++j) {
double x = log10(pow(2, i + 1) - 1) - (i + 1) * log10(2) + (pow(2, j) - 1) * log10(2);
double y = log10(a) + b;
if (fabs(x - y) < EPS) printf("%d %d\n", i, j), i = 100, j = 100;
}
}
}
return 0;
}
1 条评论
נערות ליווי במרכז · 2022年4月20日 下午8:58
Next time I read a blog, Hopefully it does not disappoint me as much as this one. After all, Yes, it was my choice to read through, nonetheless I truly thought youd have something helpful to talk about. All I hear is a bunch of crying about something that you can fix if you were not too busy seeking attention.