题型整理（5）

n点坐标求多边形面积

用计算几何的叉积解决

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
#include<iostream>
#include <cstdio>
using namespace std;
struct point{
    int x,y;
};
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n == 0)  break;
        point a[101];
        for(int i = 0;i < n;i++){
            cin >> a[i].x;
            cin >> a[i].y;
        }
        double ans = 0;
        for(int i = 2;i < n;i++){
            int x1 = a[i-1].x - a[0].x,y1 = a[i-1].y - a[0].y;
            int x2 = a[i].x - a[0].x,y2 = a[i].y - a[0].y;
            ans += 1.0 / 2.0 * (x1*y2 - x2*y1);
        }
        printf("%.1lf\n",ans);
    }
    return 0;
}

单调队列

滑动窗口/最大m段连续子序列和

可以用dp或者单调队列来写，这里使用数组模拟队列

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
#include<bits/stdc++.h>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n,k,mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
void getmin() {  // 滑动窗口最小值
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    //printf("%d ", a[q[head]]);
    mn=min(mn,a[q[head]]);
  }
  printf("%d\n",mn);
}
void getmax() {  //滑动窗口最大值 
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    //printf("%d ", a[q[head]]);
    mx=max(mx,a[q[head]]);
  }
  printf("%d\n",mx);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  getmin();
  getmax();
  return 0;
}

st表

q次询问a数组[l,r]区间最大值减最小值

st表模板题

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
#include <bits/stdc++.h>
#define MAXN 50005
using namespace std;
int read()
{
    int ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        ans = ans * 10 + c - '0';
        c = getchar();
    }
    return ans;
}
int Log2[MAXN], Min[MAXN][17], Max[MAXN][17];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
    {
        int x = read();
        Min[i][0] = x;
        Max[i][0] = x;
    }
    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
    for (int i = 1; i <= 16; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);
        }
    for (int i = 0; i < m; ++i)
    {
        int l = read(), r = read();
        int s = Log2[r - l + 1];
        int ma = max(Max[l][s], Max[r - (1 << s) + 1][s]);
        int mi = min(Min[l][s], Min[r - (1 << s) + 1][s]);
        printf("%d\n", ma - mi);
    }
    return 0;
}