牛客IOI周赛20-普及组（题解）

A —完全数

题目分析：首先，完全数是可以打表的，完全数就是那么几个直接打表判断，剩下的就是过剩数和不足数，那么有一个定理那就是奇数是不足数，偶数是过剩数，但是有一个特例，那就是2835，他虽然是一个奇数但是却是过剩数，特殊判断一下就行

方法一：打表判断

#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");
}

方法二：暴力

#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 移动撤销

题目分析：栈的思想

如果当前符号不是Z的话那我们把它的下标放到动态数组里面，如果当前遇到了字符是Z，并且当前队列如果存在即队列里有数，那么就撤销最近一次的操作就行

#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 石头剪刀布

题目分析：贪心思想

为了能得到尽可能多的分，那么牛牛就不可能输，最差的也是平手，所以我们要让牛牛能多赢一次就多赢一次，那么就用到了贪心的思想，我们每次都找能让牛牛赢的局，因为每一次都能得到两分，然后在剩余的情况里，让他们匹配平手的情况，每一种情况加一分，这样牛牛就得到最高的分了

#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 夹缝中求和

方法一：区间

题目分析：题目要我们求一共有多少对数字，满足大于x小于y，那么我们首先让数组从小到大排列，我们可以用一个数组去记录一下满足题目要求的数，如果当前数组的数大于y那么他将永远不能构成满足条件的数，我们把小于y的数用另一个数组去储存，然后对它进行从小到大排序，我们利用区间的方法去求解这道题，就一直遍历下去，求解左端点和右端点，左端点：如果当前两个数相加小于x那么左区间往右移动，类似的，右区间也是同样的求法，最后只需要把区间想减就是我们想要得到的答案，把左右满足的区间相加就是这个题目的答案

#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);
}

方法二：二分查找

从方法一中可以看到，我们是去找左端点和右端点，然后求区间长度，那么我们可以想到，找一个数最快的方法就是二分查找

STL 自带的二分函数—— upper_bound和lower_bound

这两个函数的作用是二分查找一个数在数组中出现的位置。区别是 upper 返回第一个大于搜索数的位置，而 lower 是第一个大于等于的数的位置。

#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);
}