NOIP2014 D2T3 解方程 BZOJ3751 UOJ20 数论 秦九韶算法 玄学
大家都很强， 可与之共勉 。 话说这是一道简单爆了的难题。 【NOIP2014】解方程 已知多项式方程： a0+a1x+a2x2+...+anxn=0 求这个方程在 [1,m] ...
[UOJ #140]【UER #4】被粉碎的数字
题目大意：定义$f(x)$为数字$x$每一位数字的和，求$\sum\limits_{i=1}^R[f(x)=f(kx)]$。$R\leqslant10^{18},k\leqslant10^3$ 题解：数位$DP$，从低位到高位$DP$，定义$f[i][j][x][y]$为从低到高第$i$位，$j=f...
UOJ#192. 【UR #14】最强跳蚤
题目链接 http://uoj.ac/problem/192暑期课第二天树上问题进阶具体内容看笔记博客吧题意n个节点的树T 边有边权w 求满足(u, v)上所有边权乘积为完全平方数的路径有多少条看到“所有边权乘积为完全平方数” 想到完全平方数的特殊性就是分解质因数后 质因数指数都为偶数然后就想到分解...
[UOJ#268]. 【清华集训2016】数据交互[动态dp+可删堆维护最长链]
题意给出 \(n\) 个点的树，每个时刻可能出现一条路径 \(A_i\) 或者之前出现的某条路径 \(A_i\) 消失，每条路径有一个权值，求出在每个时刻过后能够找到的权值最大的路径(指所有和该路径有交的路径 \(A\) 的权值和) \(B\) 的权值是多少。\(n\leq 10^5\)分析结论：两...
[UOJ228] 基础数据结构练习题 - 线段树
考虑到一个数开根号 \(loglog\) 次后就会变成1，设某个Node的势能为 \(loglog(maxv-minv)\) ，那么一次根号操作会使得势能下降 \(1\) ，一次加操作最多增加 \(logloga\) 的势能。#include <bits/stdc++.h>using n...
UOJ228 简单数据结构练习题
Description传送门维护一个数列, 有以下操作:对[l,r]同时加上x把[l,r]开根后下取整.查询[l,r]之和n,m \(\leq\)$ 100000, $$a_i,x \leq 10^5$Solution考虑一个简易的线段树,直接对一个区间进行开根. 如果这个区间数字不同就继续往下递归...
uoj228：基础数据结构练习题
题意：http://uoj.ac/problem/228sol ：线段树开根操作对于节点x，可以在max[x]-min[x]<=1时直接做，转化为区间减或区间覆盖#include<iostream>#include<algorithm>#include<cstd...
【线段树】uoj#228. 基础数据结构练习题
get到了标记永久化sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。给出一个长度为 nn 的数列 AA，接下来有 mm 次操作，操作有三种：对于所有的 i∈[l,r]i∈[l,r]...
uoj #228. 基础数据结构练习题 线段树
#228. 基础数据结构练习题统计描述提交自定义测试sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。给出一个长度为 nn 的数列 AA，接下来有 mm 次操作，操作有三种：对于所有...
UOJ228：基础数据结构练习题——题解
http://uoj.ac/problem/228参考：https://www.cnblogs.com/ljh2000-jump/p/6357583.html考虑当整个区间的最大值开方==最小值开方（实质上就是区间开完方后所有数都相等），那么我们开一次方就可以了。听说有证明如果达到上面的那种情况的话...
【UOJ#228】基础数据结构练习题 线段树
#228. 基础数据结构练习题题目链接：http://uoj.ac/problem/228Solution这题由于有区间+操作，所以和花神还是不一样的。 花神那道题，我们可以考虑每个数最多开根几次就会成1，而这个必须利用开根的性质我们维护区间最大、最小、和。区间加操作可以直接做。区间开方操作需要特殊...
【UOJ228】基础数据结构练习题（线段树）
【UOJ228】基础数据结构练习题（线段树）题面UOJ题解我们来看看怎么开根？如果区间所有值都相等怎么办？显然可以直接开根如果\(max-sqrt(max)=min-sqrt(min)\)怎么办？此时意味着虽然开根出来的值不同，但是减去的值相同举个例子，比如\(8,9\)开根后是\(2,3\)虽然值...
【uoj58】 WC2013—糖果公园
http://uoj.ac/problem/58 (题目链接)题意给定一棵树，每个点有一个颜色，提供两种操作：1.询问两点间路径上的${\sum{v[a[i]]*w[k]}}$，其中${a[i]}$代表这个点的颜色，${k}$表示这个点是这种颜色第${k}$次出现2.修改某个点的颜色Solution...
UOJ#7. 【NOI2014】购票 点分治 斜率优化 凸包 二分
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ7.html题解这题是Unknown的弱化版。如果这个问题出在序列上，那么显然可以CDQ分治 + 斜率优化 + 凸包上二分来做。那么它出在树上？点分治。写挂了好多地方调了好久，自闭了。代码#pragma GC...
●UOJ58 [WC2013]糖果公园
题链：http://uoj.ac/problem/58题解：树上带修莫队。每个块的大小为$n^{\frac{2}{3}}$，在dfs时，把点集分为若干块。然后类似序列带修莫队，三个关键字：bel[u],bel[v],time来排序，从上一个询问(u,v)更新到新的询问(u',v')时，首先把时间弄对...
UOJ#22. 【UR #1】外星人
传送门分析我们发现一个很神的性质，就是对于一个数如果放在它之前的数小于它那它一定对答案没有贡献于是我们用dp[i][j]表示从大往小考虑了前i个数，当前答案是j的方案数我们知道它由两种情况转移来，一种是把这个数放上，另一种是在后面的位置选任意一个给它代码#include<bits/stdc++...
uoj #5. 【NOI2014】动物园 kmp
#5. 【NOI2014】动物园Time Limit: 20 SecMemory Limit: 256 MB题目连接http://uoj.ac/problem/5Description近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭...
【uoj228】 基础数据结构练习题
http://uoj.ac/problem/228 (题目链接)题意给出一个序列，维护区间加法，区间开根，区间求和Solution线段树。考虑区间开根怎么做。当区间的最大值与最小值相等时，我们直接对整个区间开根。最坏情况下，一次开根的复杂度最坏是${O(n)}$的，然而每次开根可以迅速拉近两个数之间...
UOJ#218. 【UNR #1】火车管理 线段树 主席树
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ218.html题解如果我们可以知道每次弹出栈之后新的栈顶是什么，那么我们就可以在一棵区间覆盖、区间求和的线段树上完成这个问题。于是本题的重点转到了如何求新的栈顶。考虑用一个主席树维护一下每一个时刻每一个位置...
二分图最大匹配|UOJ#78|匈牙利算法|边表|Elena
#78. 二分图最大匹配从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶。请问这个班级里最多产生多少对配偶？输入格式第一行三个正整数，nl,nr,...