9.22模拟赛解题报告

attack

发布于 2018-09-30 09:55:45

2690

发布于 2018-09-30 09:55:45

文章被收录于专栏：数据结构与算法

心路历程

预计得分：$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，设$gi$分别表示以$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
*/