【题解】牛客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;
}
