- 博客(20)
- 收藏
- 关注
RSS订阅原创 不相邻问题
文章目录链式不相邻问题：问题解析环形不相邻问题问题解析链式不相邻问题：问题有n个球排成一列，从中取出m个不相邻的球，问有多少种解法。解析这个问题有公式，我的推导如下：n个球取m个不相邻的球相当于将n-m个球分为m+1份，除了第一份和最后一份可以没有球，其他都要有一个球。先给中间m-1份每份一个球，问题变为：n-m-(m-1)个球放入m+1个盒子，盒子可以没有球。用插板法可以得出：a...
2019-12-08 18:11:34
1904
原创 [SDOI2010]猪国杀题解
文章目录题目链接：sol游戏结束、一些数组/变量每个猪的结构体：献殷勤、表敌意、跳忠、跳反伤害、死亡无懈可击主要操作完整代码AC代码观战模式题目链接：洛谷P2482loj2885bzoj1972推荐去loj看题，可以下数据因为特别容易出错。sol其实这题码量也没那大，格式化后我的代码只有141行，在loj目前最短。最好多些一些函数，给每个猪开一个结构体。游戏结束、一些数组/变量之...
2019-09-16 10:36:02
1209
原创 [SNOI2019]字符串题解
文章目录题目链接sol10%数据另20%数据另30%数据最后40%数据code:题目链接洛谷P5329sol题目意思很明确，但似乎不太好求。还是先看看部分分。10%数据Θ(n2logn)\Theta(n^2\log n)Θ(n2logn)，暴力，先得10分。另20%数据发现一件事，在比较sis_isi和sjs_jsj时，假设i<ji<ji<j...
2019-09-05 08:15:11
212
原创 [ZJOI2013]K大数查询 浅谈整体二分
文章目录题目大意sol暴力二分整体二分总结题目大意题面连接:bzoj3110洛谷P3332重新讲一下含糊不清的题意：有n个可重集合，有m个操作，操作分为两种：1 l r c 给第l到第r个可重集合都加入一个数c。2 l r c 询问第l到第r个可重集合第c大的数是多少。n≤5000,m≤5000,1≤l≤r≤nn\le 5000,m\le 5000,1\le l\le r\l...
2019-08-27 22:28:21
241
原创 2019暑假杭二day7测试总结
T1题目大意求∑i=1n∑j=1nμ(gcd(i,j))%998244253,n≤1010\sum_{i=1}^n\sum_{j=1}^n\mu(gcd(i,j))\%998244253,n\le 10^{10}∑i=1n∑j=1nμ(gcd(i,j))%998244253,n≤1010sol∑i=1n∑j=1nμ(gcd(i,j))=∑k=1n∑i=1n∑j=1nμ(k)[gcd(i...
2019-08-23 21:03:58
106
原创 2019暑假杭二day6测试总结
T1题目大意给你一颗 个点的边权均为1的树，找到一个点 ，使得距离点最远的点最近，输出距离点最远的点到点的距离。sol输出树的直径除2向上取整。证明略T2题目大意给你nnn根木棍和mmm次询问，第i根木棍长度为aia_iai，每次询问给你两个数l,rl,rl,r，你要在l,rl,rl,r区间内选出3根木棍组成一个三角形，使其周长最大。如果区间内没有三根木棍能组成一个三角形，输出-...
2019-08-23 21:03:50
108
原创 2019暑假杭二day5测试总结
T1题目大意吹雪养了一只猫，但是猫跑走了，于是她要把猫抓回来。众所周知，猫总是喜欢乱跑，而且总是会跑进奇怪的地方：这个奇怪的地方可以被抽象成一张n个点m条边的无向图，且边的长度都为1；吹雪站在1号点，而跑走的猫可能出现在标号为2…n的点中的任意一个。为了节省时间，吹雪一定要走两点间的最短路。不幸的是，有q个事件，每个事件中都有一条边会被破坏，这使得某些点不能通过原有的最短路走到。吹雪想...
2019-08-23 21:03:41
131
原创 2019暑假杭二day4测试总结
T1题目大意给定三个整数a,b,ca,b,ca,b,c，求有多少个多项式F(x)F(x)F(x)满足F(a)=b,F(b)=cF(a)=b,F(b)=cF(a)=b,F(b)=c，多项式的系数都为非负整数，如果有无穷多个，输出−1-1−1。sol考场上我只写出了dfs的暴力。其实多项式的每一项系数都小于等于b，先特判掉等于b的情况，然后就可以把c看成b进制数（特判b等于1），算出多项式的系...
2019-08-23 21:03:32
107
原创 2019暑假杭二day3测试总结
前言Day3居然考了三到线段树+离散化，是数据结构专场吗？我虽然都想出了正解，却还是犯了一些傻逼错误。T1题目大意在一条数轴上有nnn个点，第iii个点坐标为xixixi。有mmm个操作，每个操作都是下面两种之一：p,yp,yp,y表示将初始标号为ppp的点坐标改为yyy。l,rl,rl,r表示求出∑l<=xi<=xj<=l(xj−xi)\s...
2019-08-23 21:03:22
120
原创 2019暑假杭二day2测试总结
T1题目大意给出一个字符串SSS,求出一个子序列，使原序列的每个字符出现且仅出现一次，且子序列的字典序最小。solT1我得了90分，离奇WAWAWA了第一个点，正解比我的算法要简便地多，维护一个栈，对于每个字符，如果已经在栈内就直接跳过；否则，若栈顶字符比它大，且之后出现过，则弹出栈顶，以后在加进来（贪心），当不能弹时将当前字符加入栈内。最后，把栈从下往上输出即可。...
2019-08-23 21:03:13
117
原创 2019暑假杭二day1测试总结
2019年8月1日，进入杭二集训，目前集训模式是上午队测，下午讲评与订正，再加上李建老师讲课，晚上是自主学习。想把每天的测试作个记录。下面是day1的测试日志。T1T1我得了80分，第一档分直接用线筛筛每个数的最小质因子，就可以算出每个数的最大约数。第二档分可以预处理sqrt(r)内的所有质数，然后用它们去埃筛[l,r]内的每一个数，复杂度O(nloglng(n))O(nloglng(n))...
2019-08-23 21:02:54
129
原创 2019暑假杭二day8测试总结
2019暑假杭二day8测试总结T1题目大意solT1题目大意从前有一个国家，国力繁盛。然而众所周知，一旦一个国家强大了起来，那么这个国家一定会有许多奸臣想要上位。所以来进谏的人无论是谁，无论提出的是什么建议，都有可使国家走向灭亡。郭紫丽现在就身处这个国家之中，但是她不希望国家出现这种情况。所以她希望给国王出主意。然而旁边的大臣美国恶女同样也知道这个定律，所以她看到郭紫丽来进谏时，断定她...
2019-08-23 21:02:21
201
原创 [USACO11OPEN]玉米田迷宫Corn Maze题解
题目链接洛谷p1825bzoj3299以下描述针对于洛谷环境这一题本来是普通的bfs，但坑点却很多，其中有一个疑似数据问题。坑点1： 传送门可以多次走bfs不扩张重复点，这是它比dfs快的原因之一。但这一题传送门可以多次走，比如这个样例：5 5######.#.##A#A=#.#@######传送门是强制传送的，没有选择，所以需要两次经过传送门，传过去再传回来。解决...
2019-02-18 19:34:12
455
原创 [USACO07OCT]障碍路线Obstacle Course题解
题目链接：洛谷p1649bzoj1644发一个不一样的题解算法:标签是spfa或DP，有的人用spfa，有的人用bfs，有的人用dfs，可我用的居然是用双端队列优化的Dijkstra。思路：这一题可以看成一个最短路。对于某个点，它有四种状态，面对前、后、左、右，所以我们可以把一个点分成四个点。由于我们要求的不是最要需要多少步，而是最要需要拐多少弯，所以边权有两种，0(不拐弯)和1(...
2019-02-10 21:18:09
295
原创 [USACO14DEC] Cow Jog_Gold 牛慢跑(金)题解
题目链接洛谷P4873bzoj3826写在前面的话这一题的本质其实是求牛结束位置的最长不上升子序列，其他一些篇题解都说了，但没说为什么，我在这可以给出两种有证明的思路。思路1对于两头牛，A牛和B牛，如果A牛超过了B牛，则说明A牛初始位置<=B牛初始位置且A牛结束位置>=B牛结束位置。在这种情况下，它们需要两条跑道。同样的，如果有k头牛，第一头牛超过第二头牛，第二头牛超过第...
2019-02-06 21:35:45
182
原创 [USACO16DEC]Moocast(gold)奶牛广播-金 题解
题目链接洛谷P2847bzoj4744简化题面给你n个点，可以在任意两点间连边，代价为两点间的距离。在保证图联通的情况下，最小化最大边权。输出最小的最大边权的平方。思路有题解说可以用二分答案，可我不会怎么办？其实并不用二分答案，最小生成树就行，输出最小生成树的最大边权。证明（自己瞎写的，不一定完善 应该是一定不）首先，树保证了连通，对于任何一幅图，去掉一些边后变成树，它依然满足条...
2019-02-03 20:21:28
191
原创 [USACO17FEB]Why Did the Cow Cross the Road III S题解
题目链接洛谷P3663bzoj4997思路这道题要我们求遥远的牛，其实就是把道路当成障碍，去统计每个连通块有多少头牛，不在一个连通块的牛都是遥远的，可以用乘法直接计算。在找连通块时用bfs搜索，暴力统计连通块。存图时可以用三维数组存它能否走到相邻的格子，但我用的是二维数组进行二进制压缩，可以省空间，也好看一些。具体还有一些细节和优化，代码里有注释。code：#include<...
2019-02-01 21:28:43
172
原创 [USACO4.3]逢低吸纳Buy Low, Buy Lower题解
[USACO4.3]逢低吸纳Buy Low, Buy Lower题目链接洛谷P2687思路这一题第一问还简单，就是要我们求最长下降子序列。可以用n^2算法。第二问问本质不同的最长下降子序列的种数，先不考虑本质不同，可以设a[i]为第i天的股价，f[i]为以i结尾有多长，s[i]为有多少种序列，则s[i]等于长度为f[i]-1的序列种数之和。考虑到本质相同，其实就是重复的数字只算一次，如...
2019-01-31 21:16:32
470
原创 洛谷P5057 [CQOI2006]简单题题解
[CQOI2006]简单题洛谷P5057 [CQOI2006]简单题题目描述有一个 n 个元素的数组，每个元素初始均为 0。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1 变 0（操作 1），要么询问某个元素的值（操作 2）。 例如当 n = 20 时，10 条指令如下：输入输出格式输入格式：第一行包含两个整数 n, m，表示数组的长度和指令的条数； 以下 m 行...
2019-01-30 20:51:10
242
原创 [Usaco2006 Mar]Mooo 奶牛的歌声题解
**发表自己的一个代码试试** 先看题目[Usaco2006 Mar]Mooo 奶牛的歌声DescriptionFarmer John’s N (1 &lt;= N &lt;= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the...
2018-08-17 14:13:27
392
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人