ChangKe's Blog

20160409模拟测试

不知道老师从哪里找的题,很水的样子,2hAK,虐标程0.5s。

题1.单词公共子串(pow)

问题描述

有一个单词序列,单词中的字母来自字母表。编程求所有单词中最长的公共部分。

任务

从文本文件pow.in中读入单词序列,计算在每一个单词中都出现的最长子串长度,将结果写入文本文件pow.out中。

输入格式

在输入文件pow.in的第一行有一个整数,表示单词个数。下面的行,每行有一个由小些英文字符组成的单词。每个单词的长度最少为,最大不超过

输出格式

在文本文件pow.out中只有一个整数,为包含在每个单词的公共子串的最大长度。

样例输入

3
abcb
bca
acbc

样例输出

2

题解

这也要题解?后缀数组裸题啊。详见国家集训队论文《后缀数组——处理字符串的有力工具》,作者罗穗骞。

#include <cstdio>
#include <cstring>
char str[5][3000], s[20000];
int f[5], t[5], cnt[5];
int sa[20000], rank[20000];
int height[20000];
int n, len;
int Wa[20000], Wb[20000];
int Ws[20000], Wv[20000];
bool cmp(int *r,int a, int b, int l)
{
    return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void getsa()
{
    int *x = Wa, *y = Wb;
    int i, j, p, *t;
    int m = 127;
    for (i = 0; i < m; i++)
        Ws[i] = 0;
    for (i = 0; i < len; i++)
        Ws[x[i] = s[i]]++;
    for (i = 1; i < m; i++)
        Ws[i] += Ws[i - 1];
    for (i = len - 1; i >= 0; i--)
        sa[--Ws[x[i]]] = i;
    for (j = 1, p = 1; p < len; j *= 2, m = p)
    {
        for (p = 0,i = len - j; i < len; i++)
            y[p++] = i;
        for (i = 0; i < len; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;
        for (i = 0; i < len; i++)
            Wv[i] = x[y[i]];
        for (i = 0; i < m; i++)
            Ws[i] = 0;
        for (i = 0; i < len; i++)
            Ws[Wv[i]]++;
        for (i = 1; i < m; i++)
            Ws[i] += Ws[i - 1];
        for (i = len - 1; i >= 0; i--)
            sa[--Ws[Wv[i]]] = y[i];
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < len; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
}
void getheight()
{
    int i, j, k = 0;
    for (i = 1; i < len; i++)
        rank[sa[i]] = i;
    for (i = 0; i < len - 1; height[rank[i++]] = k)
        for (k ? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++);
}
bool check(int d)
{    
    for (int i = 0; i < len; )
    {
        memset(cnt, 0, sizeof(cnt));
        int j = i + 1;
        while (j < len && height[j] >= d)
            j++;
        for (int k = i; k < j; k++)
        {
            int l;
            for (l = 0; l < n; l++)
                if (sa[k] >= f[l] && sa[k] <= t[l])
                    break;
            if (l < n)
                cnt[l]++;
        }
        int l;
        for (l = 0; l < n; l++)
            if (!cnt[l])
                break;
        if (l == n)
            return true;
        else
            i = j;
    }
    return false;
}
int main()
{
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", &str[i]);
        f[i] = strlen(s);
        t[i] = f[i] + strlen(str[i]) - 1;
        strcat(s, str[i]);
        s[strlen(s)] = '$' + i;
    }
    len = strlen(s);
    getsa();
    getheight();
    int l = 0, r = len - 1;
    while (l < r - 1)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    if (check(r))
        printf("%d\n", r);
    else
        printf("%d\n", l);
    return 0;
}

题2.M序列(mseq)

问题描述

有一个非递减的整数序列。定义序列的“序列”,其中
例如,,则
现在给你序列,要你求有多少个序列的“序列”是序列

输入格式

第一行一个整数,下接行,每行一个整数

输出格式

一个整数,表示有多少个序列的“序列”是序列

样例输入

3
2
5
9

样例输出

4

样例说明

存在如下四个数列满足要求:



数据范围

的数据
的数据

题解

算法一

首先,我们可以发现,如果是已知的,那么结合序列,整个数组就确定了。因此,我们可以直接枚举,然后计算出整个序列,并判断是否是递增的。
时间复杂度,期望得分50分。

算法二

枚举太浪费了!我们把智商稍微拉高一点,直接用字母表示数。
比如,我们有了,那么
总结一下,

然后,我们可以根据这些表示,推出数列递增对应的不等式。具体来说,我们用上面的式子表示出来,然后解不等式,取所有不等式解集的交集后,计算里面的整数个数。
事实上,这些不等式的形式都是相当简单的,解集的左右端点也都是整数。因此这题实现并不困难,详见代码。
时间复杂度,期望得分100分。

#include <cstdio>
#include <algorithm>
#define INF 2000000000
using namespace std;
int c[100010];
int n;
int l, r;
int main()
{
    freopen("mseq.in", "r", stdin);
    freopen("mseq.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        c[i + 1] = 2 * x - c[i];
    }
    l = -INF, r = INF;
    for (int i = 1; i <= n; i++)
        if (i & 1)
            r = min(r, (c[i] - c[i - 1]) / 2);
        else
            l = max(l, (c[i - 1] - c[i]) / 2);
    if (r >= l)
        printf("%d\n", r - l + 1);
    else
        printf("0\n");
    return 0;
}

题3.竞技比赛(bnb)

问题描述

第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手二号选手号选手捉对厮杀,共进行场比赛。每胜一场比赛得分,平一场得分,输一场不得分。最终将双方的单场得分相加得出总分,总分高的队伍晋级(总分相同抽签决定)。
作为河南队的领队,你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,河南队最终分别能得到多少分。

输入格式

输入文件的第一行为一个整数,表示每支代表队的人数。
接下来行,每行一个整数,描述了位河南队的选手的实力值。
接下来行,每行一个整数,描述了你的对手的位选手的实力值。

输出格式

输出文件中包括两个用空格隔开的整数,分别表示河南队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

样例输入1

2
1
3
2
4

样例输出1

2 0

样例说明1

我们分别称位选手为。则可能出现以下种对战方式,最好情况下可得分,最坏情况下得分。

样例输入2

6
10000000
10000000
10000000
10000000
10000000
10000000
0
0
0
0
0
0

样例输出2

12 12

样例说明2

对手都是认真学习的好孩子,不会打游戏。无论如何排列出场顺序都无法改变被蹂躏的结果。河南队总能取得全胜的结果。

数据范围

的数据中,
的数据中,
的数据中,
的数据中,,且所有选手的实力值在之间。

题解

算法一

枚举所有排列,然后计算得分。
时间复杂度,期望得分20分。

算法二

我们可以抽象出二分图的模型。河南的选手作为左侧点,外省选手作为右侧点,如果河南队的某个选手能胜过外省的某个选手,那么在二者之间连接一条权为2的边,如果实力值相同则连权为1的边,同时为了存在完美匹配,在河南选手打不过外省选手时连权值为0的边。之后跑一遍KM求出最大权完美匹配,就是第一问的答案。第二问的话可以把所有边权取成相反数,然后是KM,最后用加上这时的最大权匹配的值(肯定不是正数)就是答案。
时间复杂度,也可以达到,但期望得分都是40分。

算法三

我们一个一个分析。对于河南省最弱的人,如果他可以打过外省最弱的人,那么就让他们打,这是最优的;对于河南省最强的人,如果他可以打过外省最强的人,那么就让他们打,这是最优的;如果两个条件都不成立,那么最弱的那个人无论如何都打不到分了,不妨利用“田忌赛马”的策略,让他和目前剩余的外省最强的人打。
不难证明,不存在比上述决策更优的决策,因此第一问可以直接输出结果。第二问的话,原理与算法二类似,将两支队伍交换,求出外省的最大得分就是最终答案。因为每一句无论结果,两方的得分总和都会,所以总分数一定,对方多,自己就少了。
时间复杂度:,期望得分100分。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int n;
int ha[100010], notha[100010]; 
inline int readint()
{
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    int x = c - '0';
    c = getchar();
    while (isdigit(c))
    {
        x = x * 10 + c -'0';
        c = getchar();
    }
    return x;
}
int main()
{
    freopen("bnb.in", "r", stdin);
    freopen("bnb.out", "w", stdout);
    n = readint();
    for (int i = 0; i < n; i++)
        ha[i] = readint();
    for (int i = 0; i < n; i++)
        notha[i] = readint();
    sort(ha, ha + n);
    sort(notha, notha + n);
    int l1 = 0, l2 = 0, r1 = n - 1, r2 = n - 1;
    int ans = 0;
    while (l1 <= r1)
    {
        if (ha[l1] > notha[l2])
        {
            l1++, l2++;
            ans += 2;
        }
        else if (ha[r1] > notha[r2])
        {
            r1--, r2--;
            ans += 2;
        }
        else
        {
            ans += (ha[l1] == notha[r2]);
            l1++, r2--;
        }
    }
    printf("%d ", ans);
    l1 = 0, l2 = 0, r1 = n - 1, r2 = n - 1;
    ans = 0;
    while (l1 <= r1)
    {
        if (notha[l1] > ha[l2])
        {
            l1++, l2++;
            ans += 2;
        }
        else if (notha[r1] > ha[r2])
        {
            r1--, r2--;
            ans += 2;
        }
        else
        {
            ans += (notha[l1] == ha[r2]);
            l1++, r2--;
        }
    }
    printf("%d\n", 2 * n - ans);
    return 0;
}