段三园的小迷弟

题解

心得(37) 未归档(1) 模板题(7) 读书笔记(2)

/ 注册

全部文章 / 题解（共110篇）

pta红色警报，并查集

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。输入格式：输入在第一行给出两个...

并查集

2020-01-20

1 810

pta列车调度，贪心+二分查找

火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待...

二分贪心

2020-01-20

0 1716

pta是否完全二叉搜索树，完全二叉树

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。输入格式：输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间...

完全二叉树

2020-01-20

1 778

P1986 元旦晚会，贪心

题目背景玛雅人预言的世界末日没有发生，我们迎来了地球的第五个太阳纪。学校将要举办第五个太阳纪的第一次元旦晚会。Brett的班级要参加，并且还表演节目。题目描述 Brett 班的节目是这样的：全班 n个同学排成一排，同学们手拿话筒，齐唱《喜洋洋与灰太...

贪心

2020-01-20

0 684

P5148 大循环，组合+逆元

题目描述 hke有一天学会了循环语句，感到很神奇。回到家，他用c++写下这段代码： void work() { ans=0; for(a[1]=1;a[1]<=n;++a[1]) for(a[2]=1;a[2]<a[1];++a[2]) ...

快速幂逆元排列组合

2020-01-20

0 631

pta多项式A除以B，模拟+取整round

模拟多项式除法 round()是c99以上版本自带，c89没有 #include <bits/stdc++.h> using namespace std; unordered_map<int,double> a,b,c; ...

模拟

2020-01-20

0 927

SP19148Kill them All，组合+阶乘逆元

a，b杀n个人，每时每刻都必须是b>a 第一个人必定是b杀，所以问题就转化为图像从（1,0）到（b杀,a杀）不碰y=x的方法数满足方法数=所有方法数-不满足方法数不满足方法数计算：从（0,1）到（b杀，a杀）的方法数（如图只要把每次的路线按y=x对称就是一条（1,0）...

逆元排列组合

2020-01-18

1 704

CF57C Array，排列组合/dp +逆元

思路一：从1~n中选几个数但这几个数的顺序不变我们把1和|的序列看作一个组合如1||11表示一个1，零个2，两个3 共2n-1个位置放n个1，n-1个隔板| 所以就有情况，然后对称性，加上不增序列共，其中有n个同一数序列重复计算，如 1 1 1 1 1 1...

逆元 dp 排列组合

2020-01-15

0 1008

P5431乘法逆元2，前缀后缀+逆元+手写读入

😀因为exgcd一次是log2N，如果直接每个a【i】求逆时间复杂度为NlogN 所以优化成 😀因为s在计算中要%p，所以s/a[i]不一定是整数，所以又要用前缀积和后缀积来处理，即s/a[i]==pre[i-1]*suf[i+1] 😀这个题目中由于时间为0.55s<1...

逆元前缀和输入输出

2020-01-14

0 671

pta7_11玩转二叉树（先序中序建树）

前序遍历：根节点 -> 左子树 -> 右子树中序遍历：左子树 -> 根节点 -> 右子树后序遍历：左子树 -> 右子树 -> 根节点步骤： 1.找根节点 2.确定左右子树范围 3.把子树当做一棵树递归求解建树代码 ma...

树的顺序遍历数据结构

2020-01-10

0 674