题目地址
注意该题不能从外面绕
判断两点是否可以消去
消去可能是可以直接一条横线连,也可能是一个折的线或者是二个折的线
我用的方法,可以同时全部考虑进去
假设A,B是两个要判断是否消去的点,如果两点数字不同,或者都为0,当然不能消去
否则计算出A,B两点向四个方向能延伸到多远
以
1 2 3 4
0 0 0 0
4 3 2 1
为例
如果A=(1,1),B=(3,4)(坐标从1开始)
那么A按上右下左的顺序能延伸的范围是1, 1, 2, 1
B按上右下左的顺序能延伸的范围是2, 4, 3, 4
即向上下的话,是记录其纵坐标的范围,左右的话是记录横坐标的范围
现在先来判断上下是否连接,
那么先得出A,B两者左右延伸的公共范围,易知A左右延伸为(1,1),B为(4,4)故其没有公共范围
再来判断左右是否连接
那么先得出A,B两者上下延伸的公共范围,易知A上下延伸为(1,2),B为(2,3)故其公共范围为(2,2)
遍历纵坐标为(2,2)中的所有数且横坐标为A的横坐标的点,看每个点左右延伸范围是否有包括B点,如果有则可以消去
注意到两点刚好邻接的情况,应该将延伸范围左右扩大1
例如
1 1
这个明显可以消去,但如果按延伸范围是否包括的话,则为不能消去,所以必须加1,注意到代码注释的地方
#include <iostream>
using namespace std;
int a[1001][1001], h, w;
const int dh[] = {-1, 0, 1, 0};
const int dw[] = {0, 1, 0, -1};
struct Point {
int h, w;
int dir[4];
} st, en;
void cal(Point v, int *p) {
Point tmp;
for(int i = 0; i < 4; ++i) {
tmp = v;
do {
tmp.h += dh[i];
tmp.w += dw[i];
} while(tmp.h >= 0 && tmp.h < h && tmp.w >= 0 && tmp.w < w && a[tmp.h][tmp.w] == 0);
tmp.h -= dh[i];
tmp.w -= dw[i];
p[i] = ((i&1) ? tmp.w : tmp.h);
}
}
void cal1(Point v, int *p, int i) {
Point tmp;
tmp = v;
do {
tmp.h += dh[i];
tmp.w += dw[i];
} while(tmp.h >= 0 && tmp.h < h && tmp.w >= 0 && tmp.w < w && a[tmp.h][tmp.w] == 0);
tmp.h -= dh[i];
tmp.w -= dw[i];
p[i] = ((i&1) ? tmp.w : tmp.h);
}
bool solve() {
if(a[st.h][st.w] == 0 || a[st.h][st.w] != a[en.h][en.w]) return false;
int mmin, mmax;
cal(st, st.dir);
cal(en, en.dir);
Point a1 = st, a2 = en;
if(a1.w > a2.w) swap(a1, a2);
mmin = max(a1.dir[0], a2.dir[0]);
mmax = min(a1.dir[2], a2.dir[2]);
Point tmp;
tmp.w = a1.w;
for(int i = mmin; i <= mmax; ++i) {
tmp.h = i;
cal1(tmp, tmp.dir, 1);
//这里必须加1,理由看开头注释
if(tmp.dir[1] + 1 >= a2.w) return true;
}
if(a1.h > a2.h) swap(a1, a2);
mmin = max(a1.dir[3], a2.dir[3]);
mmax = min(a1.dir[1], a2.dir[1]);
tmp.h = a1.h;
for(int i = mmin; i <= mmax; ++i) {
tmp.w = i;
cal1(tmp, tmp.dir, 2);
//这里必须加1,理由看开头注释
if(tmp.dir[2] + 1 >= a2.h) return true;
}
return false;
}
int main() {
int p;
while(scanf("%d%d", &h, &w)) {
if(h == 0 && w == 0) break;
for(int i = 0; i < h; ++i)
for(int j = 0; j < w; ++j)
scanf("%d", &a[i][j]);
scanf("%d", &p);
while(p--) {
scanf("%d%d%d%d", &st.h, &st.w, &en.h, &en.w);
st.h -= 1, st.w -= 1, en.h -= 1, en.w -= 1;
solve() ? puts("YES") : puts("NO");
}
}
return 0;
}
题目地址
给定一些矩形，求这些矩形围成的周长。（具体看题目的图）
很囧很囧，弄了我好多时间，，跟求矩形并的方法类似，但是加了判断结点覆盖的情况。
一开始，没有去掉y里重复的数值，而我在update时
if(nod[t].lf == e.y1 && nod[t].rf == e.y2) nod[t].cnt += e.f;
else {
if(e.y2 <= nod[t*2].rf) update(t*2, e);
else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
else {
Line tmp = e;
tmp.y2 = nod[t*2].rf, update(t*2, tmp);
tmp = e, tmp.y1 = nod[t*2+1].lf, update(t*2+1, tmp);
}
} 这种方法对于区间两端如果数值一样的话，是无法update到那个区间的，一个比较通用的方法是
if(e.y1 <= nod[t].lf && nod[t].rf <= e.y2) nod[t].cnt += e.f;
else if(nod[t].l + 1 != nod[t].r) {
int m = (nod[t].l+nod[t].r) / 2;
if(e.y1 < y[m]) update(t*2, e);
if(y[m] < e.y2) update(t*2+1, e);
} 这样即使数值一样，也可以。突然想到，貌似之前几道矩形并交的题都是使用上面的那种方法，貌似都没有出问题，其实是因为求矩形面积并时如果有端点一样的情况，访问到那里其数值也是为0,因为长度为0,而对于这题，由于需要判断端点是否重复覆盖，故一定要访问到，在端点有一样的情况下，第一种方法就不适用了。
不过最后我还是通过把y去重，这样结点数会变少许多,orz…
Meomry: 492K
Time: 15MS
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int maxn = 10001;
struct {
int l, r, lf, rf, ld, rd, cnt, len, lines;
}nod[maxn*3];
struct Line {
int x, y1, y2, f;
bool operator < (const Line &a) const {
return x < a.x || x == a.x && f > a.f;
}
}line[maxn];
int y[maxn];
void creat(int t, int l, int r) {
nod[t].cnt = nod[t].len = nod[t].ld = nod[t].rd = nod[t].lines = 0;
nod[t].l = l, nod[t].r = r, nod[t].lf = y[l], nod[t].rf = y[r];
if(l + 1 == r) return;
int m = (l+r) >> 1;
creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
nod[t].len = 0;
if(nod[t].cnt > 0) nod[t].len = nod[t].rf - nod[t].lf;
else if(nod[t].l + 1 != nod[t].r) nod[t].len = nod[t*2].len + nod[t*2+1].len;
}
void caline(int t) {
nod[t].ld = nod[t].rd = nod[t].lines = 0;
if(nod[t].cnt > 0) nod[t].ld = nod[t].rd = nod[t].lines = 1;
else if(nod[t].l + 1 != nod[t].r) nod[t].ld = nod[t*2].ld, nod[t].rd = nod[t*2+1].rd, nod[t].lines = nod[t*2].lines + nod[t*2+1].lines - (nod[t*2].rd & nod[t*2+1].ld);
}
void update(int t, Line e) {
if(nod[t].lf == e.y1 && nod[t].rf == e.y2) nod[t].cnt += e.f;
else {
if(e.y2 <= nod[t*2].rf) update(t*2, e);
else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
else {
Line tmp = e;
tmp.y2 = nod[t*2].rf, update(t*2, tmp);
tmp = e, tmp.y1 = nod[t*2+1].lf, update(t*2+1, tmp);
}
}
//if(e.y1 <= nod[t].lf && nod[t].rf <= e.y2) nod[t].cnt += e.f;
//else if(nod[t].l + 1 != nod[t].r) {
// int m = (nod[t].l+nod[t].r) / 2;
// if(e.y1 < y[m]) update(t*2, e);
// if(y[m] < e.y2) update(t*2+1, e);
//}
calen(t), caline(t);
}
int main() {
int n, x1, y1, x2, y2, i, t, s, preline, prelen, l;
while(scanf("%d", &n) != EOF) {
for(i = 0, t = 1; i < n; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
line[t].x = x1, line[t+1].x = x2;
line[t].y1 = line[t+1].y1 = y[t] = y1;
line[t].y2 = line[t+1].y2 = y[t+1] = y2;
line[t].f = 1, line[t+1].f = -1;
t += 2;
}
sort(line+1, line+t), sort(y+1, y+t);
for(i = 2, l = 2; i < t; i++) if(y[i] != y[i-1]) y[l++] = y[i];
creat(1, 1, l-1);
s = preline = prelen = 0;
for(i = 1; i < t; i++) {
update(1, line[i]);
s += abs(nod[1].len-prelen) + 2 * preline * (line[i].x - line[i-1].x);
prelen = nod[1].len, preline = nod[1].lines;
}
printf("%d\n", s);
}
return 0;
}
题目地址
题目要求覆盖大于等于二次以上的面积，其实就是求矩形面积的交集。
想法跟1542的差不多，加了个重复测度
Memory: 492K
Time: 343MS
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 2001
struct {
int c, l, r;
double cnt, recnt, lf, rf;
}nod[MAXN*3];
struct Line {
double x, y1, y2;
int f;
}line[MAXN];
bool cmp(Line a, Line b) {
return a.x < b.x;
}
double y[MAXN];
void creat(int t, int l, int r) {
nod[t].c = nod[t].cnt = nod[t].recnt = 0;
nod[t].l = l, nod[t].r = r;
nod[t].lf = y[l], nod[t].rf = y[r];
if(l + 1 == r) return;
int m = (l+r) / 2;
creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
if(nod[t].c > 0) {
nod[t].cnt = nod[t].rf - nod[t].lf;
return;
}
if(nod[t].l + 1 == nod[t].r) nod[t].cnt = 0;
else nod[t].cnt = nod[t*2].cnt + nod[t*2+1].cnt;
}
void carelen(int t) {
if(nod[t].c > 1) {
nod[t].recnt = nod[t].rf - nod[t].lf;
return;
}
if(nod[t].l + 1 == nod[t].r) nod[t].recnt = 0;
else {
if(nod[t].c == 1) nod[t].recnt = nod[t*2].cnt + nod[t*2+1].cnt;
else nod[t].recnt = nod[t*2].recnt + nod[t*2+1].recnt;
}
}
void update(int t, Line e) {
if(e.y1 == nod[t].lf && e.y2 == nod[t].rf) {
nod[t].c += e.f;
calen(t);
carelen(t);
return;
}
if(e.y2 <= nod[t*2].rf) update(t*2, e);
else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
else {
Line tmp = e;
tmp.y2 = nod[t*2].rf;
update(t*2, tmp);
tmp = e;
tmp.y1 = nod[t*2+1].lf;
update(t*2+1, tmp);
}
calen(t);
carelen(t);
}
int main() {
int n, i, t, cases;
double x1, x2, y1, y2, ans;
scanf("%d", &cases);
while(cases--) {
scanf("%d", &n);
t = 1;
ans = 0;
for(i = 1; i <= n; i++) {
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[t].x = x1, line[t+1].x = x2;
line[t].y1 = line[t+1].y1 = y[t] = y1, line[t].y2 = line[t+1].y2 = y[t+1] = y2;
line[t].f = 1, line[t+1].f = -1;
t += 2;
}
sort(line+1, line+t, cmp), sort(y+1, y+t);
creat(1, 1, t-1);
update(1, line[1]);
for(i = 2; i < t; i++) {
ans += nod[1].recnt * (line[i].x - line[i-1].x);
update(1, line[i]);
}
printf("%.2lf\n", ans);
}
return 0;
}
题目地址
题目意思很简单，要求计算被矩形覆盖过的面积，即求矩形面积的并集
对顶点进行离散化，对顶点的Y坐标从小到大排序，然后以这些点建立线段树。结点存储该区间被完全覆盖的次数c,该区间的测试cnt,以及对Y坐标的映射。对于每一个X坐标，如果是线段的起点，则覆盖次数加1,代表线段开始，如果是线段的终点，则减1,代表该线段覆盖的范围已经结束
Memory: 248K
Time: 0MS
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 201
struct {
int c, l, r;
double cnt, lf, rf;
}nod[MAXN*3];
struct Line {
double x, y1, y2;
int f;
}line[MAXN];
bool cmp(Line a, Line b) {
return a.x < b.x;
}
double y[MAXN];
void creat(int t, int l, int r) {
nod[t].c = nod[t].cnt = 0;
nod[t].l = l, nod[t].r = r;
nod[t].lf = y[l], nod[t].rf = y[r];
if(l + 1 == r) return;
int m = (l+r) / 2;
creat(t*2, l, m), creat(t*2+1, m, r);
}
void calen(int t) {
if(nod[t].c > 0) {
nod[t].cnt = nod[t].rf - nod[t].lf;
return;
}
if(nod[t].l + 1 == nod[t].r) nod[t].cnt = 0;
else nod[t].cnt = nod[t*2].cnt + nod[t*2+1].cnt;
}
void update(int t, Line e) {
if(e.y1 == nod[t].lf && e.y2 == nod[t].rf) {
nod[t].c += e.f;
calen(t);
return;
}
if(e.y2 <= nod[t*2].rf) update(t*2, e);
else if(e.y1 >= nod[t*2+1].lf) update(t*2+1, e);
else {
Line tmp = e;
tmp.y2 = nod[t*2].rf;
update(t*2, tmp);
tmp = e;
tmp.y1 = nod[t*2+1].lf;
update(t*2+1, tmp);
}
calen(t);
}
int main() {
int n, i, t, cases = 1;
double x1, x2, y1, y2, ans;
while(scanf("%d", &n), n) {
t = 1;
ans = 0;
for(i = 1; i <= n; i++) {
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[t].x = x1, line[t+1].x = x2;
line[t].y1 = line[t+1].y1 = y[t] = y1, line[t].y2 = line[t+1].y2 = y[t+1] = y2;
line[t].f = 1, line[t+1].f = -1;
t += 2;
}
sort(line+1, line+t, cmp), sort(y+1, y+t);
creat(1, 1, t-1);
update(1, line[1]);
for(i = 2; i < t; i++) {
ans += nod[1].cnt * (line[i].x - line[i-1].x);
update(1, line[i]);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", cases++, ans);
}
return 0;
}
题目地址
询问区间最值，并执行某个点的变更操作
没什么好说的，线段树的入门基础题。
Memory: 7148K
Time: 468MS
#include <iostream>
using namespace std;
inline int Max(int a, int b){return a > b ? a : b;}
const int MAXN = 200001;
struct {
int l, r, m;
} nod[MAXN*3];
int a[MAXN];
void creat(int t, int l, int r) {
nod[t].l = l, nod[t].r = r;
if(l == r) {nod[t].m = a[l]; return;}
int m = (l+r) / 2;
creat(t*2, l, m), creat(t*2+1, m+1, r);
nod[t].m = Max(nod[t*2].m, nod[t*2+1].m);
}
int query(int t, int l, int r) {
if(l == nod[t].l && r == nod[t].r) return nod[t].m;
int s;
if(r <= nod[t*2].r) s = query(t*2, l, r);
else if(l >= nod[t*2+1].l) s= query(t*2+1, l, r);
else s = Max(query(t*2, l, nod[t*2].r), query(t*2+1, nod[t*2+1].l, r));
return s;
}
void update(int t, int n, int v) {
if(nod[t].l == nod[t].r && nod[t].l == n) {nod[t].m = v; return;}
if(n <= nod[t*2].r) update(t*2, n, v);
else update(t*2+1, n, v);
nod[t].m = Max(nod[t*2].m, nod[t*2+1].m);
}
int main() {
int n, m, i, x1, x2;
char s[2];
while(scanf("%d%d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
creat(1, 1, n);
while(m--) {
scanf("%s%d%d", s, &x1, &x2);
if(s[0] == 'Q') printf("%d\n", query(1, x1, x2));
else update(1, x1, x2);
}
}
return 0;
}
题目地址
给一组棍子染色，不同的颜色有不同的值，执行一系列的区间染色后，问这组棍子的总值是多少。
每个线段树的结点，存储该结点所代表区间的染色状况c，如果该区间全为同样的颜色，则用一个正数表示，如果含有多种颜色，则用-1表示，每次执行染色操作时，如果所要染的颜色与区间颜色一样，则停止，如果所要染区间跟当前结点区间一致，则直接将所要染颜色赋给当前结点的c,否则，如果当前结点区间不是混合色，则先将当前结点的颜色赋给左右子结点的c,并递归下去。
Memory: 3284k
Time: 406MS
#include <iostream>
using namespace std;
const int MAXN = 100001;
struct {
int l, r, c;
} nod[MAXN*3];
void creat(int t, int l, int r) {
nod[t].l = l, nod[t].r = r, nod[t].c = 1;
if(l == r) return;
int m = (l+r) / 2;
creat(t*2, l, m), creat(t*2+1, m+1, r);
}
void color(int t, int l, int r, int c) {
if(c == nod[t].c) return;
if(l == nod[t].l && r == nod[t].r) {nod[t].c = c; return;}
if(nod[t].c != -1) nod[t*2].c = nod[t*2+1].c = nod[t].c;
nod[t].c = -1;
if(r <= nod[t*2].r) color(t*2, l, r, c);
else if(l >= nod[t*2+1].l) color(t*2+1, l, r, c);
else color(t*2, l, nod[t*2].r, c), color(t*2+1, nod[t*2+1].l, r, c);
}
int count(int t, int l, int r) {
if(nod[t].c > 0) return (r-l+1) * nod[t].c;
return count(t*2, l, nod[t*2].r) + count(t*2+1, nod[t*2+1].l, r);
}
int main() {
int cases, n, q, x1, x2, c, t = 1;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &q);
creat(1, 1, n);
while(q--) {scanf("%d%d%d", &x1, &x2, &c); color(1, x1, x2, c);}
int aa;
printf("Case %d: The total value of the hook is %d.\n", t++, count(1, 1, n));
}
return 0;
}
题目地址
题目大意是，给定n个数，每次选择2个数（取出后不放回），求出两数之差的平方，累加，选k对(k<=n/2),问最终累加之和最小为多少
先对n个数排序，因为结果要求最小，那么每次择时，只能选择相邻的两个数，只有这样，最终的差才可能最小，构造dp[i][j],代表从1到n个物品中选择k对，那么状态转移方程为
dp[i][j]=Min{dp[i-2][j-1]+a[i-1],dp[i-1][j]}
其中a[i-1]存放的是第i与第i-1个数的差的平方。
#include <iostream>
#include <algorithm>
using namespace std;
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define INF 2100000000
int dp[2001][1001];
int main() {
int i, j, n, k, a[2001];
while(scanf("%d%d", &n, &k) != EOF) {
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+1+n);
for(i = 1; i < n; i++) a[i] = (a[i]-a[i+1]) * (a[i]-a[i+1]);
for(i = 0; i <= n; i++)
for(j = 1; j <= k; j++)
dp[i][j] = INF;
for(i = 0; i <= n; i++) dp[i][0] = 0;
for(i = 2; i <= n; i++)
for(j = 1; j * 2 <= i; j++)
dp[i][j] = Min(dp[i-2][j-1]+a[i-1], dp[i-1][j]);
printf("%d\n", dp[n][k]);
}
return 0;
}
Recent Comments