2019 计蒜之道初赛第一场|2020 计蒜之道初赛第三场

xiaoxiao2024-12-07 74

文章目录

2019 计蒜之道预赛第一场A. 商汤的AI伴游小精灵B. 商汤AI园区的n个路口（简单）C. 商汤AI园区的n个路口（中等）D. 商汤AI园区的n个路口（困难） 2020 计蒜之道预赛第三场B. 石子游戏（简单）B. 石子游戏（中等）

2019 计蒜之道预赛第一场

题目链接：传送门

A. 商汤的AI伴游小精灵

数据范围：

n (5000)

首先这是一颗联通树，

O(n^2)

枚举删除的两个点，他们对答案的贡献是出度和若选择了一个根节点，贡献要减一；若两点相邻，贡献也要减一本题个人感觉不能

O (n)

写，很多人都是错误的写法，但是没被叉掉。。。 int main() { n = read(); for(int i = 1, a, b; i < n; ++i) { a = read(), b = read(); ar[a][b] = ar[b][a] = 1; ++ du[a]; } int ans = 1; for(int i = 1; i <= n; ++i) { int tmp = 1 + du[i]; if(i == 1) -- tmp; ans = max(ans, tmp); for(int j = i + 1; j <= n; ++j) { tmp = 1 + du[i] + du[j]; if(i == 1) -- tmp; if(ar[i][j]) -- tmp; ans = max(ans, tmp); } } printf("%d\n", ans); return 0; }

B. 商汤AI园区的n个路口（简单）

数据范围：

1\le n\le m\le 50

，且保证是一条链。

d p [i] [j]

表示第

i

个路口频段为

j

时，前

1 - i

的路段均合法的方案数。

O(nm^2)

转移即可，枚举路口

i

和

i - 1

的频段。答案是

\sum_{i=1}^{m} dp[n][i]

int main() { n = read(), m = read(); for(int i = 2,a ,b, c; i <= n; ++i) { a = read(), b = read(), c = read(); ar[b] = c; } for(int i = 1; i <= m; ++i) dp[1][i] = 1; for(int i = 2; i <= n; ++i) { for(int j = 1; j <= m; ++j) { for(int k = 1; k <= m; ++k) { if(__gcd(j, k) != ar[i]) dp[i][j] = (dp[i][j]+dp[i-1][k])%mod; } } } LL ans = 0; for(int i = 1; i <= m; ++i) ans = (ans + dp[n][i])%mod; printf("%lld\n", (ans+mod)%mod); return 0; }

C. 商汤AI园区的n个路口（中等）

题目和上面一样，数据范围： $1\le n\le m\le 1000$ ，是一颗树。

考虑树 $d p$ ， $d p [u] [i]$ 表示路口 $u$ 的频段是 $i$ 时， $u$ 的子树路线均合法的方案数

显然 $d p [u] [i]$ 的贡献是他所有儿子合法方案数的乘积。

然后你会发现固定 $x$ 满足 $gcd(x,y)=w,1\lt w$ 的 $y$ 不会超过 $l o g (m)$ 个

考虑链 $(u, v, w)$ ，计算 $d p [u] [i]$ ：先提前累加出 $\sum_{i=1}^m dp[v][i]$ 作为 $v$ 暂时的贡献，然后枚举 $w$ 的倍数 $j$ ，减去 $g c d (i, j) = w$ 的方案数即可。

复杂度： $O (n m l o g (m))$

$dp[u][j]=\prod_{v\in son(u)} \sum_{k=1}^m dp[v][k]-\sum_{k=1}^m[gcd(j,k)=w]dp[v][k]$

const int MXN = 1e3 + 7; const int mod = 1e9 + 7; int n, m; int ar[MXN]; LL dp[MXN][MXN]; std::vector<pii > mp[MXN]; void dfs(int u, int ba) { int ye = 1, fir = 1; for(auto x: mp[u]) { if(x.fi == ba) continue; ye = 0; dfs(x.fi, u); //debug(u, x.fi) LL all = 0; for(int i = 1; i <= m; ++i) all = (all+dp[x.fi][i])%mod; for(int i = 1; i <= m; ++i) { LL tmp = all; if(__gcd(i, x.se) == x.se) { for(int j = x.se; j <= m; j += x.se) { if(__gcd(j,i)==x.se) tmp -= dp[x.fi][j], tmp %= mod; } } if(fir) dp[u][i] = tmp; else dp[u][i] = tmp*dp[u][i]%mod; } if(fir) fir = 0; } if(ye) for(int i = 1; i <= m; ++i) dp[u][i] = 1; } int main() { #ifndef ONLINE_JUDGE freopen("E://ADpan//in.in", "r", stdin); //freopen("E://ADpan//out.out", "w", stdout); #endif n = read(), m = read(); for(int i = 2,a ,b, c; i <= n; ++i) { a = read(), b = read(), c = read(); mp[a].eb(mk(b, c)); mp[b].eb(mk(a, c)); } dfs(1, -1); LL ans = 0; for(int i = 1; i <= m; ++i) ans = (ans + dp[1][i]) % mod; printf("%lld\n", (ans+mod)%mod); return 0; }

D. 商汤AI园区的n个路口（困难）

题意：一颗树

1\le n\le m\le 100000

，边权

w(1\le w\le m)

各不相同，点权可取范围为

[1, w]

。要求

gcd(val_u, val_v)!=w_{uv}

，求合法的给每个点赋予权值的方案数。题解：莫比乌斯反演原始状态转移：

dp[u][j]=\prod_{v\in son(u)} \sum_{k=1}^m dp[v][k]-\sum_{k=1}^m[gcd(j,k)=w]dp[v][k]

令

illegal_j=\sum_{k=1}^m[gcd(j,k)=w]dp[v][k]=\sum_{k=1}^{\frac mw}[gcd(\frac jw,k)=1]dp[v][kw]

=\sum_{k=1}^{\frac mw}\sum_{d|gcd(\frac jw,k)}\mu(d)dp[v][kw]

=\sum_{d|\frac jw}\mu(d)\sum_{k=1}^{\frac mw}[d|gcd(\frac jw, k)]dp[v][kw]

=\sum_{d|\frac jw}\mu(d)\sum_{k=1}^{\frac m{wd}}dp[v][kwd]

但是大多数 $dp[u][j]=\sum dp[v]$ ，上述这种 $d p [u] [j]$ 数量不超过 $O (m l o g (m))$ ，用一个 $m a p$ 记即可。然后就枚举 $u$ 每一个儿子 $v$ 更新 $illdgal_j$ ：枚举 $d$ 然后枚举 $k$ ，再更新贡献到 $illegal_j$ ，复杂度： $O (m l o g (m))$ . 总体复杂度： $O(mlog^2(m))$ . 思路来源：rzO_KQP_Orz

AC_CODE here

const int MXN = 1e5 + 7; const int mod = 1e9 + 7; int n, m; int64 dp[MXN], ilg[MXN]; vector<pii > mp[MXN]; map<int, int64> ump[MXN];//保存受到影响的dp[u][j],最多只有O(mlog(m))个 bool noprime[MXN]; int pp[10004], pcnt, mu[MXN]; void init_prime() { noprime[0] = noprime[1] = 1; mu[1] = 1; for(int i = 2; i < MXN; ++i) { if(!noprime[i]) pp[pcnt++] = i, mu[i]=-1; for(int j = 0; j < pcnt && i*pp[j] < MXN; ++j) { noprime[i*pp[j]] = 1; mu[i*pp[j]] = -mu[i]; if(i % pp[j] == 0) { mu[i*pp[j]] = 0; break; } } } } int ksm(int a, int b, int Mod) { int res = 1; for (; b > 0; b >>= 1, a = (int64)a * a % Mod) { if (b & 1) res = (int64)res * a % Mod; } return res; } void upd(int64 &x) { if(x >= mod) x %= mod; else if(x < 0) x += mod; } void dfs(int u, int ba) { // debug(u, ba) int64 all = 1;//当前节点不考虑边权影响的方案数 for(auto x: mp[u]) { if(x.fi == ba) continue; dfs(x.fi, u); all = all * dp[x.fi]; upd(all); for(int d = 1, dv = x.se; dv <= m; dv += x.se, ++ d) { int64 sum = 0;//\mu(d)\sum_{k=1}^{\frac m{wd}f_{son,kwd}}, dv=wd for(int kwd = dv; kwd <= m; kwd += dv) { sum += mu[d] * (ump[x.fi].find(kwd) != ump[x.fi].end()?ump[x.fi][kwd]:ump[x.fi][0]) % mod; upd(sum); } for(int tj = dv; tj <= m; tj += dv) { ilg[tj / x.se] += sum; upd(ilg[tj / x.se]); } } int64 ny = ksm(dp[x.fi], mod - 2, mod); for(int j = x.se; j <= m; j += x.se) { if(ump[u].find(j) != ump[u].end()) { ump[u][j] = ump[u][j] * (dp[x.fi] - ilg[j / x.se]) % mod * ny % mod;//受到若干条边权影响后的合法方案数比例 }else { ump[u][j] = (dp[x.fi] - ilg[j / x.se]) * ny % mod; } } for(int j = m / x.se; j >= 1; --j) ilg[j] = 0; } dp[u] = all * m % mod;//假设全部不受路径边权影响的方案数 for(auto &p: ump[u]) { p.se = p.se * all % mod;//根据比例算出方案数 dp[u] = (dp[u] + p.se - all + mod) % mod;//更新总的合法方案数 upd(dp[u]); } ump[u][0] = all;//不受影响的单个dp[u][j]的方案数 } int main() { #ifndef ONLINE_JUDGE freopen("D://in.in", "r", stdin); freopen("D://out.out", "w", stdout); #endif init_prime(); n = read(), m = read(); for(int i = 2, a, b, c; i <= n; ++i) { a = read(), b = read(), c = read(); mp[a].eb(mk(b, c)); mp[b].eb(mk(a, c)); } dfs(1, -1); printf("%lld\n", (dp[1] + mod) % mod); return 0; }

2020 计蒜之道预赛第三场

B. 石子游戏（简单）

暴力背包问题即可。

int n, m, Q; int ar[MXN], br[MXN]; class node { public: int l, r, x; }cw[MXN]; unsigned int ans[MXN], tf[66]; int f[66], r[66]; void read_data() { n = read(); m = read(); Q = read(); // debug(n, m, Q) for(int i = 1; i <= n; ++i) { ar[i] = read(); br[i] = read(); } for(int i = 1; i <= Q; ++i) { cw[i].l = read() + 1; cw[i].r = read() + 1; cw[i].x = read(); } } void gao_solve() { for(int t = 1; t <= Q; ++t) { // debug(cw[t].l, cw[t].r) for(int i = 1; i < m; ++i) f[i] = -1; f[0] = 0; for(int i = cw[t].l; i <= cw[t].r; ++i) { for(int i = 0; i < m; ++i) r[i] = f[i]; for(int j = m - 1; j >= 0; --j) { if(r[j^ar[i]] != -1) f[j] = max(f[j], r[j^ar[i]] + br[i]); } } tf[0] = f[0]; for(int i = 1; i < m; ++i) { if(f[i] == 0) f[i] = -1; tf[i] = f[i]; // if(t == 2 && f[i] != -1) debug(t, i, f[i]) } ans[t] = 0; for(int i = 0; i < m; ++i) ans[t] += tf[i] * (cw[t].x ^ i); } } void print_ans() { unsigned int res = 0; for(int i = 1; i <= Q; ++i) res += (i^ans[i]); printf("%u\n", res); } int main() { #ifdef LH_LOCAL freopen("D:in.in", "r", stdin); freopen("D:out.out", "w", stdout); #endif read_data(); gao_solve(); print_ans(); #ifdef LH_LOCAL // cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl; // system("pause"); #endif return 0; }

B. 石子游戏（中等）

线段树

const int MXN = 1e6 + 5; const int MXE = MXN + MXN; int n, m, Q; int ar[MXN], br[MXN]; class node { public: int l, r; unsigned int x; }cw[2005]; unsigned int ans[2005], tf[64]; class edge { public: int f[64]; int l, r; }tr[MXE], tmpans; int inde, root; void push_up(edge &c, edge a, edge &b) { for(int i = 0; i < m; ++i) { if(a.f[i] == -1) continue; for(int j = 0; j < m; ++ j) { if(a.f[i] != -1 && b.f[j] != -1) c.f[i^j] = max(a.f[i] + b.f[j], c.f[i^j]); } } } void push_up2(edge &c, const edge &a, const edge &b) { for(int i = 0; i < m; ++i) { if(a.f[i] == -1) continue; for(int j = 0; j < m; ++ j) { if(a.f[i] != -1 && b.f[j] != -1) c.f[i^j] = max(a.f[i] + b.f[j], c.f[i^j]); } } } void build(int l, int r, int &rt) { if(rt == 0) rt = ++ inde; clr(tr[rt].f, -1); tr[rt].f[0] = 0; if(l == r) { tr[rt].f[ar[l]] = br[l]; return ; } int mid = (l + r) >> 1; build(l, mid, tr[rt].l); build(mid + 1, r, tr[rt].r); push_up2(tr[rt], tr[tr[rt].l], tr[tr[rt].r]); // debug(l, r) // for(int i = 0; i < m; ++i) debug(i, tr[rt].f[i]) } void query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { push_up(tmpans, tmpans, tr[rt]); return; } int mid = (l + r) >> 1; if(L > mid) query(L, R, mid + 1, r, tr[rt].r); else if(R <= mid) query(L, R, l, mid, tr[rt].l); else { query(L, mid, l, mid, tr[rt].l); query(mid + 1, R, mid + 1, r, tr[rt].r); } } void read_data() { n = read(); m = read(); Q = read(); for(int i = 1; i <= n; ++i) { ar[i] = read(); br[i] = read(); } for(int i = 1; i <= Q; ++i) { cw[i].l = read() + 1; cw[i].r = read() + 1; cw[i].x = read(); } } void gao_solve() { clr(tr[0].f, -1); tr[0].f[0] = 0; build(1, n, root); for(int i = 1; i <= Q; ++i) { ans[i] = 0; clr(tmpans.f, -1); tmpans.f[0] = 0; query(cw[i].l, cw[i].r, 1, n, 1); tf[0] = tmpans.f[0]; // debug(tf[0]) for(int i = 1; i < m; ++i) { if(tmpans.f[i] == 0) tmpans.f[i] = -1; tf[i] = tmpans.f[i]; // if(tf[i] != -1) debug(i, tf[i]) } for(unsigned int j = 0; j < m; ++j) ans[i] += tf[j] * (cw[i].x ^ j); } } void print_ans() { unsigned int res = 0; for(unsigned int i = 1; i <= Q; ++i) res += (i^ans[i]); printf("%u\n", res); } int main() { #ifdef LH_LOCAL freopen("D:in.in", "r", stdin); freopen("D:out.out", "w", stdout); #endif read_data(); gao_solve(); print_ans(); #ifdef LH_LOCAL // cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl; // system("pause"); #endif return 0; }

分块暴力肯定过不去。

int n, m, Q; int ar[MXN], br[MXN]; class node { public: int l, r, x; }cw[50005]; unsigned int ans[5005], tf[66]; class edge { public: int f[66]; }tr[20004], tmpans, tmp2; int l[MXN], r[MXN], bel[MXN], block, num; int f[66], rr[66]; inline void build() { block = sqrt(n); num = n / block; if(n % block) ++ num; for(int i = 1; i <= num; ++i) { l[i] = (i-1) * block + 1; r[i] = i * block; } r[num] = n; for(int i = 1; i <= n; ++i) { bel[i] = (i - 1) / block + 1; } for(int tt = 1; tt <= num; ++tt) { for(int i = 1; i < m; ++i) f[i] = -1; f[0] = 0; for(int i = l[tt]; i <= r[tt]; ++i) { for(int i = 0; i < m; ++i) rr[i] = f[i]; for(int j = m - 1; j >= 0; --j) { if(rr[j^ar[i]] != -1) f[j] = max(f[j], rr[j^ar[i]] + br[i]); } } for(int i = 0; i < m; ++i) tr[tt].f[i] = f[i]; } } inline void push_up(edge &c, edge &a, edge &b) { for(register int i = 0; i < m; ++i) { if(a.f[i] == -1) continue; for(register int j = 0; j < m; ++ j) { if(b.f[j] != -1) c.f[i^j] = max(a.f[i] + b.f[j], c.f[i^j]); } } } void read_data() { n = read(); m = read(); Q = read(); for(int i = 1; i <= n; ++i) { ar[i] = read(); br[i] = read(); } for(int i = 1; i <= Q; ++i) { cw[i].l = read() + 1; cw[i].r = read() + 1; cw[i].x = read(); } } void query(int x, int y) { if(bel[x] == bel[y]) { for(int i = 1; i < m; ++i) f[i] = -1; f[0] = 0; for(int i = x; i <= y; ++i) { for(int i = 0; i < m; ++i) rr[i] = f[i]; for(int j = m - 1; j >= 0; --j) { if(rr[j^ar[i]] != -1) f[j] = max(f[j], rr[j^ar[i]] + br[i]); } } for(int i = 0; i < m; ++i) tmpans.f[i] = f[i]; return; } for(int i=bel[x] + 1; i < bel[y]; ++i){ tmp2 = tmpans; push_up(tmpans, tmp2, tr[i]); } if(x==l[bel[x]]) { tmp2 = tmpans; push_up(tmpans, tmp2, tr[bel[x]]); }else{ for(int i = 0; i < m; ++i) f[i] = tmpans.f[i]; for(int i = x; i <= r[bel[x]]; ++i) { for(int i = 0; i < m; ++i) rr[i] = f[i]; for(int j = m - 1; j >= 0; --j) { if(rr[j^ar[i]] != -1) f[j] = max(f[j], rr[j^ar[i]] + br[i]); } } for(int i = 0; i < m; ++i) tmpans.f[i] = f[i]; } if(y==r[bel[y]]){ tmp2 = tmpans; push_up(tmpans, tmp2, tr[bel[y]]); }else{ for(int i = 0; i < m; ++i) f[i] = tmpans.f[i]; for(int i = l[bel[y]]; i <= y; ++i) { for(int i = 0; i < m; ++i) rr[i] = f[i]; for(int j = m - 1; j >= 0; --j) { if(rr[j^ar[i]] != -1) f[j] = max(f[j], rr[j^ar[i]] + br[i]); } } for(int i = 0; i < m; ++i) tmpans.f[i] = f[i]; } } void gao_solve() { build(); for(int i = 1; i <= Q; ++i) { ans[i] = 0; clr(tmpans.f, -1); tmpans.f[0] = 0; query(cw[i].l, cw[i].r); tf[0] = tmpans.f[0]; // debug(tf[0]) for(int i = 1; i < m; ++i) { if(tmpans.f[i] == 0) tmpans.f[i] = -1; tf[i] = tmpans.f[i]; // if(tf[i] != -1) debug(i, tf[i]) } for(int j = 0; j < m; ++j) ans[i] += tf[j] * (cw[i].x ^ j); } } void print_ans() { unsigned int res = 0; for(int i = 1; i <= Q; ++i) res += (i^ans[i]); printf("%u\n", res); } int main() { #ifdef LH_LOCAL freopen("D:in.in", "r", stdin); freopen("D:out.out", "w", stdout); #endif read_data(); gao_solve(); print_ans(); #ifdef LH_LOCAL // cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl; // system("pause"); #endif return 0; }

ST表因为内存限制的原因过不去。

int n, m, Q; int ar[MXN], br[MXN]; class node { public: int l, r, x; }cw[50005]; unsigned int ans[5005], tf[66]; class edge { public: int f[66]; }dp[100006][21], tmpans, tmp2; int f[66], rr[66]; void push_up(edge &c, edge &a, edge &b) { for(int i = 0; i < m; ++i) { for(int j = 0; j < m; ++ j) { if(a.f[i] != -1 && b.f[j] != -1) c.f[i^j] = max(a.f[i] + b.f[j], c.f[i^j]); } } } void RMQ(){ for(int i = 1; i <= n; ++i) { for(int j = 0; j < 21; ++j) { clr(dp[i][j].f, -1); dp[i][j].f[0] = 0; } dp[i][0].f[ar[i]] = br[i]; } for(int j = 1; j < 21; ++j) { for(int i = 1; i <= n; ++i) { if(i + (1 << j) - 1 <= n) { push_up(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } } } } void read_data() { n = read(); m = read(); Q = read(); for(int i = 1; i <= n; ++i) { ar[i] = read(); br[i] = read(); } for(int i = 1; i <= Q; ++i) { cw[i].l = read() + 1; cw[i].r = read() + 1; cw[i].x = read(); } } void query(int a, int b) { for(int i = 20; i >= 0; --i) { if(a + (1 << i) - 1 <= b) { // debug(a, b, i, a + (1 << i)) tmp2 = tmpans; push_up(tmpans, tmp2, dp[a][i]); a += (1 << i); } } } void gao_solve() { RMQ(); for(int i = 1; i <= Q; ++i) { ans[i] = 0; clr(tmpans.f, -1); tmpans.f[0] = 0; query(cw[i].l, cw[i].r); tf[0] = tmpans.f[0]; // debug(tf[0]) for(int i = 1; i < m; ++i) { if(tmpans.f[i] == 0) tmpans.f[i] = -1; tf[i] = tmpans.f[i]; // if(tf[i] != -1) debug(i, tf[i]) } for(int j = 0; j < m; ++j) ans[i] += tf[j] * (cw[i].x ^ j); } } void print_ans() { unsigned int res = 0; for(int i = 1; i <= Q; ++i) res += (i^ans[i]); printf("%u\n", res); } int main() { #ifdef LH_LOCAL freopen("D:in.in", "r", stdin); freopen("D:out.out", "w", stdout); #endif // debug(2000 * log(1e6) * 60 * 60) read_data(); gao_solve(); print_ans(); #ifdef LH_LOCAL // cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl; // system("pause"); #endif return 0; }

最新回复(0)

2019 计蒜之道 初赛 第一场|2020 计蒜之道 初赛 第三场