可能是假期最后一场了吧，可还是......
考试经过
T1根本看不懂题，乱看发现T2似乎可以记忆化搜，随便写了一个过了样例就交了，感觉能切心情不错，正好教练说T1不太清楚叫赵sir解释一下，说完依旧看不懂题，T3发现比较可做但是不会，T4看了好半天，认为可以分块之后把询问排序，但是感觉细节极多于是暴力跑路后来我才知道差一点胡出了莫队
回去看T1，认为需要枚举所有才能找到正确答案，于是想了一个\(O(2^n\times3^n\times n^2)\)的状压做法，调吐了根本写不对，有亿点假。。。最后弃掉冲T3暴力，然后揭榜了
\(5+35+0+20=60\)
没有比我更废的了吧
T2假了，没有考虑蛇位置不能重叠就人没了，65的爆搜都没有 。。。
T3暴力没对，T1我一个样例都不对居然还有5分
还是太浪了，不稳，觉得切题了思维就开始不在线，最后一挂啥都没有
T1.打表
首先要搞明白这个cpu们是怎么操作的
考试时想的是每次枚举一个当前选的位置和填的数字，然后枚举剩下的全排列除以方案总数来选择最优决策
这样复杂度有多爆炸先不说，至少正确性就没有，因为你不能保证他当前选了之后后面方案总数是全排列，因为都要最优你不能保证后面所有方案都一定出现，相当与只保证了一步最优，但是没有考虑以后的影响
我也不知道我是怎么想出来这个假贪心的
正确暴力做法是dfs，表示当前状态下结果差的期望，记忆化搜索有\(3^n\)就是50分，相当于是dfs时候在最后返回然后一直回溯更新，假如你只有最后一个位置没有填那你肯定知道填什么，然后就能回推到有2个，3个位置，一直到整个序列都没填的答案
说白了，不用管他们具体策略是什么，（科学的）枚举就好了
然后想优化，这个序列最后每一位都会被填，那么其实只要按顺序填，考虑下一位填0还是填一就行了，然后搜一遍就是\(2^n\)，已经能过了
然而还可以接着想，发现两个cpu概率一样，而且两个一定会在同一位填不同的数，其实所有数最后都会等概率被选一次，然后直接盲猜：
所以你发现就是个结论题然后感觉智商被嘲讽了，游戏结束
题解提供了归纳证明，感觉也差不多
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int mod=1e9+7;
inline int ksm(int x,int y)
{
int s=1;x%=mod;
for(;y;y>>=1)
{
if(y&1)s=s*x%mod;
x=x*x%mod;
}
return s;
}
inline int ny(int x)
{
return ksm(x,mod-2);
}
int a[1<<19];
signed main()
{
int k,ans;cin>>k>>ans;
int an=0;
for(int i=0;i<=(1<<k)-1;i++)a[i]=read();
for(int i=0;i<=(1<<k)-1;i++)an=(an+abs(a[i]-a[ans]))%mod;
cout<<an*ny(ksm(2,k))%mod;
return 0;
}
那么考场上如何切掉呢？显然你并没有rp高到一眼猜出结论
首先你要能看懂题，接着要打出正确的dfs，大部分人做不到上两条，俺也一样你要拥有想\(zero4338\)一样敏锐的洞察力在代码里随便加几个break再删一大堆东西发现他还是对的
出题人其实挺良心，题解就是题目，只不过大佬AC，吾辈爆零罢了
最后记住一句话：
战神是战神，你还是你
T2.蛇
发现蛇一定是这么走的：往回一段在回来一段，曲折蛇行一段，前进一段再往回一段
中间的dp，前后哈希预处理
似乎细节很多，于是咕了
T3.购物
付哥哥NB，没了其实懒得写就咕了
T4.ants
被斥为回滚莫队裸题
苣蒻连啥是莫队都不知道，爬了
考试总结
1.不要以为写出了（所谓的）正解就放弃暴力，更不能放弃思考
2.四个题其实有很多分可以拿，所以不能浪费时间，否则结果是别人几百分你啥都没有
3.别死磕，看分值安排时间，优先拿性价比高的分数