Zhao70's Blog

发表于 | 分类于

看了半天各种大手子解析， 也许是数学基础不好吧，熟练背诵吧。

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
#include <iostream>
using namespace std;
int exgcd(int a, int b, int& x, int& y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return r;
}
bool linear_equation(int a, int b, int c, int &x, int &y)
{
    int d = exgcd(a, b, x, y);
    if(c % d)
        return false;
    int k = c / d;
    x *= k; y *= k;
    return true;
}
int main(int argc, char const *argv[])
{
    int x, y;
    if(linear_equation(47, 30, 1, x, y))
        cout << x << " " << y << endl;
    return 0;
}

Zhao70's Blog

发表于 | 分类于

简介

想KMP这个算法的时间， 前前后后加起来能有48个小时吧。 学这种算法还是画画图实在啊， 空想是没有用的~

kmpSearch

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int kmpSearch(const string &s, const string &p)
{
    int i = 0;
    int j = 0;
    int sLen = s.length();
    int pLen = p.length();
    while(i < sLen && j < pLen)
    {
        if(j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j == pLen)
        return i - j;
    else
        return -1;
}

讲解

对于kmpSearch这个函数来讲， 思路是不难理解的。 不过此 i，j 的变化和边界是需要特别注意的。

  1. 可以将 i, j 理解为指针， 所谓的-1即为空指针。
  2. 当 j 的值为 -1 时， 说明 p 中已经没有可以匹配的前缀了。 所以 i, j分别自增 1。 i 指向下一个 s 中的字符。 j 指向 p[0].

  3. 跳出while循环的可能性:

    1. i 遍历 s 中所有元素
    2. j 遍历 p 中所有元素

    只有第 2 种情况说明字符串完全匹配。 返回值 i 中找到的字符串结尾 减去 字符串 p 的长度(即 j)。

getNextVal

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getNextVal(const string &p)
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    int pLen = p.length();
    while(j < pLen - 1)
    {
        if(k == -1 || p[k] == p[j])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

讲解

next数组可是kmp算法的精华啊， 最开始看next数组生成过程的时候，有一种很玄学的感觉。。。

next数组的含义

代表当前字符之前的字符串中，有多大长度的相同前缀后缀。
例如 如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

  1. k, j分别是指向相同前后缀最后一个字符的指针。
  2. 当 p[k] == p[j] 时，k，j 自增一。 因为 k 为指向前缀的指针， 即为前缀的长度， k 的大小即最长相同前后缀的长度
  3. 因为 j 的取值范围为[0, pLen - 1] 但 next 数组的含义为 “代表当前字符之前的字符串中，有多大长度的相同前缀后缀”, 所以判断到 p[plen - 2]的字符 即可得到 next[pLen - 1]的值。
  4. 题目中的 i, j 为先判断后更新 next 的值， 保证了 3 的成立。
  5. 当p[k] != p[j]时, 便寻找更小的后缀 k = next[k]
    第五条我想了整整一下午，

    举个例子
    前缀1 和 后缀1 相同
    前缀1 包括相同的 前缀a 和 后缀b
    后缀2 包括相同的 前缀c 和 后缀d
    因为 1 == 2
    所以 a == b == c == d
    所以可以放弃 1 + p[k] 与 2 + p[j]
    来更新 a + p[k] (k = next[k]) 和 d + p[j] (j值未变)

next数组优化

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getNextVal(const string &p)
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    int pLen = p.length();
    while(j < pLen - 1)
    {
        if(k == -1 || p[k] == p[j])
        {
            j++;
            k++;
            if(p[k] != p[j])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

讲解

当p[j] == p[next[j]]时， 匹配是无效的。 所以不能允许p[j] == p[next[j]]。如果出现了p[j] == p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[next[j]]。

相关链接

关于 KMP 算法，july的博客中的关于KMP的置顶文章绝对是我目前为止见过的最好的文章了， 通俗易懂， 深入浅出。 比其他文章不知道高到哪里去了。

从头到尾彻底理解KMP（2014年8月22日版）

Zhao70's Blog

发表于 | 分类于

题目大意

现在有n个小球，每次从盒子中取出的小球数目必须是1, 3, 7, 8个, 不可弃权, 拿到最后一个小球的人为失败

思路

  1. 此题可以通过状态转移方程进行计算, 从而避免使用递归的方法, 减少了运算量
  2. 当球的数目为0时, 为必胜态, arr[0] = true
  3. 只要能转移到必败态的一定是必胜态
  4. 无法转移到必胜态的是必败态

代码

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
#include <iostream>
using namespace std;
bool arr[10500];
int  query[150];
int main(int argc, char const *argv[])
{
    arr[0] = true;
    int prob[4] = {1, 3, 7, 8};
    for(int i = 1; i <= 9999; i++)
    {
        for(int j = 0; j <= 3; j++)
        {
            if(i - prob[j] < 0)
                continue;
            if(arr[i - prob[j]] == false)
            {
                arr[i] = true;
                break;
            }
            if(j == 3)
            {
                arr[i] = false;
            }
        }
    }
//    for(int i = 0; i <= 100; i++)
//        cout << arr[i] << " ";
    int nQuery;
    cin >> nQuery;
    for(int i = 0; i < nQuery; i++)
    {
        int val;
        cin >> val;
        cout << arr[val] << endl;
    }
    return 0;
}
Zhao70's Blog

发表于 | 分类于

前(tu)言(cao)

在做蓝桥2012预赛试题的时候， 做到“夺冠概率”这道题， 明明可以用数学上的方法求解。 结果，必须使用随机数，因为三次运行程序结果相同不给分。。。

题目

足球比赛具有一定程度的偶然性，弱队也有战胜强队的可能。
假设有甲、乙、丙、丁四个球队。根据他们过去比赛的成绩，得出每个队与另一个队对阵时取胜的概率表:
       甲 乙 丙 丁
甲 - 0.1 0.3 0.5
乙 0.9 - 0.7 0.4
丙 0.7 0.3 - 0.2
丁 0.5 0.6 0.8 -
数据含义：甲对乙的取胜概率为0.1，丙对乙的胜率为0.3，…
现在要举行一次锦标赛。双方抽签，分两个组比，获胜的两个队再争夺冠军。（参见【1.jpg】）
请你进行10万次模拟，计算出甲队夺冠的概率。

"图一"

评测标准

满分17分

编译选手提供的源代码，运行看结果

!! 至少运行3次，如果结果相同则不能得分！ 说明选手是用理论推算而非模拟方法。

输出四舍五入后为： 0.075 或 0.076 即可满分17分

如果输出 7.5 或 7.6 是采用了百分数的形式，也认为正确。

多次运行结果为：0.074 或 0.077 表明存在设计上的系统误差，可以给 5 分

如何产生随机数

  1. 添加头文件stdlib.h
  2. 由于rand()返回的是伪随机数字， 每次执行时结果是相同的

  3. 为了避免每次生成固定的随机数，引进srand()函数

    用法：srand(unsigned int seed)

  4. 可以利用中的随机函数初始化, 产生不同的随机种子

  5. srand((unsigned)time(NULL))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
    double arr[3] = {0.046, 0.102, 0.08};
    double sum = 0;
	//这里srand只能写在for循环外侧，否则会WA
	//看来srand的seed整个程序运行时只执行一次即可
    srand(time(NULL));
    for(int i = 0; i <= 100000 ; i++)
    {
        int val = rand() % 3;
        sum = sum + arr[val];
    }
    cout << sum / 100000;
    return 0;
}
Zhao70's Blog

发表于 | 分类于

题目来源
2012年蓝桥杯预赛

题目描述

假设有两种微生物 X 和 Y
X出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。
一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。
现在已知有新出生的 X=10, Y=89，求60分钟后Y的数目。
如果X=10，Y=90 呢？
本题的要求就是写出这两种初始条件下，60分钟后Y的数目。
题目的结果令你震惊吗？这不是简单的数字游戏！真实的生物圈有着同样脆弱的性质！也许因为你消灭的那只 Y 就是最终导致 Y 种群灭绝的最后一根稻草！
请忍住悲伤，把答案写在“解答.txt”中，不要写在这里！

思路与感悟

遇到这种模拟类的题目，最好还是不要随意更改题目，先按照0.5秒来模拟一下， 打表， 找出规律后再为了计算的精确性， 更改时间周期。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int main()
{
    int nX, nY;
    nX = 10;
    nY = 90;
    // i 为 0.5分钟
    for(int i = 1; i <= 120; i++)
    {
        if(i % 2 == 1)
            nY = nY - nX;
        if(i % 4 == 0)
            nY = nY * 2;
        if(i % 6 == 0)
            nX = nX * 2;
    }
    cout << nX << " " << nY;
    return 0;
}

参考链接

丁棒儿的博客

Zhao70's Blog

发表于 | 分类于

分类

欧拉环：图中经过每条边一次且仅一次的环；
欧拉路径：图中经过每条边一次且仅一次的路径；
欧拉图：有至少一个欧拉环的图；
半欧拉图：没有欧拉环，但有至少一条欧拉路径的图。

无向图

一个无向图是欧拉图当且仅当该图是连通的（注意，不考虑图中度为0的点，因为它们的存在对于图中是否存在欧拉环、欧拉路径没有影响）且所有点的度数都是偶数；一个无向图是半欧拉图当且仅当该图是连通的且有且只有2个点的度数是奇数（此时这两个点只能作为欧拉路径的起点和终点）；

证明

因为任意一个点，欧拉环（或欧拉路径）从它这里进去多少次就要出来多少次，故(进去的次数+出来的次数)为偶数，又因为(进去的次数+出来的次数)=该点的度数（根据定义），所以该点的度数为偶数。

有向图

一个有向图是欧拉图当且仅当该图的基图（将所有有向边变为无向边后形成的无向图，这里同样不考虑度数为0的点）是连通的且所有点的入度等于出度；一个有向图是半欧拉图当且仅当该图的基图是连通的且有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），其余点的入度等于出度。

证明

与无向图证明类似，一个点进去多少次就要出来多少次。

参考链接

dingchao

Zhao70's Blog

发表于 | 分类于

题目

标题：风险度量

X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路，构成通信网。
两个空间站间可能直接通信，也可能通过其它空间站中转。

对于两个站点x和y (x != y), 如果能找到一个站点z，使得：
当z被破坏后，x和y无法通信，则称z为关于x,y的关键站点。

显然，对于给定的两个站点，关于它们的关键点的个数越多，通信风险越大。

你的任务是：已知网络结构，求两站点之间的通信风险度，即：它们之间的关键点的个数。

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行，两个数u,v，代表被询问通信风险度的两个站点。

输出：一个整数，如果询问的两点不连通则输出-1.

例如：
用户输入：
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出：
2

思路解析

  1. 最开始检查a, b两点是否联通，否则，输出 -1 程序结束
  2. 从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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
using namespace std;
int nVer, nEdge;
int edge[2500][2];
int arr[1500];
bool merge(int, int);
int getFather(int);
int main(int argc, char const *argv[])
{
	cin >> nVer >> nEdge;
	for(int i = 0; i < nEdge; i++)
	{
		cin >> edge[i][0] >> edge[i][1];
	}
	int start, end;
	cin >> start >> end;
    for(int j = 1; j <= nVer; j++)
    {
        arr[j] = j;
    }
    for(int j = 0; j < nEdge; j++)
    {
        merge(edge[j][0], edge[j][1]);
    }
	if(merge(start, end) == false)
	{
        cout << "-1" << endl;
        return 0;
	}
	int cnt = 0;
	//遍历每个去掉的点
	for(int i = 1; i <= nVer; i++)
	{
		//去除需要检查联通的两点，这两点不需要遍历
	    if(i == start || i == end)
            continue;
		for(int j = 1; j <= nVer; j++)
		{
			arr[j] = j;
		}
		//合并已知点
		for(int j = 0; j < nEdge; j++)
		{
			//已经去除的点不需要继续合并
			if(edge[j][0] == i || edge[j][1] == i)
				continue;
			merge(edge[j][0], edge[j][1]);
		}
		if(merge(start, end) == false)
		{
			cnt++;
		}
	}
		cout << cnt << endl;
	return 0;
}
int getFather(int node)
{
	if(arr[node] == node)
		return node;
	node = getFather(arr[node]);
	return node;
}
bool merge(int t1, int t2)
{
	t1 = getFather(t1);
	t2 = getFather(t2);
	if(t1 == t2)
	{
		return true;
	}
	if(t1 < t2)
		arr[t2] = t1;
	else
		arr[t1] = t2;
	return false;
}
Zhao70's Blog

发表于 | 分类于

康托展开

应用

已知一个字符串， 求其字典序

公式

1
2
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
//其中a[i]为当前未出现的元素中是排在第几个（从0开始）。

原理

康托展开实际是求在当前序列之前有几种字典序
对于[D, B, A, C]
以D为开头的序列之前必定有以A、 B、 C(字典序比D小)开头的序列，共有3种, 每种有3！种可能性 所以 a4 = 3 * 3!
以B为开头的序列之前必定有以A(字典序比B小)开头的序列，共有2种, 每种有2！种可能性 所以 a3 = 1 * 2!
以A为开头的序列之前必定无序列，共有0种(因为在子串AC中, 无其他元素比A的字典序更小), 每种有1！种可能性 所以 a2 = 0 * 1!
同理 a1 = 0 * 0!

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
\\注意: 因为排列可能数目众多，所以使用long long
long long contor(string & s)
{
   long long ans = 0;
   for(long long loc = 0; loc <= s.length() - 1; loc++)
   {
   		string sub = s.substr(loc);
   		sort(sub.begin(), sub.end());
   		long long val = lower_bound(sub.begin(), sub.end(), s[loc]) - sub.begin();
   		ans = ans + fact(s.length() - 1 - loc) * val;
   }
   return ans;
}

康托逆展开

原理

如何求出ABCD的字典序为20的序列？

利用辗转相除法即可从字典序逆展开的得到an 到 a1
"康托逆展开"

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string invcontor(long long val, string& s)
{
   sort(s.begin(), s.end());
   std::vector<long long> poly;
   for(long long i = 0; i != s.length(); i++)
   {
      poly.push_back(val / fact(s.length() - 1 - i));
      val = val % (fact(s.length() - 1 - i));
   }
   string ans;
   for(long long i = 0; i < poly.size(); i++)
   {
      //cout << poly[i] << endl;
      //cout << s << endl;
      ans = ans + s[poly[i]];
      s.erase(poly[i], 1);
   }
   return ans;
}

代码

github

参考链接

zhongkeli的专栏

Zhao70's Blog

发表于

printf()函数

%%打印一个百分号

1
2
3
printf("%%\n");
\\输出结果
\\%

printf()的转换说明修饰符

.数字

%5.2f打印一个浮点数， 字段宽度为5， 其中小数点后有两位

1
2
double per = 4.23;
printf("%5.2f\n", per);

-

待打印项向左对齐

1
printf("%-10d", val);

+

若符号值为正， 则在值前面显示加号; 若为负，则在值前面显示减号

1
2
3
4
5
    printf("%+5.2f\n", per);
    printf("%+5.2f\n", -1 * per);
\\output
\\+4.23
\\-4.23

空格

若符号值为正，则显示前导空格; 若为负，则在值前面显示减号

1
2
3
4
5
    printf("% 5.2f\n", per);
    printf("% 5.2f\n", -1 * per);
\\output
\\ 4.23
\\-4.23

printf()的返回值

printf()的返回值为打印字符的个数

1
2
3
4
    int num = printf("Hello World\n");
    printf("%d\n", num);
\\output
\\12

scanf()的返回值

scanf()函数返回成功读取的项数

printf()和scanf()的*修饰符

printf()中的*

用 * 修饰符代替字符宽度

1
2
3
4
double per = 4.23;
   int width = 5;
   int percent = 2;
   printf("%*.*f\n", width, percent, per);

scanf()中的*

将 * 放在% 和 转换字符之间会使得scanf()跳过相应的输入项

1
2
3
4
5
6
    scanf("%*d%*d%d", &val);
    printf("%d\n", val);
\\input
\\4 5 6
\\output
\\6