2 七九河开

尚未进行身份认证

暂无相关描述

等级
博文 498
排名 8k+

斯坦纳树模板

出自lxw博客https://blog.csdn.net/qq_30358129/article/details/94589381给出n个点,然后给出m条双向边,边有边权。再给出一个大小为k的点集,求使得点集联通的最小花费。时间复杂度O(n*3^k+cE*2^k),其中c为spfa常数。#include<bits/stdc++.h>#definerep...

2019-07-03 21:18:33

Bus Planning Kattis - busplanning (状压DP)

题目https://cn.vjudge.net/problem/Kattis-busplanning题意给你n个人,有些人有矛盾,给定每个车的容量,问最少多少辆车能装下。思路状压DP#include<bits/stdc++.h>#definerep(i,a,b)for(inti=(a);i<=(b);i++)usingnamespa...

2019-07-01 21:18:05

Project Presentation Gym - 102191I (LCA + dfs序)

题目https://cn.vjudge.net/problem/Gym-102191I题意给你n个点的树,每个点有权值,问所有的权值的本身及祖先有多少点思路所有相同点深度之和相加就是答案,但是会有点重复计算,要求LCA,但两两求LCA就会超时,只需要按DFS序排序,和前一个求LCA就可以了代码#include<bits/stdc++.h>using...

2019-07-01 10:53:43

Birthday Cake Kattis - birthdaycake (几何)

题目https://cn.vjudge.net/problem/Kattis-birthdaycake思路给你一个圆,和n个点,m个直线,问能否把圆分成n块并每个块都有一个点思路暴力判断1判断能否分成n块直线每有个交点就可以把一块分为两块,题目保证和圆相交就把圆分成1+m块,只看暴力两两求交点是否在园内2判断是否没块只有一个点,对于每个直线,把点两两带入,求...

2019-06-21 17:24:44

Canonical Coin Systems Kattis - canonical (完全背包)

题目https://cn.vjudge.net/problem/Kattis-canonical题意给你n种钱数问有贪心凑各种钱数是否是最优的思路背包一遍和贪心一遍比较是否是一样优的代码#include<algorithm>#include<iostream>#include<cstring>#include&l...

2019-06-21 17:19:00

Height Preservation Kattis - heightpreservation

题目https://cn.vjudge.net/problem/Kattis-heightpreservation题意给你个图,为你改变高度后但不改变相对高低问有的最小高度为多少思路思维排序后一个点一个点贪心#include<bits/stdc++.h>#definerep(i,a,b)for(lli=(a);i<=(b);i++)...

2019-06-21 17:15:57

Hard Nim(fwt)

题目https://www.lydsy.com/JudgeOnline/status.php?user_id=7989题意n个数异或值为0的方案数,要求n个数为不大于m的质数。思路fwt找n次后的异或和为0的情况代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#...

2019-06-06 16:53:41

FWT(模板)

来自zylhttps://dudulu.net/blog/?p=1705intrev=mod+1>>1;voidFWT(lla[],intn)//n必须为2的某次方{for(intd=1;d<n;d<<=1){for(intm=d<<1,i=0;i<n;i+=m)...

2019-06-06 16:16:14

Ehab and the Big Finale ( 交互题)

题目https://codeforces.com/contest/1174/problem/F题意给你一个n个节点树,有一个未知的x点,让你有限次询问找到x询问的方式有两种1、dy询问x点与y点之间的距离2、sy询问y点到x点的路径中y点的下一个点。思路https://dudulu.net/blog/?p=1696代码#include<bit...

2019-06-04 20:31:02

拉格朗日插值模板

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedeflonglongll;constintN=1100;//mod一定要是质数constintmod=9999991;intpv[N];//前几项,前面无效值用0占位intst=1,ed=1100;...

2019-06-03 17:56:04

雀士分组 (校赛 二分图+二分)

题目http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4532.html题意给你n个点分成两组让max(碰精队max-碰精队min,杠精队max-杠精队min)的值最小思路二分图染色缩点将矛盾的点分为两个线段找到所有点最大和最小如果是同一个线段差即答案...

2019-05-29 21:34:30

And And And (西安邀请赛 点分治 或 树形DP)

题目https://nanti.jisuanke.com/t/39277题意求所有对于一条异或和为0的链有多少条链包含的这条链即如果x到y异或和为0那么统计所有包含x-y的路径找到所有x-y求和思路树上路径问题点分治预处理每个结点有多少后继结点:随便选一个点为根统计字数结点数和记录父亲其他看代码吧#include<bit...

2019-05-29 19:35:46

Miku and Generals (西安邀请赛 二分图+背包)

题目https://nanti.jisuanke.com/t/39271题意给你n个权值然你分成两组使他们的权值和的差最小,其中有些点是相互矛盾的,不能分在同一组思路所有点都是100的倍数,可以直接除以100二分图染色将矛盾的点缩为一个,假设每组小的分为一组,然后交换某些组,就相当于给小的一组加上他们的差值。如果总和为2x那么每组为x是最优的,每组小的和为...

2019-05-27 21:13:21

肝是不可能肝的 (校赛 完全背包)

题目http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4534.html题意R是一个休闲的痒痒鼠玩家,他参加各种活动只使用游戏中的小纸人挂机系统。小纸人会消耗自己的体力代替玩家参与一些活动,获得收益,每项活动可以参加多次。不同的活动收益不同,当然也会消耗小纸人不同数量的体力。小纸人的体...

2019-05-27 21:03:46

Distance in Tree(点分治)

题目https://codeforces.com/problemset/problem/161/D题意给你n个点的树问相距为K的有多少对思路点分治模板#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintinf=10000000;constint...

2019-05-24 21:06:22

Cow Exhibition POJ - 2184 (01背包)

题目https://cn.vjudge.net/problem/POJ-2184题意n头母牛有两个值让你选若干个使他们两个值之和最大并且每个值各自和不得小于0思路想其中一个值看做花费另一个值看做价值跑01背包dp初始化要是很小的值因为有负值存在所以dp会跑出负值因为花费也不能为负数所以扩大100000,打100000当做0花费对于不同正负价值,有按不...

2019-05-22 16:36:38

Charlie's Change POJ - 1787 (多重背包记录路径)

题目https://cn.vjudge.net/problem/POJ-1787题意裸地多重背包但要记录路径思路正常多重背包加个记录路径数组即可#include<algorithm>#include<iostream>#include<cstdio>#include<cstdlib>#include&l...

2019-05-21 20:22:39

P3806 【模板】点分治1

题目https://www.luogu.org/problemnew/show/P3806题意模板题思路模板题#include<bits/stdc++.h>usingnamespacestd;constintinf=10000000;constintmaxn=100010;intn,m;structnode{int...

2019-05-16 19:08:55

Legacy CodeForces - 786B (线段树优化建边+)

题目https://cn.vjudge.net/problem/CodeForces-786B题意最短路思路建两棵树入树和出树入树每个结点向孩子建边出树向父亲建边每棵树的叶子结点不能相互到达只能通过新建的边到达即最短路#include<bits/stdc++.h>usingnamespacestd;typedeflonglong...

2019-05-06 16:20:38

Article HDU - 5236(概率DP)

题目https://cn.vjudge.net/problem/HDU-5236题意一个打字机在打完一个字后会有p概率坏掉,只能保留之前保存的,保存需要x秒并且期间打字机不会坏掉问一个人打n个字采取什么策略需要的时间期望最小是多少思路期望DPdp[i]=(dp[i-1]+1)/(1-p)打印i个字=(打印(i-1)个期望时间+1)/(成...

2019-05-06 11:32:27
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。