希胤 - 个人主页动态 - 牛客网

发布(195) 评论刷题收藏

2021-06-02 18:07

已编辑

门头沟学院 Java

2019蓝桥国赛

A 签到题 #include<bits stdc++.h> using namespace std; #define ll long long int main(){ for(int i=2020;;++i){ for(int j=i+1;;++j){ if(i*i-2019*2019==j*j-i*i){ cout << i + j ; return 0; } else if(i*i-2019*2019<=j*j-i*i) break; } } return 0; } B 背包是一定体积内的最大价值（不需装满），装箱是刚好等于箱子体积的方案数（要装满） #inc...

0 点赞评论收藏

分享

2024-07-24 15:16

已编辑

门头沟学院 Java

分块（模板）

题目：数列分块入门 3 参考博客 分块也是对区间操作 虽然没有树状数组快但是什么都能维护 未闻花名，但识花香 #include<bits/stdc++.h> using namespace std; namespace{ template<typename T> inline void read(T &s){ T f=1;s=0;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s&...

0 点赞评论收藏

分享

2021-05-27 20:14

已编辑

门头沟学院 Java

2021浙江省赛

C 正方体比例： 1:2:3（未开根号） 直接8个点两两算边～12/12/4而且长度符合1，2，3比例（我的距离没有开方，实际上是1，√2，√3） #include<bits stdc++.h> using namespace std; int const N=107; int t; struct L{ int x,y,z; }a[N]; int pan(L a,L b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) +(a.z-b.z)*(a.z-b.z); } map<int,int>mp; map<int,i...

0 点赞评论收藏

分享

2021-06-01 15:34

已编辑

门头沟学院 Java

2020蓝桥国赛

C 一个数a不可能有比sqrt(a)还大的质因子，除了它自己 质因数分解定理 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e2+7; int n; ll p[N]; int main(){ cin >> n; for(int i=1;i<=n;++i){ int z=i; for(int j=2;j<=sqrt(z);++j){ //一个数a不可能有比sqrt(a)还大的质因子，除了它自己 while(z%j==0) p[j]++,z/=j; }...

0 点赞评论收藏

分享

2021-05-23 23:23

已编辑

门头沟学院 Java

一起来做题~欢乐赛1

A 可以用map离散化 #include<bits/stdc++.h> using namespace std; int const N=2e5+7; int t,n,m; map<int,int>pos,cnt; //可以用map离散化 //记录在数轴的位置并映射出它的值 map<int,int>::iterator it; int main(){ cin >> t; while(t--){ cin >> n >> m; pos.clear();cnt.clear(); for(int i=1;i<=n;++i){...

0 点赞评论收藏

分享

2021-12-13 16:07

已编辑

门头沟学院 Java

树上背包即在树上的背包（树上背包理解2）

题目  选课，时间冲突就是拓扑排序 这题是一个前驱对应多个后继，所以可以用树形dp（多对一也可以用） 若多个前驱对应多个后继，要用拓扑排序 看出是背包（树上）（体积为1） 强制二叉树只是让你好理解树上背包 模型的形还是用背包的外观看出 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=3e2+7; int const M=3e2+7; struct node{ int a,next,len; }e[M<<1]; int cnt,head[N]; void add(i...

0 点赞评论收藏

分享

2021-05-11 15:28

门头沟学院 Java

逆序（从根）操作，即可选黑点，但代码依然是从叶子操作 #include<bits/stdc++.h> using namespace std; #define ll long long int const INF=0x3f3f3f3f; int const N=1e5+7; int const M=1e5+7; struct node{ int a,len,next; }e[M<<1]; int head[N],cnt; void add(int x,int y,int len){ e[++cnt].a =y; e[cnt].len =len; e[cnt].next ...

0 点赞评论收藏

分享

2021-05-10 00:34

门头沟学院 Java

树形dp先分析一部分的树形结构怎样最优以及单点（放和不放）的情况

题目：旅游  住宿点可以是未被游览的任何一点游玩天数=住宿天数即求最多住宿天数易知：住宿点不能同时是父亲和儿子 即最大独立集 最大独立集（没有上司的舞会）（来的人尽可能多）最小点覆盖（放的点尽可能少）最小支配集（放的点尽可能少）最大独立集和最小支配集有些相反的意思判断是哪种模型或推转移方程时，先分析一部分的树形结构怎样最优，再看单点（放和不放）的情况 #include<bits/stdc++.h> using namespace std; #define ll long long int const M=5e5+7; int const N=5e5+7; ll const INF=...

0 点赞评论收藏

分享

2021-05-08 13:34

已编辑

门头沟学院 Java

Rinne Loves Edges

搜索时上一步的（以前的）东西可以通过参数带到下一步 #include<bits/stdc++.h> using namespace std; #define ll long long int const M=1e5+7; int const N=1e5+7; ll const INF=0x7fffffffffffffff; int n,m,s; struct node{ int a,len,next; }e[M<<1]; int head[N],cnt; void add(int x,int y,int len){ e[++cnt].a =y; e[cnt].len =...

0 点赞评论收藏

分享

2021-05-08 12:01

门头沟学院 Java

树形dp之树的直径

题目：树上子链  树的最长子链（直径）= 以根为终点的最长子链 + 以根为终点的次长子链f[i]表示以 i（根）为终点的最长子链 //树的直径有两种求法 //1.树形DP（可以有效处理负边权） //2.两次dfs或bfs（无法处理负边权） #include<bits/stdc++.h> using namespace std; #define ll long long ll const INF=0x3f3f3f3f3f3f3f3f; int const N=1e5+7; int n,cnt; int head[N]; struct node{ int a,next,len; }ed...

0 点赞评论收藏

分享

2021-05-07 10:21

门头沟学院 Java

1、unordered一般指无序的意思 unordered_map //无序的map unordered_set //无序的set

0 点赞评论收藏

分享

2021-04-28 15:09

门头沟学院 Java

P4198 楼房重建

参考博客  #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+7; int n,m; ll tr[N<<2]; //tr[p]表示斜率递增的长度 double minx[N<<2],maxn[N<<2]; ll ask(int p,int l,int r,double z){ if(l==r) return maxn[p]>z; int mid=(l+r) >> 1; if(maxn[p*2]<=z) retu...

线段树和数状数组经典例题

0 点赞评论收藏

分享

2023-03-27 22:51

已编辑

门头沟学院 Java

扫描线模板

参考博客 题目：P1502 窗口的星星 线段树处理的是线段（一维几何计数）（张昆玮） 线段树就是处理线段上的区间问题 扫描线把矩形转化为线段（二维转一维） 扫描线就是去除一维，使一堆矩形变成一堆线段，最后再使一堆线段合并成一条线段 扫描线一般处理矩形有关的问题 听懂了思想，代码随便看一份都可以 已过洛谷全部测试点 此题是把观测点缩成一个点，而把星星由一个点变成一个活动范围，再用扫描线，看哪个点的星星数最多 扫描线用了差分的思想 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=...

线段树和数状数组经典例题

0 点赞评论收藏

分享

2021-04-26 21:19

门头沟学院 Java

单点修改直接改下去，区间修改懒标记

sin(a+w)=sina* cosw - cosa* sinwcos(a+w)=cosa* cosw - sina* sinw 线段树做题方式：先判断是否是线段树（边改边查，区间修改...)再思考tr[N]维护什么若单点修改，则无懒标记区间修改，ly[N]为待操作数（再思考待操作数是什么） 注意：变量在操作后会改变值，不能乘当前的变量，要乘原来的 #include<bits/stdc++.h> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define l...

线段树和数状数组经典例题

0 点赞评论收藏

分享

2021-04-26 20:32

门头沟学院 Java

[TJOI2018]数学计算

题目：[TJOI2018]数学计算小数不能取模树状数组的tr[p]表示包含a[p]（位置p上的元素）的属性和（可能是和、乘..）树状数组的性质：查前改后 线段树的形：边改边查区间修改要有懒标记，若每个区间单点修改，它很慢单点修改可以直接修改 O(lgn),不用懒标记懒标记就是为区间修改而设计的，表示其子区间的待操作数  线段树就是要考虑维护什么东西懒标记存什么样的操作数 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+7; ll tr[N<<2]; int...

线段树和数状数组经典例题

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务