9.22模拟赛解题报告

心路历程

预计得分:$100+100+20 = 220$

实际得分:$100+85+20 = 205$

T2车祸现场:

%……&*…&*(%¥……&

幸好翻的还不算太惨。。。。

T1傻逼题。。。。然而期间翻了无数次车,做完就快过去1h了。。

T2读题就花了半个小时,而且一开始没认真理解题目的意思,前后各dp了一遍,后来仔细揣摩了一下题意,细心品味了一下出题人的语言,正着的dp好像是没用的。。。

做到T3的时候就两个多小时过去了,这个节奏打着确实挺难受的,因为一般我都是1.5h的时候开T3。。

做T3的时候。。。。我就不说啥了,可能是这几天夜熬多了吧,整个脑子里全是空白的,列出dp方程来却根本不知道要干什么,当时就是一种人脑分离的状态。

然后打了打暴力就走人了。。

总之感觉这场比赛打的确实烂,整个人都不在状态。T1明明一行代码就能解决我却楞要分四种情况讨论,T2一个普及dp调了1h。。T3应该还能多拿20Point但是调完暴力就过去了3h....

Sol

A

这题是我验的题。。。

当时我还和mjt吹什么这题很zz啊分四种情况讨论一下就好了啊然后mjt满意的笑笑觉得够毒瘤了就出了然而没想到被全机房的同学一行代码艹翻,std据说还是什么nb旋转坐标系实际上只需要输出坐标绝对值的较大值就行了。。

#include<cstdio>
#include<algorithm>
#include<iostream>
#define int long long 
using namespace std;
const int INF = 1e18 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, sx, sy, ex, ey;
main() {
    freopen("grid.in", "r", stdin);
    freopen("grid.out", "w", stdout); 
    N = read(); sx = read(); sy = read(); ex = read(); ey = read();
    cout << max(abs(ex - sx), abs(ey - sy));
    return 0;
}
/*
8 2 3 7 5
5

4
1 1 2 2
1

4
1 1 2 3
2

10 2 4 3 10

10 1 1 1 1
*/

B

神仙阅读理解题。。。。。

首先不难想到我们枚举一个位置$i$,分别判断$S(i, i+1)$和$S(i, i+1, i+2)$是否合法。

考虑到基础串可以任意长,因此该位置的前面是不用考虑的,只需要考虑后面是否合法即可

直接dp,设$g[i][0/1]$分别表示以$i$为起点的后缀中,把前$2/3$个字母划分到一块,整个后缀是否合法。

然后枚举一遍就行了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
//#define int long long 
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, T, opt, f[MAXN], g[MAXN][2];
char s[MAXN];
vector<string> ans;
map<string, bool> mp;
void get2() {
    for(int i = N - 1; i >= 4; i--) {
        int r = (N - (i + 1));
        if(r == 1) continue;
        if((opt == 0 && g[i][0]) || (opt != 0)) 
            ans.push_back(string(s + i, s + i + 2));
    }
}
void get3() {
    for(int i = N - 2; i >= 4; i--) {
        int r = (N - (i + 2));
        if(r == 1) continue;
        if((opt == 0 && g[i][1]) || (opt != 0)) 
            ans.push_back(string(s + i, s + i + 3));
    }
}
void pre() {
    g[N - 1][0] = 1;//0:末尾长度为2
    g[N - 2][1] = 1;//1: 末尾长度为3 
    for(int i = N - 3; i >= 4; i--) {
        
        if((s[i] != s[i + 2]) || (s[i + 1] != s[i + 3])) g[i][0] = g[i + 2][0];
        g[i][0] |= g[i + 2][1];
        
        if((s[i] != s[i + 3]) || (s[i + 1] != s[i + 4]) || (s[i + 2] != s[i + 5])) g[i][1] = g[i + 3][1];
        g[i][1] |= g[i + 3][0];
        
    }
}
main() {
    freopen("ling.in", "r", stdin);
    freopen("ling.out", "w", stdout);
    T = read(); opt = read();
    while(T--) {
        ans.clear();
        mp.clear();
        memset(g, 0, sizeof(g));
        scanf("%s", s + 1);
        N = strlen(s + 1);
        pre();
        get2();
        get3();
        sort(ans.begin(), ans.end());
        int num = 0;
        for(int i = 0; i < ans.size(); i++) {
            if(i == 0 || (ans[i] != ans[i - 1])) num++;
        }
        cout << num << endl;
        for(int i = 0; i < ans.size(); i++) {
            if(mp.find(ans[i]) == mp.end()) {
                mp[ans[i]] = 1;
                cout << ans[i] << endl;
            }
        }
    }
    return 0;
}
/*
2 0
abc
aaaaaa
*/

C

https://www.cnblogs.com/zwfymqz/p/9690449.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

动态规划中篇:爬楼梯

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

4099
来自专栏老九学堂

程序员揭秘:火爆朋友圈的左右脑年龄测试,真相只是一个随机函数!

最近,老九的朋友圈已经被左右脑测试刷爆了,老九也去测试了一下,只需要进入相应入口并回答几个设定的问题后,就会出现左右脑两个年龄测试结果。 ? 有不少小伙伴晒出自...

3836
来自专栏小樱的经验随笔

CTF---密码学入门第三题 奇怪的短信

奇怪的短信分值:10 来源: Ayn 难度:易 参与人数:5117人 Get Flag:2623人 答题人数:2858人 解题通过率:92% 收到一条奇怪的...

4056
来自专栏TensorFlow从0到N

讨厌算法的程序员 4 - 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

3143
来自专栏编程一生

一条项目中常用的linux命令引发的经典算法题

1243
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第四章 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

2918
来自专栏racaljk

当我们谈论计算机科学

下午偶有所悟,特作此文防止青年痴呆。 这学期的学习算是走了一半计算机科学概论。广度的学习通常会被指责为广而不精,但对我而言这是毫无意义的,因为 ...

1054
来自专栏精讲JAVA

十年之后再看“面向对象”

一起帮里有人问“面向对象”的问题。但我创建“一起帮”的目的是帮人解决“具体的”“实务性的”问题,“面向对象”太过于抽象,所以没批准发布。后来在QQ群里讨论,看他...

1906
来自专栏好好学java的技术栈

“365算法每日学计划”:01打卡

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

2803
来自专栏数据派THU

一文读懂PyTorch张量基础(附代码)

本文介绍了PyTorch Tensor最基础的知识以及如何跟Numpy的ndarray互相转换。

1073

扫码关注云+社区

领取腾讯云代金券