HGDB

题解

学习笔记(1) 未归档(2) 概念(1) 模板(4) 转载(1)

/ 注册

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

数学家的迷题

题意有个数有两种操作将的值改为给定区间，求出的不同的素数因子个数思路这里可以用线段树维护区间区间乘积可以被哪些素数整除首先预处理出内的所有素数，方便查找素因子维护数组表示第个节点表示的区间乘积可以被第个素数整除显然如果使用数组区间操作时间复杂度很高，由于这里数组只有和两种情况，...

bitset 线段树

2021-08-26

1 558

买礼物

比赛的时候知道这题是线段树，但不知道应该维护什么就没有写表示第个礼物的上一个相同礼物的位置表示第个礼物的下一个相同礼物的位置我们要维护的就是区间 ~间的最小值或者的最大值我这里维护的是的最小值，当删除位置的物品时，把置成n+1，查询时看区间最小值小于等于就好 #include <bi...

线段树

2021-02-08

2 567

加法和乘法

牛牛要最后的数为奇数，牛妹要最后的数为偶数。最后两个数可能有三种情况，奇奇、奇偶、偶偶下面分两种情况讨论： 1、最后一次操作是牛妹出手牛妹需要偶数，奇奇可以用加法变成偶数，奇偶可以用乘法，偶偶任意操作都是偶数 &nb...

博弈

2021-02-06

5 583

牛客IOI周赛20-普及组

完全数题意给定一个数n，求出1~n-1内所有n的因数的和m若 n == m ，输出 Pure若 n > m , 输出Late若 n < m ，输出 Early 思路直接暴力枚举1~n内所有n的因子数时间复杂度1e14,铁定是超时的当存在一个数，满足是的因子时，必然有也是...

2020-11-30

2 503

异或

Problem 给定一个长度为n初始全为0的数列ai，下标从1开始。定义操作模k异或v为对所有满足i \equiv 0 \pmod ki≡0(modk) 的下标i，将异或上整数v（即令）。给出q次操作，每次操作之后输出序列的异或和，并且在操作结束之后输出整个序列。序列的异或和为 Inpu...

异或

2020-10-11

3 858

[ZJOI2006]BOWL 碗的叠放来自专栏

题目描述小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：100%数据满足n < = 9。所有输入的数绝对值不超过1000。输入描述: 第一...

暴力

2020-07-17

1 817

失衡天平来自专栏

思路首先注意到数据范围只有100，所以我这里选择二维dp 通过证明不难发现，能带走的最多的重量，无论是分几次拿走的，一定可以变成一次能拿走的方案。表示前 i 个武器放入天平的两端差距为 j 的天平上武器重量的和的最大值所以状态转移方程就是 for(int i = 1 ; i <= n ...

2020-06-09

6 1060

Sumo and Electricity(Easy)

思路这题是Easy版本，只有一个发电站耗电量不确定，所以只需要统计与这个发电站直接相连的发电站的耗电量。因为是要异或和最小，所以这里我统计了与未知发电站直接相连的发电站功耗的贡献，如果某一位1的个数大于0的个数那耗电量在这意味就是1。（异或让贡献尽可能小）其他的直接暴力算就好，要注意电缆的消耗...

2020-06-06

6 774

加边的无向图来自专栏

思路并查集找到联通块的个数，答案就是联通块个数减一。因为这是无向图，所以就不用dfs跑个数了，直接裸的并查集就好了如果没有学过并查集可以去看看这篇博客，这位大佬写的巨详细那就直接上代码了代码 #include<bits/stdc++.h> using namespace std...

2020-06-06

9 925

Cut 来自专栏

思路这题和POJ 3253很像，有兴趣可以去看看可以试着反向思维考虑，将n个长度为1的序列合并成一个长度为n的序列,合并的代价就是合并前的两个序列之和最佳的合并方法应该是尽可能多的合并长的木板，所以最优的策略应该是将目前所有序列中长度最大和次大的序列合并不妨将原序列按降序排列，每次取出最大的...

贪心优先队列

2020-06-06

8 940