DAY 4 基础算法

基础算法

本来今天是要讲枚举暴力还有什么的，没想到老师就说句那种题目就猪国杀，还说只是难打，不是难。。。。

STL（一）set

感觉今天讲了好多，set，单调栈，单调队列，单调栈和单调队列保证了序列的单调性，一般的，凡是找左右第一个比他大或小的大概率是这个东西，原来作业1的奶牛歌声就是这个东西，但不是道为什么我爆力优化过了。。。。

然后就是这题

这题要用set，不用还过不了。。。。

set常用函数

begin() 　　 ,返回set容器的第一个元素
end() 　　　　 ,返回set容器的最后一个元素
clear() 　　 ,删除set容器中的所有的元素
empty() 　　　,判断set容器是否为空
max_size() 　 ,返回set容器可能包含的元素最大个数
size() 　　　　 ,返回当前set容器中的元素个数
rbegin　　　　 ,返回的值和end()相同
rend()　　　　 ,返回的值和rbegin()相同

可以这样练下手

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int main()
 5 {
 6     set<int >s;
 7     s.insert(1);
 8     s.insert(2);
 9     s.insert(3);
10     s.insert(4);
11     cout<<"长度是"<<s.size()<<endl;
12     cout<<"可能包含元素的最大个数为"<<s.max_size() <<endl;
13     cout<<"第一个元素是"<< *s.begin()<<endl;
14     cout<<"最后一个元素是"<<*s.end()<<endl;
15     s.clear();
16     if(s.empty())
17     {
18         cout<<"空啦！！！！"<<endl; 
19     }
20         cout<<"长度是"<<s.size()<<endl;
21     cout<<"可能包含元素的最大个数为"<<s.max_size() <<endl;
22 }

输出是这样的：

注意如果这样打

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int main()
 5 {
 6     set<int >s;
 7     s.insert(1);
 8     s.insert(2);
 9     s.insert(3);
10     s.insert(1);
11     cout<<"第一个元素是"<< *s.begin()<<endl;
12     cout<<"最后一个元素是"<<*s.end()<<endl;
13     return 0;
14 }

我们可以发现最后一个元素显示还是3.。。

count() 用来查找set中某个某个键值出现的次数

这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int main()
 5 {
 6     set<int >s;
 7     s.insert(1);
 8     s.insert(2);
 9     s.insert(3);
10     s.insert(1);
11     cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;
12     cout<<"set 中 4 出现的次数是 ："<<s.count(4)<<endl;
13     return 0;
14 }

输出应该是这样的

equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     set<int>::iterator iter;
10     for(int i = 1 ; i <= 5; ++i)
11     {
12         s.insert(i);
13     }
14     for(iter = s.begin() ; iter != s.end() ; ++iter)
15     {
16         cout<<*iter<<" ";
17     }
18     cout<<endl;
19     pair<set<int>::const_iterator,set<int>::const_iterator> pr;
20     pr = s.equal_range(3);
21     cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
22     cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
23     return 0;
24 }

输出因该是这样的

erase(iterator) ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int main()
 5 {
 6     set<int> s;
 7     set<int>::const_iterator iter;
 8     set<int>::iterator first;
 9     set<int>::iterator second;
10     for(int i = 1 ; i <= 10 ; ++i)
11     {
12         s.insert(i);
13     }
14     //第一种删除
15     s.erase(s.begin());
16     //第二种删除
17     first = s.begin();
18     second = s.begin();
19     second++;
20     second++;
21     s.erase(first,second);
22     //第三种删除
23     s.erase(8);
24     cout<<"删除后 set 中元素是 ：";
25     for(iter = s.begin() ; iter != s.end() ; ++iter)
26     {
27         cout<<*iter<<" ";
28     }
29     cout<<endl;
30     return 0;
31     return 0;
32 }

输出

insert(key_value); 将key_value插入到set中，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。

inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于key_value的定位器

非常尴尬的发现就算学了这个东西，那题还是不会。。。。。。。

STL（二）bitset

感觉这个东西还挺好用的，也是STL里的一个神器，感觉好多题目都能用，那个三维偏序好像除了CDQ分治，KD——tree，和bitset都能打。。。还是只占一个字符，比单纯的bool,好用不知道多少。

初始化：

 1 #include<iostream>
 2 #include<bitset>
 3 using namespace std;
 4 int main()
 5 {
 6     bitset<4> bitset1;//初始化，长度为4，全都是0 
 7     bitset<8> bitset2(12);//长度是8，用二进制存12，不足位补0 
 8     string s="10101";
 9     bitset<10> bitset3(s);//同上 
10     cout<<bitset1<<endl;
11     cout<<bitset2<<endl;
12     cout<<bitset3<<endl;
13     return 0;
14 }

输出应该是这样的：

另外，bitset只能存0或1，如果有其他的东西会报错，原来char也可以，但不知道为什么会警告，能不用最好还是不用。。。。

一些常见的位运算：

 1 #include<iostream>
 2 #include<bitset>
 3 using namespace std;
 4 int main()
 5 {
 6     bitset<4> bitset1(string("1100"));
 7     bitset<4> bitset2(string("0011"));
 8     cout<<(bitset1^=bitset2)<<endl;//按位异或后将值付给bitset1 
 9     cout<<(bitset1&=bitset2)<<endl;//按位与后将值付给bitset1 
10     cout<<(bitset1|=bitset2)<<endl;//按位或后将值付给bitset1 
11     cout<<(bitset1<<=2)<<endl;//右移后将值付给bitset1 
12     cout<<(bitset1>>=1)<<endl;//左移后将值付给bitset1 
13     cout<<(bitset1==bitset2)<<endl; //假的，返回false（0） 
14     cout<<(bitset1!=bitset2)<<endl;//真的，返回true（1或-1）
15     cout<<(bitset2&bitset1)<<endl;//左移后将值付给bitset1 ，其他同理 
16     return 0;
17 }

输出应该是这样的：

还可以像数组那样去访问每一位

一些常用的函数：

这正是STL吸引人的主要原因，可以不用手打，但会慢，对于我这样的蒟蒻就完全不会有影响，但也许对于机房旁边的大佬（传送门）就会有很大影响，这会让他AK不了IOI！！！！

#include<iostream>
#include<bitset>
#include<cstdlib>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    bitset<8> bitset1(string("10111010"));
    cout<<bitset1.count()<<endl;//（count函数用来求bitset中1的位数，foo中共有５个１
    cout<<bitset1.size()<<endl;//（size函数用来求bitset的大小，一共有８位
    cout<<bitset1.test(0)<<endl;//（test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true
    cout<<bitset1.test(2)<<endl;//（同理，foo[2]为０，返回false
    cout<<bitset1.any()<<endl;//（any函数检查bitset中是否有１
    cout<<bitset1.none()<<endl;//（none函数检查bitset中是否没有１
    cout<<bitset1.all()<<endl;//f（all函数检查bitset中是全部为１　
    //说明一下：test函数会对下标越界做出检查，而用过数组方式访问的元素则不会，所以用test更安全一些 


    string s=bitset1.to_string();//将bitset转换成string类型
    unsigned long a=bitset1.to_ulong();//将bitset转换成unsigned long类型
    cout<<s<<endl;
    cout<<a<<endl;
    

    cout<<bitset1.flip(2)<<endl;//（flip函数传参数时，用于将参数位取反，本行代码将foo下标２处"反转"，即０变１，１变０
    cout<<bitset1.flip()<<endl;//（flip函数不指定参数时，将bitset每一位全部取反
    cout<<bitset1.set()<<endl;//（set函数不指定参数时，将bitset的每一位全部置为１
    cout<<bitset1.set(3,0)<<endl;//（set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行对foo的操作相当于foo[3]=0
    cout<<bitset1.set(3)<<endl; //（set函数只有一个参数时，将参数下标处置为１
    cout<<bitset1.reset(4)<<endl;//（reset函数传一个参数时将参数下标处置为０
    cout<<bitset1.reset()<<endl;//(reset函数不传参数时将bitset的每一位全部置为０
    //这些函数同样会检查数组下标，有异常会提示。 
    
    return 0;
}

贪心：

贪心是个非常有用的东西，有时候没有思路，也不会证明，但乱搞就过了。。。。

bzoj 3668 起床困难综合征（门）

从高位到低位枚举每一位，判断是1还是0，位运算各位之间不会影响。
保证当前的数不会大于m;
对于0能变为1的两种情况直接变。
0变为的两种情况不予考虑。

代码就非常简单：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=1e5+10;
 5 char op[10];
 6 long long  n,m;
 7 long long  t;
 8 long long  ans=0,ans0=0,ans1=0x7fffffff;
 9 int main()
10 {
11     //freopen("testdata.in","r",stdin);
12     scanf("%lld%lld",&n,&m);
13     for(int i=1;i<=n;i++)
14     {
15         scanf("%s %lld",op,&t);
16         if(op[0]=='A')
17         {
18             ans1&=t;
19             ans0&=t;
20         }
21         else
22         if(op[0]=='O')
23         {
24             ans1|=t;
25             ans0|=t;
26         }
27         else
28         if(op[0]=='X')
29         {
30             ans1^=t;
31             ans0^=t;
32         }
33     }
34     for(int i=30;i>=0;i--)
35     {
36         if(ans0&(1<<i))
37         {
38             ans+=(1<<i);
39         }
40         else
41         if((m>=(1<<i))&&(ans1&(1<<i)))
42         {
43             m-=(1<<i);
44             ans+=(1<<i);
45         }
46     }
47     cout<<ans<<endl;
48     return 0;
49 }

BZOJ 2563 阿狸和桃子的游戏（门）

这题可以吧边权平分到两边的点，这样相对大小没变，一减也没变。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=1e6+10;
 5 int sum[maxn];
 6 int x,y,z;
 7 int k;
 8 int ans=0;
 9 int n,m;
10 int main()
11 {
12     cin>>n>>m;
13     for(int i=1;i<=n;i++)
14     {
15         cin>>k;
16         sum[i]=k<<1;
17     }
18     for(int i=1;i<=m;i++)
19     {
20         cin>>x>>y>>z;
21         sum[x]+=z;
22         sum[y]+=z;
23     }
24     sort(sum+1,sum+1+n);
25     for(int i=n;i>=1;i-=2)
26     {
27         ans+=sum[i]-sum[i-1];
28     }
29     ans/=2;
30     cout<<ans<<endl;
31     return 0;
32 }

NOIP 2015 跳石头（还是回淮南的测试里的题目）

显然这题这题就是二分还是比较经典的哪一类。
二分一个答案，看他是否符合条件。
贪心
从第二块开始循环（第一块不能搬走，要不然你站哪？）假设现在到了第i块，上一个没搬走的是第J块，如果当前的距离小于ans，就可以直接搬走，要不然就留下来。
最后一块不能搬走，要不你最后站哪？

快乐的代码时光（机房考试还有人打了线段树，几千字。。。）

NOIP 2012 DAY2 T2 借教室

这题好快乐，暴力拿了50分。。。
正解还是二分，二分一个答案，看他能满足到哪一个订单。
然后把1到ans的所有订单都扫描一下。
可以用差分数组优化一下复杂度。

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 
 8 using namespace std;
 9 
10 const int maxn=1e6+10;
11 
12 int need[maxn];
13 int sheng[maxn];
14 int r[maxn];
15 int l[maxn];
16 int d1[maxn];
17 int d2[maxn];
18 int n,m;
19 
20 int panduan(int x)
21 {
22     memset(d2,0,sizeof(d2));
23     for(int i=1;i<=x;i++)
24     {
25          d2[l[i]]+=d1[i];
26         d2[r[i]+1]-=d1[i]; 
27     }
28     for(int i=1;i<=n;i++)
29     {
30         need[i]=need[i-1]+d2[i];
31         if(need[i]>sheng[i])
32         return 0;
33     }
34     return 1;
35 }
36 
37 int main()
38 {
39     memset(d1,0,sizeof(d1));
40     memset(need,0,sizeof(need));
41     memset(sheng,0,sizeof(sheng));
42     memset(l,0,sizeof(l));
43     memset(r,0,sizeof(r));
44     cin>>n>>m;
45     for(int i=1;i<=n;i++)
46     {
47         cin>>sheng[i];
48     }
49     for(int i=1;i<=m;i++)
50     {
51         cin>>d1[i]>>l[i]>>r[i];
52     }
53     if(panduan(m))
54     {
55         cout<<"0"<<endl;
56         return 0;
57     }
58     else
59     {
60         int L=1,R=m;
61         while(L<R)
62         {
63             int middle=(L+R)/2;
64             if(panduan(middle))
65             {
66                 L=middle+1;
67             }
68             else
69             {
70                 R=middle;
71             }
72         }
73         cout<<"-1"<<endl<<L<<endl;
74     }
75     return 0;
76 }