ZOJ - 2112 Dynamic Rankings 动态主席树 主席树+树状数组

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-669E 题意&#xff1a;1 x y 在第x秒y点的值1.、2 x y 在第x秒y点的值-1 、 3 x y 查询在x秒y点处的值 题解&#xff1a; 动态主席树&#xff1a;但要注意内存的限制 #include <bits/stdc.h> using na…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6703 题解&#xff1a;因为每次加1e7&#xff0c;k也只有[1, n]&#xff0c;所以结果也就是[1, n 1]&#xff0c;所以对于加了1e7的数我们set记录一下原先的值&#xff0c;对于每次查询&#xff0c;我们输出set中第一个大…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6704 题解&#xff1a;ST表维护下 后缀排序后的公共长度 的最小值&#xff0c;然后二分找出左右符合的位置&#xff0c;主席树维护下排序后的序列&#xff0c;然后主席树查询第k大即可 #include <bits/stdc.h> usi…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6705 题解&#xff1a;建立源点 汇点 跑A*&#xff0c;到最后也一直超内存也真是菜到家了&#xff0c;A*时间空间怎么也得n^2&#xff0c;这个题原来是个贪心。。。。 官方题解&#xff1a; 先把每条边以 形式放进堆&am…...

题目链接&#xff1a;https://cn.vjudge.net/problem/CodeForces-1208B 题解&#xff1a;二分答案&#xff0c;然后枚举区间&#xff0c;注意要先离散&#xff0c;直接用map会T #include <bits/stdc.h> using namespace std; typedef long long ll; int mp[2010]; int …...

题目连接&#xff1a;https://cn.vjudge.net/problem/CodeForces-1208C 题解&#xff1a;因为都是4的倍数&#xff0c;想到二进制位的话应该是每四位一个整体&#xff0c;比如0-15&#xff0c;前两位表示行&#xff0c;后两位表示列&#xff0c;就能得到&#xff1a; 0 1 2 3…...

题目链接&#xff1a;https://cn.vjudge.net/problem/CodeForces-1208D 题解&#xff1a;从后往前操作&#xff0c;这样就能通过si确定出pi是什么&#xff0c;当然不能枚举&#xff0c;线段树维护下当前每个数如果放在当前位置的话si是多少&#xff0c;然后就是线段树的基本操…...

题目链接&#xff1a;https://cn.vjudge.net/problem/CodeForces-1076E 题解&#xff1a;树状数组维护下深度&#xff0c;到达每个节点&#xff0c;对于每次更新容斥一下&#xff0c;对于直接查询即可 #include <bits/stdc.h> using namespace std; typedef long long …...

问题 G: Lexical Sign Sequence 时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] [命题人:admin] 题目描述 Andi likes numbers and sequences, especially, sign sequences. A sign sequence is a sequence which consists of -1 and 1. Andi is a curious person, thus,…...

时间限制: 1 Sec 内存限制: 128 MB 题目描述 Let s be a given string of up to 106 digits. Find the maximal k for which it is possible to partition s into k consecutive contiguous substrings, such that the k parts form a palindrome. More precisely, we say…...

问题 E: Eating Everything Efficiently 时间限制: 1 Sec 内存限制: 128 MB Special Judge [提交] [状态] [命题人:admin] 题目描述 Margriet A. is in pizza heaven! She has bought a one-day access pass to Pizza World. Pizza World is a food festival, where all s…...

划分树&#xff0c;类似线段树&#xff0c;主要用于求解某个区间的第k 大元素&#xff08;时间复杂度log(n)&#xff09; 讲解&#xff1a;https://www.cnblogs.com/hchlqlz-oj-mrj/p/5744308.html 大致就是分治递归的思想&#xff1a; int tree[22][N]; //对应每层每个位置…...

题目链接&#xff1a;https://cn.vjudge.net/problem/HDU-3473 题意&#xff1a;find a number x to make as small as possible! 题解&#xff1a;本来想三分x感觉会T&#xff0c;想了一下&#xff0c;当然x就是[l, r] 所有数的中位数了&#xff0c;至于为什么&#xff0c;可…...

问题 F: The King’s Ups and Downs 时间限制: 1 Sec 内存限制: 128 MB 题目描述 The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than t…...

二维几何&#xff1a; // 计算几何模板 //二维平面 using namespace std; const double eps 1e-8; const double inf 1e20; const double pi acos(-1.0); const int maxp 1010; //Compares a double to zero int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)…...

问题 E: Fruit Slicer 时间限制: 1 Sec 内存限制: 128 MB 提交: 25 解决: 4 [提交] [状态] [命题人:admin] 题目描述 John, a student who is taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the gam…...

问题 I: Monitoring Ski Paths 时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] [命题人:admin] 题目描述 Fresh powder on a sunny day: it is a great time to ski! Hardcore skiers flock to a large mountain in the Rockies to enjoy these perfect conditions. The …...

题目链接&#xff1a;https://cn.vjudge.net/problem/POJ-3580#author0 伸展树学习&#xff1a; 很全&#xff1a;https://blog.csdn.net/qq_33184171/article/details/73549164 图&#xff1a;https://blog.csdn.net/wr132/article/details/50599747 效率&#xff1a;http…...

题目链接&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id3224 题解&#xff1a;灵活运用&#xff0c;像这种不对区间操作的&#xff0c;相同的数放到一块就可以了 #include <bits/stdc.h> using namespace std; #define INF 2e9 10 const int N 1e5 …...

题目链接&#xff1a;https://cn.vjudge.net/problem/HDU-1890 题意&#xff1a;每次将第i个位置到第i大的数所在位置 之间的数进行翻转&#xff0c;输出的是第i大的数所在的位置 题解&#xff1a;按照1-n建树&#xff0c;原序列排序&#xff0c;每次把节点 a[i].id 放到顶部…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6725 题解&#xff1a;每个节点要么取l[i]&#xff0c;要么取r[i]&#xff0c;对于每个节点维护下取最小最大值时的结果即可 #include <bits/stdc.h> using namespace std; typedef long long ll; cons…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6726 题解&#xff1a;我们倒着往前找&#xff0c;对于&#xff08;a&#xff0c;2b-a&#xff09;->&#xff08;x&#xff0c;y&#xff09;那么xy为偶数&#xff0c;(x, y) 往前的话就是(x, (xy)/2)&…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6727 题解&#xff1a;对于当前节点&#xff0c;肯定分为两个区间一个在左一个在右&#xff0c;就把小区间分到最小编号在的那个分支中&#xff0c;如果当前节点最小&#xff0c;那就尽可能让当前节点的标号小…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41298 题解&#xff1a;首先我们要把每个坐标的val求出来&#xff0c;很明显每一圈的个数是一个等差数列&#xff0c;第x圈 a[x] -8x4n4&#xff0c;然后就是先等差前n项和求出之前每一圈的总个数&#xff0c;然后对于x 与…...

题目链接&#xff1a;https://vjudge.net/problem/HihoCoder-1835 题解&#xff1a;首先我们应该能想到到达图形的距离最近那肯定是垂直过去&#xff0c;也就是坐标变为(x1 - k, x2 - k, x3 - k...)&#xff0c;假设图形原点的坐标为(x10, x20, x30 ...)&#xff0c;如果某个x…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41301 题意&#xff1a;N个点M条边的有向无环图&#xff0c;1为唯一入度为0的点&#xff0c;N为唯一出度为0的点&#xff0c;现在你从1号点出发&#xff0c;每单位时间&#xff0c;你有相同的概率&#xff0c;走向下一节点或…...

题目链接&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id1568 李超线段树&#xff1a; 问题&#xff1a; 现在要求你在线动态维护一个二维平面直角坐标系&#xff0c;支持插入一条线段&#xff0c;询问与直线xx0相交的所有线段中交点y的最大/最小值 更新&a…...

链接&#xff1a;https://ac.nowcoder.com/acm/contest/1083/C 来源&#xff1a;牛客网 勾股定理 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 32768K&#xff0c;其他语言65536K Special Judge, 64bit IO Format: %lld 题目描述 给出直…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41389 题解&#xff1a;马拉车处理回文串&#xff0c;每个位置记录后面每个字符出现的第一个位置&#xff0c;然后把每种字符额贡献加起来即可 #include<bits/stdc.h> using namespace std; typedef long long ll; c…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41391 题解&#xff1a;先找出每一对(pi​,pj​)&#xff0c;那么i&#xff0c; j 记录为 区间[l, r]&#xff0c;则查询就变为&#xff0c;在[L,R]内有多少区间&#xff0c;然后我们离线线段树就可以搞定了&#xff0c;按照…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41392 题解&#xff1a;dp[u] 表示 u这个点向下能到达最深深度的概率&#xff0c;因为对于每个点要找k次&#xff0c;只要其中有一次能到达最深即可&#xff0c;所以我们用容斥的思想&#xff0c;即表示为 1 - 不能到达最深…...

题目链接&#xff1a;https://vjudge.net/problem/FZU-2105 其实我想放银川网络赛的链接&#xff0c;emmm 题解&#xff1a;首先或和与是能相互掩盖的&#xff0c;因此我们就可以把这两者用一个laz标记&#xff0c;laz1表示区间都变为1&#xff0c;laz-1表示区间都为0&#x…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41388 题解&#xff1a;这个题比赛最后也没改对&#xff0c;训练时突然想到有个地方写了emmmm 思路&#xff1a;我们先按照dfs序把每个点跑出来&#xff0c;然后vector记录下每个深度的点&#xff0c;很容易就可以想到&…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-5489 题解&#xff1a;删除m个后的最优的LIS在原序列中肯定存在一段间距大于等于m&#xff0c;那么我们就以这一段作为划分线&#xff0c;以后面第一个数x开始作为后半部分&#xff0c;那么后半部分的LIS我们可以倒着nlo…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-750E 题解&#xff1a;哇&#xff0c;原来这个也四个原题。。。。。。维护矩阵的还真是第一次做&#xff0c;这里就说一下CF那题的思路吧 因为最后要2017&#xff0c;那么我们分为5个子序列 空 2 20 201 2017 每…...

构造n * m的螺旋矩阵 讲解&#xff1a;https://wenku.baidu.com/view/7253dc78a26925c52cc5bff4.htm #include <bits/stdc.h> using namespace std; int getnum(int n, int m, int x, int y) {int lev min(min(x, n - 1 - x), min(y, m - 1 - y));int d x y - lev *…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41399 题解&#xff1a;看见的第一思路应该都是差分&#xff0c;但是这个用数组肯定就gg了&#xff0c;所以当时的时候就想到动态开点线段树&#xff0c;mlog(n)但是T了&#xff0c;然后我就把点离散了一下&#xff0c;用点…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41415 题解&#xff1a;对于两边的&#xff0c;要哈希出相应的权重&#xff0c;中间的字符顺序无所谓&#xff0c;只关心是什么字符&#xff0c;所以哈希出每个字符的权重即可。 官方题解&#xff1a; • 但是因为询问有2…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41408 细心细心细心 #include <bits/stdc.h> using namespace std; const int N 1e5 10; struct node {char name[15];int id;int b[5]; }p[N]; int n; int a[10]; bool judge1() {for(int i 1; i < 5; i) {if…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41402 题解&#xff1a;首先和1联通的糖果屋都能到达&#xff0c;其他不能到达的肯定被恶魔屋挡住了&#xff0c;那就在挡住的所以恶魔屋中选择一个最优的就可以了&#xff0c;怎么算最优呢&#xff0c;因为到达恶魔屋之后&…...

题目链接&#xff1a;https://www.51nod.com/Challenge/Problem.html#problemId1571 现在有一个序列 a1, a2, ..., ana1, a2, ..., an &#xff0c;还有m个查询 lj, rj (1 ≤ lj ≤ rj ≤ n)lj, rj (1 ≤ lj ≤ rj ≤ n) 。对于每一个查询&#xff0c;请找出距离最近的两个元素…...

链接&#xff1a;https://ac.nowcoder.com/acm/contest/163/A 来源&#xff1a;牛客网 题目描述 Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6242 题意&#xff1a;n个点&#xff0c;找到一个圆&#xff0c;满足圆上点的数目大于等于⌈N / 2⌉ 题解&#xff1a;三个不在一条直线上的点确定一个圆&#xff0c;随机到圆上点的概率是1 / 2&#xff0c;那么三次就是…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6393 题意&#xff1a;n个点n条边的图&#xff0c;求两点间的最小距离 题解&#xff1a;如果是一个树的话&#xff0c;那么我们就可以倍增dfs序&#xff0c;然后用线段树维护下就可以了这样是nlogn的复杂度&a…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220D 题意&#xff1a;n个数&#xff0c;如果节点 i 和 j 满足 |i - j | 属于B&#xff0c;则i和j有一条边&#xff0c;问B集合最少删除多少边&#xff0c;使得得到的图是个二分图 题解&#xff1a;根据二分图的…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220E 题意&#xff1a;n个点m条边的无向连通图&#xff0c;起点s&#xff0c;每个点有权值&#xff0c;求遍历无向图得到的最大权值和。但是不能走回头路&#xff0c;即如果从U走到V那么下一步不可以从V走到U 题…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6156 题意&#xff1a;区间[L, R]的数&#xff0c;写成k进制(l<k<r)后&#xff0c;如果是回文串&#xff0c;那么f(x,k)k,否则f(x,k)1&#xff0c;对f求和 题解&#xff1a;一看这种题就是数位dp&#xff0c;当时想…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6153 题意&#xff1a;对于s2的每一个后缀&#xff0c;假设长度为l&#xff0c;在s1出现的次数为k&#xff0c;求l*k的和 题解&#xff1a;我们把两个串都倒过来&#xff0c;变为s1,s2&#xff0c;那么问题就变为&#x…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-100589A 题意&#xff1a;n个点&#xff0c;根节点为1的树&#xff0c;两种操作&#xff0c;1 L y 与根节点距离为L的节点权值全部加上y&#xff0c;2 x x子树的权值总和 题解&#xff1a;对于更新操作&#xff0c;因为更…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6731 题意&#xff1a;n个点&#xff0c;m次查询&#xff0c;每次给你一个点&#xff0c;从n个点挑出两个能组成多少直角三角形 题解&#xff1a;假设询问的是点p&#xff0c;直角可能是p也可能是其他两点的某…...