[BZOJ 2338] [HNOI 2011] 数矩形

本题两个关键点:

1. 找到四个能构成矩形的点

这一步有一个巧妙的做法:因对角线长度相等且互相平分的四边形为矩形,故可以将给定的点两两连为线段——若两条线段长度相等且中点相同,则这两条线段的四个顶点能构成一个矩形

2. 计算过程中保持精度

可以发现,在计算过程中可能导致精度损失的地方只有计算线段长度时的 sqrt() 与计算中点时的 / 2. 。这个好办——因为只需要长度与中点位置的相对值,所以存长度时不需要开方,中点坐标也不需要除以 2 了。

具体实现过程只需要对各条线段按长度与中点进行排序(保证长度中点均相同的线段落在连续区间),对每条线段向前枚举其他所有长度中点均相同的线段(并不会超时......),用叉积计算面积更新答案即可。

Reference:

http://blog.csdn.net/PoPoQQQ/article/details/39995729

代码如下:

继续阅读[BZOJ 2338] [HNOI 2011] 数矩形

BZOJ【2338】画矩形

这题要求找出一个最大面积的矩形,学过数学的都知道:矩形对角线交于一点,而且两条对角线相等。于是我们就可以枚举每一条线段,按长度排序,取长度相等的判断他们的中点是否重合,重合的话就可以构成一个矩形。

按照上面的方法,枚举线段要n^2, 排序要n^2log(n^2),所以时间大概为O(n^2log(n^2))。

但是这题的数据有10^8,如果用两点之间距离公式和中点公式有可能被卡精度,于是可以在求距离是不开根号,直接用long long存,中点公式也不除2,这样可以避免精度的影响。

最后,在求面积时用叉积求即可。

3165糖果

简化下题意就给你k个不等式,让你求出大于0的最小解。

对于不等式a <= b,则a+q <=b+q。所以只要求出一组解,再找到其中的最小值min,用所以解减去min-1即可得出答案


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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<climits>
 
using namespace std;
 
const int N = 100010;
 
struct nod
{
    int a, b, v;
}p[2 * N];
 
struct node
{
    long long v;
    int begin, end;
    node()
    {
        v = INT_MAX;
        begin = INT_MAX;
        end = 0;
    }
}f[N];
 
int n, k, b[N], un_find[N], fuck;
 
bool com(nod a, nod b)
{
    return a.a < b.a;
}
 
void find(int num)
{
    int no;
    if (n == 17 * 5) fuck = -1;
    for (int i = 1;i <= num; i++)
    {
        no = p[i].a;
        f[no].begin = min(f[no].begin, i);
        f[no].end = max(f[no].end, i);
    }
}
 
queue<int> q;
 
int work(int i)
{
    int now = p[i].a, next = p[i].b;
    if (p[i].v == 1)
    {
        if (f[now].v == f[next].v) return 0;
        f[next].v = f[now].v;
        return 1;
    }
    if (p[i].v == 2)
    {
        if (f[now].v < f[next].v) return 0;
        f[next].v = f[now].v + 1;
        return 1;
    }
    if (p[i].v == 5)
    {
        if (f[now].v <= f[next].v) return 0;
        f[next].v = f[now].v;
        return 1;
    }
    return 0;
}
 
void spfa(int t)
{
    b[t] = 1;
    q.push(t);
    while (!q.empty())
    {
        t = q.front();
        un_find[t] = 1;
        for (int i = f[t].begin;i <= f[t].end; i++)
        {
            if (work(i) && !b[p[i].b])
            {
                b[p[i].b] = 1;
                q.push(p[i].b);
            }
        }
        q.pop();
        b[t] = 0;
    }
}
 
void Ans()
{
    long long Min = INT_MAX;
    long long ans = 0;
    for (int i = 1;i <= n; i++)
        Min = min(Min, f[i].v);
    for (int i = 1;i <= n; i++)
        ans += f[i].v - Min + 1;
    cout << ans << endl;
}
 
void change(int i)
{
    int num = p[i].a;
    p[i].a = p[i].b;
    p[i].b = num;
}
 
int main(void)
{
    //freopen("candy.in","r",stdin);
   // freopen("candy.out","w",stdout);
   
    cin >> n >> k;
    int ans = 0, num = k;
    for (int i = 1;i <= k; i++)
    {
       scanf("%d%d%d", &p[i].v, &p[i].a, &p[i].b);
       if ((p[i].v == 2 || p[i].v == 4) && p[i].a == p[i].b)
            ans = -1;
        if (p[i].v == 4)
        {
            change(i);
            p[i].v = 2;
        }
        if (p[i].v == 3)
        {
            change(i);
            p[i].v = 5;
        }
        if (p[i].v == 1)
        {
            p[++num].v = 1;
            p[num].a = p[i].b;
            p[num].b = p[i].a;
        }
    }
    sort(p + 1, p + 1 + num, com);
    find(num);
    if (ans || fuck)
    {
       if (fuck) ans = fuck;
       cout << ans << endl;
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    for (int i = 1;i <= n; i++)
       if (!un_find[i])
           spfa(i);
    Ans();
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}

保持题库与本地间文件读写的一致性的技巧

在本地编程与题库提交时,我常常会遇到这么一种情况:因为我习惯在本地使用文件读写调试,但题库不允许文件读写,所以常常由于忘了注释文件读写而 RTE。在把题库上的代码复制至本地后又要删去注释。这么来来回回倒腾实在把我烦得不行。

继续阅读保持题库与本地间文件读写的一致性的技巧

某对比数据批处理生成器

[Description]

你是否还在为常见的批处理生成器不能自动处理数据点个数(10 还是 20?)与数据点起始位置(0 还是 1?)而苦恼?

出于发自内心的懒,我决定一劳永逸地解决这个问题......于是重写了一个批处理生成器——一个能自动检测数据点个数与起始位置的批处理文件。

而你所需要的,只是在运行窗口中输入该题文件名,轻敲 Enter 而已。

继续阅读某对比数据批处理生成器

【BZOJ3624】免费道路

这题大意是有n个点, 给你m条边,其中有一些是水泥路,另一些是鹅卵石路。让你取n-1条边,其中要有k条鹅卵石路,使它成为一棵生成树。

因为有两种路,所以肯定要有几条边是一定要取得,那就先将所有水泥路连边,接着再做生成树,则需要加的边肯定是在答案中的。

这时再判断必定要取的鹅卵石路是否大于k,若大于k则无答案。接着只要将剩下的点做生成树即可