竞赛讨论区 > 【题解】牛客IOI周赛20-普及组
头像
神崎兰子
编辑于 2020-11-30 14:24
+ 关注

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

}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐