4 HT008_123

尚未进行身份认证

我要认证

齐河一中的蒟蒻一只

等级
TA的排名 6k+

[HDU 多校训练] 2020 Multi-University Training Contest 2

A题:Total Eclipse题目链接题意:给出N个点M条边的无向图 每个点有权值 每次可以选择一个连通子图把每个点的权值减一,直到所有点的权值都为0,求最少的操作次数。题解:每次肯定是选择一个联通块,然后把最小值变成0,将这个点删去,分裂成多个连通块继续做。倒过来考虑,变成将B从大到小加入这个图加入每个点 x 时遍历与 x 相连的所有边 (x, y),如果 y 在 x 之前加入且 x 和 y 不连通则将 x 和 y 合并,并将 y 所在连通块的树根的父亲设为 x,得到一棵有根树。那么每个点 x

2020-07-25 02:13:05

[Ecfinal 2019] value

题目描述:给出N个A,B寻找一个集合使价值最大价值即为集合内A的和如果 i,j属于集合内并且 i >1 j>1 i^k=j(k>1) 则价值需要减去j的B值题目分析:每个幂根之间是不会交叉的,我们只需要把每个幂的链挑出来,用二进制去枚举所有的情况即可题目链接:牛客Ac代码:#include <cstdio>#include <iostrea...

2020-01-12 19:55:23

[Ec Final 2018] Misunderstood … Missing

题目描述:我有两个基本属性一个 A 表示每次攻击可以造成的伤害,D为每轮自动增加的攻击力(A D初始值都为0每轮你有三种操作(任选一个1:造成 A+ai 的伤害2:给 D 增加 Bi 的数值3:给 A 增加 Ci 的数值最后求N轮后,最大的伤害数值题目分析:考虑到2 3 操作有后效性,所有我们倒着DP由于 B操作和C操作与攻击次数和攻击与这个操作的差值有关,所以状态里要有攻击次...

2019-12-10 22:58:33

[Ec Final 2018] Eventual … Journey

题目描述:又N个车站,M条边,每个车站分为黑白两种如果两个点颜色一样,可以花1的花费到达,或者两个点有边直接连接。问每个点可以到达的点的总花费的最小值题目分析:互相到达的点花费只有三种可能1:互相连接的点或者颜色一样的点2:如果一个点链接着颜色不一样的点,我就可以通过这个点使用2的代价到达所有颜色不一样的点3:如果一个点没有链接颜色不一样的点,去的点(即终点为颜色不一样的点也没有链...

2019-12-10 22:44:26

[Ec Final 2018] Deja vu of … Go Players

题目:QAQ…题目分析:每次都能拿完一堆,先手的堆数多余后手就输了,否则后手输了题目链接:题目分析AC代码:#include <iostream>#include <cstdio>int n,m;int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&...

2019-12-10 22:33:41

[ICPC2019 南昌站] Eating Plan

题目描述:有一个N的全排列每个位置数的价值是他的阶乘 mod 998857459现在给出m个询问,每次给出一个数,问最短的子段区间和大于等于这个数的时候,这个最短子段的长度是多少, 不存在请输出 -1 (子段和也要 mod 998857459)题目分析:首先 对于M个询问,值大的子段区间长度一定不小于值小的,即如果我们把M个询问离线,按照值升序排列,最后的答案是一个单调不降序列由于mo...

2019-12-08 23:56:34

[ICPC2019 南昌站] Bob's Problem

题目描述:有N个点,M条边边有权值和颜色(黑色 白色)最多选K条白边,黑色边数量不限,问在保证选出的边让图联通的情况下,边取值和最大题目分析:由于黑色边没有限制数量我们可以先把所有的黑色边扔进去,做克鲁斯卡尔然后把白边按照权值降序排列第一次我们先尽量保证图联通,因此当边链接的点不在一个连通块的时候取这条边。记录当前用白边的数量然后判断能否用少于等于K让图联通如果白边还有剩余,我...

2019-12-08 23:46:09

[ICPC2019 南昌站] And and Pair

题目描述:给出一个数字 N (以二进制形式给出)然后寻找数对 (i,j) 满足1:1<=j<=i<=n2:i&n=i3:j&i=0题目分析:首先 第二个条件对于 n 中的二进制0位置i只能取0,1位置 i 可以取 1 或者 0对于 i 的1位置,j只能取 0 ,对于 i 的0位置 j可以取 1 或者 0对于 j<=i这个条件 我们只需要让...

2019-12-08 23:40:18

[NOIP/CSP 2019 提高组] 括号树

题目描述:QAQ…题目分析:设 dp[i]为1-x内合法的子序列括号树num[i]表示i到根的路径上连续已经匹配的括号串数last[i]表示最后一个为匹配的 ( 位置首先 dp[i] 和 last[i] 都要承接父亲的答案如果 i 为 ( 那么更新 last[i]=i如果 i 为 ) 并且有没有匹配的左括号那么 last[i]=last[fa[last[i]]]num[i]=n...

2019-11-28 15:36:55

[NOIP/CSP 2019提高组] 格雷码

题目描述:QAQ…题目分析:我们直接分两个情况讨论,看一个第N个格雷码第K个是从上个格雷码正序+0还是逆序+1来的,然后不停的递归就行了,需要注意的是,我们默认的顺序是顺序,在第二个情况里需要算出这个串在正序里排多少还有就是需要开unsigned long long题目链接:题目链接AC代码:#include <cstdio>#include <iostream...

2019-11-27 21:24:21

[蓝桥模拟] 蒜头君王国

题目描述:有N个点,每两个点都有P的概率建边,问最后N个点联通概率题目分析:概率DP。首先 如果只有一个点 Ans=1两个点 Ans=p我们设 F(n) 为 n个点联通的概率 G(n) 为n个点不联通的概率显然 F(n)=1.0-G(n)目前有i个点,枚举j个点为联通的,那么第i个和j-1个点联通概率即为F(j)∗Cj−1i−1F(j)*C_{j-1}^{i-1}F(j)∗Cj−1...

2019-11-27 00:32:36

[蓝桥杯] 青出于蓝胜于蓝

题目描述:无。题目分析:就是求一个节点子树里有多少个节点编号比这个数小,直接权值线段树动态开点线段树合并就好了。题目链接:题目AC代码:#include <iostream>#include <cstdio>const int maxm=110000;int ans[maxm],root[maxm];int head[maxm],net[maxm*2]...

2019-11-26 23:40:41

[南昌网络赛] Distance on the tree

题目描述:给出一个 N 节点 的树,N-1个边权每次求 U-V上小于等于K的边权个数题目分析:树上主席树把边权下放到深度比较深的节点转为点权求解的时候由于每个点上维护的是点到父亲的值,所以求解的时候应该是 sum[u]+sum[v]-2*sum[lca]题目链接:Distance on the treeAC代码:#include <iostream>#includ...

2019-11-07 22:41:44

[SP10628] COT - Count on a tree

题意描述:给出一个N节点的树,每个点有点权M个询问 每次询问 U->V路径上的第k值题目分析:区间第K值主席树。树上主席树维护点权得出的当前答案应该是 sum[u]+sum[v]-sum[lca]-sum[fa[lca]]题目链接:SPOJ 10628AC代码:#include <iostream>#include <cstdio>#includ...

2019-11-07 22:36:22

[石油大OJ] 腿部挂件

题目描述:给出 N 个数 M个询问每次询问给出 L R X 三个参量询问从L-R中的数字与X最大的异或值是多少题目分析:异或最大值问题应该是用 01 字典树来做然后关于区间直接像主席树那样搞个可持久化就OK了AC代码:#include <cstdio>#include <iostream>#include <algorithm>const ...

2019-11-01 19:27:14

[ICPC 2019 南京网络赛] 比赛题解

持续更新中…A:The beautiful values of the palace题意:给你M个点,Q个矩形,每个点都有一个价值,求每个矩形点价值和题目分析:首先我们根据N的值和坐标可以O1的得出每个点的价值,这样就转化成了求一个二维矩阵前缀和的问题,由于我们开不了那么大的空间,我们就把第一维X排序,第二维Y扔进树状数组查询前缀和即可,把每个询问拆成四个点询问前缀和矩阵和,然后就可以得...

2019-09-03 14:33:01

[POJ 2482] Stars in Your Window

题目描述:给出N个星星的坐标,以及的他们的亮度,给出一个矩形的长和宽,然后求最大值(边上的不算)题目分析:一个星星的贡献区域为 Xi,Yi,Xi+W,Yi+H我们把这个拆成两个线分别为 Xi ,Yi,Yi+H,价值为 valXi+W,Yi,Yi+H,价值为 -val然后把X升序排列,依次在线段树中加入这些线,每次取区间最大值,就可以计算出答案了题目链接:POJ 2482代码:...

2019-08-26 17:09:05

[CodeForces-19D] Point

题目描述:一个二维平面,有三个操作Add X Y 添加 坐标为 X Y 的点Remove X Y 删除坐标为 X Y 的点Find X Y 寻找 X Y 右上第一个点题目分析:离散化 X坐标线段树套Set,同时维护一个最大值,方便优化查询过程题目链接:CF 19D代码:#include <cstdio>#include <algorithm>#in...

2019-08-26 15:08:30

2019牛客暑期多校训练营(第九场)E All men are brothers

题目描述:有N个人M个操作,每次操作让两个人互相认识,认识关系可以互相传递,求每次操作完毕后,选4个互相不认识的人的方案数题目分析:并查集维护联通块内的人数刚开始答案一定是 C(N,4)我们定义一个数量Pre为目前选两个互相不认识的人的方案数 初始值为C(N,2)每次合并两个联通块,如果两个人本来就在一个联通块里是不需要改变答案的。如果没有在一个联通块内,我们考虑如何通过上次的答案求...

2019-08-15 21:01:08

2019牛客暑期多校训练营(第九场) H Cutting Bamboos

题目描述:英语差题目分析:思路来自这位大佬Orz我们二分一个最高的整数,用主席树查询,满足区间内 ans及以上高度的和大于等于第x次切除的,把ans+1上的去处,然后就可以算出答案来了。主席树上查树上的数字和以及数量代码:#include <cstdio>#include <iostream>#include <cstring>#defin...

2019-08-15 20:51:39

查看更多

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