CSU-ACM Home Page

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

Update Time: 2019-06-10 20:30:53     Recent Editor: Scanf     Create Time: 2019-04-28 14:56:26     Creator: Scanf    


向左看

过题: 86/234

题目大意

每个人向左侧最高且没被挡住的人看齐,问每个人向谁看齐。

问题分析

从左到右扫一遍,维护最大值位置即可。

具体实现

int ans = 0;
for (int i = 1; i <= n; i++) {
    printf("%d\n", ans);
    if (!ans || a[i] >= a[ans]) {
        ans = i;
    }
}

题目评价

考查内容:基本循环

时间复杂度:O(n)

题目难度:$\bigstar$

向右看

过题: 64/264

题目大意

每个人向右边比他高且离他最近的人看齐,问每个人向谁看齐。

问题分析

这道题的关键在于确定答案的三个条件:假设要查询的人是x,那么我们要找的答案是:①比x高的人,②在x右侧的人,③满足①②的人中离x最近的人。

那么就有两种思路,都是可行的:

  1. 从左到右处理数据,另外维护一个数据结构,用于查询哪些人比某个人矮。
  2. 从大到小处理数据,另外维护一个数据结构,用于查询哪个人是某个人右边的第一个人。

具体实现

第一种思路,用一个优先队列,最矮的人先出队。每次将所有比第i个人矮的人出队,这些人都是向i看齐的。

struct Cmp {
    bool operator()(int x, int y) const {
        return a[y] < a[x];
    }
};

for (int i = 1; i <= n; i++) {
    while (!que.empty() && a[que.top()] < a[i]) {
        ans[que.top()] = i;
        que.pop();
    }
    que.push(i);
}

第二种思路,先将所有人按从高到矮排序,然后用一个set,支持插入和upper_bound操作,就可以查询比第i高的人高的人中,编号大于他的第一个人是谁。

for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    b[i] = i;
}
sort(b+1, b+n+1, [](int x, int y) {
    if(a[x]!=a[y]) return a[x]>a[y];
    else return x<y;
});
set<int> st;
for (int i = 1; i <= n; i++) {
    set<int>::iterator it = st.upper_bound(b[i]);
    if(it!=st.end()) {
        ans[b[i]] = *it;
    }
    st.insert(b[i]);
}

题目评价

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

时间复杂度:O(nlogn)

题目难度: $\bigstar \; \bigstar$

向上看

过题:0 / 10

题目大意

有n条线段,给出他们的坐标和高度,问以每条线段的顶端为顶点,不包含任意一条线段上的点,也不包含数轴上的点的角的大小。

问题分析

可以想象到,这个过程就是用以线段顶端为端点的射线向左右两边搭,最后形成一个角,这个角就是所求的角。

左右两个方向的求法是相同的,因此只考虑一边,另外一边对称操作即可。

以从左向右处理的过程为例,可以想象到,维护每个答案的过程就是维护一个右上的四分之一凸包的过程,只要在维护凸包的过程中记录栈顶两个点所在直线与竖直方向的夹角,就是栈顶的答案。

具体实现

分别从左到右和从右到左维护两次四分之一凸包。

for (int i = 1; i <= n; i++) {
    while (sp && y[i] >= y[stk[sp - 1]] || sp >= 2 && k(i, stk[sp - 1]) >= k(i, stk[sp - 2])) {
        --sp;
    }
    if (!sp) {
        ans[i] = PI / 2;
    }
    else {
        ans[i] = atan2(x[i] - x[stk[sp - 1]], y[stk[sp - 1]] - y[i]);
    }
    stk[sp++] = i;
}

for (int i = n; i >= 1; i--) {
    while (sp && y[i] >= y[stk[sp - 1]] || sp >= 2 && k(i, stk[sp - 1]) <= k(i, stk[sp - 2])) {
        --sp;
    }
    if (!sp) {
        ans[i] += PI / 2;
    }
    else {
        ans[i] += atan2(x[stk[sp - 1]] - x[i], y[stk[sp - 1]] - y[i]);
    }
    stk[sp++] = i;
}

题目评价

考查内容:凸包

时间复杂度:O(n)

题目难度:$\bigstar \; \bigstar \; \bigstar$

代欧奇希斯三角形

过题:0 / 0

题目大意

​ 统计一个字母矩阵内,由同一个字母组成的直角三角形数量。

问题分析

标准算法

用前缀和优化单层的统计即可。 而实际上不需要手写8种情况,实际上只有2种情况,其他的可以通过旋转地图后仍旧用之前的方法计算。 复杂度: O(26*n^2)。

更优秀的算法 记录以某点为直角顶点的最长延伸的长度,四个方向都可递推得到。合并 相邻两个方向的可以得到第二类三角形的个数。 复杂度: O(n^2)。

题目评价

考查内容:旋转地图,枚举,统计

时间复杂度:O(n^2)

题目难度:$\bigstar \; \bigstar \; \bigstar$

疯狂的企鹅II

过题:14 / 53

题目大意

​ 求nxn棋盈中把n个棋子移到同一行或同一列所需最少次数。

问题分析

贪心,排序 通过计算的式子可以发现行列的步数计算是分离的,现在把行的计算拎出来发现就是一维曼哈顿距离,所以选中位数时最优。 证明:假设选的不是中位数,则两侧数的个数不相等,将选的数向中位数 方向移动,则其两侧的点到选的数的距离,-侧+1, -侧-1,且是数量较多侧-1,所以答案肯定不会比选中位数的答案优。 最后,若用计数排序优化快排可使复杂度减少-一个log。 复杂度: O(n)。

题目评价

考查内容:​贪心,排序

时间复杂度:复杂度: O(n)。

题目难度:$\bigstar \; \bigstar$

Promote Code

过题: 54 / 229

题目大意

给定一个非降数字串的加密密文,求出原文

问题分析

考虑0-9的英文中有些字母,z是0独有的,g是8独有的,x是6独有的,依次去掉这三个数字的字母后,h变为3独有的,以此类推,可以在10次判断后得出每个数字的个数

思想本质是高斯消元,即解方程组

另一种解法是采用26维背包,每个字母看作一个多维物品直接dp即可,但编写较为复杂且时间复杂度较高。

题目评价

考查内容:高斯消元

时间复杂度:O(N)

题目难度:$\bigstar$

Do You Like XOR

过题: 23 / 150

题目大意

给定3个整数a, b ,c,计算a到b间所有整数的c次方的异或和。

问题分析

根据异或的性质,c为偶数的时候结果为0。

c为奇数的时候,问题可以转化为求a到b间所有整数的异或和。将整数用二进制的形式表示,然后确定结果的二进制的每一位。设位从右往左数,从0开始。

如果a到b间,第i位上为1的数的个数是奇数,则结果的第i位置1,反之,置0。

具体实现

使用前缀和的思想,计算0到a-1间第i位上为1的数的个数,计算0到b间第i位上为1的数的个数,两者相减即可得到a到b间,第i位上为1的数的个数。

对于第i位,从0开始到无穷大,其上数字具有规律性:先是2i个0,后是2i个1,周期为2(i + 1)

根据周期性就可以很快的将1的个数计算出来。

#include <cstdio>
#include <algorithm>
using namespace std ;
long long get_xorsum(long long l,long long r){
    l--;
    long long ans=0,b=2,l1,r1,d1;
    for(long long i=0;i<=60;i++){
        l1=(b/2)*(l/b)+max(0LL,l%b-b/2+1);
        r1=(b/2)*(r/b)+max(0LL,r%b-b/2+1);
        d1=r1-l1;
        if(d1&1)ans+=b/2;
        b<<=1;
    }
    return ans;
}
int main(int argc, char *argv[]) {
    long long a,b,c,ans;
    while(~scanf("%lld %lld %lld",&a,&b,&c)){
        if(c&1)
            ans=get_xorsum(a,b);
        else
            ans=0;
        printf("%lld\n",ans);
    }
    return 0;
}

每次都枚举二进制的每一位,算法整体的复杂度是O(logN)的。

题目评价

考查内容:异或性质、计数、前缀和

时间复杂度:O(logn)

题目难度:$\bigstar \; \bigstar$

How many LOL

过题:4 / 43

题目大意

给定n,问所有长度为n的字符串中,不含子串"LOL"的字符串的数量。所有字符串仅含大写字母。

问题分析

数位DP,将字符串看成26进制的数,然后dfs+记忆化搜索

具体实现

long long dfs(int pos,int c1,int c2)
{
    if(pos==0)  return 1;
    if(dp[pos][c1][c2]!=-1)
        return dp[pos][c1][c2];
    long long ans=0;
    for(int i=1;i<=26;i++)
    {
        if(c1=='L'-'A'+1 && c2=='O'-'A'+1 && i=='L'-'A'+1)continue;
        ans=(ans+dfs(pos-1,c2,i))%mod;
    }
    dp[pos][c1][c2]=ans;
    return ans;
}
long long f(long long x)
{
    int pos=x;
    for(int i=1;i<=x;i++)digit[i]=0;
    return dfs(pos,0,0);
}

题目评价

考查内容:数位DP

时间复杂度:$ O(n * 26 ^2) $

题目难度:$\bigstar \; \bigstar$

Path

过题:2 / 12

题目大意

给一个n个点n-1条边的图,可以从某一些点出发,求从某一个出发点出发访问所有点的最短路程和,如果无法访问所有点,输出-1.

问题分析

通过画图观察,以及贪心考虑得出一个结论,从一个点出发,如果要回到原来的点,则所有边都要访问两次;而在这道题中访问到最后一个点则立即停下来,那么最短路程和就是最后走到离这个点最远的那个点停下,即所有边的长度*2-这个点走到离它最远点的距离。

而由于有多个出发点,那是我们利用从树的直径的性质,也就是在一棵树上的一个点的最远点一定是某一条树的直径的端点,于是我们只需求出某一条树的直径,那么这条直径的2个端点一定有一个是每个点的最远点。

具体实现

我们先随便选择一个点,使用最短路径算法或者dfs,找到某一条直径的一个端点,再用这个端点再跑一遍最短路径算法或dfs,找到直径的另一个端点。然后对于每个可以作为开始点的点,找到离他们最远点的距离。取最大值,最短路程即等于所有路径长的两倍减去这个最大值。

  long long da;
  spfa(1);da=-inf;
  for(int i=1;i<=n;i++)
    if(dis[i]>da)
      da=dis[i],l=i;
  spfa(l);da=-inf;
  for(int i=1;i<=n;i++)
    {
      maxdis[i]=dis[i];
      if(dis[i]>da)
        da=dis[i],r=i;
    }
  spfa(r);da=-inf;
  for(int i=1;i<=n;i++)
    {
      if(dis[i]>maxdis[i])
        maxdis[i]=dis[i];
      if(maxdis[i]>da && ok[i])
        da=maxdis[i];
    }
  ans=sum-da;

题目评价

考查内容:树的直径,dfs/最短路

时间复杂度:O(n)

题目难度:$\bigstar \; \bigstar$

set

过题:2 / 20

题目大意

让你把[A,B]中所有数字按条件合并,合并条件为i, j 都是 一个比 P大的质数p的倍数,那么合并i, j所在的集合。其中(1 ≤ A ≤ B ≤ 1012, B ≤ A + 106, 2 ≤ P ≤ B)

问题分析

由于A,B很大,我们从B ≤ A + 106这个关键条件入手。令N = B − A,那么N ≤ 106

则对于大于N的质数,那么[A, B]中至多有1个它的倍数,无需合并,于是我们只需要素数筛出106以内的素数,然后对于每个比P大的素数,去并查集合并[A, B]中所有他的倍数就行了。

具体实现

先筛质数,再枚举每个比P大的质数,去[A, B]找他们的倍数用并查集合并。

    for(long long i=ks;i<=p[0] && i<=B;i++)
    {
        long long st=A/p[i];
        if(st*p[i]<A)
            st++;
        for(long long j=st;p[i]*j<=B;j++)
        {
            x=find(p[i]*st-A+1);y=find(p[i]*j-A+1);
            if(x!=y)
                f[y]=x;
        }
    }
    for(long long i=A;i<=B;i++)
    if(find(i-A+1)==i-A+1)
        ans++;

每个质数找他们的倍数是N/p[i] ,那么N/p[ks]+N/p[ks + 1]+.....≤N/1 + N/2 + N/3 + ...N/N,由调和级数的求和可知复杂度上限位O(NlnN)

题目评价

考查内容:质数筛法和并查集

时间复杂度:O(NlnN)

题目难度:$\bigstar \; \bigstar$

Z's Lego

过题:2 / 5

题目大意

给出一个排列{1,2,...,n},问其中有多少个满足先上升后下降交替。

问题分析

对于一个排列{1,2,3,...,n},我们从中取{a1 < a2 > a3 < ... ak}, {b1 < b2 > b3 < ... bn-k }

那么 {ak ... > a3 < a2 > a1 < n+1 > b1 < b2 > b3 < ... bn-k }是一个升降(降升)交替的序列,

分析可知,先上升后下降与先下降后上升是一一对应的,数量相同

故可以得到如下状态转移方程,

$F(n+1)=\dfrac{1}{2} \sum\limits_{k= 0}^n C_n^k F(k)F(n-k)$

初值F(0) = F(1) = F(2) = 1

具体实现

首先预处理组合数,然后再根据上述状态转移方程,求出10000之内的结果,对于询问O(1)回答即可。

题目评价

考查内容:动态规划,递推,组合数

时间复杂度:O(n2)

题目难度:$\bigstar \; \bigstar \; \bigstar$