Summary3-26模拟赛 Summary

3-26模拟赛 Summary

Process

今天打的还可以。又是前两个小时一分没得,一直在想T1(这么简单我还想这么久肯定是太弱了)然后想细节+调试又搞了好久,于是最后只剩1h写最后两题的暴力,直接导致了T3中间40分部分分写错,而且还由于样例太水而没有查出来,于是60分的暴力就只剩下20分

Score

100 + 20 + 20 = 140
Rank 38

Problems

xiz

Description

给定字符串 S 和 T , 定义两个字符串匹配存在一个字符的映射,使得A应用这个映射之后等于B,且这个映射必须为一个排列, 求 S 的哪些连续子串与 T 匹配.
n, m, 字符集大小 ≤ 1000000.

Solution

记每个字符的前一个与当前字符相同的字符离自己的距离为 wi , 如果两个串的 w 数组相等, 则可以匹配. 预处理出 w 就可以用 KMP 了.
只是在KMP中的判断稍微改一下即可

Code

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1000000 + 100;
int S1[Maxn], S2[Maxn];
int Next[Maxn];
int N, M;

inline int judge1 (int x, int y)
{
    return S2[x] == max(0, S2[y] - (y - x));
}

inline int judge2 (int x, int y)
{
    return S2[x] == max(0, S1[y] - (y - x));
}

inline void Get_next()
{
    int j = 0;
    for (int i = 2; i <= M; ++i)
    {
        if (j > 0 && !judge1(j + 1, i)) j = Next[j];
        if (judge1(j + 1, i)) ++j;
        Next[i] = j;
    }
}

int Ans[Maxn];

inline void Kmp()
{
    int j = 0;
    for (int i = 1; i <= N; ++i)
    {
        while (j > 0 && !judge2(j + 1, i)) j = Next[j];
        if (judge2(j + 1, i)) ++j;
        if (j == M)
        {
            //cout<<i - M + 1<<endl;
            Ans[++Ans[0]] = i - M + 1;
            //j = 0;
            j = Next[j];
        }
    }
}

int S[Maxn], T[Maxn];
int Pos[Maxn];

inline void Init()
{
    memset(Pos, 0, sizeof Pos);
    for (int i = 1; i <= N; ++i) S1[i] = Pos[S[i]], Pos[S[i]] = i;
    memset(Pos, 0, sizeof Pos);
    for (int i = 1; i <= M; ++i) S2[i] = Pos[T[i]], Pos[T[i]] = i;
}

int main()
{
    freopen("xiz.in", "r", stdin);
    freopen("xiz.out", "w", stdout);

    int TT, C;
    scanf("%d%d", &TT, &C);
    while (TT--)
    {
        memset(Ans, 0, sizeof Ans);
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i)
            scanf("%d", &S[i]);
        for (int i = 1; i <= M; ++i)
            scanf("%d", &T[i]);
        Init();
        Get_next();
        Kmp();
        cout<<Ans[0]<<endl;
        for (int i = 1; i <= Ans[0]; ++i)
            printf("%d ", Ans[i]);
        puts("");
    }
    return 0;
}

yja

Description

在平面上找 n 个点, 要求这 n 个点离原点的距离分别为 r1 , r2 , …, rn . 最大化这 n 个点构成的凸包面积, 凸包上的点的顺序任意.
n<=8

Solution

不会。只会所有r都相等的部分分:答案显然一定为正多边形,那么直接用正弦定理将每个三角形的面积算出来再×n即可

zkb

Description

给定一个长度为 n 的正整数序列 a 1 …a n . 现在有 m 次操作, 分为两种:
• 1 l r t: 将区间 [l, r] 降序排序 (t = 0) 或升序排序 (t = 1)
• 2 l r: 询问区间 [l, r] 内元素之积的十进制下最高位

Solution

loj原题
正解是log10之后用线段树(Splay)套线段树做,还要分裂和合并
我的暴力是把每个数转化成小数,然后直接暴力乘,实测有60分。然而考场上sort的下标传错了导致只有20分的部分分
以后一定要注意一定先把暴力打完再去想正解

Categories: Summary Tags:

Comments

No Comments Yet. Be the first?

Post a comment