Educational Codeforces Round 157 D题 异或构造
https://codeforces.com/problemset/problem/1895/D 题目大意已知异或的差分(异或意义的差分)，求原数组，要求原数组是一个排列 分析异或又称模二加（其实也是模二减，所以自己才能消去自己），加法有的性质它都有。本题相当于是给了差分，在不知道初始项的情况下求原数组。我们可以假设 a1 = 0 ，先得到一个数组。根据异或的性质可知这个数组与答案只相差一个整体异或的偏移量shift。 解决如何求这个偏移量？ 由于题目保证答案一定存在，所以我们只需要尽量让数组接近答案就够了。 已知答案是一个0-n-1的排列。我们按位来考虑，对于某一个二进制位， $\sum (ans_i==0) >= (\sum ans_i==1)$ 恒成立 也就是说如果我们发现构造出的数组中某一位二进制上1比0多就翻转一下。 复杂度$O(nlogn)$ 代码123456789101112131415161718192021222324252627282930313233void solve(){ int n; cin >> n; for ...
我的ACM模板
function doDecrypt (pwd, onError) { console.log('in doDecrypt'); const txt = document.getElementById('enc_content').innerHTML; let plantext; try { const bytes = CryptoJS.AES.decrypt(txt, pwd); var plaintext = bytes.toString(CryptoJS.enc.Utf8); } catch(err) { if(onError) { onError(err); } return; } document.getElementById('enc_content').innerHTML = plaintext; document.getElementById('enc_content').style.display = 'block'; document.getElementById('enc_passwd').style.display ...
2018 ICPC青岛站 F. Tournament 题解
https://codeforces.com/gym/104270/problem/F 题目要求输出最小字典序的答案 由于要求每轮每人战斗且仅战斗了一次，不难想到第一轮的情况应该是这样的： 1-2 3-4 5-6 7-8 … 也就是说答案矩阵的第一行为 2 1 4 3 6 5 8 7 … （似乎是正整数数列以2个数为单位交换) 在推导第二行的过程中，我们可以发现第二轮只有在4|k的情况下才有解（最后会提到如何判断非法情况）。最小字典序的选法为 3 4 1 2 7 8 5 6 似乎是相邻两个元素交换，打一个表出来 2 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1 假设第0行是 1 2 3 4 5 6 7 8 则后面的每一行分别在前一行的基础上分别按 2 4 2 8 2 4 2 为长度翻转 所以只需要预处理出这样的数列，实现一个翻转函数依次进行翻转 1234567void sswap(int len){ ...
金蛋解谜纪念品
【GoldenEggs 百万粉丝-解谜挑战】第0题：我们将一串数字以高级弹幕的形式发在了这片大地。在群山之巅，在扁舟之涧；在进化边境之外，在金色三角之中；在盘根错节的星与海，在重力倒覆的不可期；在虚实交界线的午夜狂欢，在孤岛逢生后的相见恨晚。以时光为序，质素为基，可得二解；其一为群；其二为1bC3A2aBedc4EFD 这是发生在2021.12.01的事情。 解谜的早期环节发现网上很多质因数分解器数字大一点就会输出错误的结果，比如说奇数分解出了2。活动举办方之后赶紧提供了一个正确的分解器hhh 活动里得到的奖品