做本地网站赚钱吗？,泉州app开发,湖南微信网站公司简介,网站空间数据库上传7题罚时879#xff0c; 队排235#xff0c;校排79。 除了I题dp没注意空间限制第一发没有用滚动数组MLE#xff0c;以及G题启发式合并脑抽用set当容器T一发#xff0c;以及K没注意是平方的期望白wa4发这些应当避免的失误外#xff0c;基本满意。剩下的题基本都是当时写不出…7题罚时879 队排235校排79。 除了I题dp没注意空间限制第一发没有用滚动数组MLE以及G题启发式合并脑抽用set当容器T一发以及K没注意是平方的期望白wa4发这些应当避免的失误外基本满意。剩下的题基本都是当时写不出的了在这里补一发F的题解。
本题解学自知乎-CurryWOE
F. Alice and Bob博弈 计数
很妙的一个博弈思维题并没有多难的算法只是利用了题目的性质与博弈的基本思想以及巧妙的计数方法但实际比赛中还是很难想到的银牌题中上的难度。
题意
给定大小为 n n n 的数组 a a aAlice先手两人轮流走步每次可以选择两个数 a i , a j a_i, a_j ai,aj将其任意改变只能变为整数设改变后为 a i 2 , a j 2 a_{i_2},a_{j_2} ai2,aj2要求改变后满足 a i a j a i 2 a j 2 a_ia_j a_{i_2}a_{j_2} aiajai2aj2且 ∣ a i − a j ∣ ∣ a i 2 − a j 2 ∣ |a_i-a_j||a_{i_2}-a_{j_2}| ∣ai−aj∣∣ai2−aj2∣. 最后不能走步的人输。 为了帮助Alice胜利你可以选择保留任意 3 3 3 个数移除其他数问有多少方案使得Alice必胜。
思路
以上规则翻译过来就是每次选的两个数必须使得两者差距变小这样我们发现答案与数的大小无关只与数的相对大小有关。于是我们可以分情况讨论什么样的三元组使得Alice必胜或必败。
设三元组为 ( x , y , z ) ( x ≤ y ≤ z ) (x, y, z)(x\leq y\leq z) (x,y,z)(x≤y≤z). 因为只与相对大小有关可以通过平移转换为 ( 0 , x , x y ) (0, x, x y) (0,x,xy)并且若 x y x y xy 可以对称转换一下使得 x y x y xy 例如 ( 0 , 3 , 5 ) → ( − 5 , − 3 , 0 ) → ( 0 , 2 , 5 ) (0,3,5)\rightarrow(-5,-3,0)\rightarrow(0,2,5) (0,3,5)→(−5,−3,0)→(0,2,5).
接下来要用到博弈的思想 1.所有终止状态都为必败态。 2.只要能转移到必败态的状态就是必胜态。 3.只能转移到必胜态的状态就是必败态。
分情况讨论 x 0 , y 0 x 0,y0 x0,y0三元组为 ( 0 , x , x y ) (0, x, x y) (0,x,xy) 我们考虑该三元组的下一个状态有两种可能即 ( y , x , x ) (y, x, x) (y,x,x) 或者 ( x k , x , y − k ) (x k, x, y - k) (xk,x,y−k). 再考虑状态 ( y , x , x ) (y,x,x) (y,x,x) 的后继只能为 ( x k , x , y − k ) (x k, x, y - k) (xk,x,y−k). 若 ( y , x , x ) (y,x,x) (y,x,x) 为必败态则当前状态可以转移到该必败态当前为必胜态。 若 ( y , x , x ) (y,x,x) (y,x,x) 为必胜态由于其只有一个后继说明该后继一定为必败态而当前状态又能转移到该必败态当前状态同样必胜。 综上 ( 0 , x , x y ) (0, x, x y) (0,x,xy) 一定为必胜态。 x 0 , y 0 / x 0 , y 0 x 0,y 0/x 0,y0 x0,y0/x0,y0三元组为 ( 0 , 0 , x ) (0, 0, x) (0,0,x) x 0 x0 x0 为何 ( 0 , x , x ) (0,x,x) (0,x,x) 同样为该状态还是考虑平移与对称变化 ( 0 , x , x ) → ( − x , 0 , 0 ) → ( x , 0 , 0 ) (0,x,x)\rightarrow (-x,0,0)\rightarrow(x,0,0) (0,x,x)→(−x,0,0)→(x,0,0). 而 y 0 y0 y0 的情况因为只是一个变量名将其名称与 x x x 交换即可。 1若 x x x 为奇数当前状态的后继最多为 ( 0 , ⌊ x 2 ⌋ , ⌈ x 2 ⌉ ) (0,\lfloor\frac x2\rfloor,\lceil\frac x2\rceil) (0,⌊2x⌋,⌈2x⌉) 即可以表示为 ( 0 , x , y ) ( x y ) (0,x,y)(xy) (0,x,y)(xy). 而情况1 已经证明了该后继状态为必胜态则当前状态为必败态。 2若 x x x 为偶数当前状态后继若选择变为 ( 0 , x , y ) (0,x,y) (0,x,y)则必败。考虑另一种情况即将 x x x 一分为二变为 ( 0 , x 2 , x 2 ) (0,\frac x2,\frac x2) (0,2x,2x)此时我们发现又一次变为了情况2说明这是一个递归的过程而答案只与 x x x 包含的 2 2 2 的幂次有关。 综上归纳整理有若 x x x 包含的 2 2 2 的幂次为偶数先手必败否则先手必胜。
合并起来看
三元组 ( x , y , z ) , ( x y z ) (x,y,z),(xyz) (x,y,z),(xyz)必胜。三元组 ( x , y , z ) , ( x y / y z ) (x,y,z),(xy/yz) (x,y,z),(xy/yz)若 ( z − x ) (z - x) (z−x) 包含的 2 2 2 的幂次为偶数必败否则必胜。三元组 ( x , y , z ) , ( x y z ) (x,y,z),(xyz) (x,y,z),(xyz)必败。
现在我们考虑如何计数直接求必胜态数量不好求我们考虑容斥求出必败态数量再用总数减去。情况3的必败态数量很好求我们只需要考虑情况2的。 遍历所有数设当前数为 x x x那么我们只需要求 ( p , x , x ) ( x p ) (p,x,x)(xp) (p,x,x)(xp) 和 ( x , x , z ) ( z x ) (x,x,z)(zx) (x,x,z)(zx) 三元组中满足 x − p x - p x−p 和 z − x z - x z−x 包含的 2 2 2 的幂次为偶数的个数即可可以考虑用01字典树来维护。 2 2 2 的幂次的奇偶只与数末尾 0 0 0 的个数的奇偶有关而二进制减法中 x − y z x - y z x−yz z z z 末尾的第一个 1 1 1 出现在 x , y x,y x,y 从末尾开始第一个数字不同的数位我们倒序将数的数位插入字典树查询数目后就是简单的组合数学问题了。 时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)对于 n ≤ 5 e 5 , ∑ n ≤ 3 e 6 n\leq5e5,\sum n\leq3e6 n≤5e5,∑n≤3e6 的数据范围还是很轻松能通过的。 具体实现见代码有详细注释。
代码
/*
1. 三元组 (x,y,z),(xyz)必胜。
2. 三元组 (x,y,z),(xy/yz)若 (z - x) 包含的 2 的幂次为偶数必败否则必胜。
3. 三元组 (x,y,z),(xyz)必败。
*/
#include bits/stdc.h
using namespace std;#define ll long long
const int N 5e5 10;ll a[N];
int son[N * 62][2], cnt[N * 62], tot;
void clear(int p){if(son[p][0]) clear(son[p][0]);if(son[p][1]) clear(son[p][1]);son[p][0] son[p][1] cnt[p] 0;
}void insert(ll x){int p 0;for(int i 0; i 60; i ){ // 倒序插入int u x i 1;if(!son[p][u]) son[p][u] tot;p son[p][u];cnt[p] ;}
}ll search(ll x, int idx, int p, int ode){ // 查询的数x, 当前数位字典树地址 奇偶性ll sum 0;int u x idx 1;if(son[p][!u] !ode){ // 下一位数不同且当前0的个数为偶数即为差包含偶数次2的幂次加入答案sum cnt[son[p][!u]];}if(son[p][u]) sum search(x, idx 1, son[p][u], ode ^ 1); // 继续搜索return sum;
}ll C2(ll sum){ // C(sum, 2)return sum * (sum - 1) / 2LL;
}
ll C3(ll sum){ // C(sum, 3)return sum * (sum - 1) * (sum - 2) / 6LL;
}void solve(){int n;cin n;clear(0); tot 0;for(int i 1; i n; i ){cin a[i];insert(a[i]);}sort(a 1, a 1 n);ll ans C3(n); // 总方案数for(int i 1, r 1; i n; i ){while(r 1 n a[r 1] a[i]) r ;ans - C2(r - i 1) * search(a[i], 0, 0, 0); // 情况2的必败数ans - C3(r - i 1); // 情况3的必败数i r;}cout ans;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin t;for(int i 1; i t; i ){solve();if(i ! t) cout \n;}return 0;
}
