GXOI2019 题解

GXOI2019 题解

#include#defineusing namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch - '0'), ch = getchar(); return cnt * f;}typedef long long ll;cs int N = 1e3 + 5;int a[N][N], b[N][N];int n, h[N], sta[N];cs int Mod = 1e9 + 7;int mul(int a, int b){ return 1ll * a * b % Mod; }void Add(ll &a, ll b){ a += b; if(a >= Mod) a -= Mod; }ll calc(int typ){ memset(h, 0, sizeof(h)); ll sum = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(b[i][j] ^ typ) h[j] = 0; else ++h[j]; } int top = 0; ll ret = 0; for(int j = 1; j <= n; j++){ while(top && h[j] < h[sta[top]]){ Add(ret, Mod - mul(h[sta[top]] - h[j], sta[top] - sta[top - 1])); top--; } sta[++top] = j; ret += h[j]; Add(sum, ret); } } return sum;}int main(){ n = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = read(); ll ret = n * (n + 1) / 2; ll Ans1 = 0, Ans2 = 0; for(int k = 0; k < 32; k++){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) b[i][j] = a[i][j] >> k & 1; ll Or = (ret * ret - calc(0) + Mod) % Mod; ll And = calc(1); Add(Ans1, mul(And, 1 << k)); Add(Ans2, mul(Or, 1 << k)); } cout << Ans1 << " " << Ans2; return 0;}

#include#defineusing namespace std;typedef long long ll;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch - '0'), ch = getchar(); return cnt * f;}cs int N = 40;int a[N]; // 剩余牌数 int val[N]; // 宝牌ll ans;ll dp[N][5][5][3][3][2];int T;int c[5][5] = { 1, 0, 0, 0, 0,1, 1, 0, 0, 0,1, 2, 1, 0, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1};void Mx(ll &a, ll b){ if(a < b) a = b;}int ps[N] = {1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34};void Yolanda(){ // 枚举哪一个牌选两张 for(int i = 0; i < 13; i++){ ll sum = 1; for(int j = 0; j < 13; j++){ if(j == i) sum *= c[a[ps[j]]][2] * val[ps[j]] * val[ps[j]]; else sum *= a[ps[j]] * val[ps[j]]; } ans = max(ans, sum * 13); } }int value[N]; // 七连对 void FSY(){ int ret = 0; for(int i = 1; i <= 34; i++) if(a[i] >= 2) value[++ret] = c[a[i]][2] * val[i] * val[i]; if(ret >= 7){ ll sum = 1; sort(value + 1, value + ret + 1); for(int i = ret; i > ret - 7; i--) sum = sum * value[i]; Mx(ans, sum * 7); }}bool tail[N];void DP(){ dp[1][0][0][0][0][0] = 1; for(int i = 1; i <= 34; i++){ for(int j = 0; j <= 4; j++){ // j 个面子 for(int k = 0; k <= 4; k++){ // i 用了多少 for(int l = 0; l <= 2; l++){ for(int r = 0; r <= 2; r++){ ll *x = dp[i][j][k][l][r]; if(!x[0] && !x[1]) continue; if(a[i] - k >= 2){ // 雀头 Mx(dp[i][j][k + 2][l][r][1], x[0] / c[a[i]][k] * c[a[i]][k + 2] * val[i] * val[i]) ; } if(j < 4){ if(a[i] - k >= 3){ // 刻子 for(int t = 0; t < 2; t++) Mx(dp[i][j + 1][k + 3][l][r][t], x[t] / c[a[i]][k] * c[a[i]][k + 3] * (val[i]*val[i]*val[i])); } if((!tail[i]) && a[i] - k > 0 && a[i + 1] - l > 0 && a[i + 2] - r > 0 && (l^2) && (r^2)){ // 顺子 for(int t = 0; t < 2; t++){ Mx(dp[i][j + 1][k + 1][l + 1][r + 1][t], x[t] / c[a[i]][k] * c[a[i]][k+1] * val[i] / c[a[i + 1]][l] * c[a[i + 1]][l + 1] * val[i + 1] / c[a[i + 2]][r] * c[a[i + 2]][r + 1] * val[i + 2] ); } } } Mx(dp[i + 1][j][l][r][0][0], x[0]); Mx(dp[i + 1][j][l][r][0][1], x[1]); if(j == 4) Mx(ans, x[1]); } } } } }} void Solve(){ tail[8] = tail[9] = tail[17] = tail[18] = tail[26] = tail[27] = tail[28] = tail[29] = tail[30] = tail[31] = tail[32] = tail[33] = tail[34] = 1; while(1){ char c[3]; scanf("%s", c); if(c[0] == '0') break; if(c[1] == 'm') a[c[0] - '0']--; if(c[1] == 's') a[c[0] - '0' + 9]--; if(c[1] == 'p') a[c[0] - '0' + 18]--; if(c[0] == 'E') a[28]--; if(c[0] == 'S') a[29]--; if(c[0] == 'W') a[30]--; if(c[0] == 'N') a[31]--; if(c[0] == 'Z') a[32]--; if(c[0] == 'B') a[33]--; if(c[0] == 'F') a[34]--; } while(1){ char c[3]; scanf("%s", c); if(c[0] == '0') break; if(c[1] == 'm') val[c[0] - '0'] = 2; if(c[1] == 's') val[c[0] - '0' + 9] = 2; if(c[1] == 'p') val[c[0] - '0' + 18] = 2; if(c[0] == 'E') val[28] = 2; if(c[0] == 'S') val[29] = 2; if(c[0] == 'W') val[30] = 2; if(c[0] == 'N') val[31] = 2; if(c[0] == 'Z') val[32] = 2; if(c[0] == 'B') val[33] = 2; if(c[0] == 'F') val[34] = 2; } Yolanda(); // 国士无双 FSY(); // 七连对 DP(); // 3 * 4 + 2 cout << ans << '\n';}void Init(){ ans = 0; for(int i = 1; i <= 34; i++) a[i] = 4, val[i] = 1; memset(dp, 0, sizeof(dp));} int main(){ T = read(); while(T--) Init(), Solve(); return 0;}

#include#defineusing namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch - '0'), ch = getchar(); return cnt * f;}typedef long long ll;typedef long double ld;cs int N = 1e5 + 5, M = 5e5 + 5, K = 7e5 + 5;int n, k; ll a, b, c;int Xs, Xe;int y[N][2], tp[N];bool cmp(int a, int b){ return y[a][1] < y[b][1];}struct P{ ld x, y; P(ld _x = 0, ld _y = 0){ x = _x, y = _y; } P operator + (cs P &a){ return P(x+a.x, y+a.y); } P operator - (cs P &a){ return P(x-a.x, y-a.y); } P operator * (ld k){ return P(x * k, y * k);}}p[M], q[N]; int ret;struct Line{ P a, b; }L[N];P Getpos(Line u, Line v){ ld d1 = u.a.y - v.a.y, d2 = u.b.y - v.b.y; if(d1 < 0) d1 = -d1; if(d2 < 0) d2 = -d2; ld k = 1.0 * d1 / (d1 + d2); return u.a + ((u.b - u.a) * k);} struct node{ int id, h; node(int i = 0, int _h = 0){ id = i; h = _h; } bool operator < (cs node &a) cs{ return h < a.h;}};multiset S;typedef multiset::iterator Int;ll ans1, ans2;int fa[N];int find(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]);}int r[N];ld Dx[K], Dy[K]; int sx, sy;struct que{ int l, r, op; };vector v[K]; vector u[K]; #definestruct BIT{ int c[K]; void add(int x,int v){ for(;x<=sy;x+=x&-x) c[x] += v; } int ask(int x){ int ans = 0; for(;x;x-=x&-x) ans += c[x]; return ans; }}bit;int Solve(){ ll sum = 0; for(int i = 1; i <= ret; i++){ ld x = p[i].x, y = p[i].y; p[i].x = x + y; p[i].y = x - y; Dx[++sx] = p[i].x; Dy[++sy] = p[i].y; } for(int i = 1; i <= k; i++){ Dx[++sx] = q[i].x - r[i]; Dx[++sx] = q[i].x + r[i]; Dy[++sy] = q[i].y - r[i]; Dy[++sy] = q[i].y + r[i]; } sort(Dx + 1, Dx + sx + 1); sort(Dy + 1, Dy + sy + 1); sx = unique(Dx + 1, Dx + sx + 1) - (Dx + 1); sy = unique(Dy + 1, Dy + sy + 1) - (Dy + 1); for(int i = 1; i <= ret; i++){ int x = lower_bound(Dx + 1, Dx + sx + 1, p[i].x) - Dx; int y = lower_bound(Dy + 1, Dy + sy + 1, p[i].y) - Dy; u[x].pb(y); } for(int i = 1; i <= k; i++){ int lx = lower_bound(Dx + 1, Dx + sx + 1, q[i].x - r[i]) - Dx; int rx = lower_bound(Dx + 1, Dx + sx + 1, q[i].x + r[i]) - Dx; int ly = lower_bound(Dy + 1, Dy + sy + 1, q[i].y - r[i]) - Dy; int ry = lower_bound(Dy + 1, Dy + sy + 1, q[i].y + r[i]) - Dy; v[lx].pb((que){ly, ry, 1}); v[rx + 1].pb((que){ly, ry, -1}); } for(int i = 1; i <= sx; i++){ for(int j = 0; j < v[i].size(); j++){ que nx = v[i][j]; bit.add(nx.l, nx.op); bit.add(nx.r + 1, - nx.op); } for(int j = 0; j < u[i].size(); j++) sum += bit.ask(u[i][j]) > 0; } return sum;}int main(){ n = read(), a = read(), b = read(), c = read(), Xs = read(), Xe = read(); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= n; i++) y[i][0] = read(); for(int i = 1; i <= n; i++) y[i][1] = read(), tp[i] = i; sort(tp + 1, tp + n + 1, cmp); for(int i = 1; i <= n; i++){ int fx = find(i), fy = find(tp[i]); if(fx ^ fy) fa[fx] = fy; } for(int i = 1; i <= n; i++) L[i] = (Line){P(Xs, y[i][0]), P(Xe, y[i][1])}; for(int i = 1; i <= n; i++){ Int it = S.lower_bound(node(i, y[i][1])); for(;it != S.end(); it++){ p[++ret] = Getpos(L[it->id], L[i]); } S.insert(node(i, y[i][1])); } ans1 = ret * a; int cnt = 0; for(int i = 1; i <= n; i++) cnt += (find(i) == i); ans2 = (n - cnt) * a + (ret - (n - cnt)) * b; k = read(); for(int i = 1; i <= k; i++){ int x = read(), y = read(); r[i] = read(); q[i] = P(x + y, x - y); } ll sum = 1ll * Solve() * c; if(ans1 > ans2) swap(ans1, ans2); cout << ans1 + sum << " " << ans2 + sum; return 0;}

#include#defineusing namespace std;cs int Mod = 1000000007;int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }int mul(int a, int b){ return 1ll * a * b % Mod; }int T, n;cs int N = 5;struct matrix{ int a[N][N]; matrix(){ memset(a, 0, sizeof(a)); } matrix operator * (cs matrix &A){ matrix B; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) for(int k = 0; k < N; k++) B.a[i][j] = add(B.a[i][j], mul(a[i][k], A.a[k][j])); return B; }}I, TR, ST;matrix power(matrix A, int b){ matrix ans = I; for(;b;b>>=1, A=A*A) if(b&1) ans = ans*A; return ans;}int main(){ scanf("%d", &T); TR.a[0][0] = 1; TR.a[0][1] = 1; TR.a[1][0] = 1; TR.a[2][0] = 2; TR.a[2][2] = 1; TR.a[2][3] = 1; TR.a[3][2] = 1; TR.a[4][0] = Mod-2; TR.a[4][4] = 1; ST.a[0][0] = 2; ST.a[0][1] = 0; ST.a[0][2] = 3; ST.a[0][3] = 2; ST.a[0][4] = 1; for(int i = 0; i < N; i++) I.a[i][i] = 1; while(T--){ scanf("%d", &n); if(n <= 2){ puts("0"); continue; } matrix A = TR, B = ST; B = B * power(A, n - 3); cout << B.a[0][0] << '\n'; } return 0;}

#include#define#define#define#defineusing namespace std;int read(){ int cnt = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt;}int first[N], nxt[M], to[M], w[M], tot;void add(int x, int y, int z){ nxt[++tot] = first[x], first[x] = tot; to[tot] = y, w[tot] = z;}int T, n, m, k, a[N];struct Node{ int x, y, z;} E[M];LL dis[N][2]; int col[N][2];void Dijsktra(int id){ priority_queue > q; for(int i=1; i<=n; i++) dis[i][id] = inf, col[i][id] = 0; for(int i=1; i<=k; i++){ col[a[i]][id] = a[i], dis[a[i]][id] = 0; q.push(make_pair(-dis[a[i]][id], a[i])); } while(!q.empty()){ int x = q-().second; q.pop(); for(int i=first[x];i;i=nxt[i]){ int t = to[i]; if(dis[t][id] > dis[x][id] + w[i]){ dis[t][id] = dis[x][id] + w[i]; col[t][id] = col[x][id]; q.push(make_pair(-dis[t][id], t)); } } } }int main(){ T = read(); while(T--){ n = read(), m = read(), k = read(); for(int i=1; i<=n; i++) first[i] = 0; tot = 0; for(int i=1; i<=m; i++){ int x = read(), y = read(), z = read(); if(x ^ y) add(x, y, z); E[i] = (Node){x, y, z}; } for(int i=1; i<=k; i++) a[i] = read(); Dijsktra(0); for(int i=1; i<=n; i++) first[i] = 0; tot = 0; for(int i=1; i<=m; i++){ if(E[i].y ^ E[i].x) add(E[i].y, E[i].x, E[i].z); } Dijsktra(1); LL ans = inf; for(int i=1; i<=m; i++){ int x = E[i].x, y = E[i].y, z = E[i].z; if(col[x][0] && col[y][1] && col[x][0] != col[y][1]) ans = min(ans, dis[x][0] + dis[y][1] + (LL)z); } printf("%lld\n",ans); } return 0;}

#include#defineusing namespace std;cs int Mod = 998244353;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch - '0'), ch = getchar(); return cnt * f;}cs int N = 5e4 + 5;int n, m, k;int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }int mul(int a, int b){ return 1ll * a * b % Mod; }void Add(int &a, int b){ a = add(a, b); }int ksm(int a, int b){ int ans = 1; for(;b;b>>=1, a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; }vector v[N];int fa[N], dep[N], top[N], siz[N], son[N], in[N], sign;int a[N], pw[N];typedef pair pi;#defineint ans[N];vector q[N];namespace seg{ int sum[N << 2], val[N << 2], tg[N << 2]; #define void ins(int x, int l, int r, int p, int v){ Add(sum[x],v); if(l == r) return; if(p <= mid) ins(x<<1, l, mid, p, v); else ins(x<<1|1, mid+1, r, p, v); } void pushup(int x){ val[x] = add(val[x<<1], val[x<<1|1]);} void pushnow(int x, int v){ Add(val[x], mul(v, sum[x])); Add(tg[x], v); } void pushdown(int x){ if(tg[x]) pushnow(x<<1, tg[x]), pushnow(x<<1|1, tg[x]), tg[x] = 0; } void modify(int x, int l, int r, int L, int R, int v){ if(L<=l && r<=R){ pushnow(x, v); return; } pushdown(x); if(L<=mid) modify(x<<1, l, mid, L, R, v); if(R>mid) modify(x<<1|1, mid+1, r, L, R, v); pushup(x); } int query(int x, int l, int r, int L, int R){ if(L<=l && r<=R) return val[x]; pushdown(x); int ans = 0; if(L<=mid) Add(ans, query(x<<1, l, mid, L, R)); if(R>mid) Add(ans, query(x<<1|1, mid+1, r, L, R)); return ans; }}void dfs(int u){ siz[u] = 1; for(int i = 0; i < v[u].size(); i++){ int t = v[u][i]; dep[t] = dep[u] + 1; fa[t] = u; a[t] = add(pw[dep[t]], Mod - pw[dep[u]]); dfs(t); siz[u] += siz[t]; if(siz[son[u]] > siz[t]) son[u] = t; }}void dfs2(int u, int tp){ top[u] = tp; in[u] = ++sign; seg::ins(1,1,n,in[u],a[u]); if(son[u]) dfs2(son[u], tp); for(int i = 0; i < v[u].size(); i++) if(v[u][i]^son[u]) dfs2(v[u][i], v[u][i]);}void modify(int x){ while(x){ seg::modify(1,1,n,in[top[x]],in[x],1); x=fa[top[x]]; } }int ask(int x){ int ans=0; while(x){ Add(ans,seg::query(1,1,n,in[top[x]],in[x])); x=fa[top[x]];} return ans; }int main(){ n = read(), m = read(), k = read(); for(int i = 1; i <= n; i++) pw[i] = ksm(i, k); for(int i = 2; i <= n; i++){ int x = read(); v[x].push_back(i); } dep[1] = a[1] = 1; dfs(1); dfs2(1, 1); for(int i = 1; i <= m; i++){ int x = read(), y = read(); q[x].push_back(mp(y, i)); } for(int i = 1; i <= n; i++){ modify(i); for(int j = 0; j < q[i].size(); j++){ int x = q[i][j].first; ans[q[i][j].second] = ask(x); } } for(int i = 1; i <= m; i++) cout << ans[i] << '\n'; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。