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

完全数

解题思路

签到？
正常统计因子和就行，大了就直接跳，时间复杂度为根号级别，莫得问题。

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
int f;
ll n,ans=1;
int main()
{
    cin>>n;
    for(int i=2;i<=sqrt(n);i++)//从2开始
    {
        if(n%i==0) ans+=i+n/i;
        if(ans>n){f=1;break;}//因子和大于n直接break就行
    }
    if(f==0) 
    {
        if(ans==n) puts("Pure");
        else puts("Early");
    }
    else puts("Late");

}

移动撤销

解题思路

栈；
用栈实现，栈中元素为坐标；
遇到z就弹出，其他的就压入，注意特判一下如果栈中只有原点了，没法进行pop操作，直接continue就行。

AC代码

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
stack<pii> s;
string str;
int n;

int main()
{
    cin>>n>>str;
    str='.'+str;
    s.push(pii(0,0));
    for(int i=1;i<=n;i++)
    {
        if(str[i]!='Z')
        {

            int x=s.top().fi,y=s.top().se;
            if(str[i]=='W') s.push(pii(x,y+1));
            else if(str[i]=='A') s.push(pii(x-1,y));
            else if(str[i]=='S') s.push(pii(x,y-1));
            else s.push(pii(x+1,y));
        }
        else 
        {
            if(s.size()==1) continue;
            else s.pop();
        }
    }
    cout<<s.top().fi<<' '<<s.top().se<<endl;
}

石头剪刀布

解题思路

贪心；
~~做过两次类似的了，所以这次直接秒掉。~~
贪心策略：能赢就别平，能平就别输。
介绍一下变量，m开头代表man，即公牛，即牛牛；w开头代表woman，即母牛，即牛妹，ok，这样你就好理解代码了，至于a，b，c就是石头剪刀布，顺序无所谓。
详见代码~~写的比较简单，几个min搞定了，可能不是很好理解~~

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int ans,ma,mb,mc,wa,wb,wc,n;

int main()
{
    cin>>n>>ma>>mb>>mc>>wa>>wb>>wc;

    int a=min(ma,wb);ans+=(a<<1);ma-=a;wb-=a;//牛牛石头数和牛妹剪刀数较小数目为a
    int b=min(mb,wc);ans+=(b<<1);mb-=b;wc-=b;//牛牛剪刀数和牛妹布数较小数目为b
    int c=min(mc,wa);ans+=(c<<1);mc-=c;wa-=c;//牛牛布数和牛妹石头数较小数目为c
    ans+=min(ma,wa)+min(mb,wb)+min(mc,wc);//牛牛剩下的石头和牛妹剩下的石头数目中较小数目为平局数目，同理对于剪刀和布
    cout<<ans<<endl;
}

夹缝中求和

解题思路

从小到大排序，每次统计i点之后比a[i]大的点的个数；
为什么这样是正确的？
假如两个数的大小分别为a，b且x<=a+b<=y，无论a与b在序列中的相对位置是什么样的，这对成立的数都只会被统计一次；
假设a在b的左边，即排完序后a位置小于b位置，即a的值小于等于b的值，那a和b这对成立的情况只会在遍历到a的时候被统计一次，而遍历到b的时候，只会统计比b的右侧的数中比b大的数，不会重复统计与a配对成功的情况；同样的，b在a左边也是类似的。

AC代码

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

const int N=1e5+10;
int a[N],n,x,y;
ll ans;//开ll

int main()
{
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
    {
        ll lb=lower_bound(a+i+1,a+n+1,x-a[i])-a,ub=upper_bound(a+i+1,a+n+1,y-a[i])-a;
        ans+=max(0LL,ub-lb);
    }
    cout<<ans<<endl;
}