总目录 在线测评地址(ybt) 在线测评地址(LOJ) 在线测评地址(LUOGU)
总目录 在线测评地址(ybt) 在线测评地址(LOJ) 在线测评地址(LUOGU)
LOJ6436 神仙的游戏 题意 题解 Code: LOJ6436 神仙的游戏 题目传送门 题意 小 \(D\) 和小 \(H\) 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏，比如 “口算一个 4 位数是不是完全平方数” 。 今天...
Given a set of n DNA samples, where each sample is a string containing characters from {A, C, G, T}, we are trying to find a subset of samples in the set, where the length of the longest common prefix...
题目：https://loj.ac/problem/2977 想到斯坦纳树。但以为只能做 “包含一些点” 而不是 “包含一些颜色” 。而且不太会处理中位数。 其实 “包含一些颜色” 用斯坦纳树做也和普通的一模一样……只是赋初值的时候...
#6277. 数列分块入门 1内存限制：256 MiB时间限制：100 ms标准输入输出题目类型：传统评测方式：文本比较题目描述给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。输入格式第一行输入一个数字n。...
imi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N....
Given a dice with n sides, you have to find the expected number of times you have to throw that dice to see all its faces at least once. Assume that the dice is fair, that means when you throw th...
ou are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a door is equal for all doors. If you choose the ith door, it can ei...
https://loj.ac/problem/6279 题意 给出一个长为 nnn的数列，以及nnn个操作，操作涉及区间加法，询问区间内小于某个值xxx的前驱（比其小的最大元素）。 思路 分块区间修改板题。 分块的时候，就对每一个块进行排序，...
LOJ10041 LOJ关于内存计算真有毒，大概用到元素才计入内存吧。。 然后就变成SB题了，连map都不用。。 #include<bits/stdc++.h> #define LL long long using namespace std; const int maxt=(1e9)+5...
这题我是维护一个操作树，然后在操作树上进行可持久化操作，用倍增每次寻找答案，时间复杂度$O(TlogT)$。 加上读入优化，轻松卡过，最快可以做到$O(T)$，%%% 1 #include<bits/stdc++.h>...
根据分块的思想，对于不整块的我们直接暴力统计，但是对于整块的，我们可以对每一块进行一个排序，利用二分查找找出最小的大于 c*c 的位置，然后减去即可 //#pragma GCC optimize(2) //#include <...
LOJ10072 这题，N这么小，可以想到O(N3)O(N3)O(N^3)枚举三个点i,j,ki,j,ki,j,k 此时贪心想法，构成的环最小为w[i][k]+w[k][j]+min_w[i][j]（最短路）w[i][k]+w[k][j]+min_w[i][j]（最短路）w[i][k]+w[k][j]+min\_w...
LOJ10046 这题有点像反的LOJ10045，只不过这次要尽量长 KMP是找最近的，因此我们再开一个lst[]lst[]lst[]，从左往右扫，更新lst为最远的相同子串 （PS：由于要统计长度，iii要1~N枚举） #include&lt;bits/...
1.LOJ 507 接竹竿 link dp[i]表示前i个的最大分数，所以dp[i]=max(dp[i-1],dp[j-1]+sum[i]-sum[j-1]) （color i ==color j&&i>j）选与不选的两种决策 但是这样跑为O(N^2)，需要优化，发现dp[j-1]-sum...
LOJ3095 一开始还以为是什么SAM的高级题 其实就是个模拟 如果删去位置i和位置j，那他们前后都是一样的，就只用比较中间部分的大小 所以处理出f[i]表示一个点往后最多多少位是一样的 判断i和j的大小关系的时候就...
可以参见EIEIEI的博客 传送门 首先有一个exp\expexp的O(nlogn)O(nlogn)O(nlogn)做法 这里 考虑Ferrers图Ferrers图Ferrers图 从左上角向右下截一个最大的正方形 设正方形边长为hhh 那么剩下两部分就都是≤h\le h≤...
题目链接:https://loj.ac/p/6247 题目大意 给出n,kn,kn,k求 ∑0≤i≤n,i∣k(ni)\sum_{0\leq i\leq n,i|k}\binom{n}{i}0≤i≤n,i∣k∑(in) 对998244353998244353998244353取模 1≤n≤1015,1≤k≤220,k=2p(p∈N)1...
LOJ传送门 解析： 我们改变一下修改和回答方式。 令每个修改操作的被执行概率是12\frac{1}{2}21，然后我们直接询问这棵线段树中被染黑的点数的期望，乘上2t2^t2t就行了，ttt是修改操作的次数。 设fu,0f_{u,0}fu,0...
题目链接:https://loj.ac/p/6053 题目大意 定义一个积性函数f(pc)=p xor cf(p^c)=p\ xor\ cf(pc)=p xor c，求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1nf(i) 解题思路 异或这个东西不太好搞，要考虑...
题目链接：https://loj.ac/problem/2055二分答案之后变为01序列，每次排序直接将区间赋值为1或者0即可，用线段树维护即可。代码：#include&lt;bits/stdc++.h&gt; using namespace std; const int MAXN=1e5+5...
题目链接:https://loj.ac/problem/2035 题目大意 nnn个数字分成mmm段，要求方差最小。 解题思路 首先方差的公式∑i=1n(xi−∣x∣)2\sum_{i=1}^n(x_i-|x|)^2i=1∑n(xi−∣x∣)2 其中∣x∣|x|∣x∣是不变的，...
【题目】 原题地址 有nnn个人，每个敌人分别有mim_imi的生命值，接下来释放QQQ个技能。 指定一个敌人ididid，有ppp的概率使得这个敌人的生命−1-1−1 指定kkk个敌人，等概率的从这kkk个人中选取一个活着的人封印...
LOJ10047 这题是对KMP性质的深度挖掘啊。。 已知fail指针指向的是字符串中既是前缀，又是后缀的最长串 则假如fail是father，就得到了所谓的“fail树” 我们对于一段长度为R的字符串，显然就是要找到R一直到根的...
题面在这里 题意： 给一棵树，三种操作： 1.add(x,d)，给x到根路径上的点的ki += d 2.mul(x,d)，给x到根路径上的点的ti += ki*d 3.询问一个点的ti值 ...树链剖分以后就变成一道线段树好题了qaq ...
传送门 题解： 直接跑最短路，然后考虑翻转每一条边之后怎么快速算代价。 显然如果这条边不在 1−n1-n1−n 或者 n−1n-1n−1 的最短路上，直接考虑强行走过这条边的最短路就行了，可以通过记录最短路和次短路（要求...
标签： oi
题面 Solution 枚举中间点jjj，题目即求是否存在mmm使a[j]−ma[j]-ma[j]−m与a[j]+ma[j]+ma[j]+m分别在jjj两侧。 对于jjj左侧任意一个点iii，都将t[a[i]]t[a[i]]t[a[i]]赋值为1，那么若以jjj为中心的lenlenlen最大...
题目链接：洛谷 P5290 / LOJ #3052 题意 给定一棵有根树，节点有权值 MiM_iMi，将节点分为多个集合（记为 SiS_iSi），最小化 ∑imaxj∈siMj\sum\limits_{i}\max\limits_{j\in s_i}M_ji∑j∈simaxMj，...
题目链接 看到题面里的maxai>=ax,i<xi\max_{a_i>=a_x,i<x} imaxai>=ax,i<xi和minai>ax,i>xi\min_{a_i>...xi,大概能想到笛卡尔树上的dpdpdp问题了。方便起见我们假设已经建立...
LOJ10067 构造完全图 给你一棵树T，找出T能扩展出的边权和最小的完全图G。 第一行N表示树T的点数； 保证输入数据构成一棵树。 输出仅一个数，表示最小的完全图G的边权和。 4 1 2 1 1 3 1 1 4 2 12...