月度归档:2019年07月

UVA1588 换抵挡装置 Kickdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;
int solve(string a, string b) {
    a.append(b.size(), '0');
    for (int i = 0; i < a.size()-b.size()+1; i++) {
        bool flag = true;
        for (int j = 0; j < b.size(); j++) {
            if (a[i+j] + b[j] - '0' > '3') {
                flag = false;
                break;
            }
        }
        if (flag)
            return max(a.size()-b.size(), i + b.size());
    }
    return a.size();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a, b;
    while (cin >> a >> b)cout<<min(solve(a, b),solve(b,a))<<'\n';
}

UVA202 循环小数 Repeating Decimals

模拟除法,当出现余数第二次相同时可以记为一个循环节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<string>
#include<map>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;

void solve(int a, int b) {
    int OA = a;
    string strInt = to_string(a / b);
    a %= b;
    a *= 10;
    string strDec = "";
    map<int, int> dict;
    while (dict.count(a) == 0) {
        dict[a] = strDec.size();
        strDec += to_string(a / b);
        a %= b;
        a *= 10;
    }
    string strDec1 = strDec.substr(0, dict[a]);
    string strDec2 = strDec.substr(dict[a]);
    string strDec3 = "";
    if (strDec2.size() > 50) {
        strDec3 = '(' + strDec2.substr(0, 50) + "...)";
    }
    else {
        strDec3 = '(' + strDec2 + ")";
    }
    cout << OA << "/" << b << " = " << strInt << "." << strDec1 << strDec3 << '\n';
    cout << "   " << strDec2.size() << " = number of digits in repeating cycle" << '\n';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    while (cin >> a >> b)solve(a, b);
}

UVA1368 DNA序列 DNA Consensus String

解题思路是,统计所有字符串对应位置上出现次数最多的字母,并将其拼接起来作为Hamming距离和最小的DNA序列,也可以算作贪心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;
int t, m, n;
int seq[5];
string strArr[1005];
inline void seqSet(char c) {
    switch (c) {
    case 'A':seq[1]++; break;
    case 'C':seq[2]++; break;
    case 'G':seq[3]++; break;
    case 'T':seq[4]++; break;
    }
}
char seqGet[6] = " ACGT";
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> m >> n;
        for (int i = 1; i <= m; i++)cin >> strArr[i];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            memset(seq, 0, sizeof(seq));
            for (int k = 1; k <= m; k++)seqSet(strArr[k][i]);
            int Pmax = 1;
            for (int p = 2; p <= 4; p++)
                if (seq[p] > seq[Pmax])
                    Pmax = p;
            cnt += m - seq[Pmax];
            cout << seqGet[Pmax];
        }
        cout << '\n';
        cout << cnt << '\n';
    }
}