课件讲解:
然后今天开始了讲题的旅程:
- (讲思路)
- 1.
- https://nanti.jisuanke.com/t/43380
• 给 n(n<=2500)个点两两之间的距离, 现已知原图为一棵无向树, 现在让你还原.
• 可能的图有很多种, 输出一种就行.
讲解:
• 一种可能的图: 对所有距离进行排序, 不难发现两两之间的距离最小的两个点之间肯定有一条边, 边权即为距离.
• 接下来的要么是两点之间有边, 边权为距离, 要么就是已经连好了, 不需要你管, 而因为连好的边已经是尽可能的最小了, 所以一定满足条件.
- 2.
- https://nanti.jisuanke.com/t/43513
• 给一个只有二十个字母的字符串, 长度<=3e5, 要求取出其中的连续一段之后能够重排得到一个回文串, 求这个回文串最长为多少?
讲解:
• 判断一个区间是否能组成回文串有两种条件:
• 1. 长度为偶数, 每种字符出现次数为偶数
• 2. 长度为奇数, 除一种字符以外每种字符出现次数为偶数
• 为第 i 种字符赋值为 1<<i>>1, 然后算出亦或前缀和 xor, 可以发现一个符合要求的区间 [l,r] 满足:
• 1.xor[r]^xor[l-1]=0 且区间长度为偶数
• 2.xor[r]^xor[l-1]=1<<l>>1,1<=l<=20 且区间长度为奇数
• 不难发现两种情况可以合并成为:
• xor[r]^xor[l-1]=1<<l>>1,0<=l<=20
• 另外一个有趣的性质是 xor 的大小不会超过 1<<20
• 那么做法就是存储每种 xor 值第一次出现的点, 然后对于一个 xor[r]来说, 找到一个 xor 值使得亦或后为 1<<l>>1, 复杂度为 20n
(此题 ROS 还需理解)
3. 洛谷 P4942 小凯的数字
• 不难发现那个大数 = l*10^?+(l+1)*10^?+...
• 对它 mod 9 相当于对 l+(l+1)+(l+2)+...+r mod
9
• 等差数列求和
4. 洛谷 P3799 妖梦拼木棒
• 有 n 根木棒, 现在从中选 4 根, 想要组成一个正三角形, 问有几种选法?
• N<=100000, 长度<=5000
讲解:
• 显然我们要找两个相同长度的木棒, 然后再找两根长度加起来等于上面长度的木棒.
• 发现长度很小, 于是暴力枚举两根木棒的长度, 然后组合数计算一下即可.
5. 洛谷 P3197 [HNOI2008]越狱
• 监狱有连续编号为 1...N 的 N 个房间, 每个房间关押一个犯人, 有 M 种宗教, 每个犯人可能信仰其中一种. 如果相邻房间的犯人的宗教相同, 就可能发生越狱, 求有多少种状态可能发生越狱.
这道题 ROS 自己按照思路手敲了一下.
但还是按照惯例把 ppt 内的讲解 crtl+v 一下吧
• 不妨考虑有多少种状态不会越狱.
• M*(M-1)*(M-1)......
ROS 讲解:
首先先求一下所有的可能性: M^N(^ 为求次方的符号) 1
然后我们发现求有多少种状态不会越狱比较难.
那就 "正难则反" 不就好了!
求一下有多少种情况会越狱.
对于一种排布来说只有会越狱和不会越狱两种情况.
所以不会越狱的情况数 = 总情况数 - 会越狱的情况数
好的我们来看怎么求会越狱的情况数.
根据乘法原理有:
对第一个人来说他有 M 种宗教可以选择
对第二个人来说他不能选择和第一个人一样的宗教所以有 M-1 种宗教可以选择
对第三个人来说他不能选择和第二个人一样的宗教所以有 M-1 种宗教可以选择
.
.
.
所以根据乘法原理有:
会越狱的情况数: N*(M-1)^(N-1)(^ 为求次方的符号) 2
所以用1-2就好了!
是不是很简单!
好的 ROS 到洛谷上敲这道题的代码, 第一次 10 分....
原来取模没有对每个结果都取导致了溢出 (或者得到负数结果) 的问题.
好的对每个结果取模改一下.
然后第二次提交 70 分.
这又是什么情况?
最后上讨论一看发现是 c++ 的玄学取模导致的, 我们需要在最后一步 (输出答案的一步) 把原先的((ksm(m,n)%esp)-((ksm(m-1,n-1)%esp)*m))%esp 改成((ksm(m,n)%esp)-((ksm(m-1,n-1)%esp)*m)%esp+esp)%esp 防止出现玄学负数解
整体 AC 代码:
- #include<bits/stdc++.h>
- #define esp 100003
- #define ll long long
- using namespace std;
- ll m,n;
- ll ksm(ll a,ll b){
- if(a==1||a==0) return a;
- if(b==1) return a;
- if(b==0) return 1;
- ll tmp=ksm(a,b/2);
- if(b&1) return (tmp%esp)*(tmp%esp)%esp*(a%esp)%esp;
- return (tmp%esp)*(tmp%esp)%esp;
- }
- int main(){
- scanf("%lld%lld",&m,&n);
- printf("%lld",((ksm(m,n)%esp)-((ksm(m-1,n-1)%esp)*m)%esp+esp)%esp);
- return 0;
- }
代码量少但是思维含量还是有的.
6. 洛谷 P6033 合并果子 加强版
• n 堆果子, 每次合并两堆, 代价为两堆果子数量之和
• 问最小代价把所有果子合并为一堆
ppt 讲解:
• n 堆果子, 每次合并两堆, 代价为两堆果子数量之和
• 问最小代价把所有果子合并为一堆
• 一个显然的贪心! 每次合并最小的两堆.
• 证明并不显然, 要用到哈夫曼树的结论, 总之就不证了, 感兴趣可以自己去查一下.
• 毕竟选这道题的目的不是为了这个
• n 堆果子, 每次合并两堆, 代价为两堆果子数量之和
• 问最小代价把所有果子合并为一堆
• 由于 a 很小我们可以进行 O(n)的排序, 可问题是 n<=1e7 我要怎么做才能每次都拿出两个最小的果子?
• 不难发现, 我们每次合并出来的果子的大小是递增的.
• 于是原果子堆一个队列, 新果子堆一个队列, 就可以保证队列的单调性.
• n 堆果子, 每次合并两堆, 代价为两堆果子数量之和
• 问最小代价把所有果子合并为一堆
• 由于 a 很小我们可以进行 O(n)的排序, 可问题是 n<=1e7 我要怎么做才能每次都拿出两个最小的果子?
• 不难发现, 我们每次合并出来的果子的大小是递增的.
• 于是原果子堆一个队列, 新果子堆一个队列, 就可以保证队列的单调性.
课后作业:
1.P2827 蚯蚓
• 先说一句, 优先队列会被卡常 TLE
- 2.
- https://nanti.jisuanke.com/t/43514
• 请大家自己翻译
• 可以告诉大家这题是一道大模拟
• 讲的话没什么意思, 但是到时候打算问一些同学一些实现上的细节.
来源: http://www.bubuko.com/infodetail-3447674.html