【题解】牛客IOI周赛20-普及组

（Updated：听说A题有人用奇怪的方法卡过去了，于是增加了一组数据：一个奇过剩数）

写在题解前面的话

本场比赛非常简单，最终ak的人数有100多。总之是非常水的一场比赛，大家打的开心就好。
（花絮）
清楚姐姐：怎么办啊，手上还有好多场提高组，没有普及组题目了。
我：要不我出一场？但我太菜了出不了防ak题啊。
清楚姐姐：没事不需要防ak，简单点也可以。
（于是诞生了这场没有防ak的比赛）
题目出完后也被审题人吐槽太简单了，下次还是出难一点吧QAQ

A.完全数

题意：对一个数的约数之和（除去它本身）和它自身的大小进行比较。
思路： 复杂度很容易想到，但明显过不了所有样例。
事实上，可以观察到， 的所有约数可以以 为分界线一一对应，所以可以 解出这道题：
对于每个小于的因子 ，和它互相对应的因子为 。
从1遍历到 即可（不计算它本身）。要注意特判 是完全平方数的情况，当 的时候它和自己对应，不要重复计算。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f(ll x){
    ll i;
    ll sum=0;
    for(i=2;i*i<x;i++){
        if(x%i==0)sum+=i+x/i;
    }
    if(i*i==x)sum+=i;
    return sum+1;
}
int main(){
    ll i;
    cin>>i;
    if(f(i)<i)cout<<"Early";
    else if(f(i)==i)cout<<"Pure";
    else cout<<"Late";

}

B.移动撤销

题意：每次移动有4种方案，但可以撤销前面的移动。问最后的坐标。
思路：用栈模拟移动的过程即可。撤销操作意味着出栈。无效的撤销操作仅当栈空时会发生。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i;
    string s;
    stack<char>st;
    cin>>n;
    cin>>s;
    for(i=0;i<n;i++){
        if(s[i]=='Z'){
            if(!st.empty())st.pop();
        }
        else st.push(s[i]);
    }
    int x=0,y=0;
    while(!st.empty()){
        if(st.top()=='W')y++;
        if(st.top()=='A')x--;
        if(st.top()=='S')y--;
        if(st.top()=='D')x++;
        st.pop();
    }
    cout<<x<<" "<<y<<endl;

}

C.石头剪刀布

题意：两个人玩石头剪刀布，已知每个人分别出了多少石头、剪刀和布，问怎么组合让第一个人的得分最高。
思路：简单的贪心。首先让A的石头对B的剪刀、A的剪刀对B的布、A的布对B的石头，然后剩下没用完的进行平局的组合，最后就只剩A失败的情况了。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long sum=0;
    int x1,x2,x3;
    int y1,y2,y3;
    cin>>n>>x1>>x2>>x3>>y1>>y2>>y3;
    int x=min(x1,y2);
    sum+=x*2;
    x1-=x;
    y2-=x;
    x=min(x2,y3);
    sum+=x*2;
    x2-=x;
    y3-=x;
    x=min(x3,y1);
    sum+=x*2;
    x3-=x;
    y1-=x;
    cout<<sum+min(x1,y1)+min(x2,y2)+min(x3,y3);
}

D.夹缝中求和

题意：给一个数组。求任取两数之和在l和r之间的方案数。
思路：这道题如果暴力 很好码，但主要考察的是双指针思想，可以做到 （加上排序，总复杂度为 ）。如果将数组排序，选定一个数 ，那么另一个数的范围一定在 的区间内。当 递增时，所求区间的左右端点不断递减，所以每次统计区间的长度就可以了。
但是最后别忘了排除掉 在 范围内的情况，因为这相当于连续取了2次 ，但这是不合法的取法，所以应该减去。

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){

    int n,x,y,i;
    cin>>n>>x>>y;
    for(i=0;i>a[i];
    sort(a,a+n);
    int l=n-1,r=n-1;
    long long sum=0,s2=0;
    for(i=0;i<n;i++){
        while(l>=0&&a[i]+a[l]>=x)l--;
        while(r>=0&&a[i]+a[r]>y)r--;
        sum+=r-l;
       // cout<<r-l<<endl;
        if(a[i]*2>=x&&a[i]*2<=y)s2++;
    }
    cout<<(sum-s2)/2;

}