JZOJ 6944. 【2020.01.07冬令营模拟】球
题解
- 发现数据很良心，区间坐标都是非负数，避免了更多的分类讨论。
- 把区间拆开考虑， 发现在对角线
y
=
x
y=x
y=x两侧都满足每行/列分别单调，如果在某一侧框出一个矩形，可以用等差数列求和直接解决。
- 同时对角线上的可以用平方和计算，但对角边旁构不成矩形的部分如何解决？
- 又发现可以把对角线所经过部分框出一个正方形，分层后每一层都可以用一个最高次为三次的多项式求和计算，直接用立方和公式和平方和公式，那么这样剩下的部分都分居对角线两侧，用上述的方法。
- 至于模数，看似不能用自然溢出，其实并不然，因为
2
64
2^{64}
264是
2
63
2^{63}
263的倍数，所以可以自然溢出完再取模一次。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define md 9223372036854775808
ll read() {
ll s = 0;
char x = getchar();
while(x < '0' || x > '9') x = getchar();
while(x >= '0' && x <= '9') s = s * 10 + x - 48, x = getchar();
return s;
}
void write(ll x) {
if(x < 0) x += md;
if(x >= md) x -= md;
int c[25], l = 0;
if(x == 0) puts("0");
else {
while(x) c[++l] = x % 10, x /= 10;
while(l) putchar(c[l] + 48), l--;
puts("");
}
}
ll sq(ll x) {
ll t = x + 1, s = 2 * x + 1;
if(x % 2 == 0) x /= 2; else if(t % 2 == 0) t /= 2; else s /= 2;
if(x % 3 == 0) x /= 3; else if(t % 3 == 0) t /= 3; else s /= 3;
return x * s * t;
}
ll sum(ll fi, ll d, ll n) {
ll la = fi + d * (n - 1);
if(n % 2 == 0) return (fi + la) * (n / 2);
return (fi + la) / 2 * n;
}
ll ct(ll x) {
if(x < 0) return 0;
return sq(x) - sq(x / 2) * 4;
}
ll count(ll x, ll y) {
return ct(y) - ct(x - 2);
}
ll squ(ll x) {
if(x == 0) return 1;
ll s = sum(1, 1, (x * 2 + 1) * (x * 2 + 1));
ll r = sum(1, 1, x);
ll t = r * r * 24 + r * 6 - sq(x) * 4 - x;
return s - t;
}
ll solve(ll lx, ll rx, ll ly, ll ry) {
if(lx > ry) {
return sum(count(lx * 2 - 1, rx * 2 - 1) + sum(lx - ry, 1, rx - lx + 1), rx - lx + 1, ry - ly + 1);
}
if(rx < ly) {
return sum(count(ly * 2 + 1, ry * 2 + 1) - sum(ly - rx, 1, ry - ly + 1), -(ry - ly + 1), rx - lx + 1);
}
if(lx == ly) {
if(rx == ry) {
if(lx == 0) return squ(rx);
return squ(rx) - squ(lx - 1) - solve(lx, rx, 0, ly - 1) - solve(0, lx - 1, ly, ry);
}
else if(rx < ry) {
return solve(lx, rx, ly, rx) + solve(lx, rx, rx + 1, ry);
}
else if(ry < rx) {
return solve(lx, ry, ly, ry) + solve(ry + 1, rx, ly, ry);
}
}
else if(ly > lx) {
if(rx == ry) {
return solve(ly, rx, ly, ry) + solve(lx, ly - 1, ly, ry);
}
else if(rx < ry) {
return solve(ly, rx, ly, rx) + solve(lx, ly - 1, ly, ry) + solve(ly, rx, rx + 1, ry);
}
else if(ry < rx) {
return solve(ly, ry, ly, ry) + solve(lx, ly - 1, ly, ry) + solve(ry + 1, rx, ly, ry);
}
}
else if(lx > ly) {
if(rx == ry) {
return solve(lx, rx, lx, ry) + solve(lx, rx, ly, lx - 1);
}
else if(rx < ry) {
return solve(lx, rx, lx, rx) + solve(lx, rx, ly, lx - 1) + solve(lx, rx, rx + 1, ry);
}
else if(ry < rx) {
return solve(lx, ry, lx, ry) + solve(lx, rx, ly, lx - 1) + solve(ry + 1, rx, lx, ry);
}
}
}
int main() {
int Q = read();
while(Q--) {
ll lx = read(), rx = read(), ly = read(), ry = read();
write(solve(lx, rx, ly, ry));
}
return 0;
}
自我小结
- 比赛时想到了正解，但是因为一个字母写错和读入时没有开long long而爆零。
- 值得注意，写代码时避免惯性思维，因“手熟”而写错。
- 另外，内容比较对称的代码， 也可以对着检查，有错误容易查出。