xzm2019

北京理工大学第七届程序设计新生赛 题解(unofficial)
一直不敢写这场比赛的题解,感觉写的心痛 ::aru:shy:: 也许是因为早上一直忙着帮忙布置场地,比赛状态挺差的...
扫描右侧二维码阅读全文
12
2019/02

北京理工大学第七届程序设计新生赛 题解(unofficial)

一直不敢写这场比赛的题解,感觉写的心痛 也许是因为早上一直忙着帮忙布置场地,比赛状态挺差的,很多傻逼题在那里犯着傻逼错误,最终怼题怼的也开心。那还是写写自己对这些题的看法吧

SolvedABCDEFGHIJKLM
8/13ØO.OØOOØØOOOO
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

Problem A 自然语言处理 (Unsolved with 13 tries)

$T(T \leq 100)$组数据,每组数据给你$n(1 \leq n \leq 10)$个$m(1 \leq m \leq 4)$维向量,请判断他们是否线性相关。

哎呦我的妈啊……每年新生赛必考线代题,可啥是线性相关来着啊,真的不知道了啊(还好发了clarification告诉了我们一下),可我还是不记得怎么判啊,就记得应该高斯消元,从开场想抢一血写到终场,一直WA上天。

首先当向量组所含向量的个数多于向量的维数时,该向量组一定线性相关(强势怀疑自己没判这个导致WA上天),剩下的使用高斯消元找非零解。

#include <bits/stdc++.h>
using namespace std;

const int maxn=505;
const double eps=1e-8;
double A[maxn<<1][maxn],x[maxn];
int n,m;
int Guass(int n,int m)
{
    int i=1,j=1,k,r,c;
    while(i<=m && j<=n)
    {
        r=i;
        for(k=i+1;k<=m;k++)if(fabs(A[k][j])>fabs(A[r][j]))r=k;
        if(fabs(A[r][j])>=eps)
        {
            for(c=1;c<=n+1;c++)swap(A[i][c],A[r][c]);
            for(k=i+1;k<=m;k++)if(fabs(A[k][j])>=eps)
            {
                double f=A[k][j]/A[i][j];
                for(c=j;c<=n+1;c++)
                    A[k][c]-=f*A[i][c];
            }
            i++;
        }
        j++;
    }
    for(k=i;k<=m;k++)if(fabs(A[k][n+1])>=eps)return 0;
    if(i<=n)return 2;
    for(int i=n;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[i][j]*x[j];
        x[i]=A[i][n+1]/A[i][i];
    }
    return 1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        memset(A,0,sizeof(A));
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
                scanf("%lf",&A[j][i]);
        }
        if (n>m)
        {
            printf("YES\n"); continue;
        }
        m++;
        A[m][1]=1; A[m][n+1]=1;
        if (Guass(n,m)>=1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

高斯消元的板子可以在百度里查到,这里使用的是这个


Problem B The Secret of Time (Solved at 0:25 with 1 try)

要求找出一个八位数,使得他平方以后满足 x7x1 x8x0 x6x2 x9x1,其中$x$代表任意数字

本地for循环暴力找,找到答案以后print提交,满足条件的答案应该有两个,任选其一即可。


Problem C Lytchen loves JSON (Unattempted)

你需要编写一个程序,这个程序以一个合法的JSON文档作为输入,然后响应一系列查询。每个查询均会要求查询在这个JSON文档所包含的对象图上的一个值。

如果你们谁对大模拟感兴趣可以自己在这里补这个题,我是没什么可说的


Problem D 元素周期表 (Solved at 2:13 with 1 try)

$T(1 \leq T \leq 200)$组数据,每组数据给你一个长度小于1000分子式(分子式只包含元素和元素个数,没有括号、前导数字、点等),请求出它的相对分子质量。题目给出了一张元素周期表的图片。

其实我只有一句话想说,哪个出题人这么狠。

明显这题使用map存储每个元素的相对原子质量比较方便,但是敲起来会有些费劲,不过由于化学元素的首字母均为大写,所以比较好做判断,一个个字符读入即可。


Problem E 龙语魔法 (Unattempted)

给一个长度为$n(n \leq 10^5)$的每个数在$10^9$以内的序列,求第$k(1 \leq k \leq \frac{n(n+1)}{2})$小的区间和。

赛时看出来了这个是二分答案(甚至觉得这是个原题),可是在那里怼高斯消元就一直咕咕咕,咕到了比赛结束(

明显二分答案即可,对于每一个答案,统计区间和小于他的个数。统计的时候使用双指针的思路进行即可。

时间复杂度:$O(n \log{\sum{a_i}})$

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;
long long k,all;
int check(long long x)
{
    long long tmp1=0,tmp2=0,now=a[1];
    int l=0,r=1;
    while (l<=r&&r<=n)
    {
        if (now>=x)
        {
            if (now==x) tmp2++; else tmp1++;
            tmp1+=n-r;
            l++; now-=a[l];
        }
        else {r++; now+=a[r];}
    }
    if (all-tmp1-tmp2<k&&all-tmp1>=k) return 0;
    if (all-tmp1-tmp2>=k) return 1;
    else return -1;
}
int main()
{
    scanf("%d%lld",&n,&k);
    long long sum=0;
    all=1LL*n*(n+1)/2;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) sum+=a[i];
    long long l=1,r=sum;
    while (l<=r)
    {
        long long mid=(l+r)/2;
        int flag=check(mid);
        if (flag==0) return printf("%lld\n",mid),0;
        if (flag==1) r=mid-1;
        else l=mid+1;
    }
    return 0;
}

Problem F 浴缸 (Solved at 0:37 with 3 tries)

给出浴缸每个点的深度,问注入$n$升水以后从浴缸顶部到水面的距离有多长(保证答案是整数)。

简单的一个前缀和处理,求出每个距离要的水的总量,一开始看错了题WA了两发,后来数据出锅RE了两发然后rejudge了


Problem G 伙伴系统 (Solved at 1:48 with 2 tries)

$k(k \leq 10^5)$次操作,每次操作获得一块内存或者请求划分内存。内存要划分成二的次幂的内存块。每次划分不能把小的拼接,只能从大的再划分。

其实是一个很简单的二进制处理问题,划分内存,找到最接近他的二的次幂的数划分然后删去他需要的内存块即可。只需要每个数求二进制即可。


Problem H 白学串 (Unattempted)

给一个长度为$n(n \leq 10^5,\sum{n} leq 5*10^5)$的序列,每个数小于$10^8$,$m(m \leq 2*10^6, \sum{m} \leq 10^6)$组查询,每次询问一个区间是否存在三个数可以构成三角形。

赛时没想到斐波拉契速度增长,然后就不会了。现在想想,不能组成三角形的最极限情况就是斐波拉契数列,而这个数列增长很快,到40项就可以超过$10^8$,因此,可以粗略的判断,如果区间过长,直接答案是yes。否则对区间排序,如果最大的三个数能构成三角形,就是yes,反之为no

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        while (m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if (r-l+1>=40) {printf("yes\n"); continue;}
            vector<int> tmp;
            for (int i=l;i<=r;i++)
                tmp.emplace_back(a[i]);
            sort(tmp.begin(),tmp.end());
            bool flag=false;
            for (int i=0;i<(int)tmp.size()-2;i++)
                if (tmp[i]+tmp[i+1]>tmp[i+2])
                {
                    flag=true; break;
                }
            if (flag) printf("yes\n"); else printf("no\n");
        }
    }
    return 0;
}

Problem I Integer Factorization (Unattempted)

$a=(p*q)\ xor\ (p+q),b=(p*q)\ xor\ (p-q)$,$T(T \leq 3000)$组数据,给出$a,b(-2^{63} \leq a,b \leq 2^{63})$,求均为质数的$p,q$。

知道是按位去算,本来后期想莽一莽,但是思路不清晰,而且对于负数不知道怎么考虑,就放弃了。当时想到的是cf上的1088D,下面附上出题人在知乎上发的题解:

然后再说一下I题,它其实来源于今年中科大举办的hakergame2018(对是ctf),几乎就是原题了,连题面背景都差不多,当然原题要算1024位的$pq$,为了不让你们算高精度把$pq$砍到了32位,但是核心的想法(和坑点)都没有变。
加,乘,异或三个操作都有一个特性,高位不会影响低位,所以可以从低到高按位搜索。如果有$a+b=c$,那么就有$(a\%2+b\%2)\%2=c\%2,\%4,\%8$等也依然成立,所以可以先枚举$pq$的最低位,再合法解的基础上再枚举下一位,其实就是一个搜索。因为每次枚举都会有$00,01,10,11$四个结果,又有两个式子进行剪枝,所以它并不会指数爆炸,按照数学期望应该算个线性的复杂度。
坑点在减法,由于不保证$p>q$所以$p-q$可能是负数,负数遇到模运算会出现很炸裂的情况,所以正确的方法是把$\%2,\%4$换成$\&(2^1-1),\&(2^2-1)$。具体推理在这里不过多的解释了,大家可以验证一下。
作者:匿名用户
链接:https://www.zhihu.com/question/307440139/answer/563059887
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

当然也可以参照原题这个题解

好吧,刚才补了下没想象中的那么难剪枝,直接按位枚举就可以了,一开始TLE了是因为用的set不是vector,后来仔细想想根本不会重复的。

#include <bits/stdc++.h>
using namespace std;

inline long long f1(long long p,long long q)
{
    return (p*q)^(p+q);
}
inline long long f2(long long p,long long q)
{
    return (p*q)^(p-q);
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        vector<pair<long long,long long>> ans,tmp;
        ans.emplace_back(0,0);
        for (int i=0;i<64;i++)
        {
            long long base=(2LL<<i)-1;
            bool flag=false;
            tmp.clear();
            for (auto &p: ans)
            {
                long long tx=p.first,ty=p.second;
                if (f1(tx,ty)==a&&f2(tx,ty)==b)
                {
                    printf("%lld %lld\n",tx,ty);  flag=true; break;
                }
                for (long long x=0;x<=1;x++)
                    for (long long y=0;y<=1;y++)
                    {
                        long long nx=tx+(x<<i),ny=ty+(y<<i);
                        if ((f1(nx,ny)&base)!=(a&base)) continue;
                        if ((f2(nx,ny)&base)!=(b&base)) continue;
                        tmp.emplace_back(nx,ny);
                    }
            }
            if (flag) break;
            ans=tmp;
        }
    }
    return 0;
}

Problem J 机房的圣诞礼物 (Solved at 0:20 with 1try)

一个人拿礼物拿了编号为$x$的就不能拿$2x$的了,求他拿的礼物的编号和的最大值。

虽然不会证,但感觉就是贪心,从大往小,选了$x$,就不选$x/2$。


Problem K X-Window System (Solved at 3:41 with 3 tries)

模拟窗口点击,求每次需要重绘的屏幕面积。坐标范围最大$2000*2000$。

按照题意模拟即可,因为坐标范围很小,可以直接开一个int数组记录每个点当前最顶端窗口。小模拟题,而我一开始找了想了半天矩形交怎么写


Problem L Bonus Quiz (Solved at 4:13 with 2 tries)

$1-n(n \leq 10^6)$中有$m$个中奖号码,每次选择一个区间,区间里正好含有$k$个中奖号码的时候记为中奖,求中奖的期望。

首先总区间数是确定的$\frac{n(n+1)}{2}$,而可中奖方案数的记录可以先把中奖号码排序,然后考虑长度为$k$的连续区间,可以向左右两边分别延伸到下一个中奖号码前面。

注意特判$k=0$的情况。


Problem M 长安街的华灯 (Solved at 1:25 with 5 tries)

$N(0 \leq N \leq 10^9)$个半径为$R(0 \leq R \leq 10^9)$的圆,圆心距为$L(0 \leq L \leq 10^9)$,求总覆盖面积。

首先对于$L \geq 2R$的情况,可以直接判断,总面积等于$N$的圆的面积之和。

否则,如图所示

无标题.png

重叠的面积等于圆弧的面积减去三角形的面积的二倍,圆弧的面积可以通过$S=\frac{\alpha}{2}r^2$计算,三角形的面积可以通过正弦定理$S=ab\ sin\alpha$计算,角度可以通过反三角函数和计算。

注意特判$N=0,L=0,R=0$的情况(出题人挖的坑真多)

Last modification:February 13th, 2019 at 10:14 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment