基础算法

Posted on | In , | Visitors:

This is my blog.
（未完待续）
算法里面最基础的莫过于枚举、贪心、二分、搜索、分治、排序、模拟。
在这里，我简单记述一下其核心思想和自己的一些理解，并附上相关练习题（若此题做过，会附上AC代码，此博客会不断更新）

枚举

枚举：顾名思义就是把每个可能去试一遍，但是怎么枚举能使每一个可能都包含到？怎么枚举能不重复？怎么枚举可以满足题目规定的时间？所以这里我会附上优化和剪枝的内容。
上例子

1
2
3
4
5
6
7
例一：在一个N*N(N<=100)矩阵中求一个最大的正方形使得该正方形的四个顶点都是有字符“#”构成。 
#*#***
******
#*#*#*
******
#*****
***#**

思路一：枚举所有的正方形，看四个顶点是否都是“#”
思路二：枚举所有“#”，是否可以构成正方形
上述两个思路是否有优劣之分？
那我们再来想想，如何确定一个正方形，是否需要四个点呢？
很显然，确定一个正方形只需要对角线上两个点即可，也就是说我们可以通过两个点，算出另外两个点的位置。
那么我们可以通过枚举两个点，用一个判断函数，找另外两个点是否符合要求。
怎么是符合要求呢？首先算出的两个点必须是整数，再者两个位置必须是“#”。
怎么计算那两个点呢？我们来看一下示意图：
正方形计算示意图
注意，因为有除法，有精度的问题，在实际应用中应除以2.0，而在后面确定整数时，因为有精度误差，所以不能直接和整数比，而应该相减后的差值在误差范围内。
这样的时间复杂度为O(n^2),还可以优化吗？
答案是肯定的，目前想到的优化有：
1.枚举时，第一个点从左上开始，那么第二个点枚举的时候从右下开始。因为题目中所需要找的是最大的正方形。
2.设置一个全局变量ans，如果比ans大的时候，更新，否则跳出循环（因为再接下去找的点肯定比目前的tmp还小，所以不用考虑了，即剪枝。）
附上核心代码：
枚举
判断函数

补充尺取法：

我们用例子来说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
小明喜欢收集卡片，他要去商店购买新到的卡片。
商店出售的卡片有N张，是连续的，小明只能购买连续的一段，这一串卡片共有M种，每种卡片都有一个价格，小明拿的钱数为V，他想知道如何用花最少的钱来集齐所有种类的卡片。
N<=1000000 ，M<=2000 ，Ti<=2000 ,  V<=10^9
输入:第1行 三个正整数 N，M，V，
    第2行共M个正整数，第i个数Ti表示第i种卡片的价格，
    第3行 N个正整数，表示第i个卡片是哪一类。
输出:小明还剩多少钱
样例输入
5 2 20
10 5
1 1 2 2 1
样例输出
15

所谓尺取法，也称双指针法，但在实际应用中，我们不用指针，而是使用两个变量，来代替指针。
比如此题，因为题目要求连续一段，于是我们可以用尺取法来做。
我们设置变量l,r。l表示开始点，r代表结束点，r-l代表选取的长度。
我们可以设置一个cnt数组来记录在l-r范围内每张牌子的个数，t数组表示牌子的价钱，如果左边的牌子在这段范围内有的话，可以将做指针往右移动，直至左指针的牌子在整段内只有一个，当所有的种类tot==m时，就说明这是一种可行的取法，更新ans值即可。
附上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int l=r=1;
int tot=0;
int sum=0;
int ans=0x7f7f7f7f7f   //系统中的max值
for(;r<=n;r++){
    if(cnt[a[i]]==0)tot++;    //a数组记录牌子的特性
    cnt[a[i]]++;
    sum+=t[a[i]];
    while(cnt[a[l]]>1){
        sum-=t[a[l]];
        cnt[a[l]]--;
        l++;
    }
    if(tot==m)ans=min(ans,sum);
}

再给上一题，这个枚举则是关于几何方面的：

1
在一个给定的矩形中有一些障碍点，找出内部不包含障碍点的、轮廓与整个矩形平行或重合的最大子矩形。

解法一：枚举上下左右四个边界，判断中间有没有点
解法二：枚举左右边界，对处在边界内的点排序，每两个相邻的点和左右边界组成一个矩形。
解法三：悬线法。若是障碍点，不可延伸。若不是障碍点，则长度+1，直至到障碍点或到边界点。
其实相当于枚举边长。然后从左边悬线开始往右扫，若右悬线小于，则break，换下一根悬线。
（这题目前只有思路，还没有实现代码）

贪心

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，他所做出的是在某种意义上的局部最优解。
上题吧

1
2
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。 
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

假设在队伍中有A,B两人，他们的先后顺序对其他人是没有影响。
设他们之前最多的奖赏为π，
若A在前面，则max(π/rA,πlA/rB)
若A在后面，则max(π/rB,πlB/rA)
假设A前，ans值更小，那么有max(π/rA,πlA/rB)<max(π/rB,πlB/rA)
易知： π/rA<πlB/rA; πlA/rB>π/rB;
所以只需πlA/rB < πlB/rA
即：rAlA<rBlB
则将每一个人的l与r相乘，将其排序即可
这道题可能有人会觉得不怎么像，其实在分析问题的时候我们就用到了贪心的思想。
再来一题，来感受一下贪心吧！

一些位运算

1
给定4个小于等于10^18的数a,b,c,d，又有a<=x<=b，c<=y<=d，求x xor y的最大值

其中xor为异或的意思，在大数计算时，我们常常会用到位运算。
1.根据题意我们就可以知道，我们需要用位运算；
2.求最大值，根据贪心的思想，我们应从高位开始
3.我们来分析一下在第i位可能的情况：
（1）两者均可取0 1，则定可以取到……1000……和……0111……，他们异或后结果为……1111……
（2）两者唯一，那只能这么取
（3）若 x只能取1，而y可取1或0，那么y必取0，之后的上界变为……01111……
若 x只能取0，而y可取1或0，那么y必取1，之后的下界变为……11111……
注意：1.<<左移 >>右移，他们的优先级较低，一般需要用括号
2.（long long）1可写成1LL，且需观察一下评判机的系统，若为windows，则应为%I64d；若为linux，则应为%lld。
3.1e18约等于2^63
4.double输入为%lf，而输出是%f，不是%lf了
5.很多大佬会在scanf(“ %s”)中打上括号
其他：在codeblocks中ctrl+D复制一行（本人将会弃用codeblocks，其快捷键不会将特殊说明，但这个快捷键真的很好用）

二分

三分

这次做了2017下半年搜狗的题目，用到了三分，但是只过了40%，后来发现可能是输入的问题，但不知道再去何处提交。（感谢博博的help，队长厉害呢）
上题：
problem
problem

我的错误代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const ll add = 1e8, mid = 180e8;
ll get(ll a, ll b){
    ll Abs = (a - b) > 0 ? a - b : b - a;
    return Abs > mid ? Abs - mid : Abs;
}
ll in(){
    char s[100];
    scanf("%s", s);
    ll now = 0;
    int len = strlen(s);
    for(int  i = 0; i < len; i ++)  if(s[i] != '.')
        now = now * 10 + s[i] - '0';
    return now;
}
int main(){
    //initialization
    int n;
    scanf("%d", &n);
    vector<ll>q;
    for(int i = 1; i <= n; i ++){
        ll tmp=in();
        q.push_back(tmp);
//double temp;
//scanf("%lf", &temp);
//q.push_back((ll)(temp * add));
    }
//perform the algorithm : trinary search
    int len = q.size();
    ll ans = 0;
    for(int i = 0; i < len; i ++){
        int L = 0, R = len - 1;
        ll now = q[i];
        while(L < R){
//三分的两种方法
            int left = (L*2+R)/3, right = (L+R*2)/3;
            if(get(now, q[left]) > get(now, q[right]))  {R = right - 1; }
            else    {ans = max(ans, get(now, q[L]));L = left + 1;}
//            int left=(L+R)/2,right=(left+R)/2;
//            if(get(now, q[left]) > get(now, q[right]))  {R = right-1; }
//            else    {ans = max(ans, get(now, q[L]));L = left+1;}
        }
        ans = max(ans, get(now, q[L]));
    }
    printf("%.8lf\n", (double)ans/add);
}
### 据说正解
``` bash
#include <string> 
#include<algorithm> 
#include <vector> 
#include<unordered_map>   
#include <iostream> 
#include <iomanip> 
using namespace std; 
int main() 
{ 
int n; 
cin >> n; 
vector <double> a(n, 0); 
for (int i = 0; i < n; i++) 
cin >> a[i]; 
for (int i = 0; i < n; i++) 
if (a[i] < a[n-1]-180) 
a.push_back(a[i] + 360); 
int start = 0; 
int end = 0; 
double max_len = 0; 
double temp_len = 0; 
for (int i = start + 1; i < a.size(); i++) 
{ 
end = i; 
if (a[end] - a[start] > 180) 
{ 
temp_len = a[end - 1] - a[start]; 
if (temp_len > max_len) 
max_len = temp_len; 
while (a[end] - a[++start] > 180); 
} 
} 
temp_len = a[end] - a[start]; 
if (temp_len > max_len) 
max_len = temp_len; 
cout << fixed << setprecision(8) << max_len << endl; 
return 0; 
}

愿 我是你的小太阳


买糖果去喽