BZOJ 3831
bzoj 4399: 魔法少女LJJ 题解
LinkBZOJ4399题意Description在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果；鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ
日期 2023-06-12 10:48:40bzoj 2006. [NOI2010]超级钢琴 题解
Description 题目链接 给定一个长度为 n 的序列，选出 k 个长度在 [L,R] 之间的子段（不可重复），求 k 个子段和的最大值。N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq NSolution由于 n 十分巨大，我们不可能把所有符合条件的子段都列举出来再比较她们的大小，由于 k 比较小，
日期 2023-06-12 10:48:40![【BZOJ 1266】 [AHOI2006]上学路线route](/scriptcss/images/64.png)
【BZOJ 1266】 [AHOI2006]上学路线route
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 第一问是个最短路。 第二问。 利用第一问floyd算出来的任意两点之间的最短路。 那么枚举每一条边(x,y) 如果w[1][x]+cost[x][y]+w[y][n]==w[1][n] 那么就说明(x->y)这条边是某条最短路上的必经边。 则我们在一张新的网络中加入(x,y,pi)这条边。 然后我们求这个网
日期 2023-06-12 10:48:40【BZOJ 1221】 [HNOI2001] 软件开发
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 ```cpp /* 设一个超级源点S和超级汇点T S和2*i-1各连一条容量为ni的边。 花费为0 表示每天都会产生ni条要洗的毛巾 S和2*i各连一条容量为INF的边 花费为f 表示新买毛巾用 2*i-1和2*(i+a)连容量为INF的边
日期 2023-06-12 10:48:40![【BZOJ 1208】[HNOI2004]宠物收养所](/scriptcss/images/61.png)
【BZOJ 1208】[HNOI2004]宠物收养所
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 用set搞。 (因为规定了不会有相同特点值的东西。 所以可以不用multiset. 那么每次用lower_bound找离它最近的配对就好了 【代码】 #include <bits/stdc++.h> #define ll long long using namespace std; const l
日期 2023-06-12 10:48:40![【BZOJ 1452】 [JSOI2009]Count](/scriptcss/images/62.png)
【BZOJ 1452】 [JSOI2009]Count
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 维护一百个二维树状数组。 二维区间求和。 【代码】 #include <bits/stdc++.h> #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (in
日期 2023-06-12 10:48:40![【BZOJ 1053】[HAOI2007]反素数ant](/scriptcss/images/63.png)
【BZOJ 1053】[HAOI2007]反素数ant
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 用小的质数去凑那个数字。 显然比用大质数去凑划算。 因为 对于$x = p1^{q1}*p2^{q2}*...*pn^{qn}$ x的因子个数等于(q1+1）*(q2+1)....*(qn+1); 显然 你用的质数越小。 这个指数就能更大一点。 (表示相同的数字的情况下。至少不会更差。 根据这个。 又有235..
日期 2023-06-12 10:48:40![【BZOJ 1207】[HNOI2004]打鼹鼠](/scriptcss/images/66.png)
【BZOJ 1207】[HNOI2004]打鼹鼠
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 时间是按顺序的。 所以就有单调性啦。 写个DP就好。 设f[i]表示打第i只鼹鼠,最多能打几只鼹鼠。 则如果i和j的距离不超过它们的时间差,那么就可以从j转移到i 即f[i] = max(f[i],f[j]+1) 注意不要写成f[i] = max(f[i],f[j]+ok(i,j)); 因为j无法转移到i.那么就
日期 2023-06-12 10:48:40【BZOJ 1191】[HNOI2006]超级英雄Hero
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 二分图的最大匹配。 因为要答下一题，这一题必须先答完。 所以如果某道题没有匹配了。 那么就直接break掉。 【代码】 #include <bits/stdc++.h> #define LL long long #define rep1(i,a,b) for (int i = a;i <=
日期 2023-06-12 10:48:40【BZOJ 1597】 [Usaco2008 Mar]土地购买
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 把这n个土地按照x为第一关键字、y为第二关键字。都升序排。 然后考虑一个土地xi,yi 若有一个土地的x<=xi且y<=yi,则那个土地(x,y)就直接删掉就好了。 因为你总可以和(xi,yi)一起买。 ->这个去掉土地的过程可以用单调队列实现。 这样。我们会发现剩下的土地按照从1开始的顺序。
日期 2023-06-12 10:48:40【34.14%】【BZOJ 3110】 [Zjoi2013]K大数查询
Time Limit: 20 Sec Memory Limit: 512 MB Submit: 5375 Solved: 1835 [Submit][Status][Discuss] Description 有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第
日期 2023-06-12 10:48:40【58.75%】【BZOJ 1087】[SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 3040 Solved: 1786 [Submit][Status][Discuss] Description 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及
日期 2023-06-12 10:48:40【41.34%】【BZOJ 1003】[ZJOI2006]物流运输
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 6420 Solved: 2654 [Submit][Status][Discuss] Description 物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般
日期 2023-06-12 10:48:40【BZOJ 1041】[HAOI2008]圆上的整点
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1041 【题意】 【题解】 由圆的方程可得 X^2+Y^2=R^2 X^2=R^2-Y^2 X^2=(R+Y)(R-Y) 这里令 D = gcd(R+Y,R-Y); 则 gcd((R+Y)/D,(R-Y)/D)==1 那么 令R+Y
日期 2023-06-12 10:48:40【BZOJ 1040】[ZJOI2008]骑士
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1040 【题意】 【题解】 题目相当于给你了若干个环(基本环->简单环); 然后每个环里面选一些点;相邻的点不能同时选; 先考虑只有一个环的情况 这样, 我们可以任意删掉一条边,它的两个端点为u和v； 它就变成一条链了; 然后因为一
日期 2023-06-12 10:48:40【BZOJ 1031】[JSOI2007]字符加密Cipher(后缀数组模板)
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1031 【题意】 【题解】 后缀数组模板题; 把整个字符串扩大一倍. 即长度乘2 然后搞出后缀数组; 然后顺序枚举i; 对于sa[i]< n的输出对应的s[sa[i]+n-1]就好了 后缀的含义是把后缀按照字典序从小到大排一下.
日期 2023-06-12 10:48:40【BZOJ 1028】[JSOI2007]麻将
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1028 【题意】 【题解】 /* 枚举新加入的一张牌是哪一张牌; 然后尝试把它加进去; 再枚举1..n里面是哪一张牌组成了对子; 然后再看看剩余的牌能不能按照要求 分成3*m组
日期 2023-06-12 10:48:40【BZOJ 1024】 [SCOI2009]生日快乐
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1024 【题意】 【题解】 要求恰好分成n个部分;每个部分的面积都一样; 则dfs的时候三个域分别表示矩形的长宽以及要被切成的份数; 每次切一刀下去的时候肯定是按照比例分配的; 比如要这一刀切下去(假设竖着切)之后左边还要切x刀,右边切y刀
日期 2023-06-12 10:48:40【BZOJ 1023】[SHOI2008]cactus仙人掌图
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1023 【题意】 【题解】 如果不考虑有环的情况; 那么有一个经典的求树的直径的方法; 首先; 树的直径的两端的端点必然都在树的叶子上(或在根节点,考虑一条链的情况); 则 设f[i][0]表示离i这个点最远的叶子节点的距离 f[i][1
日期 2023-06-12 10:48:40【BZOJ 1020】 [SHOI2008]安全的航线flight
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1020 【题意】 【题解】 二分+判断点是否在多边形区域内+计算点到直线的最短距离 对于每条线段,假设这条线段为(x,y)首先将线段的两段尝试更新距离陆地距离最近的距离中最远的距离ans,并求出其在陆地上对应的点u和v;(如果x和y都在陆地上那么u
日期 2023-06-12 10:48:40【BZOJ 1017】 [JSOI2008]魔兽地图DotR
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1017 【题意】 【题解】 设f[i][j][k] 表示第i个节点以下的总花费为j, 然后i物品有k个用来给上一层的人合成东西用了的最大力量值. 转移方式看代码吧。 代码加了lots of “注释” (数据有一组里面没有高级物品,这个时候就
日期 2023-06-12 10:48:40【BZOJ 1016】 [JSOI2008]最小生成树计数(matrix-tree定理做法)
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1016 【题意】 【题解】 /* 接上一篇文章; 这里用matrix-tree定理搞最小生成树个数; 对于每一种相同边权的边; 当做一个阶段; 这个阶段,我们需要看看这个边权的边能连接哪些联通块;
日期 2023-06-12 10:48:40【BZOJ 1016】[JSOI2008]最小生成树计数(搜索+克鲁斯卡尔)
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1016 【题意】 【题解】 /* 两个最小生成树T和T'; 它们各个边权的边的数目肯定是一样的; 且相同边权的边; 那些边所形成的联通性是一样的; 可以考虑T和T'的形成; 比如说一开始
日期 2023-06-12 10:48:40【BZOJ 1011】[HNOI2008]遥远的行星
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1011 【题意】 【题解】 这里的答案误差不超过5%是突破点; 如果是直接暴力写; 复杂度是O（N*a*N) 对于第j个行星; ans[j]+=∑m[i]*m[j]/(j-i)这里的i∈[1..j*a]; 这里如果j比较大的话,j*a也不会
日期 2023-06-12 10:48:40【BZOJ 1005】[HNOI2008]明明的烦恼(化简的另一种方法)
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1005 【题意】 【题解】 题目和题解在上一篇; 这里 对 【(m^(n-2-tot))* (n-2)!】/【(n-2-tot)!* (d[1]-1)!*(d[2]-1)!……(d[n]-1)!】; 这个式子的化简再说一个方法; 对于n!
日期 2023-06-12 10:48:40【BZOJ 1004】 [HNOI2008]Cards
【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1004 【题意】 给你sr+sb+sg张牌,(令n=sr+sb+sg),让你把这n张牌染成3种颜色(红蓝绿),且红色sr张,蓝色sb张,绿色sg张; 同时再给你m个变化关系change[i],这里从左往右数第change[i]张牌可以移动到第i个位置; m
日期 2023-06-12 10:48:40【b704 && BZOJ 1999】树网的核
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=b704 &&http://www.lydsy.com/JudgeOnline/problem.php?id=1999 【题意】 给你一棵树; 让你找出所有的直径; 并在这些直径上面选取连续的一段; 使得它的偏心距最小; 【题解】 这题有个思维量比较大
日期 2023-06-12 10:48:40【BZOJ 3172】单词
【链接】h在这里写链接 【题意】 给你n个单词; 这n个单词组成了一篇文章; 问你每个单词在这篇文章中出现了多少次. 其中每个单词之间用一个逗号隔开->组成一篇文章。 (单词的总长度不会超过
日期 2023-06-12 10:48:40【AHOI2013】【BZOJ3238】差异
Description Input 一行，一个字符串S Output 一行。一个整数。表示所求值 Sample Input cacao Sample Output 54 HINT 2<=N<=500000,S由小写英文字母组成 后缀自己主动机的性质: 5.两个串的最长公共后缀,位于这两个串相应状态在Parent树上的近期公共祖先状态
日期 2023-06-12 10:48:40BZOJ 1901 Dynamic Rankings 树董事长
标题效果：间隔可以改变k少 我的两个天树牌主席。。。隔断Count On A Tree 之后我一直认为，随着树的主席的变化是分域林木覆盖率可持久段树。。。事实上，我是误导。。。 尼可持久化线段树毛关系都木有啊！！！ 那就是动态的权值线段树啊啊啊啊啊啊啊！！！ 好吧这里给不明确主席树的孩纸一些简单介绍： 1.外层树状数组 2.里层线段树 3.线段树动态开节点。仅此而已。和可持久化全然没关系
日期 2023-06-12 10:48:40BZOJ 1015 JSOI2008 星球大战 starwar 并检查集合
标题效果：给定一个无向图。联通谋求块的数目，以及k一个点的破坏后每次；联通，块的数目 侧面和摧毁的地步全记录，我们可以做相反的。 需要注意的是该点不能算作破坏联通块 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 400400
日期 2023-06-12 10:48:40