Celery's Blog

0%

挑战程序设计竞赛-day4

发表于 Valine：

bitset

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 注意：
 * 1. 用字符串构造时，字符串只能包含'0'或'1'，否则会抛出异常
 * 2. 构造时，需在<>中表明bitset的大小(即size)
 * 3. 在进行有参构造时，若参数的二进制比bitset的size小，则在前面用0补充，若比bitsize大，参数为整数时取后面部分，参数为字符串时取前面部分
 */
int main() {
    bitset<4> bitset1;  // 无参构造，长度为4，默认每一位为0
    bitset<8> bitset2(12);  // 长度为8，二进制保存，前面用0补充
    string s = "100101";
    bitset<10> bitset3(s);  // 长度为0，前面用0补充

    string s2 = "100101";
    bitset<4> bitset4(s2);

    cout << bitset1 << endl;
    cout << bitset2 << endl;
    cout << bitset3 << endl;
    cout << bitset4 << endl;
}

可用的操作符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));

cout << (foo^=bar) << endl;     // foo为1010
cout << (foo&=bar) << endl;     // foo为0010
cout << (foo|=bar) << endl;     // foo为0011

cout << (foo <<= 2) << endl;    // foo为1100
cout << (foo >>= 1) << endl;    // foo为0110

cout << (~bar) << endl;         // 输出1100,但不赋值
cout << (bar << 1) << endl;     // 输出0110,但不赋值
cout << (bar >> 1) << endl;     // 输出0001

cout << (foo == bar) << endl;   // 输出0    
cout << (foo != bar) << endl;   // 输出1

cout << (foo & bar) << endl;    // 按位与，不赋值，输出0010
cout << (foo | bar) << endl;    // 按位或，输出0111
cout << (foo ^ bar) << endl;    // 按位异或，输出0101

此外，还可以通过[]来访问元素(类似数组)，注意最低位下标为0

1
2
3
4
bitset<4> foo(string("1011"));
cout << foo[0] << endl;		// 1
cout << foo[1] << endl;		// 1
cout << foo[2] << endl;		// 0

可用函数

1
2
3
4
5
6
7
bitset<8> foo(string("10011011"));
    cout << foo.count() << endl;    // count函数用来求bitset中1的位数
    cout << foo.size() << endl;     // size函数用来求bitset的大小
    cout << foo.test(0) << endl;    // test函数用来查找下标处的元素是0还是1，并返回false或true，这里foo[0]为1，返回true
    cout << foo.any() << endl;      // any函数查找bitset中是否有1
    cout << foo.none() << endl;     // none函数检查bitset中是否没有1
    cout << foo.all() << endl;      // all函数检查bitset中是否全部为1
1
2
3
4
5
6
7
8
bitset<8> foo(string("10011011"));
cout << foo.flip(2) << endl;   // 10011111,flip函数传参时，用于将参数位取反，本代码将foo下标为2处"翻转"
cout << foo.flip() << endl;    // 01100000,flip函数不指定参数时，将bitset每一位全部取反
cout << foo.set() << endl;     // 11111111,set函数不指定参数时，将bitset的每一位全部置为1
cout << foo.set(3, 0) << endl; // 11110111,set函数指定两位参数时，将第一位参数位的元素置为第二位参数的值，本行对foo的操作相当于foo[3] = 0
cout << foo.set(3) << endl;    // 11111111,set只有一个参数时，将参数下标处置为1
cout << foo.reset(4) << endl;  // 11101111,reset函数传一个参数时将参数下标处置为0
cout << foo.reset() << endl;   // 00000000,reset函数不传参数时将bitset的每一位全部置为0

类型转换

1
2
3
4
5
bitset<8> foo(string("10011011"));
string s = foo.to_string();
unsigned long a = foo.to_ulong();   // 将bitset转换成unsigned long类型
cout << s << endl;
cout << a << endl;

AOJ： Osenbei

有一个烤饼器可以烤r行c列的煎饼，煎饼可以正面朝上（用1表示）也可以背面朝上（用0表示）。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上，问最多能使多少煎饼正面朝上？
输入：多组输入，每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000)，剩下r行c列表示煎饼初始状态。r=c=0表示输入结束。
输出：对于每组输入，输出最多能使多少煎饼正面朝上。

测试数据：

1
2
3
4
5
6
7
8
9
10
11
输入：
2 5
0 1 0 1 0
1 0 0 0 1 
输出：9
输入：
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1
输出：15

思路：

先对行进行翻转，若有r行，一共要进行2r2^r次，对于行翻转后的每一种情况，再进行列的翻转，列不需要真的翻转，只需要统计一下每一列是正面朝上还是反面朝上的煎饼多，取综合

对于这2r2^r个综合，取最大的那个即可。

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
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
// bitset是一种类似数组的结构，它的每一个元素只能是0或1，每个元素仅用1bit空间
bitset<10000> cookie[10];
int main() {
    int r, c;
    while(cin >> r >> c && r) {
        int result = 0;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                bool what;
                cin >> what;
                cookie[i][j] = what;
            }
        }
        int permute = 1 << r;
        // 行的变换总共有2^r个，k取遍各种情况
        for(int k = 0; k < permute; k++) {
            // 每一种情况对应着r行的一次变化，每一行翻转或者不翻转
            for(int j = 0; j < r; j++) {
                // 对于每一个k，(1 << j)与i的二进制对应位上若都为1，这一行翻转
                if(k & (1 << j)) {
                    cookie[j].flip();
                }
            }
            int possible_num = 0;
            for(int j = 0;j < c; j++) {
                int up_number = 0;
                for(int i = 0; i < r; i++) {
                    if(cookie[i][j]) {
                        up_number++;
                    }
                }
                possible_num += max(up_number, r - up_number);
            }
            result = max(result, possible_num);
            for(int j = 0; j < r; j++) {
                if(k & (1 << j)) {
                    cookie[j].flip();
                }
            }
        }
        cout << result << endl;
    }
    return 0;
}

POJ：Cleaning Shifts

题意：有n头牛，它们都有一个工作时间的区间s至e，给定一个总的工作时间t，问最少需要多少头牛才能覆盖从1到t的工作时间

思路：

简单的区间贪心。首先将牛的工作时间按起始时间最小(第一优先级)、结束时间最大的顺序(第二优先级)进行排序，然后取第n头牛时，要满足一下条件：1、第n头牛的s要小于等于第n-1头牛的e+1(这里要注意题目里给的是时间点，不是区间段) 2、第n头牛的e尽可能的大。之后就得考虑一些特例情况就可以了

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
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 25005;
int n, t;
struct node {
    int s, e;
};
node cows[MAXN];
bool comp(const node a, const node b) {
    if(a.s != b.s) {
        return a.s < b.s;
    } else {
        return a.e >= b.e;
    }
}

int solve(int ans) {
    if(n < 1 || cows[0].s != 1) {
        return -1;
    }
    if(n == 1) {
        if(cows[0].s == 1 && cows[0].e == t) {
            return 1;
        } else {
            return -1;
        }
    }
    int i = 1, maxE = cows[0].e, maxNextE = cows[0].e;
    while(i < n) {
        if(maxE == t) {
            return ans;
        }
        bool flag = false;
        if(cows[i].s <= maxE + 1) {
            while(i < n && cows[i].s <= maxE + 1) {
                if(cows[i].e > maxNextE) {
                    maxNextE = cows[i].e;
                    flag = true;
                }
                i++;
            }
            if(flag) {
                maxE = maxNextE;
                ans++;
            }
        } else {
            return -1;
        }
    } 
    if(maxE == t) {
        return ans;
    } else {
        return -1;
    }
}

int main() {
    while(scanf("%d%d", &n, &t) == 2) {
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &cows[i].s, &cows[i].e);
        }
        sort(cows, cows + n, comp);
        printf("%d\n", solve(1));
    }
    return 0;
}

区间贪心问题

选择不相交区间

描述

数轴上有n个开区间(ai, bi)。选择尽量多个区间，使得这些区间亮亮没有公共点

思路
  • 区间x完全包含y，选y
  • 按照bi从小到大排序，从第一个区间开始选
  • 把所有和上一个区间相交的区间排除在外

贪心策略是：一定要选第一个区间（实际上就是活动安排问题）

区间选点问题

描述

数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每一个区间内都至少有一个点（不同区间内含的点可以是同一个）

思路
  • 按bi从小到大排序（b相同时，a从大到小排序）
  • 区间包含的情况下，大区间不需要考虑
  • 取最后一个点

![img](file:///C:\Users\12751\Documents\Tencent Files\1275121799\Image\C2C{3393526A-72A4-D6B5-6CB3-E225F6C2D3D2}.png)

区间覆盖问题

描述

数轴上有n个闭区间[ai, bi]，选择尽量少的区间覆盖一条指定线段[s, t]

思路

  • 每个区间在[s, t]外的部分都应该被预先切掉

  • 按照a从小到大排序，选择起点在s的最长区间[ai, bi]

  • 新的起点应该设置为bi，忽略所有区间在bi之前的部分

img

POJ 1328: Radar Installation

1579597650530

大意：

​ 给定一个直角坐标系，定义x轴为海岸线，海岸线上方是海，下方是陆地.
​ 在海域零星分布一些海岛, 需要要在海岸线上安装若干个雷达覆盖这些海岛,
​ 每个雷达的覆盖半径都是相同且固定的.
​ 现在给定所有海岛的坐标(x,y), 以及雷达的覆盖半径d，
​ 问可以覆盖所有海岛的最小雷达数.

思路：

  • 如果出现任意一个海岛的y值大于d，即无解

  • 在所有y值都小于d的时候，考虑每一个海岛的设置的雷达的边界（即预处理）

    • 假设一个海岛的位置为(x, y)，雷达半径为d
    • 设雷达在海岸线上的左右边界为left, right
    • m = sqrt(d*d - y*y)
    • 则left = x - m, right = x + m

    然后针对上述所求的每一对(left, right)按照left进行排序，然后从左往右遍历，如果当前最右边的雷达不能覆盖当前海岛，则增加一个雷达，其位置为radio_x = x + m，即安排在能观测到该海岛的最右侧位置，这样即可保证所需的雷达数目是最少的。

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
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct node {
    double s, e;
};
int n, d, k;
node area[1010];
int cmp(node a, node b) {
    if(a.e == b.e) {
        return a.s > b.s;
    }
    return a.e < b.e;
}

int change(int x, int y, int k) {
    if(y > d) {
        return 0;
    }
    double a, b, m = sqrt(d * d - y * y);
    a = x - m;
    b = x + m;
    area[k].s = a;
    area[k].e = b;
    return 1;
}

int main() {
    int x, y, k = 0;
    while(scanf("%d%d", &n, &d) && (n || d)) {
        bool flag = false;
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &x, &y);
            if(!change(x, y, i)) {
                flag  = true;
            } 
        }
        if(!flag) {
            sort(area, area + n, cmp);
            double x = area[0].e;
            int num = 1;
            for(int i = 1; i < n; i++) {
                if(area[i].s > x) {
                    num++;
                    x = area[i].e;
                }
            }
            printf("Case %d: %d\n", k + 1, num);
        } else {
            printf("Case %d: -1\n", k + 1);
        }
        k++;
    }
}

PS：这里最重要的是预处理工作，我这个zz，在设x的时候，double x写成了int x，然后就一直没过…无语了

POJ 3190: Stall Reservations

1579595679052

大意：每头奶牛拥有自己的可以挤奶的时间。且每头牛都必须挤奶，而他们又不愿意在一间房，问最少需要造多少间房。

思路：

可以用贪心做，依据开始时间排序。依次放奶牛（开始时间最小），若所有房间都没空，那么就再造一间房。

判断房间状态，用for循环会超时，可以使用优先队列，队列排序是房间空的越早越排前。

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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 50010;
int n;
struct node {
    int s, e;
    int stall;
    int tag;
};

struct RNode {
    int first;
    int second;
    bool operator < (const RNode &a) const {
        if(first == a.first) {
            return second > a.second;
        } 
        return first > a.first;
    }
};

// 小顶堆
priority_queue<int, vector<RNode> >q;
bool cmp(const node a, const node b) {
    if(a.s == b.s) {
        return a.e < b.e;
    }
    return a.s < b.s;
}
node cows[N];

int solve(int n) {
    int maxH = 1;
    cows[1].stall = 1;
    RNode node;
    node.first = cows[1].e;
    node.second = maxH;
    q.push(node);
    for(int i = 2; i <= n; i++) {
        if(cows[i].s <= q.top().first) {
            maxH++;
            RNode node;
            node.first = cows[i].e;
            node.second = maxH;
            q.push(node);
            cows[i].stall = maxH;
        } else {
            int house = q.top().second;
            cows[i].stall = house;
            q.pop();
            RNode node;
            node.first = cows[i].e;
            node.second = house;
            q.push(node);
        }
    }
    return maxH;
}

int main() {
    while(scanf("%d", &n) != EOF) {
        int res[n];
        for(int i = 1;i <= n; i++) {
            scanf("%d%d", &cows[i].s, &cows[i].e);
            cows[i].tag = i;
        }
        sort(cows + 1, cows + n + 1, cmp);
        // for(int i = 1; i <= n; i++) {
        //     printf("%d %d %d\n", cows[i].s, cows[i].e, cows[i].tag);
        // }
        int maxH = solve(n);
        printf("%d\n", maxH);
        for(int i = 1; i <= n; i++) {
            res[cows[i].tag] = cows[i].stall;
        }
        for(int i = 1; i <= n; i++) {
            printf("%d\n",res[i]);
        }
        while(!q.empty()) {
            q.pop();
        }
    }
    
}

大致思路：先按照起始时间对奶牛进行排序，这里需要注意因为疏忽的时候是按照原来奶牛的顺序，所以需要记录下奶牛的编号，即使在排序之后也依然能够按照顺序输出

然后创建一个优先队列，按照结束时间创建的一个小根堆，每次给一头奶牛安排stall的时候，就先判断小根堆的top()的时间是否小于当前奶牛的起始时间，如果小于，则说明该房间已经空出来了，可以安排该奶牛，如果大于，则表明当前所有的stash都已经满了，需要重新建造一个stash来放这头奶牛。

最后按照编号顺序输出他们的stash号码。

优先队列（priority_queue）

基本操作

1
2
3
4
5
6
7
top			// 访问队头元素 
empty		// 队列是否为空
size		// 返回队列内元素个数
push		// 插入元素到队尾(并排序)
emplace 	// 原地构造一个元素并插入队列
pop			// 弹出队头元素
swap		// 交换内容

定义

priority_queue<Type, Container, Functional>

  • Type就是数据类型
  • Container就是容器类型(Container必须是用数组实现的容器，比如vector，deque等等，但不能用list。STL里面默认是vector)
  • Functional就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
1
2
3
4
// 升序队列
priority_queue<int, vector<int>, greater<int> > q;
// 降序队列
priority_queue<int, vector<int>, less<int> > q;

基本类型例子

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
// 基本类型
int main() {
    // 对于基础类型，默认是大顶堆
    priority_queue<int> a;
    // 等同于 priority_queue<int, vector<int>, greater<int> > a;

    // 这样就是小顶堆
    priority_queue<int, vector<int>, greater<int> > c;  
    priority_queue<string> b;

    for(int i = 0; i < 5; i++) {
        a.push(i);
        c.push(i);
    }
    while(!a.empty()) {
        cout << a.top() << " ";
        a.pop();
    }
    cout << endl;

    while(!c.empty()) {
        cout << c.top() << " ";
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while(!b.empty()) {
        cout << b.top() << " ";
        b.pop();        
    }
    cout << endl;
    return 0;   
}
/*
输出：
4 3 2 1 0
0 1 2 3 4
cbd abcd abc
*/

pair（先比较第一个元素，第一个相等再比较第二个元素）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(b);
    a.push(c);
    a.push(d);
    while(!a.empty()) {
        cout << a.top().first << " " << a.top().second << endl;
        a.pop();
    }
    return 0;
}
/*
输出：
2 5
1 3
1 2
*/

对于自定义类型

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
// 方法1, 运算符重载
struct node {
    int x;
    node(int a) {
        x = a;
    }
    bool operator < (const node &a) const {
        return x < a.x;
    } 
};

// 方法2, 重写仿函数
struct cmp {
    bool operator() (node a, node b) {
        return a.x < b.x;   // 大顶堆
    }
};

int main() {
    node a(1);
    node b(2);
    node c(3);
    priority_queue<node> q;
    q.push(a);
    q.push(b);
    q.push(c);
    while(!q.empty()) {
        cout << q.top().x << " ";
        q.pop();
    }
    cout << endl;

    priority_queue<node, vector<node>, cmp> f;
    f.push(a);
    f.push(b);
    f.push(c);
    while(!f.empty()) {
        cout << f.top().x << " ";
        f.pop();
    }
    cout << endl;
    return 0;
}
/*
输出：
3 2 1
3 2 1
*/