『模拟赛』CSP-S模拟5

news/2024/9/27 21:07:03

Rank

一般

A. 光

胱！

妈的传奇题目控我两个小时想 $\mathcal{O(1)}$ 做法。

其实带下取整的四个四元一次方程根本解不了，考虑到这个题给的范围只有 $n\le 1500$，可以枚举两维剩下二分到一个小区间里去做，复杂度 $\mathcal{O(n^2\log n)}$，当然数据水卡卡枚举的边界 $\mathcal{O(n^3)}$ 也能过。

学的 K8He 的带 $4^4$ 常数的 $\mathcal{O(n)}$ 做法。考虑到以四为单位减小不会有浪费的亮度，因此这样贪心着耗电是很优的。我们枚举最后剩下需要的亮度，进而求出我们需要进行以四为单位贪心的数据，优先队列随便维护一下，然后处理一下以四为单位贪不了的和我们枚举的剩余局面，三者消耗之和即为答案。

想卡最优解来着，所以提前跑了一遍把剩余局面的所有消耗跑出来赋给数组了，结果还是比不过小常数选手们，拜谢！

注释掉的是跑剩余局面的代码，有需要的自行打开。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5 , M = 6000;
const int mod = 998244353;
int a, b, c, d;
int ans = 1e9;
int res[4][4][4][4]={0,1,2,3,1,2,2,3,2,2,3,4,3,3,4,4,1,2,2,3,2,2,2,3,3,3,3,4,4,4,4,4,2,2,
3,4,3,3,3,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,5,5,6,6,6,6,1,2,3,4,2,3,3,4,2,2,3,4,3,3,
4,4,2,3,3,4,3,3,3,4,3,3,4,4,4,4,4,4,2,2,3,4,3,3,4,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,
5,5,6,6,6,6,2,3,4,5,2,3,4,5,3,3,4,5,4,4,5,5,2,3,4,5,2,3,4,5,3,4,4,5,4,4,5,5,3,3,4,5,3,4,
4,5,4,4,4,5,5,5,5,6,4,4,5,5,4,4,5,5,5,5,5,6,6,6,6,6,3,4,5,6,3,4,5,6,4,4,5,6,4,4,5,6,3,4,
5,6,3,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,5,5,5,6,5,5,6,6,4,4,5,6,4,4,5,6,5,5,6,6,6,6,6,6};
priority_queue<pii, vector<pii >, less<pii > > q;
namespace Wisadel
{void Wfang(pii x, pii y){if(x.se + y.se == 5) q.push({y.fi - 1, y.se});else q.push({y.fi - 2, y.se});}short main(){freopen("light.in", "r", stdin) , freopen("light.out", "w", stdout);a = qr, b = qr, c = qr, d = qr;fo(i1, 0, 3) fo(i2, 0, 3) fo(i3, 0, 3) fo(i4, 0, 3){int A = a - i1, B = b - i2, C = c - i3, D = d - i4;q.push({A, 1}), q.push({B, 2}), q.push({C, 3}), q.push({D, 4});int tim = 0, cs;int ba, bb, bc, bd;while(q.top().fi >= 4){pii aa = q.top(); q.pop();pii bb = q.top(); q.pop();pii cc = q.top(); q.pop();pii dd = q.top(); q.pop();q.push({aa.fi - 4, aa.se});Wfang(aa, bb), Wfang(aa, cc), Wfang(aa, dd);tim++;}A = max(q.top().fi, 0), ba = q.top().se, q.pop(), B = max(q.top().fi, 0), bb = q.top().se, q.pop(),C = max(q.top().fi, 0), bc = q.top().se, q.pop(), D = max(q.top().fi, 0), bd = q.top().se, q.pop();cs = A + B + C + D;if(ba + bd != 5) swap(B, D), swap(bb, bd);if(ba + bd != 5) swap(C, D), swap(bc, bd);fo(i, 0, A) fo(j, 0, B) fo(k, 0, C){int l = -1;if(A - i - (j / 2) - (k / 2) >= 0) l = max(l, (A - i - (j / 2) - (k / 2)) * 4);if(B - j - (i / 2) - (k / 4) >= 0) l = max(l, (B - j - (i / 2) - (k / 4)) * 2);if(C - k - (i / 2) - (j / 4) >= 0) l = max(l, (C - k - (i / 2) - (j / 4)) * 2);if(D - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, D - (i / 4) - (j / 2) - (k / 2));if(l != -1) cs = min(cs, i + j + k + l);}// fo(i, 0, i1) fo(j, 0, i2) fo(k, 0, i3)// {//     int l = -1;//     if(i1 - i - (j / 2) - (k / 2) >= 0) l = max(l, (i1 - i - (j / 2) - (k / 2)) * 4);//     if(i2 - j - (i / 2) - (k / 4) >= 0) l = max(l, (i2 - j - (i / 2) - (k / 4)) * 2);//     if(i3 - k - (i / 2) - (j / 4) >= 0) l = max(l, (i3 - k - (i / 2) - (j / 4)) * 2);//     if(i4 - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, i4 - (i / 4) - (j / 2) - (k / 2));//     if(l != -1) res = min(res, i + j + k + l);// }// cout<<res<<',';ans = min(ans, res[i1][i2][i3][i4] + tim * 4 + cs);}// cout<<endl;printf("%d\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}

B. 爬

感觉最简单的一道，赛时 20min 就做出来了，不过因为 T1 耽误太久导致没细想复杂度，暴力找每一个点的所有贡献好像无论时间空间都是 $\mathcal{O(2^n)}$ 的，不过还是能拿到 80pts，但是我在求贡献的时候没取模导致爆 long long 了挂 20pts。

其实关键点在于想到每个点的贡献是独立的，只与它和它的子节点有关。一共只有 $n-1$ 个点可以移动，因此共有 $2^{n-1}$ 种方案。对于非根的节点来说，它对全局的贡献应该是它的总贡献乘上其它节点的总方案数，即若设它和它子节点的个数为 $tot$，应乘上 $2^{n-1-tot}$，因为根节点上的蚂蚁不会动，所以 $tot$ 要减一。

然后考虑怎么求每个点的贡献和。一种优化的思路是二进制拆分。对于二进制下数的每一位，只有出现的次数为奇异或起来才会有贡献，因此我们可以将每个数拆成二进制，在统计总贡献时先求出一点和它的子节点每一位上为 1 的数的个数，再逐位去求，那么有贡献的方案应该是 $C_{tot}^1 \ +\ C_{tot}^3\ +\cdots\ = 2^{tot-1} $，每次的贡献是 $1$<<$i$，记得算上该位为 0 的数的方案数，把各位上的贡献加起来就是该点的总贡献。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
int fa[N], a[N][31], num[N][31];
int hh[N], to[N], ne[N], cnt;
ll Ans;
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}ll Wqp(ll x, int y){ll res = 1;while(y){if(y & 1) res = res * x % mod;x = x * x % mod;y >>= 1;}return res;}void Wdfs(int u, int fa){int tot = (u != 1);for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;tot++;Wdfs(v, u);fo(j, 0, 30) num[u][j] += a[v][j];}ll res = 0;if(u != 1){fo(i, 0, 30){if(!num[u][i]) continue;res = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - num[u][i] + mod) % mod) % mod;}}else{fo(i, 0, 30){if(a[u][i]){if(!num[u][i])res = (res + (1ll << i) * (Wqp(2, tot) - 1) % mod) % mod;elseres = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - 1 + mod) % mod) % mod;}else{if(!num[u][i]) continue;res = (res + (1ll << i) * Wqp(2, num[u][i] - 1) % mod * Wqp(2, tot - num[u][i]) % mod) %mod;}}}Ans = (Ans + res * Wqp(2, n - 1 - tot) % mod) % mod;}short main(){freopen("climb.in", "r", stdin) , freopen("climb.out", "w", stdout);n = qr;memset(hh, -1, sizeof hh);fo(i, 1, n){int bb = qr, ttt = 0;while(bb) a[i][ttt] = bb & 1, bb >>= 1, ttt++;if(i != 1) fo(j, 0, ttt) num[i][j] = a[i][j];}fo(i, 2, n) fa[i] = qr, Wadd(fa[i], i);Wdfs(1, 0);printf("%lld\n",Ans);return Ratio;}
}
signed main(){return Wisadel::main();}

C. 字符串

贪心唐氏大分讨。

感觉做到这如果有时间静下心来想应该很好得出结论：只有 $A$ 与 $B$ 紧密交替出现时每个字符的回报率是 1，其它情况均小于 1，因此能交替就交替是第一准则。称 1 个 $A$ 与 $c$ 个 $B$ 交替出现的串为紧密交替出现的串。

我们枚举交替串的数量，规定 $B$ 在前 $A$ 在后。对于剩下的 $A$，首先置于串首最优，回报率为 1；其次由于我们交替串数量固定了，不能在新加串，因此剩下的 $A$ 要插入到原来的 $A$ 串中，考虑到此时每个 $A$ 串长度为 $1$，因此每 $a$ 个 $A$ 可以提供 1 的贡献。再考虑剩下的 $B$，首先在末尾增加一个最优；其次考虑在原有的长度为 $c$ 的 $B$ 串中加入 $B$，先都将其补至长度为 $b$，剩下的每 $b$ 个还能产生 1 的贡献。然后就做完了。

头脑冷静，理清思路最重要。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, a, b, c;
int ans;
namespace Wisadel
{short main(){freopen("string.in", "r", stdin) , freopen("string.out", "w", stdout);int T = qr;while(T--){n = qr, m = qr, a = qr, b = qr, c = qr;int sum = 0; ans = -1e9;fo(i, 0, m / c){sum = i * 2 + (c - 1) / b * i;int _n = n - i, _m = m - i * c;if(_n < 0 || _m < 0) break;if(_m){_m--, sum++;if(_m){int w = min(i, _m / (b - (c - 1) % b));sum += w + (_m - w * (b - (c - 1) % b)) / b;}}if(_n){_n--,sum++;if(_n) sum += _n / a;}ans = max(ans, sum);}printf("%d\n", ans);}return Ratio;}
}
int main(){return Wisadel::main();}

D. 奇怪的函数

赛时没时间了，5pts 暴力都没打完。

稍微手模一下就能发现这 $n$ 次操作本质上是一个分段函数，考虑如何实现动态维护这个函数。

容易想到线段树，以操作为维护对象，维护每个区间有实际意义值域对应的定义域范围，所有 1 操作的总和。由于可能存在上述定义域范围不存在的情况，而此时该函数实质上变为了一个定函数，即只有一个值，所以我们还需要维护这个值。

考虑两个问题：首先是边界问题。比较好得出取 min 操作是划定定义域的上界，取 max 划定下界。其他情况我们将范围赋成极大区间即可。定值由于是定值？无论取啥都一样。

第二是 pushup，考虑如何合并两个分段函数。1 操作的总和不用说，直接加就行。定义域，我们要取左区间的定义域在右区间上仍有意义的区间，思考一下，从左到右之间做了左区间的加操作，那么若一个数在定义域内，一定有 $x+sum_{ls} \ge L_{rs}$，转换过去就是 $x\ge L_{ls}- sum_{ls}$，由于我们取得是区间的交集，所以要取 $L$ 的最大值和 $R$ 的最小值。至于定值，我们可以看成是执行完左区间的操作后继续执行右区间的，如果右区间定义域不存在就取右区间的，否则视为求 $ans_{ls}$ 在右区间上的值，跟总函数一样如下：

\[F(x)=\begin{cases}R+sum\quad x\ge R\\ x+sum\quad L\lt x\lt R\\L+sum\quad x\le L\end{cases} \]

其中 $L,R$ 表示区间函数的定义域。

然后就做完了，比一般的线段树甚至好写。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int op[N], v[N];
ll L[N << 2], R[N << 2], sum[N << 2], ans[N << 2];
namespace Wisadel
{#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)void Wpushup(int rt){L[rt] = max(L[ls], L[rs] - sum[ls]), R[rt] = min(R[ls], R[rs] - sum[ls]);sum[rt] = sum[ls] + sum[rs];if(L[rs] > R[rs]) ans[rt] = ans[rs];else if(ans[ls] < L[rs]) ans[rt] = L[rs] + sum[rs];else if(ans[ls] > R[rs]) ans[rt] = R[rs] + sum[rs];else ans[rt] = ans[ls] + sum[rs];}void Wbuild(int rt, int l, int r){L[rt] = -1e9, R[rt] = 1e9;if(l == r){if(op[l] == 1) sum[rt] = v[l], ans[rt] = v[l];else if(op[l] == 2) R[rt] = v[l], ans[rt] = 0;else L[rt] = v[l], ans[rt] = v[l];return ;}Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);Wpushup(rt);}void Wupd(int rt, int l, int r, int x, int k, int opp){if(l == r){if(opp == 1) L[rt] = -1e9, R[rt] = 1e9, ans[rt] = sum[rt] = k;else if(opp == 2) L[rt] = -1e9, R[rt] = k, ans[rt] = sum[rt] = 0;else ans[rt] = L[rt] = k, R[rt] = 1e9, sum[rt] = 0;return ;}if(x <= mid) Wupd(ls, l, mid, x, k, opp);else Wupd(rs, mid + 1, r, x, k, opp);Wpushup(rt);}ll Wq(int x){if(L[1] > R[1]) return ans[1];if(x < L[1]) return 1ll * L[1] + sum[1];else if(x > R[1]) return 1ll * R[1] + sum[1];else return x + sum[1];}short main(){freopen("function.in", "r", stdin) , freopen("function.out", "w", stdout);n = qr;fo(i, 1, n) op[i] = qr, v[i] = qr;Wbuild(1, 1, n);m = qr;fo(i, 1, m){int opp = qr, pos = qr, vv;if(opp == 4) printf("%lld\n", Wq(pos));else vv = qr, Wupd(1, 1, n, pos, vv, opp);}return Ratio;}
}
int main(){return Wisadel::main();}