CSU-ACM Home Page

中南大学第十二届大学生程序设计竞赛正式赛题解

Update Time: 2018-04-23 23:50:33     Recent Editor: Scanf     Create Time: 2018-04-22 15:07:57     Creator: Scanf    


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

Problem A 觉醒!MACROSS!

题目大意:

给出N个点距MACROSS的相对空间位置,求最远距离是多少?

问题分析:

求最大值

具体实现:

N个点扫一遍求最大距离

题目评价

考查内容:基本循环语句的应用

时间复杂度:O(n)

题目难度: ☆ 

Problem B 航行日志的修复

题目大意:

给出一个用循环替换加密(凯撒密码)的密文,求明文。

问题分析:

根据频率最大的字母求出偏移量,在根据最后一个字符,求出句号的对应字符,再根据逗号接空格,求出逗号和句号的对应字符。

具体实现:

扫一遍文本按上述规则找出相应量,再进行解密。

题目评价

考查内容:字符串的读入,基本分支、循环语句的应用

时间复杂度:O(|s|)

题目难度: ☆  ☆

Problem C 神山神石

题目大意

    神山每天可以选择吃掉一个神石并修改自身高度,或者让所有神石能力值+1

问在p天能能够组成 [l,r]间的多少个数

p<=100,l,r<=10^9    

问题分析

    可以知道小于 100 的素数 27 个,且每个素数的指数都在 4 ~ 30,可以DFS暴力出所有27个素因子能组成的数字

从小到大排序后可DP得到变为高度 x的时间为 Dis[x]   

具体实现

    暴力枚举结束后,排序,再枚举每一天去喂石头,类似于做背包,只是背包需要离散化

利用单调性可以将寻找转移点降低一个log

const int P[29]={0,2,3,5,7,11,13,
                17,19,23,29,31,37,
                41,43,47,53,57,59,
                61,67,71,73,79,
                83,89,91,97,101};

void Dfs(int now,int x)
{
    if (now>n)
    {
        num[++num[0]]=x;
        return;
    }
    while(true)
    {
        Dfs(now+1,x);
        if (r/x<P[now]) break;
        x*=P[now];
    }
}

    Dfs(1,1);
    for (int i=1;i<=num[0];i++) Dis[i]=INF;
    Dis[1]=0;
    sort(num+1,num+num[0]+1);
    for (int i=2;i<=p;i++)
    {
        int l=1;
        for (int j=1;j<=num[0];j++)
        {
            while (l<=num[0] && num[l]<i*num[j]) l++;
             //l=lower_bound(num,num+num[0]+1,i*num[j])-num;
            if (l<=num[0])
            {
                Dis[l]=min(Dis[j]+1,Dis[l]);
                if (Dis[l]+i<=p) FF[l]=true;
            }
        }
    }

    for (int i=1;i<=num[0];i++)
        if (FF[i] && num[i]<=r && num[i]>=l) ans++;
    printf("%d\n",ans);

题目评价

考查内容:暴力,素数,DP,单调性

时间复杂度:O(|List|*p)

题目难度: ☆ ☆ ☆ ☆

Problem D I'm new here

题目大意

给一棵树,树边有权值,每一条路径的长度为路径上所有边权的异或和。问所有路径的长度之和 

问题分析

首先考虑一条路径的长度的快速求法

如果路径长度是边权的累加,则显然是个经典问题,做法是任选一个点作为树根,对于每个点u求出到根的路径长度d[u],则对于u->v的路径长度为d[u] + d[v] - 2*d[lca]

又由于本题是异或和,则根据异或的性质,lca部分刚好被抵消

所以我们依旧可以预处理数组d[u]表示u到树根的路径异或和,则对于u->v的路径,长度为d[u] ^ d[v]

又因为要计算所有路径的距离的累加,再加上位运算,我们很容易联想到这里需要分别计算每一位的贡献

对于第i位,若有k个点的d[]值在第i位为1,则显然有n-k个点的d[]值在第i位为0,那根据异或的性质,能对答案产生的贡献为(1<<i) * k * (n-k)

所以只需要按位统计,累加贡献即可

具体实现

首先dfs处理出d[]数组,再0~31枚举位数i,同时枚举点统计第i位为1的个数,累加贡献即可

题目评价

考查内容:异或的性质 树上路径的性质 贡献思想

时间复杂度:O(n * 31 )

题目难度: ☆ ☆ ☆

Problem E EZ's binoculars

题目大意

给你一些点

然后其实是每次询问给你一个中心在( x , y )的四边相等的菱形,对角线长为d,求问多少点在菱形里。

问题分析

首先可以想到二维树状数组维护。但是显然内存不允许,时间复杂度也不允许。

所以需要离线优化

那么考虑优化,可以基于离线排序后优化。现将所有的点P按照( x + y )关键字排序,然后将菱形的四个点按照( x + y )排序。

那么,每次如果P的(x+y)<= 菱形的(x+y),那么将p的(y-x)离散化后的值插入到树状数组

那么查询菱形中一点 t 下方有多少个点时,就是查询小于等于t.y - t.x的点的个数,树状数组查询即可(必须离散化后查询)。

所以时间复杂度就是O(nlgn)。

具体实现

题目评价

考查内容:数据结构题

时间复杂度:O(nlgn)

题目难度: ☆ ☆ ☆

Problem F Lunch War with the Donkey

题目大意

    有两种食物,王境泽会尽可能的多吃,但只会配对着一起吃。一对搭配的食物的美味度定义为两者的乘积,输出王境泽所有吃东西的方案中最大和最小的总美味度。

问题分析

   对于无法搭配食用的单一食物,我们可以假想它和0搭配。统一补齐成相同种数后,问题变为:

max/min~~a_1b_1+a_2b_2+…+a_k*b_k=max/min~~_{i=1}^{k} a_i*b_i

利用贪心思想猜出结论或者由熟知的排序不等式得出:max=按大小排序后的顺序和,min=按大小排序后的逆序和

具体实现

    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=m;i++) scanf("%d",&b[i]);
    int len=max(n,m);
    for (int i=n+1;i<=len;i++) a[i]=0;
    for (int i=m+1;i<=len;i++) b[i]=0;
    sort(a+1,a+1+len);
    sort(b+1,b+1+len);

题目评价

考查内容:贪心思想/数学基础

时间复杂度:O(nlogn)

题目难度: ☆ ☆

Problem G 手游大佬

题目大意

给你一个注册日期,计算注册以来到2018年4月22日,平均每天的花费和平均每天的上线时间。

问题分析

其实最主要的问题就是求两个日期间隔的天数。

一个比较好的做法是,设计一个关于日期的函数,计算从2000年1月1日以来的天数,然后把题目确定的日期(2018年4月22日)和输入给定的注册日期分别带入这个函数,求两个结果的差值就可以了。

这个题首先考察格式读入,可以使用scanf很自然地解决。

一个需要注意的点是,题中描述的是“12小时”而输入给出的在线时间单位是“分钟”。

另外就是,注意闰年的计算。2000年是闰年。

时间复杂度是O(n)。

具体实现

题目评价

考查内容:模拟,日期减法

时间复杂度:O(n)

题目难度: ☆ ☆

Problem H 星罗棋布的湖泊

题目大意

    给出n 个高度为hi 个点m 条边的连通平面图,且所有区域均为三角形,边界外的点高度都比与其相邻的边界低。求暴雨淹没整个区域后形成的湖泊个数。两个只有一些深度为0 的公共点的湖泊会被当作不同的湖泊。

问题分析

    一个点的水面高度取决于它到边界需要经过的海拔最高的点。则从边界上的点出发,  dijkstra 求出每个点的水面高度,然后对于有水的部分dfs或bfs 求连通块即可。

需要注意的是求边界的问题,  可以先找出x 坐标最小的点,该点肯定在边界上。从该点出发的极角最小的边肯定是边界。从该边出发并绕回该边(边界会经过一个点多次,若从点出发会使边界不全),  每次往逆时针方向第一条边走,  即反向边的下一条边。  可以使用循环链表(或加链尾特判,比如链尾指向某一负数) 实现,将所有边排序后依次加入链表以保证有序,链表节点从2 开始标号后xor 1即可得到反向边。本题范围较小,可以暴力找反向边(会被卡到O(m^2),  利用单调性后为O(m) 。

具体实现 略 题目评价

考查内容:基本数据结构的使用

时间复杂度:O(mlogm)

题目难度: ☆ ☆ ☆ ☆

Problem I Tragedy Words

题目大意

    给定若干个位置求符合悲伤定义的单词有多少个

问题分析

    按类即可枚举每一位为元音,辅音和特殊字符L即可,这样复杂度为3^10

具体实现

    注意要开long long答案最大可以达到26^10

for (i=1;i<=Que[0];i++)
   if (c[Que[i]]=='A') sum*=5ll;
   else if (c[Que[i]]=='B') sum*=20ll;
   ans+=sum;


 c[Que[x]]='A';
 dfs(x+1);
 c[Que[x]]='B';
 dfs(x+1);
 c[Que[x]]='L';
 dfs(x+1);

题目评价

考查内容:带优化的爆搜

时间复杂度:O(3^m),m为下划线个数

题目难度: ☆ ☆

Problem J Pigs can't take a sudden turn

题目大意

  两个点以两个恒定的速度移动,问过程中两点的最短距离。

问题分析

其实有个加强版的题,在白书计算几何部分。

首先我们要发现它有“凸函数”的性质,即距离先减少再增加或者一直增加。

怎么看呢?一是可以推公式,可以发现是个抛物线,二可以通过相对参考系,即固定一个点不动,另一个点走一个射线或者是相对静止(此时速度相同)。

接下来有很多方法解决这个问题了,数学公式求导,或求抛物线对称轴,或三分找凸函数极值点,或计算几何的思想点积叉积搞一搞。       

具体实现

方法一:数学推导

distance^2 = ((x1+t * u1)-(x2+t * u2))^2+((y1+t * v1)-(y2+t * v2))^2

化简整理distance是关于t的一个二次函数,求对称轴即可。

唯一的坑点是对称轴公式中,-b/2a的a可能为0,要特判,此时是两个速度相同的时候。      

方法二:三分

和上面一样,发现是个二次函数后,直接计算,逼近结果即可,一样要注意特判。

方法三:计算几何

典型的控制一个点不动,相对参考系下就是求点到射线的距离,射线的另一端取t无穷大后的点,用无穷远的线段来代替,一样注意速度相同的时候。

题目评价

考查内容:数学,三分,几何

时间复杂度:O(1)

题目难度: ☆