MJOI-(-1)2020年愚人节比赛赛后题解

tuxiaobei · 2020-04-04 23:38:23 · 个人记录

简单总结：参加的人还是挺多的，但是得分率太低了，可能是题目确实太毒瘤了一点（

T1 B

https://www.luogu.com.cn/problem/T128358

这道题最重要的线索是数据范围：

“B 是 1024 \times 1024 的倍数，1024 \times 1024 \le B \le 256 \times 1024 \times 1024”

而 1024 这个数在平时用得最多的地方就是描述计算机储存单位了。

GB,MB,KB,B等储存单位的进率是 1024.

而 256 这个数通常在空间限制中出现，并且你如果随便交一波程序会在最终出现MLE，提醒你注意空间。

所以，题目中B的意思是"Byte(字节)"

而题目中还给了一个提示“洛谷内存计算方式是按实际使用的内存计算，也就是说只定义数组/变量而不访问是不计入的”

推测输出B实际上指的是让你的程序此测试点占用内存大小为这么多B

由于程序本身运行占用需要占用一定内存，所以需要酌情减少一定的手动新增内存，一般 1\sim 1.5 MB 。

然后由于洛谷评测机波动，可能需要多提交几次即可。

实际上最终评测允许你的程序有 ±1MB 的误差。

注：long long占 8 字节。

#include <cstdio>
#include <cstring>
long long f[60000000];
signed main()
{
    long long b;
    scanf("%lld",&b);
    b-=1024*1024*1.5;
    memset(f,0x3f,sizeof(long long)*(b/8));
}

另：细心的大佬可能会注意到题目中原来是小写的b，不久都改成大写的B

b一般指的bit(比特)，1Byte=8bit。

所以用B是更严谨的。

T2 统计

https://www.luogu.com.cn/problem/T128360

这题码量稍大，（~~愚人节比赛哪有码量一说~~），但是是最不坑的，不知道为什么没人AC。

这题其实挺正常的，就是算一条回归直线。

直接套公式可以得到 20 分，

稍微想一想亲爱的老师在课上说过的话，“如果遇到明显偏离的点要舍去”。

所以我们需要舍去点。

我们可以先求一次所有点的回归直线，然后计算每个点的偏差量，如果偏差超过一定值就舍去。

最后第二次求回归直线。

实际上，数据中正常的点的偏差大约在 10\% 左右，而不正常的点在 80 \% 以上，所以给的判定范围是相当宽的。

最后一点是，4 月 4 日 10 时起，全国人民默哀 3 分钟，为表达全国各族人民对抗击新冠肺炎疫情斗争牺牲烈士和逝世同胞的深切哀悼。

所以 601 \sim 603 秒的数据是没有价值的，应该舍去，数据范围内 n \ge 5 也是一个提示，除去至多 3 个点后至少还有 2 个数据点，保证直线存在。

人民英雄永垂不朽！

#include <bits/stdc++.h>
#define maxn 888
using namespace std;
int x[maxn], y[maxn];
bool flag[maxn];
long long sumx, sumy;
long double a, b, c, d;
int tot;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        sumx += x[i], sumy += y[i];
    }
    long double barx = (long double)sumx / n;
    long double bary = (long double)sumy / n;
    for (int i = 1; i <= n; i++) {
        c += (x[i] - barx) * (y[i] - bary);
        d += (x[i] - barx) * (x[i] - barx);
    }
    b = c / d;
    a = bary - b * barx;
    sumx = sumy = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i] >= 601 && x[i] <= 603) continue;
        double y_ = b * x[i] + a;
        if (fabs(y_ - y[i]) / y_ <= 0.5) {
            tot++;
            sumx += x[i], sumy += y[i];
            flag[i] = true;
        }
    }
    a = b = c = d = 0;
    barx = (long double)sumx / tot;
    bary = (long double)sumy / tot;
    for (int i = 1; i <= n; i++) {
        if (!flag[i]) continue;
        c += (x[i] - barx) * (y[i] - bary);
        d += (x[i] - barx) * (x[i] - barx);
    }
    b = c / d;
    a = bary - b * barx;
    printf("%.6Lf %.6Lf", a, b);
}

T3 玄学树

https://www.luogu.com.cn/problem/T128359

我们看到一种神奇的数：jiangly数！

进入附加文件，在众多数字的空隙中，有这样一些字：“对于产生jiangly数的操作，

用数列Z的某一项代替即可”

并且附加一个神秘网址“https://www.luogu.com.cn/blog/zhengenxi/”

进入后发现是ZEX博客，看见一些密文，这些密文加密方式为“第 i 个字母转化为26-i+1 个字母” （至于 1000+100+80+1=1181 表示FZOJ的1181题，就有我所说的加密方式）

加密完成后是一段英文，进行翻译后“对于数列Z的任意一项，都是相同的，他的值为A+B+C”

（X+Y+Z 解密转化为 A+B+C ）

A的值就是欧拉公式，e^πi+1+1=0

B的值是下面的密文“CQCSP-S最高成绩”529，答案是 530-529=1

C=A+B-1=0

A+B+C=1，所以“玄学树”产生的每个jiangly数，都是1

即：除了根节点其他都是1，SUM=W+N-1

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w;
    cin>>n>>w;
    cout<<n+w-1;
    return 0;
}
//根据代码长度进行分析，真香

T4 Fast Than PYB

https://www.luogu.com.cn/problem/T128361

(附加部分)https://www.luogu.com.cn/problem/T128362

这道题得分率不高，感觉挺可惜的，这里不讲正解，只给出一些解密思路，感兴趣的大佬可以继续找。

题目Fast Than PYB，是不是感觉怪怪的，其实关键的是它的首字母FTP
题目描述的一段密文是MD5加密，可以上网搜破解网站破解，解密后得到www.juruoyyx.fun（直接是无法访问的），通过端口扫描可以发现其开启了 21,22,88 等端口，21 端口就是FTP服务端口。
右键查看网页源代码，可以发现最后有一张图片，图片根网址www.juruoyyx.fun:88，有一串密文bddpvou;kjbohmz。建议通过PS等工具处理图片，另外图片用除图片查看器/编辑器以外的软件试试。
可以尝试获取上面域名的DNS解析记录，注意不要局限于最常用的A记录。
题目中www.luogu.com.cn/*/*在线索中使用了两次，一次是www.luogu.com.cn/record/*(很可能会用到)，另一次是www.luogu.com.cn/user/*(不一定会用到)