本文共 7244 字,大约阅读时间需要 24 分钟。
题解:
std
C++版本一:
#include#include #include #include #include using namespace std;const int maxn = 1e3 + 100, maxm = 1e6 + 100, mod = 1000000007;typedef long long ll;typedef pair 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
C++版本二
#includeusing 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;}/*4196834957756977419969355163913484590797953655*/
C++版本三
/**@Author: STZG*@Language: C++*/#include#define RI register intusing namespace std;typedef long long ll;int t,n,m;const int maxn = 1000+10, mod = 1000000007;typedef pair P;ll s[maxn][maxn];ll x[maxn][maxn], y[maxn][maxn];int main(){ scanf("%d%d",&n,&m); for(RI i=0; i
C++版本四
/**@Author: STZG*@Language: C++*/#include#define RI register intusing 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#define RI register intusing 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 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 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 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#define RI register intusing 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;}
转载地址:http://oyzof.baihongyu.com/