CSU-ACM Home Page

中南大学第十二届大学生程序设计竞赛网络预选赛题解

Update Time: 2018-04-15 19:29:53     Recent Editor: Scanf     Create Time: 2018-04-15 10:59:08     Creator: Scanf    


A:跳一跳

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
int main()
{
    LL t,last=-1,sum=0,x=0,tmp=0; char s[10],ss[10];
    while(~scanf("%lld%s%s",&t,s,ss))
    {
        if(last>=0&&t-last>=2000) sum+=tmp;
        if(ss[0]=='O')
        {   printf("%lld\n",sum);
            last=-1; sum=0; x=0; tmp=0;
            continue;
        }
        if(s[0]=='P')
        {   if(x>1) x+=2;
            else
            {   if(last>=0&&t-last<=1000) x=4;
                else x=2;
            }
        }
        else if(last>=0&&t-last<=1000) x=2;
        else x=1;
        sum+=x; last=t;
        if(ss[0]=='R') tmp=10;
        else if(ss[0]=='S') tmp=20;
        else if(ss[0]=='M') tmp=30;
        else tmp=0;
    }
    return 0;
}

微信跳一跳模拟

时间复杂度:O(n)

B:well’s lottery

​给N个数和一个X,要求删除最少的数使得剩余的数选任意个数or起来不能等与x. 考虑数字的每一个bit位,对于ai | X ==X 的说明对答案有贡献,把ai所有不为0的bit位的贡献+1即可 最后输出X所有为1的bit位的贡献得最小值 每个ai在判断有贡献后将1-30个bit位都for一遍计算贡献

    scanf("%d%d",&n,&x);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        if ((t|x)==x)
        {
            for (int i=0;(1<<i)<=t;i++)
                if ((1<<i)&t) Bit[i]++;
        }
    }
    for (int i=0;(1<<i)<=x;i++)
    if ((1<<i)&x) ans=min(ans,Bit[i]);

考查内容:位运算的性质,贪心

时间复杂度:O(n)

C:a simple game

通过分析可以得到当且仅当b或者b的反串为a的子串时,小A才能赢 kmp

D:Z‘s array

对这个数列扫一遍,记录上升段紧接下降段的个数,即为峰的个数。 大量数据,建议使用scanf

考查内容:模拟

时间复杂度:O(n)

E:water problem

我们可以把z形线无限延长,那么它就类似于三根直线,于是任意两条z形线之间就都可以有9个交点,这就表明对于所有的N>0都有ans(Z)=ans(Z-1)+9*(Z-1)+1 于是就可以算出ans(Z)=$(\frac{9}{2})$N^2-$(\frac{7}{2})$N+1

​long long ans=(9NN-7*N)/2+1;

时间复杂度:O(1)

F:Z's Coffee

设当前每杯的容量为x, y, z, 因为x + y + z = A 则可以枚举i, j,将第i杯中的咖啡倒入第j杯 如果满足条件,设倒入后的状态为x′,y′,z 判断其中是否有D,并记录其前驱 为保证操作最少,用BFS扩展即可

复杂度 O(n2)