算法竞赛入门经典第三章

string.h
char buff[99],e;
memcpy(b,a,sizeof(int)*k);//int数组a复制k个元素到int数组b
memcpy(b,a,sizeof(a));//全部复制
memset(a,0,sizeof(a));//a数组清零
sprintf(buf,”%d%d”,i,j);//打印到字符数组中
strchr(buf,e);//在buff中查找是否有字符e，e的位置
strlen(buff);//返回buff有效字符的长度，‘\0’之前字符个数
strcpy(a,b);strcmp(a,b);strcat(a,b);//赋值、比较、连接

fgetc(stdin)等价于getchar()//返回int型(因为文件结束符EOF并不是char)
fgets(buf,manx,stdin) //读一行或不超过max-1个字符，最后一个字符’\0’

习题3-1
https://cn.vjudge.net/problem/UVA-1585

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    getchar();
    while (n--) {
        char e;
        int cnt = 0, sum = 0;
        while (scanf("%c", &e) && e != '\n') {
            if (e == 'O') ++cnt;
            else {
                sum += (cnt + 1)*cnt>>1;
                cnt = 0;
            }
        }
        sum += (cnt + 1)*cnt >> 1;
        printf("%d\n", sum);
    }
}

习题3-2
https://vjudge.net/problem/UVA-1586
用3-1的输入模式，即一个字符一个字符读遇到\n结束，调教wa
用字符串处理确是对的，很是奇怪

#include<iostream>
#include<cctype>
#include<string>
using namespace std;
int main() {
    int n;
    cin >> n;
    getchar();
    while (n--) {
        char e;
        int cnt = 0;
        double sum = 0.0, per = 0.0;
        string s;
        cin >> s;
        for(int i=0;i<s.size();++i){
            e = s[i];
            if (isalpha(e)) {
                if (!cnt) cnt = 1;
                sum += cnt*per;
                cnt = 0;
                switch (e)
                {
                case 'C':per = 12.01;
                    break;
                case 'H':per = 1.008;
                    break;
                case 'O':per = 16.00;
                    break;
                default:per = 14.01;
                    break;
                }
            }
            else if(isdigit(e))
                cnt = cnt * 10 + e - '0';
        }
        if (!cnt) cnt = 1;
        sum += cnt*per;
        printf("%.3lf\n", sum);
    }
}

3-3习题
https://vjudge.net/problem/UVA-1225

#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    while (n--) {
        int AA[10] = {};
        int k;
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i) {
            int j = i;
            while (j) {
                ++AA[j % 10];
                j /= 10;
            }
        }
        printf("%d", AA[0]);
        for (int i = 1; i < 10; ++i)
            printf(" %d", AA[i]);
        printf("\n");
    }
}

3-4习题
https://vjudge.net/problem/UVA-455

#include<iostream>
#include<string>
using namespace std;
bool pd(string &s,int k) {
    for (int i = k; i < s.size(); ++i)
        if (s[i] != s[i%k]) return false;
    return true;
}
int main() {
    int n;
    string s;
    cin >> n;
    int cnt = 0;
    while (n--) {
        cin >> s;
        if (cnt++) cout << endl;
        for (int i = 1; i <= s.length(); ++i) {
            if (s.length() % i) continue;       
            if (pd(s, i)) { cout << i << endl; break; }
        }
    }
}

3-5习题
https://vjudge.net/problem/UVA-227

#include<iostream>
#include<string>
using namespace std;
int main() {
    string s[5],str,sss;
    int x, y,tt;
    int flag ;
    int cnt = 0;
    while (getline(cin, s[0]) && s[0] != "Z") {
        ++cnt;
        if (s[0].size() == 4) s[0]+= " ";
        if ((tt = s[0].find(' ')) != string::npos) { x = 0; y = tt; }
        for (int i = 1; i < 5; ++i) {
            getline(cin, s[i]);
            if (s[i].size() == 4) s[i] += " ";
            if ((tt = s[i].find(' ')) != string::npos) { x = i; y = tt; }
        }
        str = "";
        do {
            getline(cin, sss);
            str += sss;
        } while (str.back() != '0');
        flag = 0;
        for (int i = 0; i < str.size() - 1; ++i) {
            switch (str[i])
            {
            case 'A':
                if (!x) { flag = 1; break; }
                swap(s[x][y], s[x - 1][y]);
                x -= 1;
                break;
            case 'B':
                if(x==4) { flag = 1; break; }
                swap(s[x][y], s[x + 1][y]);
                x += 1;
                break;
            case 'L':
                if(!y) { flag = 1; break; }
                swap(s[x][y], s[x][y - 1]);
                y -= 1;
                break;
            case 'R':
                if(y==4) { flag = 1; break; }
                swap(s[x][y], s[x][y + 1]);
                y += 1;
                break;
            default:
                break;
            }
            if (flag) break;
        }
        if (cnt > 1) printf("\n");
        printf("Puzzle #%d:\n", cnt);
        if (flag) printf("This puzzle has no final configuration.\n");
        else {
            for (int i = 0; i < 5; ++i) {
                printf("%c", s[i][0]);
                for (int j = 1; j < 5; ++j)
                    printf(" %c", s[i][j]);
                printf("\n");
            }
        }   
    }
}

3-6习题
https://vjudge.net/problem/UVA-232

#include<iostream>
#include<string>
using namespace std;
struct node {
    int x,y,number;
    node(int a, int b,int c) {
        x = a, y = b,number=c;
    }
    node() = default;
};
node ssta[105];//上无白格
node lsta[105];//左无白格
int stop, ltop;
int main() {
    string s[15];
    int r, c, cnt = 0, nn;
    while (cin >> r && r != 0) {
        ++cnt;
        nn = 0;
        stop = ltop = -1;
        cin >> c;
        for (int i = 0; i < r; ++i)
            cin >> s[i];
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j) {
                if (s[i][j] != '*' && (i == 0 || s[i - 1][j] == '*' || j == 0 || s[i][j - 1] == '*')) ++nn;
                if (s[i][j] != '*' && (i == 0 || s[i - 1][j] == '*')) ssta[++stop] = node(i, j, nn);
                if (s[i][j] != '*' && (j == 0 || s[i][j - 1] == '*')) lsta[++ltop] = node(i, j, nn);
            }
        if (cnt != 1) cout << endl;
        printf("puzzle #%d:\nAcross\n", cnt);
        for (int i = 0; i <= ltop; ++i) {
            printf("%3d.", lsta[i].number);
            int k = lsta[i].y;
            while (k < c && s[lsta[i].x][k] != '*')
                printf("%c", s[lsta[i].x][k++]);
            printf("\n");
        }
        printf("Down\n");
        for (int i = 0; i <= stop; ++i) {
            printf("%3d.", ssta[i].number);
            int k = ssta[i].x;
            while (k < r && s[k][ssta[i].y] != '*') 
                printf("%c", s[k++][ssta[i].y]);
            printf("\n");
        }
    }
}

3-7习题
https://vjudge.net/problem/UVA-1368

#include<iostream>
#include<string>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s[55];
    while (n--) {
        int a, b;
        cin >> a >> b;
        for (int i = 0; i < a; ++i)
            cin >> s[i];
        string str;
        int sum=0;
        for (int k = 0; k < b; ++k) {
            int num[4] = {};//ACGT
            for (int i = 0; i < a; ++i) {
                switch (s[i][k])
                {
                case 'A':++num[0]; break;
                case 'C':++num[1]; break;
                case 'G':++num[2]; break;
                case 'T':++num[3]; break;
                default:
                    break;
                }
            }
            if (num[0] >= num[1] && num[0] >= num[2] && num[0] >= num[3]) {
                str += "A"; sum += a - num[0];
            }
            else if (num[1] >= num[0] && num[1] >= num[2] && num[1] >= num[3]) {
                str += "C"; sum += a - num[1];
            }
            else if (num[2] >= num[0] && num[2] >= num[1] && num[2] >= num[3]) {
                str += "G"; sum += a - num[2];
            }
            else {
                str += "T"; sum += a - num[3];
            }
        }
        cout << str << endl << sum << endl;;    
    }
}

3-8
https://vjudge.net/problem/UVA-202
答案要求是结果后面都空一行,我以为是结果之间空一行，唉，体验好差，题目都没说明

#include<iostream>
using namespace std;
int main() {
    int a, b;
    while (cin >> a >> b) {
        int sta[3005], top = 0;//sta[1...3004]
        int vis[3005] = {};//存放访问过的余数的位置+1
        printf("%d/%d = %d.", a, b, a / b);
        a %= b;
        vis[a] = 1;
        while (1) {
            sta[++top] = a * 10 / b;
            a=a * 10 % b;
            //如果vis[a]存在，说明top后面的即是重复的，【vis[a]开始到top】
            if (vis[a]) break;
            vis[a] = top+1;
        }
        for (int i = 1; i <= top; ++i) {
            if (vis[a]<=50 && i == vis[a]) printf("(");
            if (i <= 50) printf("%d", sta[i]);
            if(vis[a]>50 &&i==51) printf("(");
            if (i == 51) printf("...");
        }
        printf(")\n   %d = number of digits in repeating cycle\n\n",top-vis[a]+1);
    }
}

习题3-9
https://vjudge.net/problem/UVA-10340

#include<iostream>
#include<string>
using namespace std;
int main() {
    string s, t;
    while (cin >> s >> t) {
        int i = 0, j = 0;
        for (; i < s.length(); ++i) {
            while (t[j] != s[i]) {
                if (++j > t.length()) break;
            }
            if (j > t.length()) {
                break;
            }
            ++j;
        }
        if (i == s.length())cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

习题3-10
https://vjudge.net/problem/UVA-1587

#include<iostream>
using namespace std;
int main() {
    int a[6][2],cnt;
    int sta[15], top;//sta[1...14]
    while (cin >> a[0][0] >> a[0][1]) {
        top = 0;
        int vis[10006] = {};
        vis[a[0][0]] = 1; sta[++top] = a[0][0];
        if (!vis[a[0][1]]++) sta[++top] = a[0][1];
        for (int i = 1; i < 6; ++i){
            cin >> a[i][0] >> a[i][1];
            if (!vis[a[i][0]]++)  sta[++top] = a[i][0]; 
            if (!vis[a[i][1]]++)  sta[++top] = a[i][1]; 
        }
        if (top == 1) cout << "POSSIBLE" << endl;//一个数字
        else if (top == 2 && (vis[sta[1]]==8|| vis[sta[1]] == 4)) {//1*1 2个 1*2 4个
            int nn = 0;
            for (int i = 0; i < 6; ++i)
                if (a[i][0] == a[i][1]) ++nn;
            if (nn != 2)cout << "IMPOSSIBLE" << endl;
            else cout << "POSSIBLE" << endl;
        }
        else if (top == 3 && vis[sta[1]]==4 && vis[sta[2]]==4) {//3个数字
            bool flag = true;
            for (int i = 0; i < 6; ++i)
                if (a[i][0] == a[i][1]) { flag = false; break; }
            if(flag) cout << "POSSIBLE" << endl;
            else cout << "IMPOSSIBLE" << endl;
        }
        else
            cout << "IMPOSSIBLE" << endl;
    }
}

习题3-11
https://vjudge.net/problem/UVA-1588

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
    string s, t;
    while (cin >> s >> t) {
        if (s.size() < t.size()) swap(s, t);//t代表短的串
        int gap = 0,gmax=0;
        for (int i = 0; i < s.size()+t.size(); ++i) {
            if (i < t.size()) ++gap;
            if (i >= s.size()) --gap;
            bool flag = true;
            for (int k = 0; k < t.size(); ++k)
                if (i - t.size() + 1 + k >= 0 && i - t.size() + 1 + k <s.size()&& t[k] +s[i - t.size() + 1 + k]-'0'>'3'){
                    flag = false; break;
                }
            if (flag) {
                gmax = max(gap, gmax);
            }
        }
        cout << s.size() + t.size() - gmax << endl;
    }
}

习题3-12
为避免误差，用打表法做，直接求可能会有一些误差导致wa
https://vjudge.net/problem/UVA-11809

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
double X[15][40];
long long int Z[15][40];
int main() {
    string s;
    int E, M;
    for (M = 0; M <= 9; ++M)
        for (E = 1; E <= 30; ++E) {
            double k = log10(2)*(pow(2, E) - 1) + log10(1 - pow(2, -M - 1));
            Z[M][E] = k;
            X[M][E] = pow(10, k - Z[M][E]);
        }
    double A; int B;
    while (cin>>s && s!="0e0") {
        s[s.find('e')] = ' ';
        sscanf(s.c_str(), "%lf %d", &A, &B);
        bool flag = false;
        for (M = 0; M <= 9; ++M) {
            for (E = 1; E <= 30; ++E)
                if (fabs(X[M][E] - A) < 1e-5 && B==Z[M][E]) { flag = true; cout << M << ' ' << E << endl; }
            if (flag) break;
        }
    }

}