Editorial for VOI 13 Bài 1 - Phần thưởng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <utility> #include <vector> #include <cstdlib> using namespace std; const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; int k, a[10][10], E, used[10][10], flag[100]; long long ans, total; pair <int,int> e[100]; vector < pair<int,int> > c[10][10][4]; int inside(int x, int y) { return x > 0 && y > 0 && x < 9 && y < 9; } void init() { for (int x = 1; x <= 8; x++) for (int y = 1; y <= 8; y++) { for (int i = 0; i < 8; i++) { int xx = x + dx[i], yy = y + dy[i]; if (inside(xx, yy) && a[xx][yy]) c[x][y][0].push_back(make_pair(xx, yy)); } for (int xx = 1; xx <= 8; xx++) { int yy = x + y - xx; if (inside(xx, yy) && a[xx][yy]) c[x][y][1].push_back(make_pair(xx, yy)); yy = xx + y - x; if (inside(xx, yy) && a[xx][yy]) c[x][y][1].push_back(make_pair(xx, yy)); } for (int i = 1; i <= 8; i++) { if (a[i][y]) c[x][y][2].push_back(make_pair(i, y)); if (a[x][i]) c[x][y][2].push_back(make_pair(x, i)); } for (int z = 1; z < 3; z++) for (int i = 0; i < int(c[x][y][z].size()); i++) c[x][y][3].push_back(c[x][y][z][i]); } } void att(int z, long long score) { if (z == 4) { ans = max(ans, score); if (ans == total) { cout << ans << endl; exit(0); } return; } for (int i = 0; i < E; i++) if (!flag[i]) { flag[i] = 1; int x = e[i].first, y = e[i].second; for (int j = 0; j < int(c[x][y][z].size()); j++) { int xx = c[x][y][z][j].first, yy = c[x][y][z][j].second; if (!used[xx][yy]++) score += a[xx][yy]; } if (z + score) att(z + 1, score); for (int j = 0; j < int(c[x][y][z].size()); j++) { int xx = c[x][y][z][j].first, yy = c[x][y][z][j].second; if (!--used[xx][yy]) score -= a[xx][yy]; } flag[i] = 0; } } int main() { int x, y, z; cin >> k; for (int i = 0; i < k; i++) { cin >> x >> y >> z; a[x][y] = z; total += z; } init(); for (int i = 1; i <= 8; i++) for (int j = 1; j <= 8; j++) if (!a[i][j]) e[E++] = make_pair(i, j); att(0, 0); cout << ans << endl; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #include <climits> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int QUEEN = 1; const int ROOK = 2; const int BISHOP = 3; const int KNIGHT = 4; const int N = 20; const int gap = 8; const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2}; using namespace std; int nFree, nRes; LL ans; int val[N][N], cnt[N][N], cntX[N], cntY[N], cntDiag1[N], cntDiag2[N]; II freeCells[N * N], resCells[N * N]; void readInput() { ios :: sync_with_stdio(0); cin.tie(0); int k, u, v, c; cin >> k; FOR(i, 0, k) { cin >> u >> v >> c; val[u][v] = c; } REP(i, 1, 8) REP(j, 1, 8) if (val[i][j] == 0) freeCells[nFree++] = MP(i, j); else resCells[nRes++] = MP(i, j); } void update() { int x, y; LL sum = 0; FOR(i, 0, nRes) { x = resCells[i].X, y = resCells[i].Y; if (cnt[x][y] || cntX[x] || cntY[y] || cntDiag1[x + y] || cntDiag2[x - y + gap]) sum += val[x][y]; } ans = max(ans, sum); } void put(int type, int x, int y, int v) { if (type == QUEEN || type == ROOK) cntX[x] += v, cntY[y] += v; if (type == QUEEN || type == BISHOP) cntDiag1[x + y] += v, cntDiag2[x - y + gap] += v; if (type == KNIGHT) FOR(i, 0, 8) { x += dx[i]; y += dy[i]; if (0 < x && 0 < y && x < 9 && y < 9) cnt[x][y] += v; x -= dx[i]; y -= dy[i]; } } bool was[N * N]; void backtrack(int now) { if (now > 4) { update(); return; } FOR(i, 0, nFree) if (!was[i]) { was[i] = 1; put(now, freeCells[i].X, freeCells[i].Y, 1); backtrack(now + 1); was[i] = 0; put(now, freeCells[i].X, freeCells[i].Y, -1); } } int main() { readInput(); backtrack(1); cout << ans; return 0; }
Code mẫu của RR
#include <iostream> #include <cstdio> #include <vector> #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define REP(i,a) for(int i=0;i<(a);++i) #define sqr(x) ((x)*(x)) using namespace std; typedef pair<int,int> P; int id[10][10]; long long board[10][10], cur[10][10], res; int n, a[66], b[66], c[66], sum[66], diff[66], id2[66]; bool can[10][10][10][10]; int nGood; P good[66]; vector<P> ke[5][66]; const int di[] = {-2,-2,-1,-1,1,1,2,2}; const int dj[] = {-1,1,-2,2,-2,2,-1,1}; bool inside(int u, int v) { return (u > 0 && u < 9 && v > 0 && v < 9); } void init() { FOR(i,1,8) FOR(j,1,8) { // 1 : Knight REP(dir,8) { int u = i + di[dir], v = j + dj[dir]; if (inside(u,v)) ke[1][id[i][j]].push_back(make_pair(u, v)); } // 2 : Rook FOR(x,1,8) { ke[2][id[i][j]].push_back(make_pair(x, j)); ke[2][id[i][j]].push_back(make_pair(i, x)); } // 3 : Knight FOR(u,1,8) { int v = i + j - u; if (inside(u, v)) ke[3][id[i][j]].push_back(make_pair(u, v)); v = u - (i - j); if (inside(u, v)) ke[3][id[i][j]].push_back(make_pair(u, v)); } // 4 : Queen FOR(t,2,3) REP(x,ke[t][id[i][j]].size()) ke[4][id[i][j]].push_back(ke[t][id[i][j]][x]); } } bool mark[10][10]; void solve2() { FOR(i,1,n) { int a, b, c; scanf("%d%d%d", &a, &b, &c); board[a][b] += c; } FOR(i,1,8) FOR(j,1,8) { if (!board[i][j]) { good[++nGood] = make_pair(i,j); id[i][j] = nGood; } cur[i][j] = board[i][j]; } init(); res = 0; int u, v; FOR(knight_id,1,nGood) FOR(rook_id,1,nGood) if (rook_id != knight_id) FOR(bishop_id,1,nGood) if (bishop_id != knight_id && bishop_id != rook_id) FOR(queen_id,1,nGood) if (queen_id != knight_id && queen_id != rook_id && queen_id != bishop_id) { FOR(i,1,8) FOR(j,1,8) cur[i][j] = board[i][j]; long long now = 0; REP(x,ke[1][knight_id].size()) { u = ke[1][knight_id][x].first, v = ke[1][knight_id][x].second; now += cur[u][v]; cur[u][v] = 0; } REP(x,ke[2][rook_id].size()) { u = ke[2][rook_id][x].first, v = ke[2][rook_id][x].second; now += cur[u][v]; cur[u][v] = 0; } REP(x,ke[3][bishop_id].size()) { u = ke[3][bishop_id][x].first, v = ke[3][bishop_id][x].second; now += cur[u][v]; cur[u][v] = 0; } REP(x,ke[4][queen_id].size()) { u = ke[4][queen_id][x].first, v = ke[4][queen_id][x].second; now += cur[u][v]; cur[u][v] = 0; } res = max(res, now); } cout << res << endl; } void solve1() { for(int i = 1; i <= 8; ++i) for(int j = 1; j <= 8; ++j) for(int u = 1; u <= 8; ++u) for(int v = 1; v <= 8; ++v) can[i][j][u][v] = sqr(i-u) + sqr(j-v) == 5; for(int i = 1; i <= n; ++i) { scanf("%d%d%d", &a[i], &b[i], &c[i]); sum[i] = a[i] + b[i]; diff[i] = a[i] - b[i]; board[a[i]][b[i]] += c[i]; } long long res = 0, cur; for(int rooki = 1; rooki <= 8; ++rooki) for(int rookj = 1; rookj <= 8; ++rookj) if (!board[rooki][rookj]) { for(int bishopi = 1; bishopi <= 8; ++bishopi) for(int bishopj = 1; bishopj <= 8; ++bishopj) if (!board[bishopi][bishopj]) if (bishopi != rooki || bishopj != rookj) { int bishop_sum = bishopi + bishopj, bishop_diff = bishopi - bishopj; for(int queeni = 1; queeni <= 8; ++queeni) for(int queenj = 1; queenj <= 8; ++queenj) if (!board[queeni][queenj]) if (queeni != rooki || queenj != rookj) if (queeni != bishopi || queenj != bishopj) { int queen_sum = queeni + queenj, queen_diff = queeni - queenj; long long cursum = 0; int nId = 0; for(int i = 1; i <= n; ++i) { if (a[i] == rooki || b[i] == rookj || sum[i] == bishop_sum || diff[i] == bishop_diff || a[i] == queeni || b[i] == queenj || sum[i] == queen_sum || diff[i] == queen_diff) cursum += c[i]; else id2[++nId] = i; } for(int knighti = 1; knighti <= 8; ++knighti) for(int knightj = 1; knightj <= 8; ++knightj) if (!board[knighti][knightj]) if (knighti != rooki || knightj != rookj) if (knighti != bishopi || knightj != bishopj) if (knighti != queeni || knightj != queenj) { cur = 0; for(int i = 1; i <= nId; ++i) { if (can[knighti][knightj][a[id2[i]]][b[id2[i]]]) cur += c[id2[i]]; } res = max(res, cur + cursum); } } } } cout << res << endl; } int main() { scanf("%d", &n); if (n >= 30) { solve2(); } else solve1(); }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) //#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = {+2, +1, +2, +1, -2, -1, -2, -1}; const int dc[] = {+1, +2, -1, -2, +1, +2, -1, -2}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const ll mod = (ll)1e9 + 7; #define maxn 105 ull X[64], H[64], T[64], M[64]; ll f[64], d[64]; ull cal(int r, int c){ ull t = 1; t <<= (r * 8 + c); return t; } ull cal1(int r, int c){ int t = r * 8 + c; if(d[t] != -1) return ((ull)(1) << d[t]); return 0; } bool inside(int r, int c){ return r >= 0 && r < 8 && c >= 0 && c < 8; } void getX(int id){ int r = id / 8, c = id % 8; X[id] = 0; Rep(i, 8){ X[id] |= cal1(r, i); X[id] |= cal1(i, c); } } void getH(int id){ int r = id / 8, c = id % 8; H[id] = 0; Rep(i, 8){ H[id] |= cal1(r, i); H[id] |= cal1(i, c); } Rep(i, 8) Rep(j, 8){ if(i - j == r - c || i + j == r + c){ H[id] |= cal1(i, j); } } } void getT(int id){ int r = id / 8, c = id % 8; T[id] = 0; Rep(i, 8) Rep(j, 8){ if(i - j == r - c || i + j == r + c){ T[id] |= cal1(i, j); } } } void getM(int id){ int r = id / 8, c = id % 8; M[id] = 0; Rep(h, 8){ int rr = r + dr[h], cc = c + dc[h]; if(inside(rr, cc)){ M[id] |= cal1(rr, cc); } } } void init(){ Rep(i, 64){ getX(i); getH(i); getT(i); getM(i); } } ull mask; ll res = 0; int num, r, c, g; void go(int id, ull Mask, ull mask1){ if(id == 4){ if(Mask){ ll ret = 0; Rep(i, num) if(getbit(Mask, i)){ ret += f[i]; } res = max(res, ret); } return; } Rep(i, 64) if(!getbit(mask, i) && !getbit(mask1, i)){ ull Maskt = Mask, mask1t = mask1; mask1t |= ((ull)(1) << i); if(id == 0) Maskt |= X[i]; if(id == 1) Maskt |= H[i]; if(id == 2) Maskt |= T[i]; if(id == 3) Maskt |= M[i]; go(id + 1, Maskt, mask1t); } } int main() { // freopen("in.txt", "r", stdin); cin >> num; mask = 0; ms(f, 0); ms(d, -1); Rep(i, num){ cin >> r >> c >> g; r--; c--; int x = r * 8 + c; mask |= cal(r, c); d[x] = i; f[i] = g; } init(); go(0, 0, 0); cout << res << endl; // cout << clock() << endl; return 0; }
Comments