Hướng dẫn giải của Bedao Regular Contest 05 - SQRSUM
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Code mẫu
#include <bits/stdc++.h> using namespace std; #define fo(i, a, b) for(int i = a; i <= b; i++) #define _fo(i, a, b) for(int i = a; i >= b; i--) #define foa(i, a) for (auto &i : a) #define sz(a) ((int) a.size()) #define all(a) begin(a), end(a) #define fi first #define se second #define pb(x) push_back(x) #define mk(x, y) make_pair(x, y) typedef unsigned long long ull; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vl; typedef pair<int, int> pii; typedef vector<int> vi; const int MAX = 1e5+5; const int LOG = 20; const ll MOD = 1e9+7; const ll INF = 1e15+5; const int SQRT = 44721; int n, m, q; vector<vector<ll>> mat, pref; vector<vector<vector<ll>>> ver, hor, corner_1, corner_2; vector<pii> color[MAX]; ll rect(int x1, int y1, int x2, int y2) { return pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1]; } void precompute() { fo(i, 1, n) { fo(j, 1, m) { pref[i][j] = mat[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]; } } fo(i, 1, n) { fo(j, 1, m) { int temp = min(i, j); ver[i][j].assign(temp+1, 0); if(temp > 1) ver[i][j][1] = rect(i-1, j-1, i, j); fo(k, 2, temp-1) ver[i][j][k] = rect(i-k, j-k, i, j)-rect(i-k+1, j-k+1, i-1, j-1)+ver[i][j][k-1]+ver[i-1][j-1][k-1]-ver[i-1][j-1][k-2]; } } // corner_1 fo(i, 1, n) { fo(j, 1, m) { int temp = min(i, j); corner_1[i][j].assign(temp, 0); fo(k, 1, temp-1) corner_1[i][j][k] = ver[i][j][k]+corner_1[i][j-1][k-1]; } } // corner_2 fo(i, 1, n) { fo(j, 1, m) { int temp = min(i, j); corner_2[i][j].assign(temp, 0); fo(k, 1, temp-1) corner_2[i][j][k] = ver[i][j][k]+corner_2[i-1][j][k-1]; } } //hor fo(i, 1, n) { fo(j, 1, m) { int temp = min(i, j); hor[i][j].assign(temp+1, 0); fo(k, 1, temp-1) hor[i][j][k] = ver[i][j][k]+hor[i][j-1][k]; } } //ver fo(i, 1, n) { fo(j, 1, m) { int temp = min(i, j); fo(k, 1, temp-1) ver[i][j][k] = ver[i][j][k]+ver[i-1][j][k]; } } } ll get(int c1, int c2) { ll res = 0; foa(p1, color[c1]) { foa(p2, color[c2]) { int x1 = min(p1.fi, p2.fi), y1 = min(p1.se, p2.se), x2 = max(p1.fi, p2.fi), y2 = max(p1.se, p2.se); int dx = x2-x1, dy = y2-y1; if(dx == 0 || dy == 0) continue; if(dx < dy) { x1 += dx; y1 += dx; res ^= hor[x2][y2][dx]-hor[x1][y1-1][dx]+corner_1[x1][y1-1][dx-1]+corner_2[x2-1][y2][dx-1]; } else { x1 += dy; y1 += dy; res ^= ver[x2][y2][dy]-ver[x1-1][y1][dy]+corner_2[x1-1][y1][dy-1]+corner_1[x2][y2-1][dy-1]; } } } return res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("SQRSUM.INP", "r", stdin); // freopen("SQRSUM.OUT", "w", stdout); cin >> n >> m >> q; mat.assign(n+1, vector<ll>(m+1, 0)); pref.assign(n+1, vector<ll>(m+1, 0)); ver.assign(n+1, vector<vector<ll>>(m+1, vector<ll>())); hor.assign(n+1, vector<vector<ll>>(m+1, vector<ll>())); corner_1.assign(n+1, vector<vector<ll>>(m+1, vector<ll>())); corner_2.assign(n+1, vector<vector<ll>>(m+1, vector<ll>())); fo(i, 1, n) { fo(j, 1, m) { cin >> mat[i][j]; } } fo(i, 1, n) { fo(j, 1, m) { int c; cin >> c; color[c].pb(mk(i, j)); } } precompute(); while(q--) { int c1, c2; cin >> c1 >> c2; cout << get(c1, c2) << "\n"; } } /* 3 3 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 2 3 4 5 6 7 8 9 1 9 */
Bình luận