CSU-ACM Home Page

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

Update Time: 2019-04-15 12:43:40     Recent Editor: Scanf     Create Time: 2019-04-14 22:02:07     Creator: Scanf    


A-跨界增援

题目大意

有n个物品,每个物品具有两类属性A,B,每个物品需要被分为三类且每一类最终数量相同,被分为第一类贡献为A,被分为第二类贡献为B,被分为第三类(A+B)/2,要求贡献最大

问题分析

我们可以将这个问题转化一下,每一类贡献乘2,那么贡献分别为A+A,A+B,B+B,那么从第一类到最后一类每一类的差距都是定值+B-A,因此我们可以求出n个物品2*A的和,然后按+B-A排序,只需要令选出的+B-A和最大即可,令m=n/3,那么[m+1,2*m]取一次,[2m+1,3m]取两次即可。

另:使用nth_element可以做到O(n)

题目评价

考查内容:转换、贪心、排序

时间复杂度:O(nlogn) 或 O(n)

题目难度:★ ★ ★

B-Magic Spell

题目大意

有一串数,由0和1组成,是二进制数1, 2, 3...连接起来的小段每次多一个数再连接起来的数(真拗口)。问第i位是什么。

问题分析

因为 i 的范围很大,所以我们不能想着模拟处理出来。所以我们可以通过分段,查找它是在那个段 sk 中,然后再查找它是在这个段的哪个数中,又是这个数的第几位。

具体实现

具体我们可以通过预处理出记录i段长度的s[i]数组和记录加入i段总长度的dp[i]数组,用lower_bound二分查找实现。

//预处理
s[0]=dp[0]=0;
for(int i=1;i<=maxk;++i){
    s[i]=s[i-1]+log2(i)+1;   //log2(i)+1是i数字的二进制长度
    dp[i]=dp[i-1]+s[i];
}
//二分查找
int pos=lower_bound(dp,dp+maxk+1,i)-dp; //位于s_pos段中
i-=dp[pos-1];   //是s_pos段的第i个数
pos=lower_bound(s,s+maxk+1,i)-s;  //位于pos数中
i-=s[pos-1];  //是pos数的第i位
int l=log2(pos)+2-i;    //是pos数的倒数第l位
int ans;
while(l--){
    ans=pos&1;
    pos>>=1;
}

预处理的复杂度是O(N),二分查找求解是可以O(logN)计算出来的,因此算法整体的复杂度是 O(N)的。

题目评价

考查内容:二分思想,递推思想

时间复杂度:O(n)

题目难度:★ ★

C-Magina Loves Bounty Rune

题目大意

给定起点和终点,每秒可以移动一格(上下左右)或者保持不动,每c秒可以瞬移d格一次(上下左右)。问最少几秒能到达终点。

问题分析

BFS+优先队列。由于每个状态有4个参数,其中时间已经由优先队列取最短时间,所以只需要搜索其余3个参数。

具体实现

#include <bits/stdc++.h>
using namespace std ;
const int INF =1e9;
struct node{
    int x,y,cd,st;
    bool operator<(const node& x)const{
        return st>x.st;
    }
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int cx[4],cy[4];
bool vis[505][505][13];
int n,m,d,c,ans;
int tx,ty,sx,sy;

inline bool check(node x){
    if(x.x>=1 && x.x<=n && x.y>=1 && x.y<=m && vis[x.x][x.y][x.cd]==false)
        return true;
    return false;
}
void bfs(){
    node now=(node){sx,sy,0,0},next;
    vis[sx][sy][0]=1;
    priority_queue<node>q;
    q.push(now);
    while(!q.empty()){
        now=q.top();q.pop();
        if(now.x==tx && now.y==ty){
            ans=now.st;
            return;
        }
        next=now;
        if(next.cd)next.cd--;
        next.st++;
        if(check(next)){
            q.push(next);
        }
        if(now.cd==0){
            next=now;
            next.cd=c;
            for(int i=0;i<4;i++){
                next.x=now.x+cx[i];
                next.y=now.y+cy[i];
                if(check(next)){
                    vis[next.x][next.y][next.cd]=1;
                    q.push(next);
                }
            }
        }
        next=now;
        if(next.cd)next.cd--;
        next.st++;
        for(int i=0;i<4;i++){
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(check(next)){
                vis[next.x][next.y][next.cd]=1;
                q.push(next);
            }
        }
    }
}

int main(int argc, char *argv[]) {
    scanf("%d %d %d %d",&n,&m,&d,&c);
    memset(vis,0,sizeof(vis));
    ans=INF;
    cx[2]=d;cx[3]=-d;cy[0]=d;cy[1]=-d;
    scanf("%d %d",&tx,&ty);
    scanf("%d %d",&sx,&sy);
    bfs();
    printf("%d\n",ans);
    return 0;
}

算法分析:每个点至多访问12次,所以算法复杂度为O(12nm)

题目评价

考查内容:BFS

时间复杂度:O(12nm)​

题目难度:★ ★

D-bcc的约数研究

题目大意

F(X)表示X的约数个数,求F(1)+F(2)+F(3)+……+F(N)的值。

问题分析

解法一:

可以按照 题意给出的方式,对1-n的每个数字进行质因子分解,最后求出每一个F(i)的值

解法二:

换一种思路,F(X)表示X的约数个数,求F(1)+F(2)+F(3)+……+F(N)的值,那就只要枚举1-n中的每一个数,看它是1-n中多少个数的因数就行了。

具体实现

解法一:

线性筛处理出每个数的最小质因子,然后对每一个数进行质因子分解,从而求出所有的F(x)

long long add(int x)
{   //dy[x]为x的最小质因子
    long long ans=1,tot=1,last=dy[x];
    while(x>1)
    {
        if(dy[x]==last)
            tot++;
        else
            ans*=tot,tot=2,last=dy[x];
        x/=p[dy[x]];
    }
    ans*=tot;
    return ans;
}
for(int i=1;i<=n;i++)
    ans+=add(i);

每个数分解是O(logn),总复杂度为O(nlogn)

解法二:

for(int i=1;i<=n;i++)
    ans+=n/i;

题目评价

考查内容:质数筛法或模拟

时间复杂度:O(n) 或 O(nlogn)

题目难度:★

E-小Z的单词

题目大意

给出一个字符串,问包含k个相同字母的连续子序列有多少。

问题分析

找出该字符串中相同字母的连续子序列,设其长度为L,如果L < k,跳过,如果 L ≥ k ,那么这个子序列包含L - k + 1个“k-易记值子序列”。数据量比较大,不要使用cin、cout,建议使用scanf、printf等快速输入输出方法。另外请注意一些边界情况,比如单词的长度只有1、都是相同的字母等等

具体实现

对每个单词扫一遍,在这个过程中统计出相同字母连续子序列的长度,选择符合要求的统计即可。

题目评价

考查内容:计数,基本程序结构的使用

时间复杂度:O(n|s|) (除了输入输出的问题,还有很大一部分同学超时是因为写成了O(n|s|k)的暴力复杂度了)

题目难度:★