树剖一好题。我心水了ww 题目描述 给定一棵n个节点的树,有两个操作: CHANGE i ti 把第i条边的边权变成ti QUERY a b 输出从a到b的路径中最大的边权,当a=b的时候,输出0 输入输出格式 输入格式: 第一行输入...
因为人傻常数大写了一天的题目。 原题传送门 题目意思另一种表达: 定义特殊二元组\((x,z)\)。 1.\(x<z\)。 2.\(x\)与\(z\)要么都为奇数要么都为偶数。 (即\(x \ mod \ 2 = z \ mod \ 2\)) 3.\(c_x=c_z\) 4...
这道题在模拟界地位不亚于Luogu P4604 [WC2017]挑战在卡常界的地位了吧。 早上到机房开始写,中间因为有模拟赛一直到1点过才正式开始码。 一边膜拜CXR dalao一边写到3点左右,然后调啊调 最后发现杀死反猪抽的牌...
题外话:以Ingress为题材出的比赛好评,绿军好评 T1 考虑枚举第\(i\)个人作为左边必选的一个人,那左边剩余\(i-1\)个人,选法就是\(2^{i-1}\),也就是可以任意选或不选,右侧剩余\(n-i\)个人,选法就是\(\sum\li...
题目描述 小 F 是一个能鸽善鹉的同学,他经常把事情拖到最后一天才去做,导致他的某些日子总是非常匆忙。 比如,时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单: 看 iG 夺冠; 补月赛题的锅。 小 F ...
点分治好题 统计距离正常点分治统计即可,我们只需考虑何时达到最优 有两种情况: 第一:代价最大的询问两个端点在不同的两个子树中 因为这种情况下,无论根向那个子树移动都会等价地增加到达另一个端点的代价,...
P2375 动物园 题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学...
首先题意就是裸的最小割啦 然后考虑如何统计边数 这里有一个trick: 我们设定一个大于$m$的阈值,对于每条边的边权我们乘这个阈值+1后跑最小割,得到的答案除以阈值就是真正的最小割,取模阈值后就是最少割掉的边...
费用流好题 本题的建图很有意思 正常我们看到棋盘问题应该先对整个棋盘黑白染色构成一个二分图,然后再考虑建图的问题 但是本题题目中已经明确区分了不同的斜线,问题在于怎么保证一个"L"形 因此我们进一步分析:...
真·小清新... 其实本题正解是动态点分治,但是考虑到那个东西需要先大力推导一波再套上一个幻想乡战略游戏的搞法,所以还不如大力推导一波,然后无脑套上一个树剖+线段树写法... 首先我们考虑没有换根操作: 没有...
原题链接:樱花,还有你 $\scr{\color{DarkOrchid}{Solution}}$ Subtask1 这是一个送分的:总和都不到$n$,无论怎么收集,花瓣数肯定不到$n$,输出impossible 即可,$5$分。 因为此题要取模,可能最后答案...
超短代码 #include<iostream> #include<cstdio> using namespace std; long long b,p,k; long long Pow(long long n,long long m,long long k){//快速幂啊 if(m==1)return n%k; else {long long r=...
题目描述 输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。 输入输出格式 输入格式: 三个整数b,p,k. 输出格式: 输出“b^p mod k=s” s为运算结果 输入输出样例 输入样例#1: 2 10 9 输...
题目链接 题意 给定一个格点三角形,三个顶点分别为(0,0),(n,m),(p,0),求三角形内部的格点个数。 思路 皮克公式: \[S = \frac{i}{2}+b-1 \] \(S\)为三角形面积,\(i\)为三角形边界上的格点个数,\(b\)为三角形...
题目传送门 感想:相信自己的想法!继续挖掘! 读完题目后:看到的最大值最小?二分答案啊!再仔细一看:wi达到了1e9,二分可能费点劲。(其实真的是可以的)而且check函数貌似并没有什么行之有效的写法。继续往...
https://www.luogu.org/problemnew/show/P3611 二分答案+优先队列 二分O(logn) 判一次正确性O(nlogn) 总体O(nlognlogn) 为了让priority_queue变成小根堆,就把元素全部取相反数了。 #include<iostream> #in...
LINK:数字序列 这是一道论文题 我去看了一眼论文鸽的论文。 发现讲的还算能懂。可并堆的操作也讲的比较清晰。 对于这道题首先有一个小trick 我们给a数组全部减去其对应的下标这样我们求出来的b数组就可以不需要满...
[Luogu 2023] AHOI2009 维护序列 <题目链接> 恕我冒昧这和线段树模板二有个琴梨区别? #include <cstdio> int n,m; long long p; class SegmentTree { private: struct Node ...
[Luogu 1073] NOIP2009 最优贸易 <题目链接> 分层图,跑最长路。 真不是我恋旧,是我写的 Dijkstra 求不出正确的最长路,我才铤而走险写 SPFA 的… #include <algorithm> #include <cstdio> #i...