3747: [POI2015]Kinoman Time Limit: 60 Sec  Memory Limit: 128 MBSubmit: 830  Solved: 338 Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部. 你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影.如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值

「ZJOI2017」树状数组(二维线段树) 吉老师的题目真是难想... 代码中求的是 \(\sum_{i=l-1}^{r-1}a_i\),而实际求的是 \(\sum_{i=l}^{r}a_i\),所以我们直接判断 \(a_{l-1}\) 和 \(a_r\) 是否相等就行了. 我们用二维线段树,一维存左端点 \(l\),一维存右端点 \(r\),里面存 \(a_l=a_r\) 的概率. 若 \(a\in [1,l-1],b\in [l,r]\),操作不在 \(b\),概率为 \(1-p\) 若 \

$ \color{#0066ff}{ 题目描述 }$ 「Hanabi, hanabi--」 一听说祭典上没有烟火,Karen 一脸沮丧. 「有的哦-- 虽然比不上大型烟花就是了.」 还好 Shinobu 早有准备,Alice.Ayaya.Karen.Shinobu.Yoko 五人又能继续愉快地玩耍啦! 「噢--!不是有放上天的烟花嘛!」Karen 兴奋地喊道. 「啊等等--」Yoko 惊呼.Karen 手持点燃引信的烟花,「嗯??」 Yoko 最希望见到的是排列优美的烟火,当然不会放过这个机会-

「ZJOI2017」树状数组 以下均基于模2意义下,默认\(n,m\)同阶. 熟悉树状数组的应该可以发现,这题其实是求\(l-1\)和\(r\)位置值相同的概率. 显然\(l=1\)的情况需要特盘. 大暴力 对于\(l=1\)的情况,可以发现一个操作不会产生影响当且仅当增加\(r\)的值,而其他情况会改变\(l-1\)或\(r\). 对于\(l!=1\)的情况: ​ 针对一次修改区间\([ql,qr]\). \([ql,qr]\)包含\(l-1,r\),那么有\(\displaystyle 2

学习了新姿势..(一直看不懂大爷的代码卡了好久T T 首先数字范围那么小可以考虑枚举众数来计算答案,设当前枚举到$x$,$s_i$为前$i$个数中$x$的出现次数,则满足$2*s_r-r > 2*s_l-l$的区间$[l+1,r]$其众数为$x$,这个显然可以用一个数据结构来维护. 直接扫一遍效率是$O($数字种类数$*nlogn)$的,无法承受,但是我们发现,对于每一段非$x$的数,$2*s_i-i$是公差为$-1$的等差数列,所以它们对答案的贡献实际上可以一次性计算.设$L$为一段非$x$数

1A,拿来练手的好题 用一个优先队列按煮熟时间从小到大排序,被煮熟了就弹出来. 用n个vector维护每种食物的煮熟时间,显然是有序的. 用树状数组维护每种煮熟食物的数量. 每次操作前把优先队列里煮熟时间<=当前时间的弹出,BIT上+1. 每次0操作把食物塞进优先队列和vector 每次1操作先看看树状数组里有没有数,没有输出angry,有的话在树状数组上二分找到最小的数. 每次2操作先看看树状数组里有没有这一种数,有的话输出并-1,没有的话看看vector有没有,有的话输出时间差,没有的话输出

题目描述 给你一个长度为 $n$ 的01串,$m$ 次询问,每次询问给出 $l$ .$r$ ,求从 $[l,r]$ 中选出两个不同的前缀的最长公共后缀长度的最大值. $n,m\le 10^5$ 题解 后缀自动机+STL-set+启发式合并+离线+扫描线+树状数组 两个前缀的最长公共后缀,在正串后缀自动机上体现为pre树上两点LCA的深度. 考虑统计pre树上一个点的贡献:对于两个前缀 $x$ .$y$ ,它能够影响的询问左端点小于等于 $x$ ,右端点大于等于 $y$ .因此影响最大化的前缀对就

题目描述 回忆树是一棵树,树边上有小写字母. 一次回忆是这样的:你想起过往,触及心底--唔,不对,我们要说题目. 这题中我们认为回忆是这样的:给定 \(2\) 个点 \(u,v\) (\(u\) 可能等于 \(v\))和一个非空字符串 \(s\) ,问从 \(u\) 到 \(v\) 的简单路径上的所有边按照到 \(u\) 的距离从小到大的顺序排列后,询问边上的字符依次拼接形成的字符串中给定的串 \(s\) 出现了多少次. 输入 第一行 \(2\) 个整数,依次为树中点的个数 \(n\) 和回忆的

题目描述 给定 \(n,k\) ,求有多少个三元组 \((a,b,c)\) 满足 \(1≤a≤b≤c≤n\)且\(a + b^2 ≡ c^3\ (mod\ k)\). 输入 多组数据,第一行数据组数\(T\). 每组数据两个整数,\(n\)和\(k\). 输出 \(T\)行,每行一个整数,表示满足条件的三元组的个数. 样例 样例输入 1 10 7 样例输出 27 //为什么老被和谐啊 数据范围 \(1≤n,k≤10^5\) \(T≤400\) 时间限制\(4s\) 题解 与其他学校互测,然后做题

网格图给予我的第一反应就是一个状态 f[i][j] 表示走到第 (i,j) 这个位置的最大价值. 由于只能往下或往右走转移就变得显然了: f[i][j]=max{f[i-1][j], f[i][j-1]}+a[i][j] 但是面对庞大的数据范围,再优秀的电脑也无法驾驭 百亿亿 的时间复杂度,与 百亿亿 的空间复杂度. 其实只要稍加思考我们就可以发现,枚举那些没有价值的 (x,y) 的坐标是多余的,所以我们只需要枚举有价值的点,在进行Dp转移就会起到加速. 因此新的状态即为:f[i] 表示到达第

\(\mathrm{Sleepy Cow Sorting}\) 问题描述 LG5200 题解 树状数组. 设\(c[i]\)代表\([1,i]\)中归位数. 显然最终的目的是将整个序列排序为一个上升序列,于是倒序枚举,先把最后有序的插入. 剩下来前面无序的就是要操作的,于是直接输出操作次数. 接下来方案很容易构造. \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; void read(int &x){ x=0;

链接:https://ac.nowcoder.com/acm/contest/984/D 来源:牛客网 饥饿的牛 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld 题目描述 Farmer John养了N(1 <= N <= 5,000)头奶牛,每头牛都有一个不超过32位二进制数的正整数编号.FJ希望奶牛们在进食前,能按编号从小到大的顺序排好队,但奶牛们从不听他的话.为了让奶牛们养成这个习惯,每次开饭时

A. 梦境 没啥可说的原题.... 贪心题的常见套路我们坐标以左端点为第一关键字,右端点为第二关键字 然后对于每个转折点,我们现在将梦境中左端点比他小的区间放进$multiset$里 然后找最近的右端点, 然后没了...... 思路总结: 1.贪心套路,坐标排序,最优性选择 2.再有原题一定要赶紧打 B. 玩具 大神题,我考场再也不敢肝期望了kukuku 定义三个数组 $dp_{i,j}$表示当前森林中有$i$个点,然后有$j$个点在第一棵子树的概率 $f_{i,j}$表示当前树有$i$个点,深

又死了......T1 Merchant 因为每个集合都可以写成一次函数的形式,所以假设是单调升的函数,那么随着t越大就越佳 而单调减的函数,随着t的增大结果越小,所以不是单调的??? 但是我们的单调只需凭借t时刻的sum值是否大于S即可 如果某个单减的集合符合情况,那么他在t==0时就符合情况 如果不符合,那么他就不会作出贡献 所以可以二分 T2 Equation 一开始以为是高斯消元??? 当然不是..... 把每个xi均用x1表示,那么我们发现,对于深度奇偶不同的点,他的表示方式是不同的,

T1 冒泡排序 题目描述 clj 想起当年自己刚学冒泡排序时的经历,不禁思绪万千 当年,clj 的冒泡排序(伪)代码是这样的: flag=false while (not flag): flag=true for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] flag=false 现在的 clj 想知道冒泡排序究竟有多慢,所以在(伪)代码的第三行下面加入了这么一句: printf("LJS NB\n"); 但是随着需要排序的

BZOJ_4378_[POI2015]Logistyka_树状数组 Description 维护一个长度为n的序列,一开始都是0,支持以下两种操作: 1.U k a 将序列中第k个数修改为a. 2.Z c s 在这个序列上,每次选出c个正数,并将它们都减去1,询问能否进行s次操作. 每次询问独立,即每次询问不会对序列进行修改. Input 第一行包含两个正整数n,m(1<=n,m<=1000000),分别表示序列长度和操作次数. 接下来m行为m个操作,其中1<=k,c<=n,0&l

今天考试考了这题,所以来贡献\([POI2015]LOG\)的第一篇题解.代码略丑,调了快三个小时才调出来\(AC\)代码. 对于这种小清新数据结构题,所以我觉得树状数组才是这道题的正确打开方式. 首先离散化,这样才不会爆内存.开两个树状数组,第一个树状数组记录离散化后\(1\)到\(i\)中数字出现的个数,第二个树状数组离散化前\(1\)到\(i\)数字出现值的和.把所有询问都读入进来,对于每次操作: 操作\(1\):单点修改,若之前的数是正数,第一个树状数组\(-1\),第二个树状数组\(-

[BZOJ4382][POI2015]Podział naszyjnika Description 长度为n的一串项链,每颗珠子是k种颜色之一. 第i颗与第i-1,i+1颗珠子相邻,第n颗与第1颗也相邻.切两刀,把项链断成两条链.要求每种颜色的珠子只能出现在其中一条链中.求方案数量(保证至少存在一种),以及切成的两段长度之差绝对值的最小值. Input 第一行n,k(2<=k<=n<=1000000).颜色从1到k标号.接下来n个数,按顺序表示每颗珠子的颜色.(保证k种颜色各出现至少一次

[BZOJ4384][POI2015]Trzy wieże Description 给定一个长度为n的仅包含'B'.'C'.'S'三种字符的字符串,请找到最长的一段连续子串,使得这一段要么只有一种字符,要么有多种字符,但是没有任意两种字符出现次数相同. Input 第一行包含一个正整数n(1<=n<=1000000),表示字符串的长度.第二行一个长度为n的字符串. Output 包含一行一个正整数,即最长的满足条件的子串的长度. Sample Input 9 CBBSSBCSC Sample

[BZOJ4378][POI2015]Logistyka Description 维护一个长度为n的序列,一开始都是0,支持以下两种操作:1.U k a 将序列中第k个数修改为a.2.Z c s 在这个序列上,每次选出c个正数,并将它们都减去1,询问能否进行s次操作.每次询问独立,即每次询问不会对序列进行修改. Input 第一行包含两个正整数n,m(1<=n,m<=1000000),分别表示序列长度和操作次数.接下来m行为m个操作,其中1<=k,c<=n,0<=a<=

P3586 [POI2015]LOG 维护一个长度为n的序列,一开始都是0,支持以下两种操作:1.U k a 将序列中第k个数修改为a.2.Z c s 在这个序列上,每次选出c个正数,并将它们都减去1,询问能否进行s次操作.每次询问独立,即每次询问不会对序列进行修改. 离散化按照权值建立树状数组. 那么对于大于s的值,可以直接减去s,这一部分的贡献为\(c*(query_{geshu}(tot)-query_{geshu}(s-1))\). 剩下的数,我们只知道他们小于s,但是不知道确切的值所以