Day1
开把写了 A 的 \(k=0\),然后想 \(n=1\) 去了,想了大概一个半小时,就去开 BC 了。
看到 C 就把 C 弃了想 B,然后也是写了一点性质分。
事实证明没几个对的,爆搜还炸了。
写完之后继续想了一下 \(n=0\),然后写了个蜜汁二分,发现不对。
此时意识到了这个东西应该是一个单峰函数,然后并没有写三分,降智了。(好像有人三分过了?)
实际上需要解一个绝对值不等式的东西,考场上也并没有去推。
A
性质 B (\(k=0\)):
因为 \(k=0\),所以直接考虑前缀和。此时需要判一下整个序列和为 \(0\) 的情况,为 \(0\) 的话循环放多少次都可以。
对于不为 \(0\) 的,直接枚举循环若干次之后再放多少个,然后判断是否可行,取 \(\min\) 即可。
\(n=0\)
傻呗二分加一堆特判居然过了三个点,真神奇
总分:\(50\)
B
测试点 \(7,8\) (\(n \le 2\),\(m \le 1\),\(b_i \in \{1,2\}\),且只有一个 \(i\) 满足 \(b_i =1\))
\(n=1\) 直接贪就行。
先把小的放在 \(a_1\)。
(好像有个东西不是很好描述,贴个代码在这)
int f(int x){
int num=0;
for(int i=0;i<k;i++){
int val=(1ll<<i);
if((x&val)==0) num+=val;
}
return num;
}
然后若大的可加,答案就是 \(\min(a_1 \bigoplus f(a_1),a_2 + f(a_1))\)。这样可以使小的尽量大,大的也不会减小。
若小的可加,枚举每个二进制位,尝试进行操作。(即对小的加,大的异或)
然后如果小的变成更大的那个了,就当做大的可加的情况来做。
否则用现在的状态更新一下答案就是了。
如果两个都不可加,那就加上两个数都为 \(0\) 的二进制位就可以了。
(十分抽象)
爆搜挂了好像是因为把特判 if(n<=2)
写前面了。
总分:\(8\)
C
输出 \(n!\) 有 \(8\) 分,然后没看题没拿,傻呗了。
wsy 这题写了 \(16\) 分?
总分:\(0\)
Day1 总分:\(58\)
Day2
先扫了一遍三个题,首先判断 C 完全不可做,然后感觉 B 的性质分比较好写,就写了一个小时 B。
然后开了 A,先是写了性质 A,然后爆搜了一下。
想了一下 A,感觉是类似于分治的东西,推了一下发现在大样例就假了。
然后好像就写不出来了。
A
测试点 \(1 \sim 5\) (\(n<=4\))
直接 dfs 开哪些石像,然后贪心地走就好了。
特殊性质 A
首先需要尽可能地让 Bob 往左走,这样如果我能够开当前这个石像就肯定开,然后先递归处理左边;否则需要先递归处理右边。
然后也是跑一遍贪心算答案就可以了。
然后性质 B 应该是个树上背包,正解还真就是类似分治的东西,考场上应该是没有想到开启一个石像对于答案的影响。
总分:\(35\)
B
测试点 1
爆搜,但是太难写了,一直没写出来。
\(m=0\)
没有限制,直接输出 \(1\) 即可。
特殊性质 B
若 \(1\) 已经在第一个,就一定可以成功,概率为 \(\dfrac{1}{n}\);
若第一个不是 \(1\),则只要有一个分割点刚好在 \(1\) 左边的那个位置就可以成功。
大力算概率:首先,遇到这种情况的概率为 \(\dfrac{n-1}{n}\);前 \(i-1\) 个都不是 \(1\) 左边,且第 \(i\) 个是 \(1\) 左边的空位的概率为 \(\dfrac{n+i}{1} \times \prod\limits^{i-1}\limits_{j=1} \dfrac{n+i-1}{n+i}\)。全部加起来即可。
总分:\(20\)
C
不可做。
总分:\(0\)
Day2 总分:\(55\)
总分:\(50+8+0+35+20+0=113\)
中规中矩吧。
标签:总分,测试点,int,dfrac,然后,HNOI2023,性质 From: https://www.cnblogs.com/luqyou/p/18063526