绝渡逢舟模拟赛 Ⅰ

2016.01.14 19:36 Thu| 60 visits oi_2016| 2016_竞赛日常| Text

暴走的图灵机

题目描述

所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

一种最朴素的图灵机只有 0 和 1,一种高度抽象的图灵机初始的内部状态是这样表示的:“我的左手是字符串 “0”,右手是字符串“1”。之后图灵机会进行 N 次操作,每次操作之后,图灵机的左手将会变成操作前右手的字符串,而图灵机的右手将会变成操作前左右手从左至右链接起来的字符串。

人类对一个高度抽象的图灵机是否满意取决于图灵机的 N 次操作后,左手的字符串包含多少个已知子串 T。为了简化问题,你只需计算这种图灵机 N 次操作后所包含的 T 串个数除以 P 的余数。

输入格式

第一行有三个正整数 N、M、P,N、P 如题中所述,M 表示串 T 的长度。

第二行为一个长度为 M 的 01 串 T。

输出格式

仅包含一个整数,表示答案除以 P 的余数。

样例输入

7 3 100
101

样例输出

8

数据范围和注释

对于30%的数据,N≤20。

对于60%的数据,N≤10^5,M≤200。

对于100%的数据,N≤10^9,M≤10000,P≤10^9。

奇妙的数列

题目描述

传说古希腊毕达哥拉斯(约公元前570-约公元前 500 年)学派的数学家经常在沙滩上研究数学问题,他们在沙滩上画点或用小石子来表示数。比如,他们研究过三角形点阵表示,

1,3,6,10,15,21...,他们就将其称为三角形数。

类似地,1,4,9,16,25,36...被称为正方形数,因为这些数能够表示成正方形。因此,按照一定顺序排列的一列数称为数列。

相传,瑞士数学家、自然科学家莱昂哈德·欧拉也研究过一种奇妙的有穷数列 A,它是由另一个有穷数列 B 导出的。数列 A 性质奇特,虽然每一项与相邻几项并无直接关系,但是若将数列 A 整体看来,却与 B 有着宏观上的近似之处。它具体表现为 an=n-k+1,其中 k 为最小的正整数使得数列 B 中,对于所有 k<=i<=n 的 i 均满足bk<=bi<=bn。我们并不关心欧拉是如何逐项计算 A 的,但我们颇感兴趣的问题是 A 中的最大值是多少。

输入格式

第一行为一个正整数 N 表示已知的数列 B 共有 N 项。第二行有 N 个数依次表示b1,b2,b3,b4,...,bn。

输出格式

仅包含一个整数,表示数列 A 中的最大值。

样例输入

9
2 1 6 5 4 2 7 2 2

样例输出

6

数据范围和注释

对于20%的数据,N≤5000。

对于50%的数据,N≤10^5。

对于100%的数据,N≤10^7。

对于30%为随机数列。

提示:由于输入数据过大,请注意读入优化。

染色配对

题目描述

图匹配是图论(Graph Theory)研究的重要方向之一。当前研究较为完善的是对二分图这一特殊模型计算其极大匹配(Maximal Matching),所用的通常是匈牙利算法(Hungarian Algorithm)或网络流(Maximal Flow)。而对于一般图的极大匹配目前研究较为完善的有带花树算法又称埃德蒙通用匹配算法(Edmonds’s matching algorithm),其时间复杂度与匈牙利算法同样是O(VE)。

图匹配研究过程中,有学者指出对于具有特殊性质的一般图匹配问题会有更加低的时间复杂度求出极大匹配。如染色匹配问题(Dyed matching problem),其表现为图中的每个结点均恰好属于两个极大团(每个极大团之内的结点两两均有边联结,且极大团不被任何一个除自己本身之外的团所包含),以上性质称为图的可染色性。

我们的目标就是计算一个具有染色性质的图的极大匹配并提供匹配方案。

输入格式

第一行为两个正整数M,N,表示共有M个极大团,图中共有N个结点。

接下来N行,每行有2个整数a,b,依次表示每个结点所属的两个极大团的编号为a,b(保证 a≠b且a,b≤M),结点编号从1开始。

输出格式

第一行输出极大匹配个数K,接下来输出一个合法的匹配方案,共K行,每行两个正整数a,b 表示每组匹配结点的编号。

样例输入

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6

样例输出

5
1 2
5 7
6 8
3 9
4 10

数据范围和注释

对于20%的数据,N,M≤10。

对于40%的数据,M≤100,N≤1000。

对于60%的数据,M≤1000,N≤10000。

对于100%的数据,M≤20000,N≤200000。

题解(伪)

暴走的图灵机

设 s[n] 表示操作 n 次之后,图灵机左手中的字符串,f[n] 表示 T 串在 s[n] 中的出现次数。发现我们总有 s[n] = s[n - 2] + s[n - 3] + s[n - 2]。当 n 比较大的时候,有 f[n] = f[n - 2] * 2 + f[n - 3] + t,其中 t 为常数,即在合并两个串的时候,在接缝处出现的答案。这样,在 n 较小的时候暴力求解,较大时使用矩阵乘法优化递推即可。

考场上,我观察字符串,发现 s[n] 和 s[n - 1] - s[n - 3] + s[n - 1] 只在前两位有区别,即若 s[n] = "01....",s[n - 1] - s[n - 3] + s[n - 1] 即为 "10...",反之亦然。

于是竟然得到了一个奇怪的方程:f[n] = f[n - 1] * 2 - f[n - 3] + t,其中 t 有可能为 0,也有可能是 1 与 -1 交替出现。这样的方程真是足够鬼畜,然而果然是正确的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

int n, m, p;
long long f[25];
string s[2], t;

struct matrix
{
    long long t[4][4];
    matrix() { memset(t, 0, sizeof t); }
    friend matrix operator *(matrix a, matrix b)
    {
        matrix re;
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j)
                for (int k = 0; k < 4; ++k)
                    re.t[i][j] = (re.t[i][j] + a.t[i][k] * b.t[k][j]) % p;
        return re;
    }
    friend matrix pow(matrix a, int b)
    {
        matrix re;
        for (int i = 0; i < 4; ++i)
            re.t[i][i] = 1;
        while (b)
        {
            if (b & 1) re = re * a;
            a = a * a, b >>= 1;
        }
        return re;
    }
} a, b;

int main()
{
    freopen("bugs.in", "r", stdin);
    freopen("bugs.out", "w", stdout);
    cin >> n >> m >> p >> t;
    s[0] = "0"; s[1] = "1";
    if (t == "0") f[0] = 1;
    for (int i = 1; i <= 24; ++i)
    {
        swap(s[0], s[1]), s[1] += s[0];
        for (int j = 0; j + m <= (int)s[0].size(); ++j)
            for (int k = 0; k <= m; ++k)
                if (k == m) ++f[i];
                else if (t[k] != s[0][j + k]) break;
    }
    if (n <= 24) { cout << f[n] % p << endl; return 0; }
    a.t[0][0] = f[24] % p, a.t[0][1] = f[23] % p, a.t[0][2] = f[22] % p;
    a.t[0][3] = (f[24] - 2 * f[22] - f[21]) % p;
    b.t[0][1] = 1, b.t[1][0] = 2, b.t[1][2] = 1;
    b.t[2][0] = 1, b.t[3][0] = 1, b.t[3][3] = 1;
    cout << (a * pow(b, n - 24)).t[0][0] << endl;
    return 0;
}

奇妙的数列

cena 测评神卡 STL 我给 100 个差评!

维护两个单调栈,其中一个中的元素单调递增,另一个中元素单调递减。依次扫描数组,找到第二个栈中比第一个栈里最后的元素的下标大的坐标最小的元素,之后更新栈。其实这题挺简单的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

int n, a[10000005], ans;
stack<int> s1, s2;

char getc()
{
    static const int LEN = 1 << 15;
    static char buf[LEN], *S = buf, *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf, 1, LEN, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}

inline int read()
{
    static char ch;
    static int D;
    while (!isdigit(ch = getc()));
    for (D = ch - '0'; isdigit(ch = getc());)
        D = (D << 3) + (D << 1) + (ch - '0');
    return D;
}

int main()
{
    freopen("array.in", "r", stdin);
    freopen("array.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    s1.push(0), s2.push(0);
    for (int t, i = 1; i <= n; ++i)
    {
        while (s1.size() > 1 && a[s1.top()] <= a[i]) s1.pop();
        while (a[i] < a[s2.top()]) s2.pop(); s2.push(i);
        while (s2.top() > s1.top()) t = s2.top(), s2.pop();
        s2.push(t);
        ans = max(ans, i - s2.top() + 1), s1.push(i);
    }
    cout << ans << endl;
    return 0;
}

染色配对

带花树建完全图裸跑 ** 有 60 分啊!

正解是点边转化(其实在样例里面已经提示得很明显了)。对于每一个连通块找到一棵生成树,对于非树边可以随意确定让它关于哪个端点去进行匹配,而我们可以通过调整树边的归属使得最终匹配的个数等于连通块中边的个数除以二再下取整,输出方案也很简单。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

#define N 20005

int n, m, head[N], vis[N];
vector<int> v[N];
vector<pair<int, int> > ans;

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[400005];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x, int fa, int fe)
{
    vis[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (vis[edge[i].to] && edge[i].val != fe)
            v[edge[i].to].push_back(edge[i].val);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            dfs(edge[i].to, x, edge[i].val);
    if (v[x].size() % 2 == 0) v[fa].push_back(fe);
    else v[x].push_back(fe);
    for (int i = 0; i < (int)v[x].size(); i += 2)
        if (v[x][i] && v[x][i + 1])
            ans.push_back(make_pair(v[x][i], v[x][i + 1]));
}

int main()
{
    freopen("pair.in", "r", stdin);
    freopen("pair.out", "w", stdout);
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
        scanf("%d%d", &x, &y), add(x, y, i), add(y, x, i);
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i, 0, 0);
    cout << ans.size() << endl;
    for (int i = 0; i <(int)ans.size(); ++i)
        cout << ans[i].first << ' ' << ans[i].second << endl;
    return 0;
}