1081 Rational Sum (20 points)

• Rational numbers; numerator/denominator; integer part; fractional part
• Give n scores, sum, write true scores and approximate scores
• Idea: initialize a as 0 and B as 1; Output: if the denominator is 1, you can directly output the integer part; If a > b, there are integer and decimal parts; The data range of numerator and denominator on pat is long int, which is equivalent to int, while acwing is long long. If there is no middle step, it will overflow. Therefore, the denominator should become the minimum common multiple of B and D and find the maximum common divisor of B and D, then the denominator is B / the maximum common divisor and then * D (originally b *d), and the numerator is... (originally a * d + b * c), But the first half of the formula is composed of d/t instead of a/t
• Syntax: gcd template; If scanf is negative, the symbol is read on the molecule

#include <iostream>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    cin >> n;
    
    LL a = 0, b = 1;
    
    for (int i = 0; i < n; i ++ )
    {
        LL c, d;
        scanf("%lld/%lld", &c, &d);
        
        LL t = gcd(c, d);
        c /= t, d /= t;
        
        t = gcd(b, d);
        a = d / t * a + b / t * c;
        b = b / t * d;
        
        t = gcd(a, b);
        a /= t, b /= t;
    }
    
    if (b == 1) cout << a;
    else
    {
        if (a > b) printf("%lld ", a / b), a %= b;
        printf("%lld/%lld", a, b);
    }
    
    return 0;
}

1088 Rational Arithmetic (20 points)

• Question meaning: give two scores and output the addition, subtraction, multiplication and division formula respectively. Note that the score should be converted into a real score. What you give may be a false score
• Idea: when printing, make an approximate score first, then judge whether the denominator is negative, and then judge whether the numerator is negative, so as to determine whether two half brackets need to be output. Then, if the denominator is 1, it depends on whether it is a false score. When making a false score, pay attention to abs, because the numerator may be negative or the denominator may be negative

#include <iostream>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

void print(LL a, LL b)
{
    LL t = gcd(a, b);
    a /= t, b /= t;
    
    if (b < 0) a *= -1, b *= -1;
    bool is_minus = a < 0;
    
    if (is_minus) cout << "(";
    
    if (b == 1) cout << a;
    else
    {
        if (abs(a) > b) printf("%lld ", a / b), a = abs(a) % b;
        printf("%lld/%lld", a , b);
    }
    
    if (is_minus) cout << ")";
}

void add(LL a, LL b, LL c, LL d)
{
    print(a, b), cout << " + ", print(c, d), cout << " = ";
    a = a * d + b * c;
    b = b * d;
    print(a, b), cout << endl;
}

void sub(LL a, LL b, LL c, LL d)
{
    print(a, b), cout << " - ", print(c, d), cout << " = ";
    a = a * d - b * c;
    b = b * d;
    print(a, b), cout << endl;
}

void mul(LL a, LL b, LL c, LL d)
{
    print(a, b), cout << " * ", print(c, d), cout << " = ";
    a = a * c;
    b = b * d;
    print(a, b), cout << endl;
}

void div(LL a, LL b, LL c, LL d)
{
    print(a, b), cout << " / ", print(c, d), cout << " = ";
    if (!c) puts("Inf");
    else
    {
        a = a * d;
        b = b * c;
        print(a, b), cout << endl;
    }
}

int main()
{
    LL a, b, c, d;
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
    
    add(a, b, c, d);
    sub(a, b, c, d);
    mul(a, b, c, d);
    div(a, b, c, d);
    
    return 0;
}

1096 constructive factors (20 points)

• Give a number and find the longest continuity factor
• Idea: first enumerate the starting position, and then enumerate the length; Note that there may be only its own situation
• Syntax: 2 31 2^{31} 231 or int range; When the loop breaks continuously, you can exit the for loop directly

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> res;
    for (int i = 2; i * i <= n; i ++ )
        if (n % i == 0)
        {
            vector<int> seq;
            
            for (int m = n, j = i; m % j == 0; j ++ )
            {
                seq.push_back(j);
                m /= j;
            }
            
            if (seq.size() > res.size()) res = seq;
        }
    
    if (res.empty()) res.push_back(n);
    
    cout << res.size() << endl;
    cout << res[0];
    for (int i = 1; i < res.size(); i ++ ) cout << "*" << res[i];
    
    return 0;
}

1104 Sum of Number Segments (20 points)

• Syntax: both I and n-i+1 are 1 0 5 10^5 105, multiply by 1 0 10 10^{10} 1010, it will exceed int, so when writing the formula, try to write double in front of it. If it is written later, it will overflow; (precision?) long double output is% Lf

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    long double res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        long double x;
        cin >> x;
        
        res += x * i * (n - i + 1);
    }
    
    printf("%.2Lf", res);
    
    return 0;
}

#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    
    ll res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        double x;
        cin >> x;
        res += (ll)(1000 * x) * i * (n - i + 1);		// Multiply by 1000 to enlarge the number, avoid the influence of accuracy, and pay attention to parentheses
    }
    
    printf("%.2lf", res / 1000.0);		// Add. 0 to convert to decimal
    
    return 0;
}

1112 Stucked Keyboard (20 points)

• Give k and a string. The string that appears k times in a row is bad
• Idea: use the original string to judge whether a key (fixed number) is bad; Traverse the original string. There are only three cases for each character. It is not bad, it is bad but has not been output, and it is bad but has been output. Therefore, instead of bool, use int

#include <iostream>

using namespace std;

const int N = 200;

int st[N];      // 1 is not broken, 0 is broken, and 2 is output

int main()
{
    string s;
    int k;
    cin >> k >> s;
    
    for (int i = 0; i < s.size(); i ++ )
    {
        int j = i + 1;
        while (j < s.size() && s[j] == s[i]) j ++ ;
        int len = j - 1 - i + 1;
        if (len % k) st[s[i]] = 1;
        i = j - 1;      // Because I have to++
    }
    
    string res;
    for (int i = 0; i < s.size(); i ++ )
    {
        if (!st[s[i]]) cout << s[i], st[s[i]] = 2;
        
        if (st[s[i]] == 1) res += s[i];
        else
        {
            res += s[i];
            i += k - 1;
        }
    }
            
    cout << endl << res << endl;
    
    return 0;
}

1116 Come on! Let's C (20 points)

• Question meaning: give id (positive integer within 1e4) according to the ranking, judge whether it has appeared in the ranking and whether it has been asked according to the asked id, and then rank first and rank whether it is a prime number
• Idea: first mark the prime number within 10 ^ 4, and use the sieve method to find the prime number, O(nloglogn); First use Rank[id] and then mark it as - 1; Rank array has three states. Rank==0 means no occurrence, rank - 1 means output, and rank is a positive integer, indicating normal ranking and no output; The st array has three states. 0 means that it has not been screened (not stained) in the screening method. If it is within 10 ^ 4, there is only 1. 1 means that it is a prime number and 2 means that it is a non prime number
• Syntax: note that the output must be%04d, such as this fixed digit number question;

#include <iostream>

using namespace std;

const int N = 1e4 + 10;

int Rank[N], st[N];

void init()
{
    for (int i = 2; i < N; i ++ )
        if (!st[i])
        {
            st[i] = 1;
            for (int j = i * 2; j < N; j += i)
                st[j] = 2;
        }
}

int main()
{
    init();
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int id;
        cin >> id;
        Rank[id] = i;
    }
    
    int k;
    cin >> k;
    while (k -- )
    {
        int id;
        cin >> id;
        printf("%04d: ", id);
        
        if (!Rank[id]) puts("Are you kidding?");
        else if (Rank[id] == -1) puts("Checked");
        else
        {
            int t = st[Rank[id]];
            
            if (!t) puts("Mystery Award");
            else if (t == 1) puts("Minion");
            else puts("Chocolate");
            
            Rank[id] = -1;
        }
    }
    
    return 0;
}

1152 Google Recruitment (20 points)

• Meaning: find the prime number of the first K (< 10) bit in a given number of L (< = 1000) bits
• Idea: judge whether a number is a prime number. The maximum k of this question is 9 bits, which is 1 0 9 − 1 10^9-1 109 − 1, it is impossible to find all the prime numbers between them. You can use trial division to judge. You can use both natural numbers and prime numbers to try x 1 / 2 x^{1/2} x1/2, if natural numbers are used to try, in the worst case, each time ( 1 0 9 ) 1 / 2 (10^9)^{1/2} (109) 1 / 2, almost 3e4, up to 1000 bits, so 3e7 may timeout. Let's optimize it. When trying division, we don't try natural numbers, but prime numbers; Fermat: the number of prime numbers from 1 to n is about n / ( l n n ) n/(lnn) n/(lnn), ln(3e4) must be greater than 10, that is, it can be more than 10 times higher than the natural number efficiency; So this question is to put 1 to 1 first ( 1 0 9 ) 1 / 2 (10^9)^{1/2} (109) prime numbers within 1 / 2 are screened out first,
• Syntax: here is to screen the prime number instead of judging the prime number, so don't worry about the special case of 1, because we only use the things in the primes array, and the st array is not used in this problem; primes[i] in cyclic conditions

#include <iostream>

using namespace std;

const int N = 4e4;

int primes[N], cnt;
bool st[N];

void init()
{
    for (int i = 2; i < N; i ++ )
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            for (int j = i * 2; j < N; j += i)
                st[j] = true;
        }
}

bool check(string s)
{
    int x = stoi(s);
    for (int i = 0; primes[i] <= x / primes[i]; i ++ )
        if (x % primes[i] == 0)
            return false;
    return true;
}

int main()
{
    init();
    
    int l, k;
    string s;
    cin >> l >> k >> s;
    
    for (int i = 0; i + k <= l; i ++ )
    {
        string ss = s.substr(i, k);
        if (check(ss))
        {
            cout << ss;
            return 0;
        }
    }
    
    cout << 404;
    
    return 0;
}