http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4438
题解：
std
C++版本一：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;
const int maxn = 1e3 + 100, maxm = 1e6 + 100, mod = 1000000007;
typedef long long ll;
typedef pair<int, int> P;
ll s[maxn][maxn];
int n, m;
ll x[maxn][maxn], y[maxn][maxn];
void solve(){
memset(x, 0,sizeof x);
memset(y, 0,sizeof y);
scanf("%d%d", &n, &m);
for(int i=0; i<m; ++i)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x[x1+1][y1] += 1;
x[x2+1][y1] += -1;
x[x2+1][y1] += -(x2 - x1);
x[x2+2][y1] += (x2 - x1);
x[x1+1][y2+1] -= 1;
x[x2+1][y2+1] -= -1;
x[x2+1][y2+1] -= -(x2 - x1);
x[x2+2][y2+1] -= (x2 - x1);
y[x1][y1+1] += 1;
y[x1][y2+1] += -1;
y[x1][y2+1] += -(y2 - y1);
y[x1][y2+2] += (y2 - y1);
y[x2+1][y1+1] -= 1;
y[x2+1][y2+1] -= -1;
y[x2+1][y2+1] -= -(y2 - y1);
y[x2+1][y2+2] -= (y2 - y1);
}
for(int t=0; t<2; ++t)
for(int j=1; j<=n; ++j)
for(int i=1; i<=n; ++i)
x[i][j] += x[i-1][j];
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
x[i][j] += x[i][j-1];
for(int t=0; t<2; ++t)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
y[i][j] += y[i][j-1];
for(int j=1; j<=n; ++j)
for(int i=1; i<=n; ++i)
y[i][j] += y[i-1][j];
ll ans = 1;
bool flag = false;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(x[i][j]+y[i][j]) ans = (ans * (x[i][j]+y[i][j]))%mod, flag = true;
if(flag)
cout << ans << endl;
else puts("0");
}
char fre[10] = "data1.in";
char fot[20] = "check1.out";
int main()
{
solve();
// int T = 6;
// for(int cas = 1; cas <= T; ++cas){
// fre[4] = ('0' + cas);
// fot[5] = ('0' + cas);
// freopen(fre, "r", stdin);
//// freopen(fot, "w", stdout);
// solve();
// }
return 0;
}
C++版本二
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
char fre[10] = "data1.in";
char fot[20] = "data1.out";
int tot[N][N];
int sum[N][N];
void solve(){
int n, m, u, l, d, r;
scanf("%d%d", &n, &m);
memset(tot, 0, sizeof tot);
memset(sum, 0, sizeof sum);
for(int i = 1; i <= m; ++i){
scanf("%d%d%d%d", &u, &l, &d, &r);
sum[u][l] += (u + l);
sum[u][r + 1] -= (u + l);
sum[d + 1][l] -= (u + l);
sum[d + 1][r + 1] += (u + l);
tot[u][l] ++;
tot[u][r + 1] --;
tot[d + 1][l] --;
tot[d + 1][r + 1] ++;
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
sum[i][j] += sum[i][j - 1];
tot[i][j] += tot[i][j - 1];
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
sum[i][j] += sum[i - 1][j];
tot[i][j] += tot[i - 1][j];
}
}
LL ans = 1, now = 0;
bool flag = false;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
now = tot[i][j] * (i + j) - sum[i][j];
// sum[i][j] = 0, tot[i][j] = 0;
if(now) ans = ans * now % mod, flag = true;
}
}
if(!flag) ans = 0;
printf("%I64d\n", ans);
}
int main()
{
solve();
// int T = 6;
// for(int cas = 1; cas <= T; ++cas){
// fre[4] = ('0' + cas);
// fot[4] = ('0' + cas);
// freopen(fre, "r", stdin);
// freopen(fot, "w", stdout);
// solve();
// }
return 0;
}
/*
419683495
775697741
996935516
391348459
0
797953655
*/
C++版本三
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#define RI register int
using namespace std;
typedef long long ll;
int t,n,m;
const int maxn = 1000+10, mod = 1000000007;
typedef pair<int, int> P;
ll s[maxn][maxn];
ll x[maxn][maxn], y[maxn][maxn];
int main()
{
scanf("%d%d",&n,&m);
for(RI i=0; i<m; ++i){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x[x1+1][y1] ++;
x[x2+1][y1] --;
x[x2+1][y1] += -(x2 - x1);
x[x2+2][y1] += (x2 - x1);
x[x1+1][y2+1] --;
x[x2+1][y2+1] ++;
x[x2+1][y2+1] -= -(x2 - x1);
x[x2+2][y2+1] -= (x2 - x1);
y[x1][y1+1] ++;
y[x1][y2+1] --;
y[x1][y2+1] += -(y2 - y1);
y[x1][y2+2] += (y2 - y1);
y[x2+1][y1+1] --;
y[x2+1][y2+1] ++;
y[x2+1][y2+1] -= -(y2 - y1);
y[x2+1][y2+2] -= (y2 - y1);
}
for(RI t=0; t<2; ++t)
for(RI j=1; j<=n; ++j)
for(RI i=1; i<=n; ++i)
x[i][j] += x[i-1][j],y[j][i] += y[j][i-1];
for(RI i=1; i<=n; ++i)
for(RI j=1; j<=n; ++j)
x[i][j] += x[i][j-1],y[j][i] += y[j-1][i];
ll ans = 1;
bool flag = false;
for(RI i=1; i<=n; ++i)
for(RI j=1; j<=n; ++j)
if(x[i][j]+y[i][j])
ans = (ans * (x[i][j]+y[i][j]))%mod, flag = true;
if(flag)
cout << ans << endl;
else puts("0");
//cout << "Hello world!" << endl;
return 0;
}
C++版本四
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#define RI register int
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, m, u, l, d, r,t;
int tot[N][N];
int sum[N][N];
int main()
{
scanf("%d%d", &n, &m);
for(RI i = 1; i <= m; ++i){
scanf("%d%d%d%d", &u, &l, &d, &r);
t=u+l;
sum[u][l] += t;
sum[u][r + 1] -= t;
sum[d + 1][l] -= t;
sum[d + 1][r + 1] += t;
tot[u][l] ++;
tot[u][r + 1] --;
tot[d + 1][l] --;
tot[d + 1][r + 1] ++;
}
for(RI i = 1; i <= n; ++i){
for(RI j = 1; j <= n; ++j){
sum[i][j] += sum[i][j - 1];
tot[i][j] += tot[i][j - 1];
}
for(RI j = 1; j <= n; ++j){
sum[i][j] += sum[i - 1][j];
tot[i][j] += tot[i - 1][j];
}
}
LL ans = 1, now = 0;
bool flag = false;
for(RI i = 1; i <= n; ++i){
for(RI j = 1; j <= n; ++j){
now = tot[i][j] * (i + j) - sum[i][j];
if(now) ans = ans * now % mod, flag = true;
}
}
if(!flag) ans = 0;
printf("%lld\n", ans);
//cout << "Hello world!" << endl;
return 0;
}
C++版本五
追求更快40ms
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#define RI register int
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, m, u, l, d, r,t;
int tot[N][N];
int sum[N][N];
namespace IO {
const int MT = 116 * 1024 * 1024;
char IO_BUF[MT];
int IO_PTR, IO_SZ;
void begin() {
IO_PTR = 0;
IO_SZ = fread (IO_BUF, 1, MT, stdin);
}
template<typename T>
inline bool scan_d (T & t) {
while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))
IO_PTR ++;
if (IO_PTR >= IO_SZ) return false;
bool sgn = false;
if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;
for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)
t = t * 10 + IO_BUF[IO_PTR] - '0';
if (sgn) t = -t;
return true;
}
inline bool scan_s (char s[]) {
while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] == ' ' || IO_BUF[IO_PTR] == '\n') ) IO_PTR ++;
if (IO_PTR >= IO_SZ) return false;
int len = 0;
while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != ' ' && IO_BUF[IO_PTR] != '\n')
s[len ++] = IO_BUF[IO_PTR], IO_PTR ++;
s[len] = '\0';
return true;
}
template<typename T>
void print(T x) {
static char s[33], *s1; s1 = s;
if (!x) *s1++ = '0';
if (x < 0) putchar('-'), x = -x;
while(x) *s1++ = (x % 10 + '0'), x /= 10;
while(s1-- != s) putchar(*s1);
}
template<typename T>
void println(T x) {
print(x); putchar('\n');
}
};
using namespace IO;
int main()
{
begin();
//scanf("%d%d", &n, &m);
scan_d(n);
scan_d(m);
for(RI i = 1; i <= m; ++i){
//scanf("%d%d%d%d", &u, &l, &d, &r);
scan_d(u);
scan_d(l);
scan_d(d);
scan_d(r);
t=u+l;
sum[u][l] += t;
sum[u][r + 1] -= t;
sum[d + 1][l] -= t;
sum[d + 1][r + 1] += t;
tot[u][l] ++;
tot[u][r + 1] --;
tot[d + 1][l] --;
tot[d + 1][r + 1] ++;
}
for(RI i = 1; i <= n; ++i){
for(RI j = 1; j <= n; ++j){
sum[i][j] += sum[i][j - 1];
tot[i][j] += tot[i][j - 1];
}
for(RI j = 1; j <= n; ++j){
sum[i][j] += sum[i - 1][j];
tot[i][j] += tot[i - 1][j];
}
}
LL ans = 1, now = 0;
bool flag = false;
for(RI i = 1; i <= n; ++i){
for(RI j = 1; j <= n; ++j){
now = tot[i][j] * (i + j) - sum[i][j];
if(now) ans = ans * now % mod, flag = true;
}
}
if(!flag) ans = 0;
//printf("%lld\n", ans);
print(ans);
//cout << "Hello world!" << endl;
return 0;
}
C++版本六
最简版本
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#define RI register int
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, m, u, l, d, r,t;
int tot[N][N];
int sum[N][N];
int main()
{
scanf("%d%d", &n, &m);
for(RI i = 1; i <= m; ++i){
scanf("%d%d%d%d", &u, &l, &d, &r);
t=u+l;
sum[u][l] += t;
sum[u][r + 1] -= t;
sum[d + 1][l] -= t;
sum[d + 1][r + 1] += t;
tot[u][l] ++;
tot[u][r + 1] --;
tot[d + 1][l] --;
tot[d + 1][r + 1] ++;
}
LL ans = 1, now = 0;
bool flag = false;
for(RI i = 1; i <= n; ++i){
for(RI j = 1; j <= n; ++j){
sum[i][j] += sum[i][j - 1]+sum[i - 1][j]-sum[i - 1][j-1];
tot[i][j] += tot[i][j - 1]+tot[i - 1][j]-tot[i - 1][j-1];
now = tot[i][j] * (i + j) - sum[i][j];
if(now) ans = ans * now % mod, flag = true;
}
}
if(!flag) ans = 0;
printf("%lld\n", ans);
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号