打卡信奥刷题（3054）用C++实现信奥题 P6747 『MdOI R3』Teleport

P6747 『MdOI R3』Teleport题目背景凯瑞甘从帝国的围攻下击毁了大天使号乘着雷诺的飞船逃了出来到了休伯利安号上。“吉米”凯瑞甘着急地四处寻找着。“很抱歉我们没能救出他”马特·霍纳向凯瑞甘走来。“你丢下了他”凯瑞甘回想起曾经的自己被蒙斯克丢下便起了杀心用灵能将马特抓了起来。“不是的凯瑞甘我们受到了帝国的伏击现在必须马上离开过会可以回头来找他”马特解释道。“这里没有我们你走吧我自己去找他。”凯瑞甘放下了马特回头坐着雷诺的回到了星球上。“警告警告敌军突破能量场。”帝国的舰队突破了马特舰队设下的能量场控制着钢铁舰队折越到了这里并对休伯利安号发起猛烈的攻击。“立即进行折越我们必须马上离开”马特·霍纳下令道。题目描述马特·霍纳想要控制休伯利安号进行折越想要进行折越就要激活休伯利安号上的所有nnn个位点。休伯利安号上有nnn个位点每个位点有aia_iai​点能量为了激活马特·霍纳会消耗k×nk\times nk×n点地嗪这k×nk\times nk×n点地嗪会平均分给nnn个位点每个位点在接受kkk点地嗪后会激发得到aixor⁡ka_i \operatorname{xor} kai​xork点高能所有位点的高能总和为这次折越的消耗SSS。为了能够快速的进行折越马特·霍纳决定用最多的k×nk\times nk×n点地嗪但可惜的是如果地嗪使用太多使得消耗SSS超过限制值mmm那么休伯利安号就会不堪重负最终爆炸。现在你的任务是帮助马特·霍纳找到这个最大的kkk使得休伯利安号能在安全的前提下尽可能快的折越走。如果任何情况下都不能安全的折越走则输出−1-1−1。这里的xor⁡\operatorname{xor}xor表示的是位运算中的按位异或运算。输入格式第一行一个整数nnn表示位点数量。第二行nnn个整数a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​表示每个位点拥有的能量。第三行一个数qqq表示询问次数。接下来qqq行表示qqq次询问每行一个数mmm。输出格式对于每次询问输出一行一个非负整数表示最大的kkk。若无解输出−1-1−1。输入输出样例 #1输入 #13 1 2 3 2 10 1输出 #13 -1输入输出样例 #2输入 #21 0 1 1073741824000000输出 #21073741824000000说明/提示对于第一个询问最大的kkk为333此时S2103≤10S2103 \le 10S2103≤10可证没有更大的kkk满足条件。对于第二个询问没有任何kkk满足条件。数据点nnnaia_iai​mmmqqq111≤10\le 10≤10≤220\le 2^{20}≤220≤220\le 2^{20}≤220111222≤103\le 10^3≤103≤103\le10^3≤103≤103\le10^3≤103≤103\le 10^3≤103333≤103\le 10^3≤103≤230\le 2^{30}≤230≤103\le 10^3≤103≤103\le 10^3≤1034∼64\sim 64∼6≤105\le 10^5≤105≤220\le 2^{20}≤220≤106\le 10^6≤106≤105\le 10^5≤1057∼107\sim 107∼10≤105\le 10^5≤105≤230\le 2^{30}≤230≤230×106\le 2^{30}\times10^6≤230×106≤105\le 10^5≤105本题不进行捆绑测试。所有测试点的数据范围如上所示。对于所有数据0n,q≤105, 0≤ai≤230, 0≤m≤230×1060n,q\leq 10^5,\ 0\leq a_i\leq 2^{30},\ 0\leq m\leq 2^{30}\times 10^60n,q≤105,0≤ai​≤230,0≤m≤230×106。C实现#includeiostream#includecmath#includealgorithmusingnamespacestd;typedeflonglongll;ll n,a[100005],q,t[55],m,ans,poww[55];boolflagfalse;voidtong(ll x){for(inti1;i52;i){if(x0)break;if(x%21){t[i];}x/2;}}//开桶统计一下voiddfs(intw,ll x){if(flag)return;if(w0){printf(%lld\n,ans);flagtrue;return;}anspoww[w-1];if(double(x)double(n-t[w])*double(poww[w-1])double(m))//转化一下doubledfs(w-1,x(n-t[w])*poww[w-1]);ans-poww[w-1];if(double(x)double(t[w])*double(poww[w-1])double(m))dfs(w-1,xt[w]*poww[w-1]);}intmain(){poww[0]1;for(inti1;i52;i)poww[i]poww[i-1]*2;//预处理一下2的幂scanf(%lld,n);for(inti1;in;i){scanf(%lld,a[i]);tong(a[i]);}scanf(%lld,q);for(inti1;iq;i){flagfalse;ans0;scanf(%lld,m);dfs(52,0);if(!flag)printf(-1\n);//判无解}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容