题意： 小H正在玩一个战略类游戏，她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸敌国的城市形成了一棵树，小H会依次进行Q次轰炸，每次会选择一个城市A进行轰炸，和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数)，轰炸结束后，小H还想知道当前城市A受损的次数作为游戏的开发者之一，你有义务回答小H的问题 题解： 考虑每个点对其他点的影响，当我们将任意一点设为跟后，由于每个点的父亲只有一个，那么当攻击某个点后，该点对他的父亲节点即父亲节点的父亲节点的影响都可以O(1)的更新 所以我们设dp[i][j]。表示i节点能向下攻击的范围，所以即为所求 代码： #pr...

题意： 多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x0<=l,r<=1e9 题解： 预处理出范围内所有完全平方数（小于1e5个），然后分别二分l，r所在的位置做差就可以 代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts(...

题意： 给n个时间长度（秒），问这些时间是否能组成3600的倍数 -- 题解： 方案1：bitset<3603>b，记录每个时间是否能够得到，枚举每个数的贡献：最后看b0是否为1即可方案2：普通背包，令dp[i]表示i是否到达，然后转移即可，注意转移顺序！！ 代码 1 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second ...

相反数 题意： 给一个数n，输出n颠倒后的数与n的和 n<1e5 代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace st...

题目描述 For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far. 题解 有两种方法第一种就是直接离散化后，用权值线段树查询第k大就行。这里主要说一下第二种，也就是对顶堆做法，顾名思义，对顶的堆：一个最小值在前qq，一个最大值在前q，那么我们在不断插入数据的...

A Maximize The Beautiful Value 题目大意： 给一单调不减序列，问进行一次操作和序列的 最大值是多少？操作为：选择下标为j的数字使他向前移动大于等于k个位置,显然j>k; 题解: 显然贪心来讲，大的数位置越靠后 越大，所以对于每个数我们肯定贪心的向前移动K个位置，并且数列未操作时已经达到最大值，那么我们只需要枚举一下，每个数往前移动k个位置，使当前的和减小的最少就好了 代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt&lt...

题目描述 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 题解 首先分析题意，发现题目中 '每次操作需要选择一个节点i，i必须是白色的' 这一限制其实是没有意义的，因为我们只要从上向下染色，是不会碰到染色的点的，因为每个点只能向上传递颜色。那么问题就转换成最少选几个点，使整颗树变...

题目描述 shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数 题解 太妙了太妙了，1.首先既然任意相同颜色的点的路径均为一个颜色，那这其实就是当于一个联通块。那么本题就转化为把这颗树划分为小于等于k的连通块，然后在这些颜色相同的连通块上任意染色就可以了。 2.所以我们可以枚举连通块的个数，然后用这棵树能划分成这些连通块的方案数*染色的排列组合就能得到答案 3.那现在的问题就是怎么求i个连通块的方案数？由于这是一颗树，任意一条边都连接着两个连通块，那么将这颗树划分...

题意 给一主串s，有m次询问，每次询问串t是否为s的子序列 题解 很简单的一道题呀！考虑最暴力的方法：每次询问的串直接在主串上扫描复杂度为O(nsumbi)但其实这其中有很多步骤是没有意义的我们只需要把每种字母出现的位置存进一个vector里，然后对于每次询问，只需循环模拟二分就可以啦！时间复杂度为O(lenlog(n)) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #d...

题目描述 Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 w现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。 题解 m=n-1并且图联通，那么这个图就是一棵树，所以本题可转换为，以S为根的树，求所有叶子节点与S不连通的最小代价。那么我们可以将每条边的边...

题目描述 有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。现在你想要对每一次行程，求出会进行多少次购买事件。 题解 注意题目里所说的‘**保证 v 在 u 前往首都的最短...

题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 题解 首先问题可以转化为solve(r)-solve(l-1)的形式那么考虑如何求1~x中满足题意的数量既然要求高位，那么我们可以枚举这个最高位，可以看做[1,2),[10,20),[100,200)这样的形式来算1的数量即，我们要求每个区间里的每个数的倍每个倍数<x的数量，那么对于一个数i，它的倍数<x的数量为 ceil(x/i);所以问题就转化为对每个区间的sigma(ce...

题面 Today HH becomes a designer, and he faces a problem so he asks you for help.Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between ...

Question 给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。 Sample input 8 31 3 -1 -3 5 3 6 7 Sample output -1 -3 -3 -3 3 33 3 5 5 6 7 Answer: 第一眼看这题好简单啊直接建立一颗线段树，然后区间查询(easy!)，交上去发现 MLE了40%；😟考虑更优的解法:单调队列：就像单调栈一样，保证队列里的下标代表的元素一直是递增或递减。我...