WuTao's Blog

题目链接：

AcWing
牛客

题目描述

输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。
例如 1,-3,5,1,-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6

题目链接：POJ 2823

Problem Description

An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position	Minimum value	Maximum value
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

Your task is to determine the maximum and minimum values in the sliding window at each position.

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps = 1e-10;  // 误差
const db pi = acos(-1.0);  // 圆周率
const ll inf = 0x3f3f3f3f3f3f3f3f;  // 无穷大
const ll maxn = 1e5 + 10;

// 精度三态函数
inline int dcmp(db x) {
    if(fabs(x) < eps) return 0;
    return x > 0? 1: -1;
}

class Point {
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}  // 构造器
    // 输入
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    // 一般用于排序
    bool operator<(const Point &a) const {
        return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x;
    }
    // 判断点的坐标是否相同
    bool operator==(const Point &a) const {
        return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
    }
    // 点到点的距离的平方
    db dis2(const Point a) {
        return pow(x - a.x, 2) + pow(y - a.y, 2);
    }
    // 点到点的距离
    db dis(const Point a) {
        return sqrt(dis2(a));
    }

    // 向量的模的平方
    db dis2() {
        return x * x + y * y;
    }
    // 向量的模
    db dis() {
        return sqrt(dis2());
    }
    // 向量加法
    Point operator+(const Point a) {
        return Point(x + a.x, y + a.y);
    }
    // 向量减法
    Point operator-(const Point a) {
        return Point(x - a.x, y - a.y);
    }
    // 向量数乘
    Point operator*(double p) {
        return Point(x * p, y * p);
    }
    // 向量数除
    Point operator/(double p) {
        return Point(x / p, y / p);
    }
    // 向量点积
    db dot(const Point a) {
        return x * a.x + y * a.y;
    }
    // 向量叉积
    db cross(const Point a) {
        return x * a.y - y * a.x;
    }
    // 向量与 a 向量的夹角
    db ang(Point a) {
        return acos((a.dis() * dis()) / dot(a));
    }
    // 向量在 b 向量上的投影
    db projection(Point b) {
        if(dcmp(dis()) == 0) return 0;
        if(dcmp(b.dis()) == 0) return dis();
        return cos(ang(b)) * dis();
    }
    // 向量逆时针旋转 rad 弧度
    Point Rotate(double rad) {
        return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }

};
typedef Point Vector;

class Line {
public:
    Point s, e;
    Line(Point s, Point e) : s(s), e(e) {}
    // 点 p 在有向线段 se 的左边返回 1, 右边返回 -1
    int toLeftTest(Point p) {
        if((e - s).cross(p - s) > 0) return 1;
        else if((e - s).cross(p - s) < 0) return -1;
        return 0;
    }
    // 直线与直线位置关系 0-重合 1-平行 2-相交
    int linecrossline (Line l) {
        if(dcmp((e - s).cross(l.e - l.s)) == 0) {
            if(dcmp((l.s - e).cross(l.e - s)) == 0) {
                return 0;
            }
            return 1;
        }
        return 2;
    }
    // 直线与直线交点
    Point crosspoint(Line l) {
		double a1 = (l.e - l.s).cross(s - l.s);
		double a2 = (l.e - l.s).cross(e - l.s);
        double x = (s.x * a2 - e.x * a1) / (a2 - a1);
        double y = (s.y * a2 - e.y * a1) / (a2 - a1);
        if(dcmp(x) == 0) x = 0;
        if(dcmp(y) == 0) y = 0;
		return Point(x, y);
	}
};

// 凸包
typedef vector<Point> Polygon;
Polygon Andrew(vector<Point> p) {
    int n = p.size(), cnt = 0;
    Polygon ans(2 * n);
    sort(p.begin(), p.end());
    for (int i = 0; i < n; ++i) {
        while (cnt >= 2 && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i] - ans[cnt - 2]) < eps) {
            --cnt;
        }
        ans[cnt++] = p[i];
    }
    int t = cnt + 1;
    for (int i = n - 1; i > 0; --i) {
        while (cnt >= t && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i - 1] - ans[cnt - 2]) < eps) {
            --cnt;
        }
        ans[cnt++] = p[i - 1];
    }
    ans.resize(cnt - 1);
    return ans;
}

// 判断点在线段上
bool OnSegment(Point p, Point a1, Point a2) {
    return dcmp((a1 - p).cross(a2 - p)) == 0 && dcmp((a1 - p).dot(a2 - p)) < 0;
}

// 判断线段相交
bool Intersection(Point a1, Point a2, Point b1, Point b2) {
    double c1 = (a2 - a1).cross(b1 - a1), c2 = (a2 - a1).cross(b2 - a1),
            c3 = (b2 - b1).cross(a1 - b1), c4 = (b2 - b1).cross(a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

// 判断点在凸包内
int isPointInPolygon(Point p, vector<Point> s) {
    int wn = 0, cc = s.size();
    for (int i = 0; i < cc; i++) {
        Point p1 = s[i];
        Point p2 = s[(i + 1) % cc];
        if (p1 == p || p2 == p || OnSegment(p, p1, p2)) return -1;
        int k = dcmp((p2 - p1).cross(p - p1));
        int d1 = dcmp(p1.y - p.y);
        int d2 = dcmp(p2.y - p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1;
    return 0;
}

// 凸包面积
double PolygonArea(Polygon p) {
    double ans = 0;
    for(int i = 2; i < p.size() - 1; ++i) {
        ans += abs((p[i] - p[1]).cross(p[i + 1] - p[1]));
    }
    return ans * 0.5;
}

(更新中)

题目链接：POJ 1265

Problem Description

Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new research and development facility the company has installed the latest system of surveillance robots patrolling the area. These robots move along the walls of the facility and report suspicious observations to the central security office. The only flaw in the system a competitor抯 agent could find is the fact that the robots radio their movements unencrypted. Not being able to find out more, the agent wants to use that information to calculate the exact size of the area occupied by the new facility. It is public knowledge that all the corners of the building are situated on a rectangular grid and that only straight walls are used. Figure 1 shows the course of a robot around an example area.

Figure 1: Example area.

You are hired to write a program that calculates the area occupied by the new facility from the movements of a robot along its walls. You can assume that this area is a polygon with corners on a rectangular grid. However, your boss insists that you use a formula he is so proud to have found somewhere. The formula relates the number I of grid points inside the polygon, the number E of grid points on the edges, and the total area A of the polygon. Unfortunately, you have lost the sheet on which he had written down that simple formula for you, so your first task is to find the formula yourself.

题目链接：POJ 3264

Problem Description

For the daily milking, Farmer John’s $N$ cows $(1 \le N \le 50,000)$ always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of $Q (1 \le Q \le 200,000)$ potential groups of cows and their $heights (1 \le height \le 1,000,000)$. For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

题目链接：HDU 5443

Problem Description

In Land waterless, water is a very limited resource. People always fight for the biggest source of water. Given a sequence of water sources with $a_1,a_2,a_3,…,a_n$ representing the size of the water source. Given a set of queries each containing $2$ integers $l$ and $r$, please find out the biggest water source between $a_l$ and $a_r$.

Codeforces Round #384 (Div. 2)

题目链接：Vladik and fractions

Vladik and Chloe decided to determine who of them is better at math. Vladik claimed that for any positive integer $n$ he can represent fraction $\frac{2}{n}$ as a sum of three distinct positive fractions in form $\frac{1}{m}$.

Help Vladik with that, i.e for a given $n$ find three distinct positive integers $x, y$ and $z$ such that $\frac{2}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$. Because Chloe can’t check Vladik’s answer if the numbers are large, he asks you to print numbers not exceeding $10^9$.

If there is no such answer, print $-1$.

题目链接：

洛谷

BZOJ

题意

给定 $n$ 个矿石，每个矿石有编号和魔力值两种属性，选择一些矿石，使得魔力值最大且编号的异或和不为 0。

Codeforces Round #198 (Div. 2)

题目链接：Maximal Area Quadrilateral

Iahub has drawn a set of $n$ points in the cartesian plane which he calls “special points”. A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn’t have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

比赛链接：Codeforces Round #572 (Div. 2)

官方题解：Editorial of Codeforces Round #572