9.18考试 第一题count题解
2024-09-01 02:12:14
这道题说起来挺可惜的,当时纠结是用常数大但有可能减少递归层数的模还是用常数小但递归多的回溯纠结了好半天,最终错误的选择了模。导致T了20分,改成回溯就A了。
先分析一下性质,我在考试的时候打表发现在数据范围内因子最多有240个,因此有可能是通过枚举因子进行计算,然后如果说对于一个块他的确可以把一棵树分为几块方法只有一种(不要问我为什么,我也不知道怎么证,但的确如此)那么我们的最坏复杂度就是O(240*n),比理论最大复杂度还多了一倍,这也是为什么当时我自己预估60分的原因,然而这就很尴尬了,这的确能过,因为我们只要搜索到一个不合法位置就可以直接return所以会快许多。而且,对于size小于当前check的我们就没有必要再去搜了,这会降低对于较大因子的时间复杂度。然后就很玄学的过了,额,过了……
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cmath> #include<map> #include<vector> #define N 1000005 using namespace std; int size[N],fa[N],n,a[N]; struct ro { int to,next; }road[N*]; int zz1,zz,sx[N]; void build(int x,int y) { zz++; road[zz].to=y; road[zz].next=a[x]; a[x]=zz; } void dfs(int x) { size[x]=; ;i=road[i].next) { int y=road[i].to; if(y==fa[x])continue; fa[y]=x; dfs(y); size[x]+=size[y]; } } ; bool yx; int dfs2(int x,int l) { ; ;i=road[i].next) { int y=road[i].to; if(y==fa[x])continue; if(size[y]>=l) { int k=dfs2(y,l); ) ; sum+=k; } else { sum+=size[y]; } if(sum>l) { ; } } if(sum==l) { ; } else return sum; } void check(int l) { ,l); ) ans++; } int main() { scanf("%d",&n); ;i<n;i++) { int x,y; scanf("%d%d",&x,&y); build(x,y); build(y,x); } ;i<n;i++) { ) { zz1++; sx[zz1]=i; } } dfs(); ;i<=zz1;i++) check(sx[i]); printf("%d\n",ans); ; }
最新文章
- 利用opencv训练样本分类
- c++之函数重载(函数匹配)
- jquery 之height(),innerHeight(),outerHeight()方法区别详解
- [HDOJ1231]最大连续子序列
- 服务器下自动备份MySQL
- trap命令使用
- WM_VSCROLL
- 人工神经网络简介和单层网络实现AND运算--AForge.NET框架的使用(五)
- 5 输出的properties文件按照key进行排序
- Win10 的虛擬桌面
- 本地文件与服务器文件同步shell脚本。
- SQL2008全部数据导出导入两种方法
- C#文件增删改查
- linux选择sdb sdb4 fat32 还是sda分区
- vue中连续点击3次且时间间隔不超过3秒,才显示div(刚开始隐藏的)
- WISH开发API
- Photoshop CS4破解方法
- SpringBoot详细研究-03系统集成
- (转)Unity3D 游戏贴图(法线贴图,漫反射贴图,高光贴图)
- shiro学习笔记_0200_认证
热门文章
- Linux学习之“vfork函数”
- Objective
- 零元学Expression Blend 4 - Chapter 19 如何让做好的Blend专案变Silverlight网页
- -bash: /root/java/jdk/bin/java: cannot execute binary file
- Model1简介
- qtextedit中的光标问题(通过调用repaint去掉Focus的阴影)
- x64系统的判断和x64下文件和注册表访问的重定向(举例了GetProcAddress后转成函数指针的用法)
- “多团队大规模”开发模式 - 基于SAP HANA平台的多团队产品研发
- python常用数据结构(1)
- 常用Linux网络命令