Niuke IOI weekly competition 20 popularization group (problem solving)

Cattle guest IOI Weekly game 20- Popularization group （ Answer key ）

A — Perfect number

Topic analysis ： First , Perfect numbers can be tabulated , Perfect numbers are just a few that can be judged directly by typing tables , The rest is the excess and the deficiency , Then there is a theorem that odd numbers are insufficient numbers , Even numbers are excess numbers , But there is a special case , That's it 2835, Although it is an odd number, it is an excess number , Just make a special judgment

Method 1 ： Make a table to judge

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int main()
{
    
    ll n;
    scanf("%lld", &n);
    if (n == 6 || n == 28 || n == 120 || n == 496 || n == 8128 || n == 33550336 || n == 8589869056 || n == 137438691328)
        puts("Pure");
    else if(n==2835)
        puts("Late");
    else if (n & 1) 
       puts("Early");
    else
        puts("Late");
}

Method 2 ： violence

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int main()
{
    
    ll n, ans = 1;
    scanf("%lld", &n);
    ll m = sqrt(n);
    for (int i = 2; i <= m; ++i)
        if (n % i == 0)
            ans += i, ans += n / i;
    if (ans == n)
        puts("Pure");
    else if (ans > n)
        puts("Late");
    else
        puts("Early");
}

B Move undo

Topic analysis ： The idea of stack

If the current symbol is not Z Then we put its subscript into the dynamic array , If the current encountered character is Z, And if the current queue exists, there are several in the queue , Then undo the last operation

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
vector<int> v;
char c[maxn];
int main()
{
    
    int n, x = 0, y = 0;
    scanf("%d", &n);
    getchar();
    scanf("%s", c);
    for (int i = 0; i < n; ++i)
    {
    
        if (c[i] != 'Z')
            v.push_back(i);
        else if (v.size() > 0)
            v.pop_back();
    }
    for (int i = 0; i < v.size(); ++i)
    {
    
        if (c[v[i]] == 'W')
            ++y;
        else if (c[v[i]] == 'A')
            --x;
        else if (c[v[i]] == 'S')
            --y;
        else
            ++x;
    }
    printf("%d %d\n", x, y);
}

C Rock-paper-scissors

Topic analysis ： Greedy thoughts

In order to get as many points as possible , Then Niuniu can't lose , The worst is a tie , So we want Niuniu to win once more , Then the idea of greed is used , We always find a game that can be won by Niuniu , Because I can get two points every time , And then in the rest of the case , Match them to a tie , Add one point for each case , So Niuniu gets the highest score

#include <bits/stdc++.h>
using namespace std;

int main()
{
    
    int n;
    scanf("%d", &n);
    int a1, a2, b1, b2, c1, c2;
    scanf("%d%d%d", &a1, &b1, &c1);
    scanf("%d%d%d", &a2, &b2, &c2);
    long long ans = 0;
    // cout <<sc << endl;
    int sa = min(a1, b2);
    int sb = min(b1, c2);
    int sc = min(c1, a2);
    ans = sa * 2 + sb * 2 + sc * 2;
    a1 -= sa;
    b2 -= sa;
    b1 -= sb;
    c2 -= sb;
    c1 -= sc;
    a2 -= sc;
    ans += (min(a1, a2) + min(b1, b2) + min(c1, c2));
    printf("%lld\n", ans);
}

D Sum between cracks

Method 1 ： Section

Topic analysis ： The question asks us to find out how many pairs of numbers there are , Satisfaction is greater than x Less than y, So let's first arrange the array from small to large , We can use an array to record the number that meets the requirements of the topic , If the number of current arrays is greater than y Then he will never be able to form a number that satisfies the condition , We put less than y The number of is stored in another array , Then sort it from small to large , We use the interval method to solve this problem , Just go on and on , Solve the left endpoint and the right endpoint , Left end point ： If the sum of the current two numbers is less than x Then the left section moves to the right , Allied , The same is true for right intervals , Finally, we just need to subtract the interval to get the answer we want , Adding the left and right satisfying intervals is the answer to this question

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 2e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn], num[maxn];
int main()
{
    
    ll n, x, y, cnt = 0;
    scanf("%lld %lld %lld", &n, &x, &y);
    for (ll i = 1; i <= n; ++i)
    {
    
        scanf("%lld", &a[i]);
        if (a[i] >= y)
            continue;
        else
            num[++cnt] = a[i];
    }
    sort(num + 1, num + cnt + 1);
    ll l = 2, r = cnt, ans = 0;
    for (ll i = 1; i <= cnt; ++i)
    {
    
        ll l = i + 1;
        while (num[l] + num[i] < x)
            ++l;
        while (num[r] + num[i] > y)
            --r;
        if (l > r)
            break;
        ans += r - l + 1;
    }
    printf("%lld\n", ans);
}

Method 2 ： Two points search

As can be seen from method 1 , We are looking for the left endpoint and the right endpoint , Then find the length of the interval , So we can think of , The fastest way to find a number is binary search

STL Its own bisection function —— upper_bound and lower_bound

These two functions are used to find the position of a number in the array . The difference is that upper Returns the first location greater than the number of searches , and lower Is the position of the first number greater than or equal to .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
ll a[maxn];
int main()
{
    
    ll n, x, y;
    scanf("%lld %lld %lld", &n, &x, &y);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
    
        int l = lower_bound(a + 1 + i, a + n + 1, x - a[i]) - a;
        int r = upper_bound(a + 1 + i, a + n + 1, y - a[i]) - a;
        ans += r - l;
    }
    printf("%lld\n", ans);
}

I read this passage on Weibo “ The worst , It is not inexplicable to be led astray , It's when you carry the lonely sword on your back , Decide to keep going , When you are determined to go alone , Suddenly a man appeared , Hold you tight , say , juvenile , I want to share this long life with you , When you get excited , Throw the sword away , Roast the horse , Look back , There's no one left .”